11
포츈의 방법을 사용하여 2 차원에서 보로 노이 다이어그램을 생성하는 방법을 성공적으로 구현했습니다. 하지만 지금은 포인트 (다이어그램을 생성하는 데 사용되는 원래 포인트 중 하나가 아닌)에 대한 가장 가까운 이웃 쿼리에 사용하려고합니다. 나는 사람들이 O (lg n) 시간 (그리고 나는 그것들을 믿을 수있는) 시간에 끝날 수 있다고 말하고있다. 그러나 나는 그것이 실제로 어떻게 행해졌는지에 대한 설명을 찾을 수 없다.보로 노이 다이어그램을 사용한 가장 가까운 이웃 검색
저는 바이너리 검색에 익숙하지만, 그 상한을 보장하는 좋은 기준을 이해할 수 없습니다. 또한 다이어그램에 포인트를 삽입하고 주변 셀을 업데이트하는 것과 관련이있을 수 있지만이를 수행하는 좋은 방법을 생각하거나 찾을 수는 없다고 생각했습니다.
누구나 나를 단서에 몰아 넣거나 더 자세한 설명이있는 곳을 가리킬 수 있습니까?
그건 의미가 있습니다. 나는 그 방법에 익숙하다고 생각한다. 나는 너를 상상하지만, 나는 아직 할 수 없다. –
@Chad : 귀하의 질문 때문에 검색 할 때까지 커크 패 트릭 구조에 익숙하지 않았습니다. :-) 나는 보로 노이 다이어그램을 사용 했었지만 이전에는 포인트 위치로 사용한 적이 없었습니다. 이 방법은 상당히 멋지게 보입니다. – Ante