计算几何中的平面点集Voronoi图与Delaunay三角剖分的对偶性 我们已学过Delaunay三角剖分，现在深入探讨其核心关联——Voronoi图，以及两者之间深刻而优美的 对偶性 。这个对偶关系是计算几何的基石之一。 第一步：从点集划分到Voronoi图 设想平面上有一组离散的点，称为 站点 。一个很自然的问题是：平面上的任意一个位置，离哪个站点最近？由此可将平面划分成多个区域。 定义 ：给定点集 \( P = \{p_ 1, p_ 2, ..., p_ n\} \)，站点 \( p_ i \) 对应的 Voronoi单元 定义为： \( V(p_ i) = \{ x \in \mathbb{R}^2 \mid \text{dist}(x, p_ i) \leq \text{dist}(x, p_ j), \forall j \neq i \} \)。 即，所有到 \( p_ i \) 距离不大于到其他任何站点距离的点的集合。 几何构造 ：Voronoi单元的边界是两点连线的 垂直平分线 的一部分。整个平面被所有Voronoi单元划分，这个划分称为点集 \( P \) 的 Voronoi图 。单元边界称为 Voronoi边 ，边界交点称为 Voronoi顶点 。 第二步：理解Voronoi图的性质 单元形状 ：每个Voronoi单元是一个凸多边形（可能是无界的）。 局部性 ：两个站点的Voronoi单元共享一条边，当且仅当存在一个圆经过这两点，且圆内不含其他任何站点（这是理解对偶性的关键）。 顶点特征 ：一个Voronoi顶点是三条或更多Voronoi边的交点，它到至少三个站点的距离相等，并且以它为圆心的 空圆 （圆内无其他站点）经过这些站点。 第三步：引入已学概念——Delaunay三角剖分 回顾已知知识：点集 \( P \) 的 Delaunay三角剖分 是一种最大化最小角特性的三角网格，其核心性质是 空圆性质 ：任意一个三角形的外接圆内部不包含 \( P \) 中的其他任何点。 第四步：揭示对偶性——核心桥梁 Voronoi图与Delaunay三角剖分是 对偶图 。这种对偶性提供了一种在两个结构间精确转换的几何规则： 点与面 ：Voronoi图中的每个 站点 (对应一个Voronoi单元) 对偶于Delaunay三角剖分中的一个 三角形 。更准确地说，在标准对偶定义中，Voronoi图的每个 单元 对偶于Delaunay图（三角剖分的对偶图）中的一个 顶点 （即原站点）。而更直观的构造对偶是： 边与边 ：在Voronoi图中连接两个站点的 线段是Delaunay边 ， 当且仅当 这两个站点的Voronoi单元共享一条边。也就是说，每一条Delaunay边，都垂直于一条Voronoi边，且通常穿过它。 顶点与面 ：Voronoi图中的一个 顶点 （到三个等距站点的点）对偶于Delaunay三角剖分中的一个 三角形 。这个Voronoi顶点正好是那个Delaunay三角形外接圆的圆心。 第五步：形式化对偶构造算法 给定点集 \( P \)： 从Voronoi图得到Delaunay三角剖分 ：对每一个Voronoi顶点（圆心），连接其对应的三个等距站点，形成一个Delaunay三角形。遍历所有顶点即可得到整个三角剖分。 从Delaunay三角剖分得到Voronoi图 ：计算每个Delaunay三角形的外接圆圆心，这些圆心就是Voronoi顶点。然后，对于每条Delaunay边，连接其相邻两个三角形（即共享此边的两个三角形）的外心，这条连线就是该边对应的Voronoi边。 第六步：深入理解对偶性的价值与意义 计算等价 ：在一般位置假设下（无四点共圆），两者包含的拓扑（组合）信息是等价的。知道其中一个，可以用 \( O(n) \) 时间得到另一个。 算法应用 ：许多算法利用这种对偶性来高效构造其中之一。例如，可以先计算Delaunay三角剖分（有分治、增量等多种成熟算法），再通过对偶变换得到Voronoi图，这通常比直接计算Voronoi图更简单。 自然解释 ：Voronoi图表示“最近区域”，是解决邻近性问题的自然模型（如最近邻查询、设施选址）。Delaunay三角剖分表示“最优连接性”，是解决网格生成、表面重建等问题的自然模型。对偶性揭示了这两种不同视角的本质联系。 总结 ：平面点集的Voronoi图和Delaunay三角剖分通过 空圆性质 紧密相连，形成了精确的几何对偶。理解这种对偶性，意味着你掌握了从“区域划分”视角到“点连接”视角的自由转换，这是计算几何中连接不同核心概念与算法的关键桥梁。