가장 가까운 유클리드 거리를위한 효율적인 데이터 구조

Question

질문은 다음 UVA 문제에 의해 영감을 얻었습니다. https : //onlinejudge.org/index.php? option= onlinejudge & itemID= 99999999 & Category= 18 & page= show_problem & problem= 1628 .

Amazon 지역의 기후를 모니터하기 위해 자율, 배터리 전원 공급 장치 획득 스테이션 네트워크가 설치되었습니다. 주문 디스패치 스테이션은 제어 스테이션에 대한 명령어의 전송을 시작하여 현재 파라미터를 변경할 수 있습니다. 배터리를 오버로드하지 않으려면 각 스테이션 (Order-Dispatch Station 포함)은 두 개의 다른 방송국 만 전송할 수 있습니다. 역의 목적지는 가장 가까운 곳입니다. 그릴의 경우 첫 번째 기준은 서쪽 (지도의 가장 왼쪽)을 선택하는 것입니다. 두 번째 기준은 최남단 (지도에서 가장 낮은)을 선택하는 것입니다. 아마존 주 정부가 각 방송국의 현지화를 감안할 때 메시지가 모든 방송국에 도달 할 수있는 메시지를 결정하는 프로그램을 작성하는 프로그램을 작성합니다.

물론 순진 알고리즘은 정점으로서의 스테이션을 가진 그래프를 구축하고 가장 가까운 두 개의 꼭지점을 검색하여 주어진 정점에서 가장자리를 계산합니다. 그런 다음 우리는 단순히 DFS / BFS를 실행할 수 있습니다. 물론 이것은 $ o (v ^ 2) $ 시간을 눌러 그래프 (테스트 케이스를 통과하는)를 구성합니다. 그러나 나의 질문은 적절한 데이터 구조로 더 빠른 그래프를 빌드 할 수있는 경우입니다. 특히 임의의 쿼리 지점 $ P $ 및 주어진 점 $ S $ , 우리는 $ S $ 에서 $ s $ $ P $ ( $ \ log v $ 시간?).

Answer 1

이 문제를 올바르게 이해하면 대부분의 공간 인덱스를 사용할 수 있습니다.

공간 인덱스는 일반적으로 $ o (log {v}) $ 삽입 시간 및 가장 가까운 이웃에 대한 유사한 룩업 시간을 갖습니다. 물론 Voronoi 다이어그램을 만들 수는 있지만 인덱스를 직접 사용하여 필요할 때마다 가장 가까운 이웃을 찾을 수도 있습니다.

낮은 차원 (2D, 3D)의 공간 인덱스의 공통 가정은 KD-trees입니다 (꽤 간단하고 일반적으로 좋지만 포인트의 밀도가있는 클러스터에 문제가있는 경향이 있음), 쿼드 트리 (수치 정밀도가 까다로울 수 있기 때문에 자신을 구현하기가 더 어렵습니다) 및 트리 (구현하는 가장 어려운, 그러나 최상의 보장 성능, 특히 R * 트리 (R-Star-tree)).

C ++을 사용하는 경우 libspatialindex 또는 r-tree 부스트 . Java를 사용하는 경우 My Tinspin 라이브러리를 살펴보십시오.

이 기술 용어는 " $ k $ 가장 가까운 이웃 쿼리"또는 " $ k $ -nn 쿼리 쿼리 ", $ k $ 을 찾으려는 가장 가까운 이웃의 수를 참조하십시오.

Answer 2

관련 데이터 구조가 동적 인 voronoi 다이어그램 . voronoi 다이어그램은 평면의 점 집합이 관련 될 때 종종 응답입니다.

이 경우 포인트 세트가 진화하기 때문에 동적 버전을 원합니다.