Convex Hull (Graham Scan)

How the Graham scan works

Stretch a rubber band around a scatter of nails on a board and let it snap tight. The shape it settles into — the smallest convex polygon containing every nail — is the convex hull. The Graham scan, published by Ronald Graham in 1972, was the first algorithm to compute it in optimal O(n log n) time, and it does so with a trick that still feels clever fifty years on: sort the points once, then build the boundary with a single stack that only ever accepts left turns.

The algorithm runs in three phases:

1. Anchor. Pick the point with the lowest y-coordinate, breaking ties by lowest x. Call it P₀. This point is provably on the hull — nothing sits below it — so it is a safe place to start and a safe place to finish.
2. Sort. Order every other point by the polar angle it makes with P₀, measured counterclockwise from the positive x-axis. After this step the points spiral outward from the anchor in the same rotational order they will appear on the hull boundary.
3. Scan. Walk the sorted points, pushing each onto a stack. Before every push, look at the top two points already on the stack together with the incoming point. If those three make a clockwise (right) turn, the middle point is a dent in the boundary — pop it. Keep popping until the turn is counterclockwise, then push.

When the walk finishes, the stack holds exactly the hull vertices in counterclockwise order. The whole correctness argument rests on one invariant: the stack always describes a convex chain. A new point can only ever break convexity at the most recent vertices, and popping them restores it.

The turn test is a cross product

The single primitive the scan needs is "do A → B → C turn left, right, or go straight?" That is answered by the z-component of the 2D cross product of the two edge vectors:

cross(A, B, C) = (Bx − Ax)·(Cy − Ay) − (By − Ay)·(Cx − Ax)

  cross > 0   counterclockwise (left turn)   → keep
  cross < 0   clockwise        (right turn)  → pop B
  cross = 0   collinear                       → policy choice

Geometrically the cross product is twice the signed area of triangle ABC. A positive area means C is to the left of the directed line A→B. Because the scan never needs the magnitude — only the sign — the test is a handful of multiplies and subtractions with no square roots, no trigonometry, and on integer inputs no rounding at all. That exactness is the reason the cross product, not the slope or the actual angle, is the workhorse of practical computational geometry.

When to reach for Graham scan

• Static point sets you process once. The sort is paid a single time; after that the hull is essentially free to recompute on a subset that is already in angular order.
• Dense point clouds where most points are interior. Graham scan's O(n log n) does not degrade no matter how many points end up on the hull, unlike output-sensitive methods.
• Collision detection and physics broad-phase. Convex shapes make separating-axis tests cheap; hulls turn arbitrary point clouds into convex proxies.
• Pre-processing for diameter, width, or smallest enclosing rectangle — all of which only need the hull, then run a linear rotating-calipers pass on it.

If your points arrive incrementally, or you need the hull to update as points are inserted and deleted, a dynamic or incremental hull beats re-running Graham scan from scratch. And if you expect almost every point to sit inside, with only a few on the boundary, the output-sensitive gift-wrapping or Chan's algorithm can win.

Graham scan vs other hull algorithms

	Graham scan	Andrew's monotone chain	Jarvis march	QuickHull	Chan's algorithm
Time complexity	O(n log n)	O(n log n)	O(nh)	O(n log n) avg, O(n²) worst	O(n log h)
Sort key	polar angle	x then y	none (angular per step)	none (recursive split)	angle, in groups
Output-sensitive	no	no	yes	partly	yes (optimal)
Numerical robustness	good (single turn test)	good (single turn test)	good	fragile near-collinear	good
Collinear handling	needs tie-break by distance	clean, x-sorted	needs care	tricky	inherits Graham
Best for	classic, teaching, dense sets	production 2D default	tiny hulls (h ≪ n)	average-case speed	theory-optimal output

In practice many production geometry libraries ship Andrew's monotone chain rather than the original Graham scan. It computes the same hull in the same O(n log n) but sorts by coordinate instead of by angle, which sidesteps the messy atan2 / anchor-relative angle bookkeeping and the collinear tie-breaking, while building the upper and lower hulls in two clean linear passes. Think of monotone chain as the engineering refinement of Graham's idea.

What the numbers actually say

• The sort dominates. For n = 1,000,000 points, the angular sort is roughly 2·10⁷ comparisons (n log₂ n ≈ 20 million), while the scan does at most 1,000,000 pushes plus 1,000,000 pops (≤ 2n stack operations total). The geometry is ~10× cheaper than the sort that feeds it.
• The scan is strictly linear. Each point is pushed once and popped at most once, so total stack operations ≤ 2n. That bound holds even in the worst case where the points zig-zag and force a pop on nearly every step — amortized O(1) per point.
• Hull size is usually tiny. For n points drawn uniformly from a square, the expected number of hull vertices is only O(log n) — by the Rényi–Sulanke result it is about (8/3)·ln n, roughly 37 for a million points. For points in a disk it is O(n^1/3). This is exactly why Jarvis march and Chan's algorithm exist: when h is this small, O(n log h) beats O(n log n).
• Memory is one extra array. The hull stack never exceeds n entries, and most implementations sort in place, so total extra space is O(n) and in practice a single index array of 4n or 8n bytes.

JavaScript implementation

// Points are [x, y]. Returns hull vertices in counterclockwise order.
function grahamScan(points) {
  const n = points.length;
  if (n < 3) return points.slice();          // a hull needs ≥ 3 points

  // 1) Anchor: lowest y, tie-break lowest x.
  let p0 = points[0];
  for (const p of points) {
    if (p[1] < p0[1] || (p[1] === p0[1] && p[0] < p0[0])) p0 = p;
  }

  // twice the signed area of triangle (A, B, C)
  const cross = (A, B, C) =>
    (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0]);

  // 2) Sort the rest by polar angle around p0. Ties (collinear with p0)
  //    are broken by distance so the farther point wins the edge.
  const rest = points.filter(p => p !== p0).sort((a, b) => {
    const c = cross(p0, a, b);
    if (c !== 0) return c > 0 ? -1 : 1;        // CCW first
    const da = (a[0]-p0[0])**2 + (a[1]-p0[1])**2;
    const db = (b[0]-p0[0])**2 + (b[1]-p0[1])**2;
    return da - db;
  });

  // 3) Scan: keep only left turns.
  const stack = [p0];
  for (const p of rest) {
    while (stack.length > 1 &&
           cross(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) {
      stack.pop();                            // pop right turns and collinears
    }
    stack.push(p);
  }
  return stack;
}

Two things to watch. First, the <= 0 in the pop condition discards collinear points, giving the minimal vertex set; switch it to < 0 if you must retain every boundary point. Second, the comparator returns the cross-product sign directly instead of computing atan2 — that keeps the sort exact on integer coordinates, where atan2 would introduce floating-point ties.

Python implementation

from functools import cmp_to_key

def cross(a, b, c):
    """Twice the signed area of triangle (a, b, c)."""
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def graham_scan(points):
    pts = list(points)
    if len(pts) < 3:
        return pts

    # 1) Anchor: lowest y, then lowest x.
    p0 = min(pts, key=lambda p: (p[1], p[0]))

    # 2) Sort by polar angle around p0; break collinear ties by distance.
    def by_angle(a, b):
        c = cross(p0, a, b)
        if c != 0:
            return -1 if c > 0 else 1          # counterclockwise first
        da = (a[0]-p0[0])**2 + (a[1]-p0[1])**2
        db = (b[0]-p0[0])**2 + (b[1]-p0[1])**2
        return -1 if da < db else (1 if da > db else 0)

    rest = sorted((p for p in pts if p != p0), key=cmp_to_key(by_angle))

    # 3) Scan: pop right turns and collinear points.
    stack = [p0]
    for p in rest:
        while len(stack) > 1 and cross(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)
    return stack


# Andrew's monotone chain — same hull, no angles, the production-grade variant.
def monotone_chain(points):
    pts = sorted(set(map(tuple, points)))
    if len(pts) < 3:
        return pts
    def half(seq):
        h = []
        for p in seq:
            while len(h) >= 2 and cross(h[-2], h[-1], p) <= 0:
                h.pop()
            h.append(p)
        return h
    lower = half(pts)
    upper = half(reversed(pts))
    return lower[:-1] + upper[:-1]              # drop shared endpoints

The monotone-chain function is the variant most 2D production code actually uses: sort by (x, y), build the lower hull left-to-right and the upper hull right-to-left, each with the identical pop-on-non-left-turn loop. It needs no anchor, no atan2, and handles collinear and duplicate points more gracefully — at the cost of being slightly less obvious about why it works.

Variants worth knowing

Andrew's monotone chain (1979). Replaces the angular sort with a coordinate sort and builds upper and lower hulls separately. Same complexity, simpler and more robust; the default choice for 2D.

Jarvis march / gift wrapping (1973). Starts at a hull point and repeatedly picks the most-clockwise next point, wrapping the hull one edge at a time. O(nh) — beautiful when the hull is tiny, quadratic when it is not.

QuickHull. A divide-and-conquer cousin of quicksort: find the extreme points, recurse on the sets outside each dividing line. O(n log n) on average, O(n²) in the worst case, and the standard approach for 3D and higher (it generalizes; Graham scan does not).

Chan's algorithm (1996). Combines Graham scan on small groups with a Jarvis-style wrap across groups to hit the output-optimal O(n log h). It matches the earlier Kirkpatrick–Seidel "ultimate" algorithm (1986), which first reached O(n log h), but is far simpler to implement — and like it, beats O(n log n) when h is small.

Akl–Toussaint heuristic. A preprocessing filter, not a hull algorithm: form a quadrilateral from the extreme points in x and y and discard everything inside it before running any hull algorithm. On uniformly random data it throws away most points for nearly free.

Common bugs and edge cases

• Floating-point sign flips. A near-collinear triple can make the cross product round to the wrong sign, producing a concave or self-crossing "hull". Use integer coordinates where possible, or an exact-arithmetic kernel; never compare the cross product to a naive 0.0 for borderline data.
• Mishandling collinear points. Decide up front whether you want the minimal vertex set (pop on cross ≤ 0) or every boundary point (pop on cross < 0 and break sort ties by distance). Mixing the two leaves stray points mid-edge or out of order.
• Degenerate inputs. Fewer than three points, all points identical, or all points collinear have no 2D hull. Guard these explicitly — most off-by-one crashes live here.
• Duplicate points. Two identical points give a zero cross product against everything and confuse the comparator. Deduplicate before sorting (monotone chain does this with set()).
• Wrong anchor tie-break. If several points share the lowest y, you must pick the lowest x among them. Choosing any other one can place the anchor in the interior of the bottom edge and corrupt the angular order.
• Forgetting the stack-size guard. The pop loop must check stack.length > 1 (or >= 2) before reading the top two entries, or it underflows on the very first turn.