3.8 分治
(Divide and Conquer)

最后我们再考虑一种实现了最优的 \(O(n \log n)\) 时间复杂度的二维凸包算法。它采用了一种与 Graham 算法完全不同的思路——分治(Divide and Conquer)，是目前已知唯一能够扩展到三维并达到渐近最优 \(O(n \log n)\) 时间复杂度的技术。因此在二维情况下，即使它相对复杂，也值得深入研究。

3.8.1 分治递归关系(Divide-and-Conquer Recurrence Relation)

"分治"是计算机科学中一种行之有效的通用方法。其本质是将问题分解成两个(几乎)相等的部分，分别递归地解决每个部分，最终通过"合并"这两个部分的解来生成完整的解。当递归地将原问题分解成非常小的子问题时，这些子问题通常很容易解决。因此，大量工作都集中在合并步骤上。

设 \(T(n)\) 为 \(n\) 个点的分治凸包算法的时间复杂度。如果合并过程可以在线性时间内完成，则有递推关系 \(T(n) = 2T(n/2) + O(n)\)。两个规模减半的问题需要 \(2T(n/2)\) 的时间，合并过程需要 \(O(n)\) 的时间。如前所述，该问题的解为 \(O(n \log n)\)。

练习 3.8.5[1] 和 [2] 要求探索合并过程效率较低时的递推关系。结论是合并必须为 \(O(n)\) 才能达到最优。

3.8.2 算法描述(Algorithm Description)

最早 Preparata & Hong (1977) 将分治法应用于凸包问题，他们的目标是创建一个高效的三维算法。为了简化解释，我们假设问题满足两种非退化情况: 任意三个点不共线，任意两个点不位于一条垂直线上。他们的算法大体需要如下几步:

参考 \(x\) 轴坐标对点排序。
将点集拆分成 \(\mathcal{A},\mathcal{B}\) 两个子集，\(\mathcal{A}\) 中包含左侧 \(\lceil n/2 \rceil\) 个点，\(\mathcal{B}\) 中包含右侧 \(\lfloor n/2 \rfloor\) 个点。
递归的计算凸包 \(A = \mathcal{H}(\mathcal{A}), B = \mathcal{H}(\mathcal{B})\)。
合并 \(A,B\)，计算 \(\text{conv}\{A \cup B\}\)。

步骤(1)的排序保证集合 \(\mathcal{A}\) 和 \(\mathcal{B}\) 被一条垂直线分隔，假设任意两点都不位于同一条垂直线上，可以保证 \(A,B\) 不会重叠，这简化了合并过程。步骤 2,3,4 在递归过程中重复执行，当 \(n ≤ 3\) 时停止。如果 \(n = 3\)，根据非共线假设，凸包为三角形。

分治算法的所有工作都集中在合并过程，在线性时间内完成是很困难的。朴素的算法只能达到 \(O(n^2)\) 的时间复杂度，正如我们之前提到的，这不足以实现 \(O(n \log n)\) 的整体性能。

我们将分别使用 \(a\) 和 \(b\) 作为多边形 \(A\) 和 \(B\) 的顶点索引，每个多边形的顶点按逆时针方向排列，并从 O 开始编号。所有索引运算均对相关多边形的顶点数取模，因此像 \(a + 1\) 和 \(a - 1\) 这样的表达式，可以分别解释为围绕 \(A\) 边界的下一个和前一个顶点。我们目标是找到两条切线，一条从下方支撑两个凸包，另一条从上方支撑。利用这两条切线，可以在 \(O(n)\) 时间内轻松构造出 \(\text{conv}\{A \cup B\}\)。这里我们仅讨论如何找到下切线，上切线的寻找方法类似。

设下切线为 \(T = ab\)。难点在于 \(T\) 的两个端点都事先未知，因此必须同时在 \(A\) 和 \(B\) 上进行搜索。值得注意的是，增量算法中的任务要简单得多，因为切线只有一个端点未知，另一个端点是一个固定的点。现在，如果朴素的搜索所有可能的 \(a\) 端点和 \(b\) 端点，最坏情况下合并过程的复杂度将达到二次方，这显然不够。因此，搜索过程必须更加精细。

Preparata & Hong 的思路是，从连接 \(A\) 的最右点到 \(B\) 的最左点的直线 \(T\) 开始，然后向下"行走(walk)"，先沿着一个凸包前进，再沿着另一个凸包前进，交替进行，直到到达下切线。参见图 3.11。伪代码见算法 3.9。注意，\(a-1\) 在 \(A\) 上是顺时针方向，\(b+1\) 在 \(B\) 上是逆时针方向，两者都表示向下移动。如果 \(a-1\) 和 \(a+1\) 都位于 \(T\) 的上方，则 \(T = ab\) 是 \(a\) 点的下切线。这等价于说这两个点都在 \(a\) 的左侧或上方。类似的定义也适用于 \(B\) 的下切线。为了便于阐述，我们假设直线总是相切于某一点，而不是相切于某一边。

如图 3.11 所示。初始时，\(T = (4, 7)\)。注意，\(T\) 与 \(A\) 和 \(B\) 都相切，但它只是 \(A\) 的下切线。
\(A\) 循环不会执行，但 \(B\) 循环将 \(b\) 递增到 11，此时 \(T = (4, 11)\) 是 \(B\) 的下切线。
但此时 \(T\) 不再是 \(A\) 的下切线，因此 \(A\) 循环将 \(a\) 递减到 0。现在 \(T (0, 11)\) 是 \(A\) 的下切线。
但这仍不是 \(B\) 的下切线，因此 \(b\) 递增到 12。现在 \(T = (0, 12)\) 是 A 和 B 的下切线，算法停止。注意，\(b = 12\) 不是 \(B\) 的最低点，0 更低一些。

3.8.3 分析(Analysis)

合并凸包算法的时间复杂度和正确性都不是直接可以得出的。但可以肯定的是，当最外层的 while 循环终止时，\(T\) 与 \(A\) 和 \(B\) 都相切。我们还有两个问题悬而未决:

外层循环必须终止。可以设想，在 \(a\) 处建立切线总是会打破在 \(b\) 处的切线，反之亦然。
实际有四条切线，如图 3.12 所示，按照前述算法，最终应该只找到其中一条，即左侧同时支撑 \(A\) 和 \(B\) 的那条切线。

引理3.8.1.下切线 \(T = ab\) 与 \(A\) 和 \(B\) 的下半部分相切。\(a\) 和 \(b\) 分别位于从 \(A\) 和 \(B\) 的最左侧顶点逆时针连接到最右侧顶点的闭合链上。

证明: 这是由于 \(A\) 和 \(B\) 在水平方向上分离造成的。设 \(L\) 为分隔它们的垂线。那么，如果 \(B\) 远高于 \(A\)，那么 \(T\) 将趋近于平行于 \(L\)，\(a\) 趋近于\(A\) 的最右侧顶点。类似地，如果 \(B\) 远低于 \(A\)，则 \(a\) 趋近于 \(A\) 的最左侧顶点。在这两个极端情况之间，\(a\) 位于 \(A\) 的下半部分。□

由于 \(a\) 从最右侧的顶点开始，并且只能递减，即顺时针移动，因此只有当 \(a\) 可以经过最左侧的顶点时，内层关于 \(A\) 的循环才能无限迭代。然而，下一个引理将证明这是不可能的。

引理3.8.2. 在算法 3.9 的整个生命周期中，\(ab\) 始终不与 \(A\) 或 \(B\) 的内部相交。

证明: 我们采用归纳法来证明之。该命题在算法初始时是成立的。

假设经过某次迭代后该命题仍然成立，并且假设 \(a\) 即将递减，这仅在 \(T\) 不是 \(A\) 的下切线时才会发生。新的切线 \(T' = (a-1, b)\) 只有在 \(b\) 位于 \((a - 1, a)\) 左侧时才会与 \(A\) 的内部相交；参见图 3.13。但 \(b\) 不能同时位于 \((a,a + 1)\) 的左侧，因为那样 \(T\) 就会与 \(A\) 相交，而我们通过归纳法假设这种情况不会发生。因此，如果下一步会导致相交，则 \(T\) 必定是点 \(a\) 的切线，并且不会进行下一步。□

由于 \(T\) 不与 \(A\) 的内部相交，且 \(b\) 位于 \(L\)(\(A\) 和 \(B\) 之间的线段)的右侧，因此 \(a\) 不能(顺时针方向)越过 \(A\) 的最左侧顶点。类似的推理也适用于 \(B\)。因此，两个循环最终都必须终止，因为它们都只沿一个方向移动索引，而索引的移动距离是有限的。现在，所有保证正确性所需的条件都已具备。由于循环终止，它们必须与双切线相交，显然，该双切线必须是下切线。

循环的时间复杂度只能是线性的，迭代步数也受限于 \(A\) 和 \(B\) 的顶点数。因此，合并过程是线性的，这意味着整个算法的时间复杂度为 \(O(n \log n)\)。

3.8.4 输出规模敏感的最优算法(Output-Size Sensitive Optimal Algorithm)

由于下界的存在，算法的渐近时间复杂度已无法改进。我们之前讨论的包装礼物(Gift Wrapping)和快速凸包(QuickHull)算法是输出大小敏感的，对于大小为 \(h\) 的凸包，它们的运行时间为 \(O(nh)\)。更仔细地检查下界证明，可以发现它建立了 \(\Omega(n \log h)\)。但是这个更精致的下界并不适用于分治算法，它并非"终极平面凸包算法the ultimate planar convex hull algorithm"。

Kirkpatrick & Seidel (1986) 在 Preparata & Hong 算法发表七年后，发表了一篇名为"the ultimate planar convex hull algorithm?"的论文。他们引入了一种新的分治范式变体，称之为"先结婚后征服marriage-before-conquest"，实现了 \(O(n \log h)\) 的时间复杂度。该算法分别构造上凸包和下凸包，并不是在划分之后再解决子问题，而是在递归地寻找两个集合的凸包之前，先找到它们的上切线。需要一些技巧才能在线性时间内找到这个上切线，称之为桥(bridge)，但找到之后，就可以在递归之前舍弃桥下垂直方向以及桥两端点之间的所有点。这种舍弃部分点的操作，是实现更低渐近时间复杂度的关键。然而，这种理论上的改进是否值得在实际应用中增加编程复杂度，还有待商榷。

3.8.5 练习(Exercises)