使用Voronoi图的最近邻

Question

我有一个关于Voronoi图结构的问题。为什么Voronoi图对于最近邻搜索是有效的？它是如何工作的？我知道这种结构将空间划分为多个单元，但我仍然不明白在执行搜索查询时它是如何工作的。

Answer 1

您需要一个像层次集群或空间索引这样的数据结构。kirkpatrick算法看起来非常接近，但您可以尝试度量树和voronoi图的组合：http://www.cc.gatech.edu/~夹竹桃/voronoi/。voronoi图也有利于寻路：http://www.cs.columbia.edu/~pblaer/projects/path_planner/，因为它是delaunay三角剖分和最小生成树的对偶。当然，你可以检查每个单元格，但这很琐碎，对读者来说是一个很好的练习。