CODEWITHSUNDEEP
algorithmtime-complexitycomputational-geometryconvex-hull
Desibre93
Desibre93

Reputation: 99

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

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.

Upvotes: 5

Views: 2997

Answers (3)

Eric Ouellet
Eric Ouellet

Reputation: 11763

It will always be impossible to do it in O(n). Because when you insert a newly discovered valid point for the convex hull, it could (will in most case) automatically invalid one or more neigbors which make it O(n log h) where h is the result. By the way you could modify my algorithm to easily achieve your goal in O(n log h). But having point sorted by X would not give you a big advantage. First and Extremely fast Online 2D Convex Hull Algorithm in O(Log h) per point

I know my answer is too late for you but perhaps for other ;-)

Upvotes: 0

user1196549
user1196549

Reputation:

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.

Upvotes: 1

gsamaras
gsamaras

Reputation: 73444

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

Upvotes: 4

Related Questions