没有Delaunay的Voronoi的应用？

Question

所以如果这是真的：如何查询Voronoi图？

“给定的点属于哪个站点？”表示最近邻搜索问题的另一种方法:相关的Voronoi多边形是与生成Voronoi图的最近点相关联的多边形。不幸的是，

• 没有任何固定时间算法来解决这个问题，而且
• Voronoi图没有比O(N)搜索更快地解决问题。

我们怎么才能真正使用它们？

我的意思是，我知道基于Delaunay的搜索树，我可以构造它，但是我现在不需要Voronoi图来构造Delaunay三角剖分，对吗？

那么，除了在地图上打印它以便于人类消化之外，沃罗内还有什么实际用途呢？

没有对偶的Voronoi图(当然比没有它更有效)有什么问题可以解决？

Answer 1

这取决于访问模式。因为这两个图是对偶的，所以都包含了基本相同的信息。然而，从实际经验来看，计算Voronoi顶点需要昂贵的逐个案例的多精度算法，因为存在退化设置，而且有无限个和近无限个Voronoi单元。因此，根据访问模式的不同，一次计算Voronoi图往往比使用Delaunay三角剖分和一次又一次计算其对偶元素更有效。

另一方面，在Delaunay三角剖分中，最近邻搜索要简单得多，因此我为我的Voronoi图选择了一种混合数据表示。它使用Delaunay三角剖分和Voronoi表示，这样就可以在O(log(n))时间内找到点。性能表明，这是一种很好的方法:对于使用n=1000站点的Voronoi图中的100万个查询，只需要0.3秒。

编辑:对于最近的邻居查询，您不需要Voronoi单元。但对于对边界或Voronoi单元区域感兴趣的算法。举几个例子：中心线Voronoi分选，自然邻域插值，中轴