I. RIC With Example
数学大学
I. RIC With Example
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
I. RIC With Example
计算几何 · 05. Delaunay Triangulation
Idea
随机增量构造（RIC）：随机序逐点插入，每次只修被影响的三角形。
随机序
打乱插入次序，保证期望性能
局部修复
新点只影响其外接圆覆盖的三角形
Point Location
定位新点所在三角形：借助历史结构（DAG）或走启发线。
历史 DAG
记录三角形分裂历史，沿树下降定位
期望
随机序下定位路径期望 O(log n)
In-Circle Test
内圆测试：新点落入某三角形外接圆内即触发该三角形分裂修复。
判别式
四点行列式的符号即判定结果
修复
把外接圆含新点的三角形全部翻边重连
Edge Flipping
修复用边翻转完成：从新点相邻的边开始，逐条检验翻转直至全部合法。
递归翻转
翻一条边后其新邻边入队继续检验
期望次数
随机序下期望翻转次数为常数
Frontier
边界（frontier）：新点可见的边构成的星形区域边界。
可见边
外接圆含新点的三角形之并的边界
重连
全部可见边改为与新点相连
Convergence
收敛：插入完成后结构恰为全点集的 Delaunay 三角剖分。
正确性
内圆测试保证空圆性质始终维持
结束
全部点插入并修复后即最终结果
本节要点
- ✓RIC：随机序插入 + 局部修复
- ✓定位走历史 DAG，期望 O(log n)
- ✓内圆测试触发边翻转修复
- ✓收敛到全点集的 Delaunay
延伸主题：实现 RIC 骨架测量实际翻转次数
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1RIC 的「期望高效」与最坏情形之间是什么关系？
参考答案随机序是算法自己选的，期望性能对任何输入都成立（期望是对算法内部随机性取的）；但特定随机序仍可能有坏运气。工程上常加「重启」或退化检测兜底。
2历史 DAG 定位为什么期望 O(log n)？
参考答案DAG 的每层对应一次三角形分裂，随机序下节点数期望线性、深度期望对数。查询沿父子指针下降，期望路径长度 O(log n)——与跳表的分析同源。
3RIC 中「先定位后修复」为什么比「全局重算」高效？
参考答案随机插入只破坏新点外接圆覆盖的局部三角形（期望常数个），局部修复即可恢复全局 Delaunay 性质；全局重算则每次 O(n log n)。增量局部性是 RIC 高效的根本原因。