使用Voronoi圖進行最近鄰搜索

Question

我已經成功實現了一種使用Fortune的方法在兩維中生成Voronoi圖的方法。但是現在我試圖將它用於點的最近鄰查詢（這不是用於生成圖的原始點）。我一直在看人們說它可以在O（lg n）時間完成（我相信它們），但我無法找到它是如何實際完成的描述。

我熟悉二進制搜索，但我找不到一個很好的標準來保證上限。我還認爲，也許它可能與將圖表插入圖表和更新周圍單元格有關，但不能認爲（或找到）這樣做的好方法。

任何人都可以給我提供線索，或者指出一個更詳盡的描述嗎？

Answer 1

我認爲某種搜索結構必須由平面細分（Voronoi圖）製成，如Kirkpatrick's point location data structure。