如何在O(n)时间内计算按x坐标排序的点集的凸包？

Question

我了解一些计算凸包的算法。其中大多数算法的时间复杂度为 O(n*log(n))，其中 n 是输入点的数量。

设 S = {p_1, p_2, ..., p_n} 为一组按照 x 坐标排序的点集，即 p_1.x <= p_2.x <= ... <= p_n.x。

我需要描述一个算法来在 O(n) 时间内计算出 S 的凸包 CH(S)。此外，我还需要分析该算法的运行时间。

- Desibre93

---

你有没有仔细地阅读过这篇wikipedia文章？ - n. m.

阅读完维基百科文章和您的评论后，我可以得出结论，如果我理解正确并且理解良好，那么这个问题可以通过使用 Graham Scan 算法来解决。 - Desibre93

非常技术性（有些迂腐）的评论：如果点只是按x排序，那么具有相同x的点会引起问题。您将不得不识别相等x的跨度并按y进行排序（以获取字典顺序）。在极端情况下，即使一定比例的点位于同一垂直线上，这也会将复杂度降低到O(n log n)。 - user1196549

Answer 1

关键是将你的点按x坐标进行排序。因此，您可以利用 Graham scan：

排序点的时间复杂度为O(n log n)。虽然循环的时间复杂度似乎是O(n^2)，因为对于每个点，它都会回到前面检查是否有任何先前的点组成“右转”，但实际上它是O(n)，因为每个点在某种意义上最多被考虑两次。[...] 因此，总时间复杂度为O(n log n)，因为排序的时间支配了实际计算凸包的时间。

因此，在您的情况下，您可以跳过排序部分，从而使时间复杂度达到O(n)。

实际上，文章在注释中继续：

相同的基本思路也适用于输入按x坐标排序而不是角度，并且分两步计算凸包，分别产生凸包的上部和下部。[...]

- gsamaras

---

你可以使用基数排序（Radix Sort），它的时间复杂度为O(N)，从而使得完整的凸包计算也能达到O(N)。 - salva

@salva 你可以尝试，但要注意效率。 - gsamaras

我的经验是，一些变体的基数排序，如递归前向基数排序，在实践中对于浮点数来说比任何比较排序算法都要快。 - salva

嗯，我明白@salva的意思，你想让我根据你的评论来改进我的答案吗？ - gsamaras

Answer 2

我无法抵制解释这个过程。

点按字典顺序（x，y）排序。

假设我们已经构建了前K个点的上凸壳。如果我们想要得到前K+1个点的上凸壳，我们必须找到新点和上凸壳之间的“桥梁”。这是通过在凸壳上回溯来完成的，直到新点和凸壳的一条边形成凸角。

当我们回溯时，丢弃形成凹角的边，在最后将新点链接到自由端点。（在图中，我们尝试三条边并且丢弃其中两条。）现在我们有了前K+1个点的上凸壳。

线性行为仅仅是因为有N个向前的步骤（加入了N个顶点），以及N-H个向后的步骤（舍弃了N-H条边，其中H是最终凸包顶点的数量）。对称的过程构建了下半部分凸壳，拼接即可得到完整的凸壳。

- user1196549