2.4 凸包算法

这一篇继续在几何里用分治，问题是凸包（convex hull）。凸包是计算几何最基础也最重要的概念之一——图像处理、碰撞检测、地理信息系统都离不开它。我们会讲两种求法：分治的 $O(n\log n)$ ，和工业界更常用的扫描法（Graham 扫描、Andrew 单调链）。它们思路迥异，但都到达 $O(n\log n)$ ，而且这个 $O(n\log n)$ 是最优的（下界也是它）。

1.凸包是什么

给你平面上 $n$ 个点，想象用一根橡皮筋把它们全箍住，橡皮筋收紧后形成的那个凸多边形，就是这堆点的凸包。严格点说：凸包是包含所有点的最小的凸集。

等价的、更好用的刻画：凸包的顶点是这 $n$ 个点里的一组子集，使得所有其他点都落在以它们为顶点的凸多边形内部或边界上。换句话说，凸包顶点就是"撑起橡皮筋的"那些点，内部的点不参与。

注意区分"凸包的顶点"和"凸包（多边形区域）"。我们求的是顶点序列。

2.分治法：切两半，各求凸包，再缝合

分治的思路和最近点对（2.3）一脉相承：按 $x$ 切两半，递归求各自的凸包，再处理"跨边界"的缝合。

CONVEX-HULL-DIVIDE(P)
    if n <= 3: 直接返回（三角形/线段）
    按 x 中位数切，得左半 L、右半 R
    HL = CONVEX-HULL-DIVIDE(L)   // 左半凸包
    HR = CONVEX-HULL-DIVIDE(R)   // 右半凸包
    return 合并 HL 和 HR：找上下两条公切线，缝合

合并的关键是找 $H_L$ 和 $H_R$ 的公切线（common tangent，也叫桥 bridge）。因为 $H_L$ 在左、 $H_R$ 在右，它们之间能连出两条不穿过任何点的切线——一条上公切线、一条下公切线。把这两条切线之间的凸包边界拼起来，就是合并后的凸包。

找公切线有巧妙的线性算法（沿两个凸包的顶点同步行进），所以合并是 $O(n)$ ，递归 $T(n)=2T(n/2)+O(n)=O(n\log n)$ 。

3.更实用的扫描法：Graham 扫描与 Andrew 单调链

分治法优雅，但工程上更常用的是扫描法，实现更简单、常数更小。两种主流：

Graham 扫描。 先选一个肯定在凸包上的点（比如 $y$ 最小的，最下面的）。然后按相对这个点的极角排序其余点。用一个栈维护凸包顶点：依次处理排序后的点，每加一个点就检查"栈顶前两个点到这个点是否左转"——如果不是左转（右转或共线），就把栈顶弹掉（它不在凸包上），直到左转为止再压栈。一遍扫描完，栈里就是凸包。

Andrew 单调链。 比 Graham 更简单，不用算极角（算极角要用 atan2，有浮点误差）。它按 $x$ 坐标排序（ $x$ 相同按 $y$ ），然后分别从左到右、从右到左各扫一遍，分别构建凸包的上半链和下半链，拼起来。判别同样靠"是否左转"的叉积。

ANDREW(P)
    按 (x, y) 排序
    构建下凸包 lower：依次加入点 p，
        while lower 里至少 2 个点且最后两个到 p 不是逆时针(左转):
            弹掉 lower 最后一个
        压入 p
    构建上凸包 upper：从右到左同理
    拼接 lower 和 upper（去掉重复的端点）

4.叉积：判转向的核心工具

上面反复说的"左转/右转"，靠的是向量叉积。给三个点 $A,B,C$ ，看 $\overrightarrow{AB}\times\overrightarrow{AC}$ （叉积）的符号：

叉积 $>0$ ：从 $A\to B\to C$ 是逆时针（左转）， $C$ 在 $AB$ 左侧。
叉积 $<0$ ：顺时针（右转）。
叉积 $=0$ ：三点共线。

凸包算法全程用叉积判转向：扫描时，如果连续三个顶点"右转"了，说明中间那个点在凸包内部（凹进去的），该弹掉。叉积把几何的"凸性"转化成了代数的符号判断，避免了浮点误差（叉积是整数运算，只要坐标是整数）。这就是为什么凸包算法可以做到精确（无浮点误差）。

5.复杂度与下界

无论分治、Graham 还是 Andrew，复杂度都是 $O(n\log n)$ ——瓶颈都在排序那一步（极角排序或 $x$ 排序）。排序之后，扫描或合并都是 $O(n)$ 。

而且 $O(n\log n)$ 是最优的：因为如果能在 $o(n\log n)$ 求凸包，就能在 $o(n\log n)$ 排序（把数 $(x, x^2)$ 当成点，凸包顶点按 $x$ 序就是排序结果），矛盾于排序的 $\Omega(n\log n)$ 下界。所以凸包不可能比 $O(n\log n)$ 更快——这是 4.9 节下界证明思想的一个应用。

6.练习

Q1. Andrew 单调链算法为什么要分"上凸包"和"下凸包"两次扫描，而不是一次扫完？

因为凸包是上下两条凸链组成的。从左到右扫，维护的是下凸包（每步保证左转/凸向下）；从右到左扫，维护上凸包。一次扫描无法同时维护上下两条链的性质，所以分两次各管一条，最后拼起来。这个"上下分离"的拆分让算法只需 $x$ 排序（不用算极角），实现简单且无浮点误差。

Q2. 叉积 $\overrightarrow{AB}\times\overrightarrow{AC}$ 的正负各代表什么几何意义？凸包算法怎么用它？

正代表 $A\to B\to C$ 逆时针（左转， $C$ 在 $AB$ 左侧）；负代表顺时针（右转）；零代表共线。凸包算法扫描时，如果连续三个顶点叉积为负（右转），说明中间顶点是凹的、不在凸包上，弹掉它。叉积把"凸性"转成符号判断，整数运算无误差。

Q3.（思考题） 为什么凸包的下界是 $\Omega(n\log n)$ ？给出归约论证。

因为排序可以归约到凸包：把要排序的数 $x_1,\dots,x_n$ 变成平面点 $(x_i, x_i^2)$ （都在抛物线上）。这些点的凸包包含所有点（都在凸包上），按凸包顶点顺序输出就是按 $x$ 排序的结果。若凸包能 $o(n\log n)$ ，排序就能 $o(n\log n)$ ，违反排序的 $\Omega(n\log n)$ 下界。故凸包 $\ge\Omega(n\log n)$ 。这是"用一个已知困难问题归约证明新问题下界"的标准手法（第四卷、第八卷的主题）。

7.小结

凸包是计算几何的基石。分治法靠公切线缝合两半凸包，扫描法（Graham/Andrew）靠排序 + 叉积判转向一遍扫出凸包，都到 $O(n\log n)$ 且最优。叉积把凸性转化成代数符号判断是核心技巧。到这里几何的分治就告一段落——下一篇我们离开几何，进入代数世界，看分治怎么把矩阵乘法从 $O(n^3)$ 加速到 $O(n^{2.81})$ 。