B. Delaunay Triangulation
数学大学
B. Delaunay Triangulatio
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
B. Delaunay Triangulatio
计算几何 · 05. Delaunay Triangulation
Dual Graph
对偶图：Voronoi 图与 Delaunay 三角剖分互为对偶——胞腔对顶点、边对边。
对应
相邻胞腔的站点之间连 Delaunay 边
方向
知道其一即可线性时间构造另一
Triangulation
Delaunay 三角剖分：连接相邻站点得到的三角形网，无点落在空圆内。
空圆性质
每个三角形的外接圆内部不含其他点
唯一性
一般位置下 Delaunay 剖分唯一
Hardness
构造 Delaunay 的复杂度下界：排序可归约到它，Ω(n log n) 不可逾越。
下界
与凸包相同的排序归约论证
最优算法
分治、随机增量都达到 O(n log n)
History
历史脉络：Delaunay 1934 年定义，Bowyer-Watson 增量算法广泛使用。
里程碑
Delaunay(1934)、Lawson(1977)、Bowyer-Watson(1981)
演进
从理论到工程，网格生成是主要推动力
本节要点
- ✓Voronoi 与 Delaunay 互为对偶
- ✓空圆性质定义 Delaunay
- ✓构造下界 Ω(n log n)
延伸主题：由 Voronoi 图提取 Delaunay验证空圆性质
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么 Delaunay 三角剖分在网格生成中占统治地位？
参考答案空圆性质使三角形尽量饱满（最大化最小角），避免细长病态单元；数值计算（有限元）在均匀网格上误差小、收敛好。质量与理论保证兼得，工程价值自然突出。
2对偶关系在工程上如何使用？
参考答案需要「最近站点」类查询用 Voronoi 图；需要「邻接三角网」做插值或网格用 Delaunay。两者 O(n) 互转，按查询类型选主结构、另一作为辅助即可。
3退化情形（四点共圆）下 Delaunay 还唯一吗？
参考答案不唯一：四点共圆时两种对角线选择都满足空圆性质，Delaunay 不唯一。但都合法——任意一种都保持空圆性质，实际中可任选或加扰动统一。