数学大学
K. RIC Analysis
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
K. RIC Analysis
计算几何 · 05. Delaunay Triangulation
Time Cost
RIC 总时间：期望 O(n log n)，与最优静态算法同阶。
构成
定位期望 O(log n) + 修复期望均摊 O(1)
求和
n 次插入合计期望 O(n log n)
Backward Analysis
反向分析：假装从最终结构逆序删除点，第 i 步成本取决于第 i 点在 i 个点中「暴露」与否。
思路
删除第 i 点的成本 = 第 i 点在剩余 i−1 点中的依赖度
期望
随机序下逆向与正向等价，但更易分析
Preconditions
分析的前提：随机插入序、一般位置、三角剖分维护正确。
随机序
均匀随机排列，与输入分布无关
一般位置
无四点共圆等退化，公式才干净
Types Of Edge Change
边的状态变化类型：新点插入时的边分裂、翻转与新增。
三类变化
边分裂、边翻转、新生成的辐射边
Number Of Edge Changes
边变化次数的期望分析：与点的度数相关，度数期望为常数。
度数期望
随机点集中期望度数小于 6（平面图性质）
期望常数
局部修复量期望为常数 → 总量线性
Average Degree
平均度数：平面三角剖分的边数为 3n−6，平均度数小于 6。
推导
2E=3T+边界 ≤ 6n，平均度 < 6
作用
保证新点的邻居期望常数个
Number Of Rebucketings
重新分桶次数：DAG 定位中节点被重复挂接的期望总量为 O(n)。
冲突计数
一个点被重新分桶即产生一次冲突
期望控制
随机序下期望冲突总数线性
Probability For Rebucket
重分桶概率：第 i 点在第 j 步被重分桶的概率 ≤ k/j（k 为相关结构大小）。
几何级数
各步概率构成调和级数型求和
总期望
Σ k/j = O(k log n)
Expectation
总期望复杂度：定位 O(n log n) + 重分桶 O(n)，合计 O(n log n)。
合计
两个 O(n log n) 项相加仍为 O(n log n)
常数
常数因子小，实践性能优秀
Further Consideration
延伸考量：最坏情形仍可能 O(n²)，工程上可退回确定性 O(n log n) 算法。
最坏
特定插入序下退化为平方
兜底
分治法作为确定性备选
本节要点
- ✓RIC 总期望 O(n log n)
- ✓反向分析让期望计算更简单
- ✓平均度数 <6 保证局部修复期望常数
- ✓最坏情形由确定性算法兜底
延伸主题：推导期望度数 <6复现一次反向分析
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1反向分析为什么比正向分析更适合 RIC？
参考答案总时间 = 定位期望 O(log n) 每点 + 修复期望均摊 O(1) 每点，n 次插入合计 O(n log n)，与最优静态算法同阶。
2平面三角剖分「平均度数 <6」如何推出？
参考答案三角剖分边数 E=3n−6−b（b 为凸包边数），总度数 2E < 6n−12，平均度数 <6。这个常数界让「新点邻居期望常数个」成立，是修复成本低的关键。
3反向分析中「第 i 点被删除的成本」怎么定义？
参考答案等于该点在当前结构中的度数：删除它需要修复它的所有邻边。随机序下第 i 点在 i 个点中的期望度数为 O(1)（平均度数 <6），因此期望总删除成本为 O(n)。