3.3 包装礼物算法
(Gift Wrapping)

现在我们来研究一些更实际的凸包算法。对极边算法(算法 3.2)进行一点小小的改进，就能将其速度提升 \(n\) 倍， 还能按照凸包边界上出现的顺序输出。其思路是利用一条极边作为锚点，来寻找下一个。之所以这样，是因为我们知道这些极边会连接成一个凸多边形。 这个凸多边形最多可以有 \(n\) 个顶点，因此极边的数量为 \(O(n)\)。锚点搜索只需考察 \(O(n)\) 个候选点，而不是算法 3.2 中的 \(O(n^2)\) 个候选点。 这节省了 \(n\) 倍的时间，复杂度降为 \(O(n^2)\)。

现在我们来探讨一下，这种锚定搜索是如何实现的。为方便表述，我们仍然假设点集中的点都是一般位置(general position): 集合\(S\)中任意三个点都不共线。 此时3.1.1 中提到的输出 3 和 4 相同。 假设算法最后找到一条端点为 \(x\) 的极边，如图 3.2 所示。我们知道必然存在另外一条端点为 \(x\) 的极边 \(e\)。 从 \(x\) 到集合中的另一个点 \(y\) 画一条有向的直线 \(L\)。\(L\) 包含 \(e\)，当且仅当所有其他点都在其左侧时，或者说没点在其右侧。 但请注意，如果我们对每个 \(y\) 都检查所有其他点是否都在直线的左侧，我们将回到 \(O(n^3)\) 的复杂度。那需要对于每个 \(x\)，对于每个 \(y\)，检查所有其他点。

如图 3.2 所示，降低复杂度的关键在于，包含点 \(e\) 的直线 \(L\) 与包的前一条边(hull edge)的逆时针角度最小。 这意味着无需检查所有点是否都在左侧，可以从逆时针角度推断出来。因此，对于每个点 \(y\)，计算该角度，并将其记为 \(\theta\)。 产生最小 \(\theta\) 的点必定确定了一条极边(在一般位置假设下)。

这个算法被称为"包装礼物(gift wrapping)"算法。我们可以想象着，用一根绳子包裹点集，绳子从前一个包络边缘开始弯曲，角度最小，直到触及点集为止。 最早这个算法是由 Chand & Kapur(1970) 提出的，初衷是要在任意维度下寻找凸包。我们将看到，在二维情况下，我们可以有效率更高的算法。 但在很多年里，它一直是高维空间的主要算法。它的一个优点是"输出大小敏感(output-size sensitive)"。当包络较小时，它的运行速度更快。 如果凸包有 \(h\) 条边，那么它的复杂度为 \(O(nh)\)(练习 3.4.1 [1])。

按理讲，我们还需要对算法进一步改进，以移除一般位置(general position)的假设，但我们仍然先不考虑这件事。这里还有一个细节需要考虑 —— 如何启动算法。 我们可以选择集合的最低点作为第一个锚点，并将它的"前一个(previous)"的凸包边视为水平方向。伪代码如算法 3.3 所示。 该算法的时间复杂度为 \(O(n^2)\)，因为每个凸包边需要 \(O(n)\) 的复杂度。