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

I cannot resist explaining the procedure.

The points are sorted in lexicographical (x, y) order.

Assume that we have built the upper hull of the K first points. If we want to get the upper hull of the K+1 first points, we have to find the "bridge" between the new point and the upper hull. This is done by backtracking on the hull until the new point and an edge of the hull form a convex angle.

As we backtrack, we discard the edges that form a concave angle, and in the end we link the new point to the free endpoint. (On the figure, we try three edges and discard two of them.) Now we have the upper hull of the K+1 points.

The linear behavior is simply justified by the fact that there are N forward steps (N vertices added), and N-H backward steps (N-H edges discarded, where H is the number of final hull vertices).

A symmetric procedure builds the lower hull, and the whole convex hull is obtained by concatenation.