모든 선분의 지정된 거리 내의 모든 점 확인

Question

점 P와 세그먼트 S의 세트가 주어지면 어떤 세그먼트의 지정된 거리 d 내의 모든 점을 효율적으로 찾을 수 있습니까? 무차별 적으로 명령을 비교하지 않고 O(|P||S|)?

선분 집합 사이의 모든 교차점에 대한 Bentley-Ottman 검색은 O(n log n)으로 실행되며이 문제는 비슷한 맛이 있으므로 유사한 성능이 가능한지 궁금합니다.

C++의 오픈 소스 구현을위한 보너스 포인트.

Answer 1

포인트에 Voronoi diagram 네트워크를 구축하십시오. 각 셀에 모든 이웃에 대한 포인터를 보관하십시오. 무엇보다 가능합니다.

1. 는 점, 그것은에있는 세포 찾을 주어진. 간단하여 셀을 찾는 점을 지점으로 네트워크의 왼쪽 아래 모서리에서 선을 그어야하고, 그 코너의 세포에서 시작하여 접근 에있다.

2. 줄을 감안할 때, 그것이 교차하는 모든 셀을 찾는다. 하찮은.

3. 줄과 거리를 지정하면 복도 안의 모든 셀을 찾습니다. 보로 노이 네트워크 탐색 및 공간 질의하는지지 구조체로서 기능 2.

4. 등

을 따른다. 모든 작업은 로컬이므로 선형 복잡성이 있습니다. 이후 다이어그램이 작성됩니다. :)