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

5
votes

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.

2
algorithmtime-complexitycomputational-geometryconvex-hull
So did you read the wikipedia article thoroughly? – n. 1.8e9-where's-my-share m.
After reading the wikipedia article and your comments, I can conclude that this problem can be solved be using the Graham Scan algorithm if I am correct and understood it well. – Desibre93
Very technical (and somewhat pedantic) remark: if the points are just sorted on x, then points with equal x cause an issue. You will have to identify stretches of equal x and sort them on y (to obtain lexicographical ordering). In an extreme case, such that a constant fraction of the points lie on the same vertical, this degrades the complexity to O(n log n). – Yves Daoust

2 Answers

1
votes

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.

enter image description here

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.

4
votes

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(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.

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.[...]