Convex Hulls: Explained

Convex Hull Computation

7 min readApr 22, 2017

The Convex Hull of the polygon is the minimal convex set wrapping our polygon.

This blog discusses some intuition and will give you a understanding of some of the interesting and good algorithms to compute a convex hull:

Graham’s Algorithm[O(nlogn)]

A little on Orientations:

The idea of how the points are oriented plays a key role in understanding graham’s algorithm, so make sure you read this before fiddling with the algorithm.

Thus, finding out whether the points p,q,r are making a left turn or a right turn is a simple calculation of a determinant.

Algorithm

Find the leftmost and rightmost point in the point set given to us. We divide the problem of finding convex hull into finding the upper convex hull and lower convex hull separately.

2. Sort the points according to increasing x-coordinate.

3. Push p1 and p2 into the empty stack W

[Notice that travelling the upper hull from p1 to pn is sequence of right turns at every vertex lying in between. This is the property exploited in the algorithm.]

This is a form of incremental algorithm where points are added one by one and in any incremental algorithm order of insertion plays a very important role. Pre-sorting the points in the increasing order of x-coordinates guarantees that the newly added point is always outside the convex hull formed upto then(Think!).

Time Complexity: Clearly the sorting step requires O(nlogn) time achieved by merge-sort. Also checking orientation for each point requires O(1) time. For adding each new point we have to make the orientation tests “k+1” times and once a point is removed from the stack it is never considered again so the total time complexity after the sorting step is,

Jarvis Gift Wrapping Algorithm(O(nh))

The Jarvis March algorithm builds the convex hull in O(nh) where h is the number of vertices on the convex hull of the point-set. Note that if h≤O(nlogn) then it runs asymptotically faster than Graham’s algorithm.The algorithm starts by adding the first point that is guaranteed to be on the hull. For this we can choose the lowermost point(with the least y co-ordinate). Now assuming the last two points added in the hull are Pk and Pk-1, then the next point to add(Q) is selected such that it maximizes the angle ∠QPkPk-1. We can clearly find the point Q in O(n) point. This diagram from Prof. David Mount’s notes gives a good explanation:

Also note from fig(b), To find the second point in the hull we simply consider a point P0 at (-∞,0). The search will repeat exactly h times and then will reach the original point at which we started(Why?). Thus giving a overall time complexity of O(nh).

Chan’s Algorithm(O(nlogh))

It turns out that worst case time complexity for any complex hull algorithm is O(nlogn). This can be seen intuitively as convex hull involves sorting of some kind along the boundary, or it is actually sorting of slopes in the dual plane(We’ll not do into dual plane theory here,link) and any minimum bound on any convex hull algorithm if O(nlogn), so the result follows.

But here is the worst case considering all the points lie on the convex hull, but often that is not the case.

Chan’s Algorithm improved the time complexity to O(nlogh), where h is the number of points in the convex hull of the Point set(Output sensitive algorithm).

Idea:

1 . Partition the point set into groups of equal size. Suppose there are h* points in each group. Thus we’’ll have a total of n/h* groups.

2. Now just do a graham’s scan of each of the point set and compute n/h* complex hulls.Time complexity for the step:(n/h* x h* x log(h*)),

3.Perform a Jarvis’s march thinking of this convex hulls as fat points.

This step has been shown in the figure shown above. The colored polygons are the convex hulls calculated in step 2 and after that pick the lowest point and identify which hull it belongs to. Now, from this point compute tangents to all the convex hulls. Note that there will be two tangents per convex hull and this will represent the lowest or maximum angle subtending line per group of points that we need in Jarvis’s march. The tangents from a point to convex polygon can be found in O(logm), where m is the number of points on the convex polygon. So the total time complexity of this step is:O(h x (n/h*) x log(h*)).

When the value of h* is near to h, we get a time complexity of O(nlogh).

Well, the whole argument relies on the fact that the value chosen as h* is near to h. Typically we choose h* to lie between h and h² so that we get the required time complexity. For finding the value of h we run as a search 2^(2^n), varying n as 0,1,2,…,log(log(h)). Not going into rigorous details here, but summing up the time complexity for each step we still have our required bound of O(nlogh).

Kirkpatrick’s Prune and Search algorithm(O(nlogh))

This algorithm is a little complicated than the above discussed, but attempts to approach the convex hull problem at a much more basic level.

This algorithm was presented in a paper named The Ultimate Convex Hull Algorithm? by Kirkpatrick and Seidel.

Idea:

Finding the UpperHull(P)

Find the leftmost and rightmost point of our point set and we’ll start by finding the upper hull first, but the same procedure can be extended to work for lower hull as well. This is a divide and conquer algorithm.
If |P|≤2, return the obvious answer.
else
compute the median x co-ordinate of the point set(Xmid). Draw a vertical line through this point. Partition P into L and R about this point. Our aim will be to find the convex hull edge that will intersect this line y=Xmid.

4. Find the upper bridge Bridge(pq) of L and R, , p∈L, and q∈R.

5. Delete all the point lying inside the bridge(below) and let the new L be L¹ and the new R be R¹, so continue the process for L¹ and R¹ by calling the procedure UpperHull(L¹) and UpperHull(R¹) .

Finding the Upper Bridge(The genius idea)

Idea:

Divide the point set into random two point pairs. Compute median slope(m) of all the point pairs in linear time by median finding algorithm based on selection.
Now find the farthest point that you can take and draw a line of slope m, such that all the points of point set lie to its one side. See Figure.

Here note that α is the median slope and a point p in the above figure is found such that line with slope α passing through point p has all the points to its right side.Let’s call this line the supporting line of the point set. Now carefully observe that the bridge cannot have slope greater than α.

As the point on supporting line is guaranteed to be on the convex hull(can rotate the figure such that supporting line is parallel to x axis and now say that top most point always lie on the convex hull) and and all points lie below the supporting line, it is guaranteed that convex hull edge passing through this vertex will have slope less than α. Also note that the slope of convex hull is decreasing from left to right, so it can be conveniently said that slope of the Bridge(pq) is less than α.

Now whenever a pair of points(r,s) has slope greater than α, we can safely say that point r can never be the point of the bridge so it can be eliminated. Thus we eliminate n/4 points as there are [n/4] above the median.