빈 원 쿼리 알고리즘

Question

다음 작업을 수행 할 것입니다 알고리즘을 마련하기 위해 노력하고있어 : 질의 지점으로 함께 (가장 큰 원을, 점의 집합이 주어지면

를 질의 지점을 찾을 수 그것의 센터) 집합에서 포인트를 포함하지 않습니다.

지금까지 보로 노이 다이어그램을 사용하여 집합의 사이트 지점에 가장 가까운 점을 포함하는 영역 (셀)을 찾은 다음 보로 노이의 가장자리 목록을 사용하여 사다리꼴 분해를 구성하는 방법을 생각했습니다. 분해에서 쿼리 포인트가 놓이는 셀을 찾은 다음 원의 반지름이 쿼리 포인트에서 해당 셀의 지점 (사이트)까지의 거리가됩니다. Voronoi는 O (n) 저장 장치가 필요하고 Voronoi에서 사다리꼴 분해를 생성하는 것은 O (n) 저장 장치로 수행 될 수 있기 때문에 이와 같은 것을 생성하는 데 필요한 저장소는 선형이라고 생각합니다.

* 편집 : 검색어 시간은 O (logn) 여야합니다. 즉, 한 번에 한 집합의 모든 점을 반복 할 수 없습니다.

소리가 맞지 않습니까? 아니면 여기에 뭔가 빠졌습니까?

또한이 알고리즘과 관련된 일부 참조 사항이 있으면 알려 주시기 바랍니다. 감사합니다 :)

Answer 1

이 질문은 쿼리 포인트에서 세트의 가장 가까운 지점까지의 거리를 묻는 것 같습니다. 따라서 가장 가까운 지점을 찾는 것이 하나의 방법 일 것입니다. 이 작업을 수행하는 합리적 표준 방법은 http://en.wikipedia.org/wiki/K-d_tree이고이 질문은 일반적으로 http://en.wikipedia.org/wiki/Nearest_neighbour_search

Answer 2

그것은 지나치게 복잡한 소리. Voroni 다이어그램이 무엇인지는 모르겠지만, 여러분의 포인트가 모두 2D 평면에 있다고 가정하면 (이것은 구체가 아닌 원을 언급 한 이후로 생각됩니다) 이것은 매우 사소한 것입니다 :

전체 반복 포인트를 찾아서 쿼리 포인트에 가장 가까운 포인트를 찾습니다. 이 거리는 피타고라스의 정리 인 sqrt((point_x - query_x)^2 + (point_y - query_y)^2)입니다. 가장 작은 거리는 원의 반경입니다.