3.4 快速凸包算法
(QuickHull)

我们继续介绍包络算法，本节介绍的一种1970 年代末多位研究者独立提出的算法。由于它与快速排序算法(Knuth 1973)相似，Preparata & Shamos(1985) 将其命名为 "QuickHull" 算法。 它的基本思想十分简单。对于大多数点集，很容易挑出许多位于凸包内部的点，然后集中精力考察那些靠近凸包边界的点。 QuickHull 算法的第一步是找到两个不同的极点(extreme points)。我们可以使用右下角的点 \(x\) 和左上角的点 \(y\)，如图 3.3 所示，它们一定是极点且互不相同(参见引理 1.2.1 和图 1.11)。 完整的凸包由位于 \(xy\) 上方的"上包upper hull"和位于 \(xy\) 下方的"下包lower hull"组成。 QuickHull 从极点\((a, b)\)开始，找到严格位于 \(ab\) 右侧的第三个极点 \(c\)， 并排除掉 \(\Delta abc\) 内的所有点，然后递归地对 \((a, c)\) 和 \((c, b)\) 重复该过程。

令 \(S\) 为严格位于线段 \(ab\) 右侧的点集，\(S\) 可能为空集。QuickHull 的核心思想是，距离 \(ab\) 最远的点 \(c \in S\) 必定位于凸包上。它是在垂直于线段 \(ab\) 方向上的极点。 因此，我们可以排除 \(\Delta abc\) 内部的所有点，以及边上除了顶点 \(a,b,c\) 之外的所有点。如图 3.3 所示，对 \(ac\) 右侧的点 \(A\) 和 \(cb\) 右侧的点 \(B\) 重复相同的步骤。

算法 3.4 中的给出了 QuickHull 的伪代码，它返回一个点列表。伪代码中的二元运算符 "+" 表示将左右两个列表拼接成一个大的列表。 最终的凸包 \((x) + \text{QuickHull}(x, y, S_1) + (y) + \text{QuickHull}(y, x, S_2)\)，其中 \(S_1\) 和 \(S_2\) 分别是线段 \(xy\) 正上方和正下方的点。 如图 3.3 所示，递归调用时会生成的连续三角形 \(\Delta abc\)。更多细节请参见练习 3.4.1[3]。