使用Voronoi图进行最近邻居搜索 [英] Nearest Neighbor Searching using Voronoi Diagrams

问题描述

我已经成功实现了一种使用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?

推荐答案

我认为必须通过平面细分(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.

这篇关于使用Voronoi图进行最近邻居搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！