Cha*_*ing 12 voronoi nearest-neighbor computational-geometry
我已成功实现了一种使用Fortune方法生成2维维度Voronoi图的方法.但是现在我正在尝试将它用于一个点的最近邻查询(这不是用于生成图的原始点之一).我一直看到人们说它可以在O(lg n)时间内完成(我相信它们),但我找不到它是如何实际完成的描述.
我熟悉二进制搜索,但我无法找出保证上限的良好标准.我也想过可能它可能与将点插入图表并更新周围的单元格有关,但不能思考(或找到)这样做的好方法.
任何人都可以提醒我,或指向一个描述更全面的地方？
Ant*_*nte 11
我认为某种搜索结构必须通过平面细分(Voronoi图)来制作,就像Kirkpatrick的点位数据结构一样.