没有 Delaunay 的 Voronoi 应用？
Applications of Voronoi without Delaunay?
所以如果这是真的：
The question "Which site does a given point belong to?" is just another way of stating the nearest neighbor search problem: the relevant Voronoi polygon is the one associated with the nearest point in the set generating the Voronoi diagram. Unfortunately,
- there isn't any constant time algorithm for solving this problem, and
- the Voronoi diagram doesn't provide any solving the problem faster than an O(N) search.
我们如何实际使用它们？
我的意思是，我知道我可以为其构建基于 Delaunay 的搜索树，但我现在不需要 Voronoi 图来构建 Delaunay 三角剖分，我呢？
那么 Voronoi 有什么实际用途 - 除了，比如说，将其打印在地图上以便于人类消化 - Voronoi 有什么用？
什么问题可以仅使用不带对偶的 Voronoi 图来解决（当然，比没有它更有效）？
这取决于访问模式。由于这两个图是对偶的，因此都包含基本相同的信息。然而，根据实际经验，计算 Voronoi 顶点需要根据具体情况进行昂贵的多精度算法，因为存在退化设置并且因为存在无限和几乎无限的 Voronoi 单元。因此，根据访问模式，计算一次 Voronoi 图 而不是使用 Delaunay 三角剖分并一遍又一遍地计算其对偶元素通常会更有效。
另一方面，Delaunay 三角剖分中的最近邻搜索要简单得多，因此我为 Voronoi diagram 选择了混合数据表示。它使用 Delaunay 三角剖分 和 在其之上的 Voronoi 表示，因此可以在 O(log(n)) 时间内定位点。性能表明这是一种很好的方法：对于具有 n=1000 个站点的 Voronoi 图中的一百万个查询，仅需要 0.3 秒。
编辑：对于最近邻查询，您不需要 Voronoi 单元。但是对于对边界或 Voronoi 单元区域感兴趣的算法。举几个例子：Centroidal Voronoi Tesselation, Natural Neighbor Interpolation, Medial Axis
所以如果这是真的：
The question "Which site does a given point belong to?" is just another way of stating the nearest neighbor search problem: the relevant Voronoi polygon is the one associated with the nearest point in the set generating the Voronoi diagram. Unfortunately,
- there isn't any constant time algorithm for solving this problem, and
- the Voronoi diagram doesn't provide any solving the problem faster than an O(N) search.
我们如何实际使用它们？
我的意思是，我知道我可以为其构建基于 Delaunay 的搜索树，但我现在不需要 Voronoi 图来构建 Delaunay 三角剖分，我呢？
那么 Voronoi 有什么实际用途 - 除了，比如说，将其打印在地图上以便于人类消化 - Voronoi 有什么用？
什么问题可以仅使用不带对偶的 Voronoi 图来解决（当然，比没有它更有效）？
这取决于访问模式。由于这两个图是对偶的，因此都包含基本相同的信息。然而，根据实际经验，计算 Voronoi 顶点需要根据具体情况进行昂贵的多精度算法，因为存在退化设置并且因为存在无限和几乎无限的 Voronoi 单元。因此，根据访问模式，计算一次 Voronoi 图 而不是使用 Delaunay 三角剖分并一遍又一遍地计算其对偶元素通常会更有效。
另一方面，Delaunay 三角剖分中的最近邻搜索要简单得多，因此我为 Voronoi diagram 选择了混合数据表示。它使用 Delaunay 三角剖分 和 在其之上的 Voronoi 表示，因此可以在 O(log(n)) 时间内定位点。性能表明这是一种很好的方法：对于具有 n=1000 个站点的 Voronoi 图中的一百万个查询，仅需要 0.3 秒。
编辑：对于最近邻查询，您不需要 Voronoi 单元。但是对于对边界或 Voronoi 单元区域感兴趣的算法。举几个例子：Centroidal Voronoi Tesselation, Natural Neighbor Interpolation, Medial Axis