How do I compute, in O(n) time, a convex hull of a set of points which are sorted by x-coordinate?

Question

I read about algorithms to compute convex hulls. Most of them take O(n*log(n)) time, where n is the number of input points.

Let S = {p_1, p_2, ..., p_n} be a set of points which are sorted by x-coordinates, that is, p_1.x <= p_2.x <= ... <= p_n.x.

I have to describe an algorithm that computes the convex hull of S, CH(S), in O(n) time. Additionally, I also have to analyze the running time of the algorithm.

Answer 1

The key is that your points are sorted to the x coordinate. As a result you could take advantage of 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(n²), 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.

So, in your case, you skip the sorting part, allowing you to achieve O(n) time complexity.

In fact, the article continues in 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.[...]