K. Incremental Construction
数学大学
K. Incremental Construct
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
K. Incremental Construct
计算几何 · 04. Voronoi Diagram
Royal Garden
皇家花园比喻：新增站点像在花园里圈一块新领地，从邻近胞腔中划出。
增量视角
站点逐个加入，每次局部更新结构
领地
新站点从最近邻胞腔切出自己的胞腔
Disjoint Union
新胞腔是旧胞腔被新站点的垂直平分线切割的分离并集。
切割
旧胞腔被平分线分为「归新」「留旧」两块
不相交
切割出的两块互不重叠
Complexity
增量构造的复杂度：单次插入 O(k)（k 为受影响边数），最坏 O(n)。
受影响边
只有邻近胞腔被切割，其余不动
最坏
全部胞腔邻接新站点时退化为 O(n)
本节要点
- ✓增量构造：逐站加入，局部更新
- ✓新胞腔由旧胞腔切割而来
- ✓最坏单次 O(n)，随机序均摊更好
延伸主题：实现一次增量插入构造最坏的插入次序
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1增量构造的最坏插入次序是什么？
参考答案让每个新站点的胞腔都与所有旧胞腔相邻——例如站点按到中心距离递增排列，每个新站点都在外围「包一圈」。最坏时总成本 O(n²)。随机序的期望性能好得多。
2随机化对增量构造的影响有多大？
参考答案随机插入次序下，第 i 个站点的胞腔期望破坏数为 O(1)（回溯分析），总期望 O(n log n)——把最坏 O(n²) 压到接近排序的量级。随机化以期望保证换确定性。
3切割出的「新胞腔」为什么一定是凸的？
参考答案新胞腔是新站点与若干邻近站点的垂直平分线半平面之交——半平面凸，交亦凸。无论切割自多少个旧胞腔，拼出来的新胞腔天然保持凸性。