Delaunay 三角剖分

形式陈述 ​

设 $S$ 是有限平面点集，且不全共线。Delaunay 三角剖分是 $S$ 的直线平面三角剖分，覆盖其凸包公理库凸包Convex hull包含给定点集的最小凸集，是凸几何中的基本包络对象，并可进一步研究其算法构造。，并满足每个三角形的开外接圆不含 $S$ 中其他点。空圆性质直接定义 Delaunay；凸包只界定最外层覆盖区域，抬升到高一维凸包则是等价构造而非定义前置。等价地，两站点 $p,q$ 之间存在 Delaunay 边，当且仅当它们的闭Voronoi cell公理库Voronoi 图Voronoi diagram · Voronoi tessellation按到有限站点集中的最近距离把度量空间划分为闭合单元及其公共边界。 共享一条一维边；一般位置下，每个 Voronoi vertex 对偶于一个 Delaunay 三角形。

若没有四点共圆，Delaunay 三角剖分唯一。对凸四边形的一条内部对角线，局部 Delaunay 条件是对边顶点不落在相邻三角形的开外接圆内；非法对角线可通过 edge flip 换成另一条。增量算法插入点后找到受其影响、外接圆包含该点的三角形 cavity，删除后把 cavity 边界与新点连接。配合点定位可达 $O(n\log n)$ 期望或最坏构造界，具体取决于算法。

直觉 ​

空圆条件偏好避免极瘦三角形：若某点落入邻接三角形外接圆，翻转公共边会改善局部最小角。Voronoi 图按最近站点分区，Delaunay 则连接会在某处并列最近的站点，把距离区域的对偶关系变成三角网。

定义是全局空圆性质，edge flip 是维持它的局部操作；两者通过四点共圆判定连接。方向测试公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。和 in-circle 谓词的符号约定必须一致。

例子与边界 ​

三个不共线点只有一个三角形，其开外接圆内没有其他站点，因此三角剖分自动是 Delaunay。四个构成非共圆凸四边形的点有两种对角线；恰有一条满足局部空圆条件，翻转非法边得到唯一 Delaunay 结果。

正方形四点共圆时，两条对角线都满足“开圆内无其他点”，所以 Delaunay 三角剖分不唯一；对应 Voronoi 图中心有四个 cell 相交。算法若要求唯一输出，需要固定 symbolic perturbation 或 tie-break，而不能宣称几何条件已经选定一条。

全体点共线时不存在覆盖二维凸包的三角形，应返回退化的一维结构或拒绝输入。浮点 in-circle 行列式接近零时容易翻转符号，可能产生交叉边或非终止翻转；鲁棒谓词是正确性要求，不只是数值优化。

推论与应用 ​

Delaunay 三角剖分用于网格生成、地形建模、插值和最近邻结构。平面最近点对必为某条 Delaunay 边，因此构造后只需检查线性条边，但若唯一目的只是最近点对，直接分治通常更简单。

最大化最小角的性质是在所有同点集三角剖分间的字典序角度性质，不表示每个三角形都接近等边，也不自动满足有限元对边长和区域约束的全部要求。

参考资料

• Boris Delaunay, “Sur la sphère vide,” Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles, 1934, pp. 793–800.
• Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, Ch. 9.