Convex Hull Algorithms: Graham Scan and Gift Wrapping

Core Idea

The convex hull of a finite set of points in the plane is the smallest convex polygon that contains them all; picture a rubber band snapped around nails. Computing it is a basic problem of computational geometry. Graham scan sorts the points by angle around a starting point and then sweeps through them with a stack, discarding any point that would create a clockwise (right) turn, for O(n log n) time overall. Jarvis's march, or gift wrapping, walks around the hull one vertex at a time in O(nh) time, where h is the number of hull vertices, so it is faster when the hull is small. Both rely on a constant-time orientation test computed with a cross product.

How It's Best Learned

Begin with the orientation test: compute the sign of the cross product for a few point triples by hand and connect the sign to left and right turns. Trace Graham scan on 8 to 10 points drawn on grid paper, writing the stack after each step, as in the computational geometry chapter of Cormen, Leiserson, Rivest and Stein. Then compare running times of Graham scan and gift wrapping on random points in a disk (many hull points) and in a square (few hull points).

Common Misconceptions

• Hull algorithms need trigonometry to compare angles. (Sorting by angle and testing turns can be done with cross products, which use only multiplication and subtraction and avoid rounding error from angle functions.)
• Gift wrapping is always slower than Graham scan. (Gift wrapping runs in O(nh) time, which beats O(n log n) when the number of hull vertices h is smaller than about log n.)
• With clever enough code, a convex hull of unsorted points can be found in linear time. (Listing the hull vertices in order can be used to sort numbers, so in the standard algebraic decision tree model the problem needs Omega(n log n) time in the worst case.)

Explainer

Given n points in the plane, the convex hull is the smallest convex polygon that encloses them. Its vertices are a subset of the points. Hulls are used in collision detection, geographic mapping, pattern recognition and as a first step in many other geometric algorithms.

Every hull algorithm rests on one primitive: the orientation test. For points a, b and c, compute

(b - a) x (c - a) = (bx - ax)(cy - ay) - (by - ay)(cx - ax).

A positive value means a → b → c turns counterclockwise (left), negative means clockwise (right), and zero means the points are collinear. The test uses only multiplication and subtraction, so with integer coordinates it is exact.

Graham scan, published by Ronald Graham in 1972, works in two phases. First, pick the point with the lowest y-coordinate, breaking ties by x, as the anchor p0. Sort the other points by their polar angle around p0, comparing angles with the orientation test instead of trigonometry. Second, scan the sorted points with a stack. Push p0 and the first point. For each new point p, look at the top two stack entries. If they and p make a right turn, the top entry cannot be on the hull, because it lies inside or on the triangle formed by p0, the entry below it and p, so pop it and test again. When the turn is left, push p. At the end the stack holds the hull in counterclockwise order. Each point is pushed once and popped at most once, so the scan costs O(n). With the O(n log n) sort, the total is O(n log n).

Jarvis's march, or gift wrapping, published by R. A. Jarvis in 1973, takes a different route. Start at a point certain to be on the hull, such as the leftmost. Find the point that every other point lies to the left of, as seen from the current point, using one pass of orientation tests. That point is the next hull vertex. Repeat until you return to the start. Each step costs O(n), and there are h steps, so the total is O(nh). This is an output-sensitive bound: fast when the hull is small, but O(n²) when every point is on the hull.

Can we beat O(n log n) in general? Not in the standard algebraic decision tree model. Place numbers x1, ..., xn at points (xi, xi²) on a parabola. All of them are hull vertices, and reading the hull in order sorts the numbers. Sorting requires Omega(n log n) comparisons, so ordered hulls do too. Timothy Chan's 1996 algorithm reaches O(n log h), which is optimal when measured by both n and h.