12

我已经成功实现了一种使用 Fortune 方法生成二维 Voronoi 图的方法。但现在我试图将它用于最近邻查询一个点（这不是用于生成图表的原始点之一）。我一直看到人们说它可以在 O(lg n) 时间内完成（我相信他们），但我找不到关于它实际上是如何完成的描述。

我对二分搜索很熟悉，但我想不出一个好的标准来保证这个上限。我还想也许它可能与将点插入图表和更新周围的单元格有关，但想不出（或找到）一个好的方法来做到这一点。

任何人都可以提示我，或者指出一个描述更全面的地方吗？

4

1 回答 1

11

我认为必须从平面细分（Voronoi 图）中制作某种搜索结构，例如Kirkpatrick 的点位置数据结构。

于 2011-08-18T21:48:14.463 回答