해시 맵을 사용하여 포인트가 속한 영역을 찾는 방법은 무엇입니까?

Question

우리가 클러스터로 나누어 2 차원 공간 Voronoi Tessellation를 통해 말을 말해봐 :

우리는 클러스터가 설명 중간 지점이있다. 그러한 공간에서 포인트 (x, y 좌표)가 주어지면 해쉬를 어떻게 가져 와서 어느 클러스터에 속하는지 결정할 수있게됩니까?

우리는 레이어를 추가하고 트리 검색을 사용하여 포인트가 속한 위치를 그림으로써 클러스터를 이진 트리로 만들 수 있음을 알고 있습니다. 또한 우리는 클러스터에 각 공간 점 (descum)을 맵핑하고 O (1) 데이터로드를 얻을 수 있다는 것을 알고 있습니다. 그러나 나는 주어진 점으로부터 클러스터를 얻기 위해 정렬되지 않은 해시 맵 스타일을 사용하는 방법을 찾고있다. 그런 일을하는 법 (알고리즘 적으로)?

Answer 1

빌드 kd-tree 보로 노이 사이트 (셀 "센터")에 빌드하면 O (NlogN) 시간에 가장 가까운 사이트를 검색하게됩니다. 세포 (아마도 더 복잡한 방법) 각 보로 노이 테셀레이션에서

Answer 2

의 trapezoid decomposition를 구축 "- 지점과 가장 가까운 사이트가 모두 인해 보로 노이 다이어그램 속성

또 다른 옵션으로 동일한 셀에 속하는

주 클러스터 "는 가장 가까운 이웃으로 대응하는 중간 점을 갖는 점들의 궤적이다.

따라서 관심있는 것은 사실 새로운 지점의 가장 가까운 이웃 (모든 중간 지점 중에서)을 찾는 것입니다.

이 목적으로 해싱을 사용하려는 경우 지역별 해싱을 읽어야합니다.