Delaunay 三角剖分

点集的三角剖分,使每个三角形的外接圆内部不含其它点;二维有 O(n) 条边,是 EMST 的母图,并与 Voronoi 图对偶。

标签 计算几何 / Delaunay / 三角剖分 / Voronoi

定义

给定平面点集 𝑃。𝑃 的三角剖分是把 𝑃 的凸包划分成以 𝑃 中点为顶点的三角形,且任意两个三角形只在公共边或公共顶点相交。

若每个三角形的外接圆内部都不含 𝑃 中的其它点,则称这个三角剖分为 Delaunay 三角剖分。

一般位置下(没有四点共圆),Delaunay 三角剖分唯一。存在共圆点时,满足空圆性质的三角剖分可能不唯一;通常用符号扰动或一致的平局规则处理。

高维把三角形换成单形,把外接圆换成外接球:每个单形的外接球内部不含点。

基本性质

二维 Delaunay 三角剖分是平面图。若点集有 𝑛 个点、ℎ 个凸包顶点,则边数至多 3𝑛−6;一般位置下三角形数为 2𝑛−2−ℎ。

在所有三角剖分中,二维 Delaunay 三角剖分最大化最小角;一般位置下,它还按角度向量字典序最大。

Delaunay 三角剖分与 Voronoi 图对偶:

  • Delaunay 的顶点对应 Voronoi 区域;
  • Delaunay 的边对应 Voronoi 边;
  • Delaunay 的三角形对应 Voronoi 顶点。

与 EMST 的关系

Delaunay 边集包含欧氏最小生成树的边;一般位置下,Delaunay 三角剖分本身包含 EMST。设 𝑝𝑞 是 EMST 的一条边,删去它后树分成 𝐴,𝐵 两部分。若存在点 𝑟 同时满足

𝑑(𝑝,𝑟)<𝑑(𝑝,𝑞),𝑑(𝑟,𝑞)<𝑑(𝑝,𝑞)

则 𝑟 在 𝐴 或 𝐵 中;无论在哪一侧,都会有一条更短的边横跨这个割,矛盾。因此以 𝑝𝑞 为直径的圆内没有其它点,𝑝𝑞 是 Delaunay 边。

所以二维 EMST 可以先构造 Delaunay 三角剖分,再在它的 𝑂(𝑛) 条边上跑 Kruskal。具体题目见 Euclidean MST。

反过来不成立:Delaunay 边不一定是 EMST 边。

构造

二维 Delaunay 可以在 𝑂(𝑛log𝑛) 时间构造,输出只有 𝑂(𝑛) 条边;分治构造的细节见 Delaunay 三角剖分构造。

三维 Delaunay 的最坏规模是 Θ(𝑛2) 个四面体,因此三维及更高维不能沿用“Delaunay 只有线性条边”的结论。高维构造是输出敏感的,输出规模本身就可能接近平方。

常见误解

  • 认为 Delaunay 三角剖分总是唯一:只有一般位置下才唯一;共圆点会产生多种合法剖分。
  • 认为外接圆边界上也不能有点:空圆性质只限制圆的内部,边界上可以有共圆点。
  • 认为三维 Delaunay 也有 𝑂(𝑛) 条边:三维最坏有 Θ(𝑛2) 个四面体。
  • 认为 Delaunay 三角剖分就是 EMST:EMST 是它的子图,Delaunay 还包含大量不属于 EMST 的边。
源码位置