Delaunay 三角剖分
点集的三角剖分,使每个三角形的外接圆内部不含其它点;二维有 O(n) 条边,是 EMST 的母图,并与 Voronoi 图对偶。标签 计算几何 / Delaunay / 三角剖分 / Voronoi
定义
给定平面点集 。 的三角剖分是把 的凸包划分成以 中点为顶点的三角形,且任意两个三角形只在公共边或公共顶点相交。
若每个三角形的外接圆内部都不含 中的其它点,则称这个三角剖分为 Delaunay 三角剖分。
一般位置下(没有四点共圆),Delaunay 三角剖分唯一。存在共圆点时,满足空圆性质的三角剖分可能不唯一;通常用符号扰动或一致的平局规则处理。
高维把三角形换成单形,把外接圆换成外接球:每个单形的外接球内部不含点。
基本性质
二维 Delaunay 三角剖分是平面图。若点集有 个点、 个凸包顶点,则边数至多 ;一般位置下三角形数为 。
在所有三角剖分中,二维 Delaunay 三角剖分最大化最小角;一般位置下,它还按角度向量字典序最大。
Delaunay 三角剖分与 Voronoi 图对偶:
- Delaunay 的顶点对应 Voronoi 区域;
- Delaunay 的边对应 Voronoi 边;
- Delaunay 的三角形对应 Voronoi 顶点。
与 EMST 的关系
Delaunay 边集包含欧氏最小生成树的边;一般位置下,Delaunay 三角剖分本身包含 EMST。设 是 EMST 的一条边,删去它后树分成 两部分。若存在点 同时满足
则 在 或 中;无论在哪一侧,都会有一条更短的边横跨这个割,矛盾。因此以 为直径的圆内没有其它点, 是 Delaunay 边。
所以二维 EMST 可以先构造 Delaunay 三角剖分,再在它的 条边上跑 Kruskal。具体题目见 Euclidean MST。
反过来不成立:Delaunay 边不一定是 EMST 边。
构造
二维 Delaunay 可以在 时间构造,输出只有 条边;分治构造的细节见 Delaunay 三角剖分构造。
三维 Delaunay 的最坏规模是 个四面体,因此三维及更高维不能沿用“Delaunay 只有线性条边”的结论。高维构造是输出敏感的,输出规模本身就可能接近平方。
常见误解
- 认为 Delaunay 三角剖分总是唯一:只有一般位置下才唯一;共圆点会产生多种合法剖分。
- 认为外接圆边界上也不能有点:空圆性质只限制圆的内部,边界上可以有共圆点。
- 认为三维 Delaunay 也有 条边:三维最坏有 个四面体。
- 认为 Delaunay 三角剖分就是 EMST:EMST 是它的子图,Delaunay 还包含大量不属于 EMST 的边。