Convex hull

The convex hull of some points is the smallest convex polygon that holds them all. It is the first thing to compute for many geometry problems, and Andrew’s method finds it with one sort and two walks, using nothing but the cross product.

What a hull is

A shape is convex if the straight piece between any two of its points stays inside it: a square or a circle, but not a star or a crescent. The convex hull of a set of points is the smallest convex polygon that contains them all. Its corners are some of the points; the rest are inside it or on its edges.

Walking round a convex polygon counterclockwise, every corner turns left. A corner where the walk turns right, or goes straight on, is not needed. The practice problem leaves out points that lie on an edge but are not corners, so only real turns count.

Gift wrapping

The most direct method, the gift wrapping or Jarvis march (1973): start at the lowest point, which must be a corner. From the current corner, the next corner is the point that every other point is to the left of (compare candidates with the cross product). Repeat until you are back at the start.

Each step looks at all n points, and there is one step per corner, so the cost is O(n · h), where h is the number of corners. That is fast when the hull is small, and O(n²) when every point is a corner, as for points on a circle or on the curve y = x².

Andrew’s monotone chain

A.M. Andrew’s method (1979) sorts the points by x (and by y when x is equal). The leftmost and the rightmost points are corners, and they split the hull into a lower hull and an upper hull. Build the lower hull by walking left to right with a stack:

• before pushing a point p, look at the last two points on the stack, q and r;
• if q → r → p does not turn left (cross product ≤ 0), r is not a corner: pop it, and look again;
• then push p.

The upper hull is the same walk from right to left. Step through the figure.

# the lower hull: pts sorted by x, then y, with repeats removed
lower = []
for p in pts:
    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
        lower.pop()                  # not a left turn: not a corner
    lower.append(p)

The upper hull is the same loop over the points in reverse order; joining the two lists, without repeating the two end points, gives the hull counterclockwise. Details that matter. <= 0 removes points on an edge; with < 0 they stay in as extra “corners”. Repeated points must go (the set), or the cross product of a point with its copy is 0 in confusing places. If all points lie on one line, the result is just the two ends. The result starts at the leftmost point; rotate it if you need another start.

Why it works

By induction. A point popped while p is added lies on or above the line from the point below it on the stack to p, so it is inside the hull of the points up to p, or on its edge: it can never be a corner later either, because hulls only grow. The points that stay turn left at every step, so they form a convex chain, and every point so far is on or above it. That is exactly the lower hull.

Cost. Sorting is O(n log n). In each walk every point is pushed once and popped at most once, so the walks are O(n). In Python the sort runs in C, so the walks dominate for a few hundred thousand points.

Why n log n is needed

Any hull method that compares only can be used to sort. Given numbers x₁, …, xₙ, make the points (xᵢ, xᵢ²). They lie on the curve y = x², which bends upwards, so every point is a corner, and the hull lists them in order of x. So computing a hull is at least as hard as sorting, which needs Ω(n log n) comparisons (SORT-5). The practice tests use exactly these points to catch gift wrapping.

What hulls are for

• The two points farthest apart are both corners of the hull. Two pointers that go round the hull together (the “rotating calipers”) find them in O(h) after the hull.
• Collisions in games: testing whether two convex shapes overlap is much cheaper than for general shapes.
• Optimisation: the best of many straight-line costs at each x lies on a hull. Keeping only the lines on that hull speeds up some dynamic programs (ADDP-6).
• Outliers and shapes of data: peeling hulls layer by layer finds the most central points.

Now try GEOM-P3, The fence around the stations.