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 的伪代码，它返回一个点列表。伪代码中的二元运算符 "+" 表示将左右两个列表拼接成一个大的列表。 假如 \(S_1\) 和 \(S_2\) 分别是线段 \(xy\) 上方和下方的点集，那么该算法最终输出的凸包列表为 \((x) + \text{QuickHull}(x, y, S_1) + (y) + \text{QuickHull}(y, x, S_2)\)。 图 3.3 中所示的三角形 \(\Delta abc\) 就是递归调用生成的。更多细节请参见练习 3.4.1[3]。

现在我们来分析 QuickHull 的时间复杂度。找到初始极点 \(x\) 和 \(y\)，并将点集 \(S\) 分割成 \(S1\) 和 \(S2\)，可以在 \(O(n)\) 的时间内完成。 对于递归函数，假设 \(|S| = n\)，那么确定极点 \(c\) 需要 \(n\) 步。而且递归调用的复杂度取决于 \(A\) 和 \(B\) 的大小。 令 \(|A| = \alpha\) 且 \(|B| = \beta\) 有 \(\alpha + \beta ≤ n - 1 = O(n)\)。因为 \(c\) 不包含在 \(A\) 或 \(B\) 中，所以 \(\alpha + \beta\) 最多不会超过 \(n-1\)。 如果 \(|S| = n\) 那么 QuickHull 的时间复杂度为 \(T(n)\)，我们可以写出它的递归表达式 \(T(n) = O(n) + T(\alpha) + T(\beta)\)。 如果不能把 \(\alpha\) 和 \(\beta\) 写成 \(n\) 的表达式，则无法求解此方程。

我们先考虑最好的情况。假设每次分区都尽量均衡，有\(\alpha = \beta = n/2\)。在这个粗略的分析中，我们可以忽略\(\alpha + \beta\)之和应为\(n - 1\)这个微小的偏差两。 此时我们有 \(T(n) = 2T(n/2) + O(n)\)。这是一个常见的递推关系，其解为 \(T(n) = O(n \log n)\)。因此，在最好的情况下，复杂度为 \(T(n) = O(n \log n)\)。

最坏的情况是，每次划分是有偏的，即 \(\alpha = 0\) 且 \(\beta = n - 1\)。此时有递推关系式 \(T(n) = T(n - 1) + O(n) = T(n - 1) + cn\)。 重复展开递推式就可以得到 \(O(n^2)\)。因此，尽管 QuickHull 通常速度很快(练习 3.4.1 [7])，但在最坏情况下，其复杂度仍然是二次的。

下一节将要介绍的算法一个比一个快，最终得到一个最坏情况下复杂度为 \(O(n \log n\) 的理想算法。