如何基于预计算全量点集高效生成子集的Voronoi图？

可以利用预计算的全局Delaunay三角剖分来高效生成子集的Voronoi图，无需每次从头构建，具体分析如下：

核心原理：Delaunay与Voronoi的对偶性 #

Voronoi图和Delaunay三角剖分是严格对偶的结构——Voronoi图的顶点对应Delaunay三角形的外接圆圆心，Voronoi边对应Delaunay边的垂直平分线。因此，只要能快速得到子集的Delaunay剖分，就能直接生成对应的Voronoi图。

利用全局Delaunay加速子集剖分的步骤 #

1. 预计算全局Delaunay剖分
   对10000个固定点构建Delaunay三角剖分，存储每个点的全局邻接列表（即该点在全局剖分中相连的所有点）。这一步只需执行一次。

2. 提取子集的初始边集合
   当处理100个点的子集时，从全局邻接列表中筛选出所有子集内部点之间的相邻边，得到初始的候选边集合。

3. 验证并修剪得到子集Delaunay剖分
   对每条候选边，验证Delaunay核心条件：该边的外接圆内是否包含子集里的其他点。由于子集仅100个点，验证成本极低。修剪掉不满足条件的边后，就得到了子集的Delaunay三角剖分。

4. 生成子集Voronoi图
   通过对偶转换生成Voronoi图：

   • 每个Delaunay三角形的外接圆圆心作为Voronoi顶点
   • 相邻Delaunay三角形的圆心连线作为Voronoi边
   • 每个子集点的Voronoi胞元由围绕它的所有Voronoi边围成

对比从头构建的优势 #

从头构建100个点的Voronoi图本身复杂度是O(k log k)（k=100），单次计算速度也不慢，但如果需要反复执行成千上万次，利用预计算的全局Delaunay能大幅降低每次的计算开销：

• 避免了从头构建剖分的排序、增量插入等核心步骤
• 初始边集合直接从全局剖分提取，无需重新计算所有可能的点对关系

为什么不用全局Voronoi图直接处理？ #

全局Voronoi图的胞元是针对全部10000个点的，子集的Voronoi胞元需要合并大量不在子集内的点的胞元区域，这个合并过程的复杂度和从头构建几乎相当，反而不如基于Delaunay的方法高效。

内容的提问来源于stack exchange，提问作者testman8