3.7 增量算法
(Incremental Algorithm)
既然我们已经在第 3.5 节中得到了最优的 \(O(n \log n)\) 算法，似乎没有必要再去探索其他算法了。 但探索其他算法的动机依然存在，我们还想将其扩展到三维(及更高维度)。凸包在三维空间中的用途远比二维空间更为广泛，我们将在下一章探讨两种构建三维凸包的算法。 难点在于，Graham 算法不能直接扩展到三维，它主要依赖于角度排序，而角度排序在三维空间中没有直接对应的算法。因此，接下来我们将介绍另外两种二维算法，它们都可以扩展到三维空间。
增量算法是最直接的算法之一。它的基本思路很简单，每次添加一个点，每步都构建前 \(k\) 个点的凸包，并利用该凸包来添加下一个点。 事实证明，这种"分解"的方式极大的简化了问题，我们只需要处理一个非常特殊的情况，向现有凸包中添加单个点。
设点集为 \(P = \{p_0, p_1, \dots, p_{n-1}\}\)，为简化表述，我们认定这些点满足一般位置假设，即任意三个点都不共线。其顶层结构如算法 3.7 所示。 第一个凸包是三角形 \(\text{conv} \{ p_0, p_1, p_2 \}\)。令 \(Q = H_{k-1}, p = p_k\)。根据 \(p \in Q, p \notin Q\)， 计算 \(\text{conv}\{ Q \cup p \}\) 有两种情况:
- \(p \in Q\).
一旦确定 \(p\) 属于 \(Q\)，就可以将其舍弃。注意，即使 \(p\) 位于 \(Q\) 的边界上，我们也可以舍弃它(假设我们的目标是输出 (4))。 虽然有几种方法可以判断 \(p \in Q\)，但最鲁邦的方法可能是第一章中的 LeftOn 函数(代码 1.6)。 当且仅当 \(p\) 位于每条有向边上或其左侧，才有 \(p \in Q\)。显然，该测试的时间复杂度与 \(Q\) 的顶点数呈线性关系。 - \(p \notin Q\).
如果任何LeftOn测试返回 false，则有 \(p \notin Q\)，此时我们需要计算 \(\text{conv}\{Q \cup p\}\)。 这项任务相对容易的原因在于，我们只需要找到从 \(p\) 到 \(Q\) 的两条切线，如图 3.10 所示，并相应地修改凸包。 我们的一般位置假设保证了 \(p\) 和 \(Q\) 之间的每条切线都只与 \(Q\) 相切于一点。假设 \(p_i\) 是其中一个切点。我们该如何找到 \(p_i\) 呢？
图 3.10 表明，我们可以利用LeftOn测试的结果来确定切点。对于切线的下点 \(p_i\)，点 \(p\) 位于 \(p_{i-1}p_i\) 的左侧，但位于 \(p_i p_{i+1}\)的右侧。 对于切线的上点 \(p_j\)，情况则相反，\(p\) 位于 \(p_{j-1} p_j\) 的右侧，但位于 \(p_j p_{j+1}\) 的左侧。这两种情况都可以用异或 (Xor) 函数来表示， 如果两条连续的边产生不同的LeftOn结果，那么 \(pi\) 就是切点，如算法 3.8 所示。 因此，可以通过与判断 \(p \in Q\) 相同的LeftOn测试来找出这两个切点。
剩下的工作就是构造新的凸包了，图 3.10 中新的凸包就是
$$
(p_0, p_1, \dots, p_{i-1}, p_i, p, pj, p_{j+1}, \dots, p_{n-1})
$$
如果用链表的形式表示凸包，就可以通过一系列简单的插入和删除操作来完成更新。此外，我们留出练习题(练习 3.7.1[1])来探讨当从 \(P\) 点出发的切线与 \(Q\) 点的边缘齐平时该如何处理。
剩下的工作就是构造新的凸包了，图 3.10 中新的凸包就是
$$
(p_0, p_1, \dots, p_{i-1}, p_i, p, pj, p_{j+1}, \dots, p_{n-1})
$$
如果用链表的形式表示凸包，就可以通过一系列简单的插入和删除操作来完成更新。此外，我们留出练习题(练习 3.7.1[1])来探讨当从 \(P\) 点出发的切线与 \(Q\) 点的边缘齐平时该如何处理。
该算法的复杂度分析很简单。每一步的工作量为 \(O(n)\)，更准确地说，它与第 \(k\) 个凸包的顶点数成正比。最坏情况下，每一步都有 \(p \notin Q\)， 导致总计算量为 \(3 + 4 + ... + n = O(n^2)\)。实践表明，只需再多花一点精力，就可以将时间复杂度降低到 \(O(n \log n)\)(练习 3.7.1[3])。
3.7.1 练习(Exercises)
- 切线退化Degenerate tangents。修改现有增量算法，使得当在点 \(p\) 的切线包含点 \(Q\) 的一条边时，算法仍然能输出正确的凸包。"正确"的凸包不应有三个共线顶点。
- 共线Collinearities。修改增量算法以处理可能包含三个或更多共线点的点集，扩展练习1。
- 最优增量算法Optimal incremental algorithm。按 \(x\) 坐标对点进行预排序，使得每一步都有 \(p \notin Q\)。然后尝试安排切线搜索策略， 使得算法运行期间的总工作量为 \(O(n)\)。这样就得到了一个 \(O(n \log n)\) 的算法。该方法是 Edelsbrunner (1987. p. 144) 提出的.