如何在 O(n) 时间内计算一组按 x 坐标排序的点的凸包？
How do I compute, in O(n) time, a convex hull of a set of points which are sorted by x-coordinate?
我阅读了有关计算凸包的算法。他们中的大多数需要 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) 的凸包的算法。另外，我还要分析算法的运行时间。
关键是你的点排序到x坐标。因此，您可以利用 Graham scan:
Sorting the points has time complexity O(n log n). While it may seem
that the time complexity of the loop is O(n2), because for
each point it goes back to check if any of the previous points make a
"right turn", it is actually O(n), because each point is considered at
most twice in some sense. [...] The overall time complexity is
therefore O(n log n), since the time to sort dominates the time to
actually compute the convex hull.
因此，在您的情况下，您跳过排序部分，从而实现 O(n) 时间复杂度。
事实上，文章在 Notes 中继续：
The same basic idea works also if the input is sorted on x-coordinate
instead of angle, and the hull is computed in two steps producing the
upper and the lower parts of the hull respectively.[...]
我忍不住要解释一下程序。
点按字典序 (x, y) 排序。
假设我们已经构建了第K个点的上壳。如果我们想要得到第 K+1 个点的上壳，我们必须找到新点和上壳之间的 "bridge"。这是通过在船体上回溯直到新点和船体的边缘形成凸角来完成的。
当我们回溯时，我们丢弃形成凹角的边缘，最后我们 link 新点指向自由端点。 （在图中，我们尝试了三个边并丢弃了其中的两个。）现在我们有了K+1个点的上层包。
有 N 个前向步骤（添加了 N 个顶点）和 N-H 个后向步骤（丢弃了 N-H 个边，其中 H 是最终外壳顶点的数量）这一事实简单地证明了线性行为。
一个对称过程构建下层包体，通过级联得到整个凸包体。
我阅读了有关计算凸包的算法。他们中的大多数需要 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) 的凸包的算法。另外，我还要分析算法的运行时间。
关键是你的点排序到x坐标。因此，您可以利用 Graham scan:
Sorting the points has time complexity O(n log n). While it may seem that the time complexity of the loop is O(n2), because for each point it goes back to check if any of the previous points make a "right turn", it is actually O(n), because each point is considered at most twice in some sense. [...] The overall time complexity is therefore O(n log n), since the time to sort dominates the time to actually compute the convex hull.
因此，在您的情况下，您跳过排序部分，从而实现 O(n) 时间复杂度。
事实上，文章在 Notes 中继续：
The same basic idea works also if the input is sorted on x-coordinate instead of angle, and the hull is computed in two steps producing the upper and the lower parts of the hull respectively.[...]
我忍不住要解释一下程序。
点按字典序 (x, y) 排序。
假设我们已经构建了第K个点的上壳。如果我们想要得到第 K+1 个点的上壳，我们必须找到新点和上壳之间的 "bridge"。这是通过在船体上回溯直到新点和船体的边缘形成凸角来完成的。
当我们回溯时，我们丢弃形成凹角的边缘，最后我们 link 新点指向自由端点。 （在图中，我们尝试了三个边并丢弃了其中的两个。）现在我们有了K+1个点的上层包。
有 N 个前向步骤（添加了 N 个顶点）和 N-H 个后向步骤（丢弃了 N-H 个边，其中 H 是最终外壳顶点的数量）这一事实简单地证明了线性行为。
一个对称过程构建下层包体，通过级联得到整个凸包体。