J. Randomized Incremental Construction
数学大学
J. Randomized Incrementa
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
J. Randomized Incrementa
计算几何 · 05. Delaunay Triangulation
Recursive Implementation
RIC 的递归实现：插入第 i 点 = 先递归插入前 i−1 点，再修复外接圆含新点的三角形。
结构
递归展开随机序的插入历史
定位
利用上层结构快速定位新点位置
Iterative Implementation
迭代实现：逐点插入并用历史 DAG 定位，与递归版本等价但更省栈。
历史 DAG
被销毁的三角形作为中间节点记入 DAG
定位下降
从根沿包含新点的子节点下降到叶
In-Circle Test
内圆测试驱动修复：外接圆含新点的三角形全部失效、需要重连。
判别式
四点行列式符号判定新点是否在外接圆内
级联
翻边后相邻边继续检验，直至全部合法
Point Location
DAG 定位是新点的入口：期望 O(log n) 找到所落的当前三角形。
期望复杂度
随机序下 DAG 深度期望 O(log n)
结构
每个节点记录其分裂出的子节点指针
本节要点
- ✓递归与迭代等价，迭代省栈
- ✓历史 DAG 支持 O(log n) 定位
- ✓内圆测试驱动局部修复
延伸主题：实现历史 DAG 定位统计内圆测试次数
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1历史 DAG 与「重新扫描全部三角形定位」相比好在哪里？
参考答案全扫是 O(n) 每次插入、总计 O(n²)；DAG 定位沿父到子下降，期望 O(log n) 每次插入。本质是用空间（存历史节点）换定位时间——与跳表同类的时空交换。
2递归实现的栈深度在随机序下期望是多少？
参考答案递归深度等于随机二叉分裂树的期望深度，约 O(log n)。但最坏可退化到 O(n)——所以工程实现常改为迭代 + 显式历史 DAG，避免栈溢出风险。
3历史 DAG 中的「死节点」什么时候可以清理？
参考答案死节点（不再被任何查询路径经过的旧三角形）在所有可能的定位路径都不再经过它时即可回收。实践中为省事通常整批清理或直接容忍，空间换实现简单。