L. Divide-And-Conquer (2)
数学大学
L. Divide-And-Conquer (2
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
L. Divide-And-Conquer (2
计算几何 · 01. Convex Hull
Preprocessing
预处理：按 x 坐标排序并去重，为递归分半做好准备。
排序
按 x 升序排列全部点
去重
重复点只保留一份，防退化
Common Tangents
公共切线：连接左右两个凸包的上桥与下桥。
上下桥
上桥是上公切线，下桥是下公切线
查找
从内侧点对出发轮换调整至两侧都贴合
Topmost + Bottommost ?
候选端点策略：以左右各自最高点与最低点作为切线查找起点。
初值
最高/最低点是切线查找的合理起点
轮换收敛
不满足切线条件就轮换移动，必在有限步收敛
Stitch
缝合：沿上桥从左包走到右包，再沿右包、下桥、左包绕回，缝出新凸包。
缝合顺序
上桥 → 右包边界 → 下桥 → 左包边界
产物
缝出的多边形即合并后的凸包
Zig-Zag
切线查找的之字形路径：两端点轮流试探前进，轨迹呈之字收敛。
交替移动
左端点与右端点轮流按切线条件调整
终止
两侧同时贴合时即为公切线
Time Cost
时间成本分析：每层合并线性，层数 log n，总代价 O(n log n)。
递推
T(n)=2T(n/2)+O(n)
瓶颈
预排序的 O(n log n) 与主算法同阶
More Considerations
更多考量：退化情形（共线点）、动态插入与并行化的延伸讨论。
退化处理
共线点的取舍决定凸包是否含边上的点
动态与并行
在线插入用动态凸包，分治天然可并行
本节要点
- ✓预处理排序去重，递归分半
- ✓上下公切线缝合两个子凸包
- ✓之字查找收敛，总代价 O(n log n)
延伸主题：实现完整分治凸包用随机点测试正确性
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1公切线查找的轮换为什么一定会终止？
参考答案每次轮换移动都使候选切线的斜率单调地朝正确方向变化，且候选点对有限；不会来回震荡，最多走完两个凸包的边界周长即找到贴合的公切线。
2分治凸包与 Graham 扫描相比，各自的适用场景是什么？
参考答案Graham 扫描实现简单、一次性静态求解；分治法结构规整、天然支持并行与动态插入（各子凸包可独立维护）。静态小规模选 Graham，大规模或动态场景选分治。
3预处理排序在整个算法的代价里占多少？
参考答案排序本身 O(n log n)，与递归合并同阶，因此不构成额外瓶颈；但若数据已按某序给出或需要在线处理，可改用不需预排序的增量式凸包算法。