기존 지점과의 최대 거리가있는 유한 2D 영역에 지점을 삽입하십시오.

Question

유한 2D 공간 영역 안에 2D 포인트 세트가 있습니다 (현재로서는 일을 단순하게 유지하기 위해 세계적으로 정렬 된 사각형이라고 가정 해 봅시다). 새로운 포인트를 새로운 가장 가까운 이웃과 비교적 멀리 떨어진 세트에 새로운 포인트를 삽입하는 매우 효율적인 방법은 무엇입니까?

나는 천천히 Delaunay 삼각 측량을 만들고 가장 큰 삼각형으로의 검색을 제한 할 수 있었지만 누군가가 다른 (더 나은) 아이디어를 갖기를 바라고있었습니다.

영업권, 데이비드

---

편집하다:

이전 지점을 고려할 때마다 수천 번해야한다는 것을 잊어 버렸습니다. 나는 포인트 세트가 커짐에 따라 크롤링 속도가 느려지지 않는 알고리즘을 찾고 있습니다.

Answer 1

Bowyer-Watson 또는 기타 증분 알고리즘을 사용하여 Voronoi 다이어그램을 유지하십시오. Voronoi 다이어그램의 정점은 후보 포인트이며, 모든 후보 포인트를 소스 포인트와의 거리에 따라 주문한 우선 순위 대기열에 유지합니다. 그것은 매우 빠르고 최적이어야합니다 (적어도 각 단계에서 최적).

더 빠르고 덜 최적의 것을 찾고 있었습니까?