我已经成功实现了一种使用Fortune方法生成二维Voronoi图的方法。但是现在我正尝试将其用于某个点的最近邻居查询(这不是用于生成该图的原始点之一)。我一直看到人们说它可以在O(lg n)时间内完成(我相信他们)，但是我找不到关于它是如何实际完成的描述。
我熟悉二进制搜索，但是我想不出一个很好的标准来保证这个上限。我还认为，可能与将点插入到图中并更新周围的单元格有关，但无法想到(或找到)实现此目的的好方法。
有人可以帮我找寻线索，或指向一个描述得更详尽的地方吗？
最佳答案
我认为必须通过平面分割(Voronoi图)来构建某种搜索结构，例如Kirkpatrick's point location data structure。