교차하지 않는 타원에 대한 이웃의 가장 가까운 트리오

Question

임의로 배치 된 타원 타원 집합에 대해 가장 가까운 이웃 트리오를 찾는 문제에 대해 작업하고 있습니다. 새로운 사용자로서 저는 이미지 태그를 포함 할 수 없지만 시각 보조 도구로 자신을 더 잘 설명 할 수 있다고 생각하기 때문에 페이지 하단에 URL을 포함 시켰습니다. 그림은 3 개의 가장 가까운 타원을 서로 연결하는 Apollonius 원으로 의미하는 바를 보여줍니다.

지금까지 필자는 타원 사이의 최소 거리를 사용하고 증분 및 스위프 라인 방법을 통해 Delaunay 삼각 측량을 수정하고 3 개의 타원 구성 사이에 형성된 삼각형 원에 관련된 다양한 기술을 사용하고 이웃을 추정하려고 시도했습니다. 바운딩 박스를 사용하고 실제로이 작업을 효율적으로 수행하는 방법에 대한 아이디어가 완전히 없어졌습니다.

나는 타원의 모든 트리오를 모든 다른 타원과 철저히 검색하고 비교하며 시간 복잡도가 n(n-1)(n-2)/3! 인 솔루션을 만들었지 만 . 게다가 각 계산은 대수적으로 반복되는 것이 아니라 반복적으로 수행됩니다.

아무에게도 대수적으로 행해질 수있는이 방법에 대한 아이디어가 있습니까? n^2 시간 복잡성이 있습니까?

기술에 대한 제안조차도 나에게 어울리는 시험이라 할지라도, 지금은 거의 3 주 동안 작업 해 왔으며 정말 괜찮은 대답에 더 가깝기 때문에. 당신이 당신의 타원의 보로 노이 다이어그램을 계산하면

Image http://img859.imageshack.us/img859/727/nearesttrio.png

Answer 1

, 다음 서클 센터 포인트 다이어그램의 교차점에 배치된다.

http://ima.umn.edu/nuggets/voronoi.html

Answer 2

당신은 경계 상자를 기반으로 R-tree으로 타원을 포장 할 수있다. R- 트리는 공간 객체에 대한 2 진 트리와 같은 데이터 구조이며 탐색을 통해 효율적인 가장 가까운 이웃 및 가장 가까운 근사 이웃 질의를 지원합니다.

많은 타원이있는 큰 데이터 세트의 경우 R 트리를 사용하면 거리 테스트 수가 크게 줄어들어 쿼리 근처의 트리 서브 세트 만 스캔해야합니다.

희망이 도움이됩니다.