Convex Hull: Graham Scan and Monotone Chain

What the rubber band knows

Scatter some nails on a board and stretch a rubber band so it surrounds them all, then release. It snaps onto the outermost nails and forms a tight polygon; every other nail sits inside. That polygon is the convex hull of the points — the smallest convex region containing them, where 'convex' means: pick any two points inside, and the straight segment between them stays inside, no dents allowed. The hull is the standard first question of computational geometry because it is the shape of 'where the data lives': the spatial extent of a cloud, the outline a robot must not cross, the boundary you wrap a tarp around.

Here is the crucial observation that connects to last guide. Walk around that taut rubber band counter-clockwise. At every nail it touches, the band bends only one way: to the left. It never turns right and never goes straight back on itself, because a right turn would mean a dent, and a dent is exactly what a stretched band cannot have. So 'is this shape a convex hull?' becomes a sequence of orientation tests — the same cross-product sign you learned to read as left-turn, right-turn, or collinear. The hull is precisely the polygon whose every consecutive triple of vertices makes a left turn. That single fact is the engine of every algorithm below.

Andrew's monotone chain: sort, then sweep twice

The cleanest hull algorithm to learn first is Andrew's monotone chain. It builds the hull in two halves. First sort all points by x-coordinate (ties broken by y). Now sweep left to right building the lower hull, then sweep right to left building the upper hull, and glue them at the leftmost and rightmost points. Each half is built by the same little stack rule, so once you understand one half you understand both. The picture: the lower chain hugs the points from underneath, the upper chain caps them from above, and together they enclose everything.

The stack rule is the whole trick. Keep a list (used as a stack) of hull vertices so far. To add the next point p: while the list has at least two points and its last two points together with p do NOT make a left turn, pop the last point off; then push p. 'Not a left turn' means the orientation test on the top two points and p gives a right turn or collinear — a dent or a redundant flat point — so the previous vertex cannot be on the hull and gets discarded. You are erasing every nail the rubber band would lift off of as it tightens past p. After both sweeps, the concatenated chains are the hull in counter-clockwise order.

build_lower(points sorted by x):
    hull = []
    for p in points:                       # left to right
        while len(hull) >= 2 and
              orient(hull[-2], hull[-1], p) <= 0:   # not a left turn
            hull.pop()                      # drop the dent / flat point
        hull.append(p)
    return hull        # upper hull: same loop over points REVERSED

Why it costs O(n log n), and why each point is touched twice

Look at the cost in two pieces. The sort costs O(n log n) — that is the dominant term, and it is the same sort you already trust. The two sweeps look like they could be quadratic because of the inner while-loop that pops, but they are not: they run in O(n) total. The reason is a classic accounting argument. Across an entire sweep, every point is pushed onto the stack exactly once. A pop can only remove a point that was previously pushed, so the total number of pops over the whole sweep can never exceed the total number of pushes, which is n. The inner loop is not 'n work per point' — it is 'n pops shared across all points.'

So each point enters the stack once and leaves at most once: it is touched a constant number of times, the sweeps cost O(n), and the whole algorithm is O(n log n), dominated entirely by the sort. This is exactly the amortized-counting style from the data-structures ladder — you bound a sequence of operations as a whole rather than charging the worst case to every step. It would be a genuine mistake to call the sweep O(n^2) by looking at the nested loop in isolation; the pop budget is what saves it.

Graham scan: same idea, polar order

The historically famous version is the Graham scan, and it is the same stack-of-left-turns engine with a different sort key. Instead of sorting by x, pick the lowest point (smallest y, breaking ties by x) as a pivot — this point is guaranteed to be on the hull. Then sort all other points by the angle they make with the pivot, sweeping like a radar arm from right to left around it. Now walk the points in that angular order, applying the identical rule: while the top two stack points and the next point fail to make a left turn, pop; then push. The result is the full hull in one pass, not two halves.

Why does sorting by angle work? Because sweeping the points by increasing angle around the pivot visits them in the order a counter-clockwise hull would meet them. The pivot anchors the bottom, and as the angle increases you naturally encounter the right side, then the top, then the left. The same left-turn-only invariant holds throughout, so the same pop-the-dents stack builds the hull. Graham scan's sort by angle is slightly fussier to implement than monotone chain's sort by x — you compare points by orientation rather than by a plain number, and you must handle ties at equal angle carefully — which is why many people prefer monotone chain in practice. But the cost is identical: O(n log n) for the sort, O(n) for the single sweep by the same pop-counting argument.

A tiny trace, and why it is correct

Take five points and build the lower hull by monotone chain. Sorted by x they are A(0,0), B(1,2), C(2,1), D(3,3), E(4,0). Push A, push B. Add C: look at the last two, A and B, with C — going A to B to C bends down, a right turn, so pop B; the stack is [A], fewer than two points, so push C. Now [A, C]. Add D: A, C, D makes a left turn (it bends up), so no pop, push D — [A, C, D]. Add E: C, D, E bends down, a right turn, pop D; now A, C, E — A to C to E bends down again, pop C; stack is [A], push E. Lower hull: A, E. Notice B, C, and D all got discarded: B(1,2) and C(2,1) both sit above the straight A-E bottom edge (y=0), and D(3,3) bulges high above it, so none belong to the lower boundary.

1. Invariant: after processing each point, the stack holds, in order, the lower hull of all points seen so far — every consecutive triple in it makes a left turn (no dents). This is the loop invariant; verify it holds at the start (a single point trivially has no triple) and after each step.
2. Maintenance: when adding p, every pop removes a vertex that with its two neighbours fails the left-turn test — a point that cannot be on the hull of the points-including-p, because it lies inside the bend p creates. After all bad vertices are popped and p is pushed, every triple again turns left, so the invariant survives.
3. Termination and correctness: after the last point, the invariant says the stack IS the lower hull of all points. The upper sweep gives the upper hull the same way; concatenating them yields the full convex hull, and the pivot/leftmost/rightmost endpoints guarantee the two chains meet cleanly.

Honest limits and the lower bound

Can we beat O(n log n)? For comparison-based hull algorithms, no — and the reason is beautiful. There is a hull lower bound: if you could compute a convex hull in faster than O(n log n), you could sort n real numbers faster than O(n log n), which the comparison-sorting lower bound forbids. The trick is a reduction: map each number a to the point (a, a^2), all sitting on a parabola, where every point is on the hull. Reading the hull off in order recovers the numbers in sorted order. So sorting reduces to hull-finding; hull is at least as hard as sorting; and Theta(n log n) is the honest floor for this whole family.

Two honest caveats round this out. First, that lower bound is about comparison/algebraic models; output-sensitive algorithms can do better when the hull is small, running in O(n log h) where h is the number of hull vertices — so a thousand points with a triangular hull need not pay full sorting cost. Second, watch out for degeneracies: three or more collinear points on a hull edge, or duplicate points, are exactly where a hasty 'pop on not-a-left-turn' implementation goes wrong. Decide deliberately whether collinear points on an edge should be kept or dropped, and use integer or exact arithmetic in your orientation test so a near-zero cross product is not flipped by floating-point error — the same robustness worry that ran through last guide.