使用 Voronoi 图进行最近邻搜索
我已经成功实现了一种使用 Fortune 方法生成二维 Voronoi 图的方法。但现在我尝试将它用于点的最近邻查询（这不是用于生成图表的原始点之一）。我一直看到人们说它可以在 O(lg n) 时间内完成（我相信他们），但我找不到它实际上是如何完成的描述。
我熟悉二分搜索，但我无法找出一个好的标准来保证上限。我还认为这可能与将点插入图表并更新周围的单元格有关，但无法想到（或找到）一个好的方法来做到这一点。
谁能告诉我，或者指出一个有更全面描述的地方？
I've successfully implemented a way to generate Voronoi diagrams in 2 dimensions using Fortune's method. But now I'm trying to use it for nearest neighbor queries for a point (which is not one of the original points used to generate the diagram). I keep seeing people saying that it can be done in O(lg n) time (and I believe them), but I can't find a description of how it's actually done.
I'm familiar with binary searches, but I can't figure out a good criteria to guarantee that upper bound. I also figured maybe it could have to do with inserting the point into the diagram and updating surrounding cells, but can't think (or find) of a good way to do that.
Can anyone clue me in, or point to a place with a more thorough description?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为某种搜索结构必须由平面细分（Voronoi 图）组成，例如 柯克帕特里克点位置数据结构。
I think that some kind of search structure has to be made from plane subdivision (Voronoi diagram), like Kirkpatrick's point location data structure.