L. Divide-And-Conquer
数学大学
L. Divide-And-Conquer
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
L. Divide-And-Conquer
计算几何 · 04. Voronoi Diagram
Strategy
分治构造 Voronoi 图：左右两半分别建图，再沿垂直分界线合并。
分半
按 x 坐标中位线把站点分为左右两半
合并核心
两半的 Voronoi 图由一条折线缝合
Solving Overlaps
处理重叠：合并时丢弃被对侧结构覆盖的边，只保留有效的 Voronoi 边。
裁剪
每条旧边与新折线比较后截取有效段
顺序
沿折线自下而上同步推进两侧裁剪
Contour
轮廓（contour）：合并产生的左右势力分界折线——一条 y 单调的双曲折线链。
构成
折线由左右站点的垂直平分线段拼接
作用
把左右两图的边裁剪成最终形态
Bisectors
轮廓的每一段是某个左站点与某个右站点的垂直平分线。
段生成
折线拐点处切换配对的站点对
段数
至多 O(n) 段，保证合并线性
Y-Monotonicity
轮廓的 y 单调性：自下而上推进不会回头，保证合并线性时间。
单调保证
左右各按 y 排序，折线随之单调
关键地位
单调性是线性合并的正确性基础
Common Tangents
合并起点：左右凸包的公切线给出轮廓的起始配对站点。
公切线
上下公切线确定首末配对
衔接
切点同时是凸包与 Voronoi 的连接点
Contour Length
轮廓长度分析：折线段数不超过左右站点数之和，合并线性。
段数上界
每步至少消耗一个站点，段数 ≤ n₁+n₂
意义
保证递推 T(n)=2T(n/2)+O(n)
Clip & Stitch
裁剪与缝合：用轮廓截齐两侧旧边，再把轮廓本身嵌入成新边。
截齐
轮廓两侧的旧边在接触点处截断
嵌入
轮廓段成为最终 Voronoi 图的组成部分
Intersecting with Cells
轮廓与胞腔相交的处理：穿过胞腔时按站点对切换平分线段。
穿胞腔
轮廓进入新胞腔时切换配对站点
拐点
拐点是三个站点外接圆的圆心
Convexity
凸性辅助合并：凸包公切线、单调轮廓与胞腔凸性共同保证合并顺利。
凸性角色
胞腔凸 ⇒ 与扫描线的交是连续区间
保证
同步推进不出现断裂或回退
Avoiding Rescans
避免重扫：指针只前进不回退，保证合并的线性时间。
单调推进
两侧指针永不后退
代价
每条边至多被访问常数次
本节要点
- ✓分治 Voronoi：分半建图 + 轮廓合并
- ✓轮廓 y 单调、线性段数
- ✓裁剪缝合后嵌入，指针不回退
延伸主题：实现轮廓合并验证合并后图的正确性
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1合并 Voronoi 图的轮廓为什么是 y 单调的？
参考答案左右两半按 x 分割，合并线上任一点的最近站点中，左侧候选随 y 递增单调切换、右侧同理；两股单调趋势合成一条 y 单调的折线。若不单调，指针就需回退，线性合并不成立。
2分治 Voronoi 与增量构造如何取舍？
参考答案分治总代价稳定在 O(n log n)，适合大规模离线构造；增量实现简单、支持动态插入，最坏 O(n²) 但随机序下期望 O(n log n)。批量离线选分治，在线动态选增量。
3轮廓拐点（Voronoi 顶点）在合并中如何产生？
参考答案轮廓切换配对站点时，新旧两条平分线的交点就是拐点——该点到三个站点（一个旧左站点、一个旧右站点、一个新加入的站点）等距，恰好是三站点外接圆圆心。