数学大学
C. Properties
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
C. Properties
计算几何 · 05. Delaunay Triangulation
Empty Circumcircle
空外接圆：Delaunay 三角形的判定标准——外接圆内无任何其他点。
判定
三角形外接圆内不含输入点集的任何点
等价
所有边都属于某空圆三角形 ⇔ Delaunay
Empty Circle
空圆概念更广：Delaunay 边也存在过其两端的某个空圆。
边的空圆
边 ab 为 Delaunay 边 ⇔ 存在过 a、b 的空圆
层级
三角形空圆蕴含其三条边各自有空圆
Nearest Neighbor
最近邻必连：每个点的最近邻一定与它有 Delaunay 边。
结论
最近邻边是 Delaunay 边的子集
应用
由 Delaunay 图 O(n) 找出全部最近邻
Complexity
Delaunay 图的规模：边数至多 3n−6，整体线性复杂度。
边数
平面图性质限定边数 ≤ 3n−6
存储
线性空间即可存全部 Delaunay 边
本节要点
- ✓空外接圆是 Delaunay 的判定标准
- ✓最近邻边必是 Delaunay 边
- ✓Delaunay 图规模线性于点数
延伸主题：验证一个三角形的空圆性用 Delaunay 图找最近邻
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1「最近邻必是 Delaunay 邻居」为什么成立？
参考答案若 b 是 a 的最近邻，则以 ab 为直径的圆内部不含任何点（更近的点会 contradict 最近性）；这个圆是空圆，故 ab 满足 Delaunay 边的空圆判据。
2空圆性质与「最大最小角」的等价性说明什么？
参考答案局部空圆（每边通过检验）与全局最大最小角同时成立——局部优化条件蕴含全局最优结构。这种「局部判据 ⇒ 全局最优」的组合在计算几何中极为珍贵。
3Delaunay 图的线性边数上界如何得出？
参考答案Delaunay 图是平面图（边不交叉），欧拉公式限定平面图边数 ≤ 3n−6。这个上界决定了 Delaunay 的存储与遍历成本都是线性的。