vault

Convex Hull - Graham Scan

21 min read

Convex Hull - Graham Scan

Given a finite set P = {p_1, p_2, …, p_n} of points in the Euclidean plane, the convex hull of P — written conv(P) — is the smallest convex polygon that contains every point of P. Graham’s scan (Graham 1972) computes the convex hull in O(n log n) time using only the cross-product orientation test (see Vector Cross Product) and a single sweep with a stack. The algorithm is intuitive — find the bottom-most point, sort the rest by polar angle around it, then walk through the sorted list maintaining a stack and popping any vertex that would force a clockwise (or non-left) turn. Graham’s paper was the first sub-O(n²) convex-hull algorithm published, predating Andrew’s monotone chain by seven years; the latter (Convex Hull - Andrew’s Monotone Chain) is generally considered easier to implement because it replaces polar-angle sorting with a plain lexicographic sort. We cover both because they’re often asked side-by-side and they reveal complementary insights about the structure of convex hulls.

1. Intuition — Rubber Band, Then Walk Around the Sky

A child-friendly analogy that makes the convex hull tangible: imagine the points are nails sticking out of a wooden board. Stretch a rubber band so it encloses all the nails, then let it snap inward. It comes to rest touching only the outermost nails, in a closed convex loop. That loop is the convex hull. Every other nail (the “interior” ones) is inside the rubber band, never touching it.

Graham’s scan computes this loop algorithmically in three phases:

  1. Anchor. Pick a point that is provably on the hull — the lowest point (with the smallest y), tie-breaking by the smallest x. Call it P_0. Why is P_0 necessarily on the hull? Because any line strictly below P_0 separates P_0 from the rest of the plane, so a horizontal line just below P_0 is a supporting line of the point set — and supporting lines touch only hull vertices.
  2. Sort by polar angle. Sort the remaining n − 1 points by the angle they make with P_0, measured counterclockwise from the horizontal. Imagine yourself standing at P_0 and slowly rotating your gaze from due-east, sweeping counterclockwise across the sky; you encounter the points in this sorted order.
  3. Walk and pop. Push P_0 onto a stack, then iterate through the sorted points. For each new candidate p, look at the top two stack entries top and second_top. If the turn from second_top → top → p is a left turn (counterclockwise), keep top and push p. If it is a right turn or straight, pop top — it cannot be on the hull because the rubber band would skip over it — and re-test against the new top. Repeat the popping until the turn is strictly left, then push p.

When the iteration ends, the stack holds exactly the convex-hull vertices in counterclockwise order. The total amount of work is dominated by the O(n log n) sort; the walk-and-pop pass is O(n) amortised because each point is pushed at most once and popped at most once across the whole run.

The genius of Graham’s 1972 paper is the realisation that polar-angle sorting makes the popping criterion local — you only ever need to look at the top three stack entries, never further back. Without the sort, you would have to test every triple, leading to the quadratic-time gift-wrapping (“Jarvis march”) algorithm.

2. Tiny Worked Example — 7 Points, One Walk

Let

P = [
    A = (0, 0),
    B = (2, -1),    # actually below the y=0 line — but we'll pick anchor first
    C = (3, 1),
    D = (1, 1),
    E = (4, 2),
    F = (5, 0),
    G = (3, 3),
]

Step 1: Anchor. The lowest point (smallest y) is B = (2, −1). Set P_0 = B. Move it to position 0.

Remaining points (relative to B):

A − B = (−2, 1)
C − B = ( 1, 2)
D − B = (−1, 2)
E − B = ( 2, 3)
F − B = ( 3, 1)
G − B = ( 1, 4)

Step 2: Sort by polar angle from P_0 = B. We sort by the angle counterclockwise from the positive x-axis (i.e., from due-east). For comparison-based sorting, we use the cross-product comparator cross(B, p, q) > 0 ⟹ p comes before q (see Vector Cross Product):

  • The polar-angle order, from “rightmost” (smallest angle) to “leftmost” (largest angle):
    • F = (5, 0) — vector (3, 1), angle ≈ 18.4°
    • C = (3, 1) — vector (1, 2), angle ≈ 63.4°
    • E = (4, 2) — vector (2, 3), angle ≈ 56.3°
    • G = (3, 3) — vector (1, 4), angle ≈ 76.0°
    • D = (1, 1) — vector (−1, 2), angle ≈ 116.6°
    • A = (0, 0) — vector (−2, 1), angle ≈ 153.4°

So sorted: F, E, C, G, D, A. (Notice: E came before C because E’s angle ≈ 56° is smaller than C’s ≈ 63°. The cross-product comparator cross(B, E, C) = ? … let’s check: (4−2)·(1−(−1)) − (2−(−1))·(3−2) = 2·2 − 3·1 = 4 − 3 = 1 > 0, so E comes before C. Correct.)

Step 3: Walk and pop.

Initialise stack: [B, F] (the anchor and the first sorted point).

Process E:

  • top = F, second_top = B. Test cross(B, F, E) = (5−2)·(2−(−1)) − (0−(−1))·(4−2) = 3·3 − 1·2 = 9 − 2 = 7 > 0. Left turn. Push E.
  • Stack: [B, F, E].

Process C:

  • top = E, second_top = F. Test cross(F, E, C) = (4−5)·(1−0) − (2−0)·(3−5) = (−1)·1 − 2·(−2) = −1 + 4 = 3 > 0. Left turn? Yes. Push C.
  • Stack: [B, F, E, C].

Hmm — but visually, the segment F → E → C is a left turn at E, and C is “deeper into” the interior than the straight line from F to G. Continue.

Process G:

  • top = C, second_top = E. Test cross(E, C, G) = (3−4)·(3−2) − (1−2)·(3−4) = (−1)·1 − (−1)·(−1) = −1 − 1 = −2 < 0. Right turn — C is interior. Pop C.
  • Stack: [B, F, E].
  • Re-test: top = E, second_top = F. cross(F, E, G) = (4−5)·(3−0) − (2−0)·(3−5) = (−1)·3 − 2·(−2) = −3 + 4 = 1 > 0. Left turn. Push G.
  • Stack: [B, F, E, G].

Hmm, but E lies inside the triangle B F G! Let me double-check: line F−G from (5,0) to (3,3) has equation y = -1.5 x + 7.5. At x = 4, y = 1.5. Point E = (4, 2) has y = 2 > 1.5, so E is above line F−G, meaning E is outside triangle B F G and indeed on the hull. Continue.

Process D:

  • top = G, second_top = E. cross(E, G, D) = (3−4)·(1−2) − (3−2)·(1−4) = (−1)·(−1) − 1·(−3) = 1 + 3 = 4 > 0. Left turn. Push D.
  • Stack: [B, F, E, G, D].

Process A:

  • top = D, second_top = G. cross(G, D, A) = (1−3)·(0−3) − (1−3)·(0−3) = (−2)·(−3) − (−2)·(−3) = 6 − 6 = 0. Collinear!
    • Convention: treat collinear (cross == 0) as “not a strict left turn” and pop. (Many implementations include collinear points as hull vertices; we choose the strict version.)
  • Pop D.
  • Stack: [B, F, E, G].
  • Re-test: top = G, second_top = E. cross(E, G, A) = (3−4)·(0−2) − (3−2)·(0−4) = (−1)·(−2) − 1·(−4) = 2 + 4 = 6 > 0. Left turn. Push A.
  • Stack: [B, F, E, G, A].

Done. Hull (CCW order): B → F → E → G → A → B. That’s (2, −1) → (5, 0) → (4, 2) → (3, 3) → (0, 0) → (2, −1). Five hull vertices out of seven; C and D were rejected as interior. Drawing the hull on graph paper confirms: it is a 5-gon enclosing all 7 input points.

3. Pseudocode — The Classical Three-Phase Form

function graham_scan(P):
    if length(P) < 3:
        return P                                             # hull is the points themselves

    # Phase 1: anchor on lowest-then-leftmost point
    P_0 := point in P with smallest y (tie-break by smallest x)
    swap P_0 with P[0]

    # Phase 2: polar-angle sort relative to P_0
    sort P[1..n-1] by polar-angle comparator:
        compare(p, q):
            c := cross(P_0, p, q)
            if c > 0: return p < q                          # p has smaller angle
            if c < 0: return p > q                          # q has smaller angle
            # collinear with P_0: closer point first (so far points get popped later)
            return distance²(P_0, p) < distance²(P_0, q)

    # Phase 3: walk and pop
    stack := []
    push P_0
    push P[1]
    push P[2]                                                # we process from index 3 below
    for i from 3 to n − 1:
        while length(stack) >= 2 and
              cross(stack[-2], stack[-1], P[i]) <= 0:        # not a strict left turn
            pop stack
        push P[i]

    return stack                                            # hull in CCW order

A few comments:

  • The <= 0 in the popping test rejects both right turns and collinear points. If you want to include collinear points on the hull boundary, change to < 0. There is no universally correct choice — it’s a specification decision.
  • The collinear-with-P_0 tie-break in the polar-angle comparator is subtle. If two points p, q lie on the same ray from P_0, the closer one should come first so that during the walk-and-pop the farther one is the eventual hull vertex (the closer one is popped). If you don’t tie-break this way, the algorithm can produce a hull that has a colinear interior point as a vertex, or it can miss a hull vertex entirely. CLRS §33.3 and Graham’s original paper handle this case explicitly.
  • The initial three pushes P_0, P[1], P[2] jump-start the walk. We don’t test the first triple because by construction P_0 is the lowest point and P[1] is the smallest-polar-angle point — together with any P[2] they form a valid CCW prefix (by the sort).

4. Python Implementation

from functools import cmp_to_key
from typing import Sequence
 
Point = tuple[int, int]
 
 
def cross(o: Point, a: Point, b: Point) -> int:
    """2D cross product (b - o) × (a - o); see [[Vector Cross Product]]."""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
 
 
def dist_sq(a: Point, b: Point) -> int:
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
 
 
def graham_scan(points: Sequence[Point]) -> list[Point]:
    """
    Return the convex hull of `points` in CCW order, starting from the lowest
    point. Collinear interior points are excluded from the hull.
 
    O(n log n) time, O(n) space.
    """
    pts = list(points)
    n = len(pts)
    if n < 3:
        # Hull of 0, 1, or 2 points is just the points themselves (after dedup).
        return list(set(pts))
 
    # Phase 1: pick the anchor — lowest y, tie by lowest x.
    p0_index = min(range(n), key=lambda i: (pts[i][1], pts[i][0]))
    pts[0], pts[p0_index] = pts[p0_index], pts[0]
    p0 = pts[0]
 
    # Phase 2: polar-angle sort relative to p0.
    def compare(p: Point, q: Point) -> int:
        c = cross(p0, p, q)
        if c > 0:
            return -1                       # p has strictly smaller angle ⇒ p first
        if c < 0:
            return +1                       # q has smaller angle ⇒ q first
        # collinear with p0: the closer one comes first
        if dist_sq(p0, p) < dist_sq(p0, q):
            return -1
        return +1
 
    rest = sorted(pts[1:], key=cmp_to_key(compare))
 
    # Pre-clean: drop all but the *farthest* of any colinear-with-p0 tail.
    # This handles the corner case where many points lie on the same final ray.
    # Without it, the walk-and-pop can produce a hull edge that includes
    # interior collinear points as "vertices".
    m = len(rest)
    while m >= 2 and cross(p0, rest[m - 2], rest[m - 1]) == 0:
        m -= 1
    rest = rest[:m]
 
    # Phase 3: walk and pop.
    stack: list[Point] = [p0]
    for p in rest:
        # Pop until the last three form a strict left turn.
        while len(stack) >= 2 and cross(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)
 
    return stack

Some implementation choices worth flagging:

  1. cmp_to_key wraps a comparison-based comparator into a key= function. Polar-angle sorting requires a comparator, not a key — there’s no single number that totally orders points by polar angle without computing atan2 (which we want to avoid for floating-point reasons; see Vector Cross Product §6.5).
  2. Distance² as the tie-break stays integer for integer inputs. Never use sqrt.
  3. The collinear tail pre-clean. This is one of those “every implementation gets it wrong the first time” details. If the last few sorted points all lie on a single ray from p0 (e.g., (2, 2), (4, 4), (6, 6)), only the farthest should appear on the hull — the others are interior to the hull edge p_0 → farthest. Without the pre-clean, the algorithm pushes them all and produces a hull with collinear interior vertices.
  4. Strict <= 0 popping criterion excludes collinear points. If your problem statement says “include all points lying on the hull boundary” (LeetCode 587 says yes), change to < 0 and remove the tail-cleanup pass.

5. Complexity — Sort Dominates, Walk Is Amortised Linear

5.1 The Recurrence

There is no recurrence — Graham’s scan is iterative. Total work:

  1. Finding the anchor: O(n).
  2. Polar-angle sort: O(n log n). This is the dominant term.
  3. Tail cleanup: O(n).
  4. Walk-and-pop: O(n) amortised.
  5. Total: O(n log n), all dominated by the sort.

Space: O(n) for the sorted array and the stack. The stack peaks at n if the input is in “convex position” (every point is on the hull, e.g., uniformly random points on a circle).

5.2 Why the Walk Is Amortised O(n)

Each input point is pushed onto the stack at most once and popped at most once. Therefore the total number of push and pop operations across the whole walk is at most 2n. Each individual cross-product comparison is O(1). So the walk’s total cost is O(n) despite the inner while loop having a worst-case O(n) iteration count for a single iteration of the outer for loop. This is a classic amortised-analysis result; see Amortised Analysis for the general technique.

5.3 Lower Bound — Sorting Reduces to Convex Hull

Convex-hull computation has a lower bound of Ω(n log n) in the algebraic decision tree model: given an O(n log n) convex-hull algorithm, you can sort n numbers x_1, …, x_n by mapping them to points (x_i, x_i²) (which lie on a parabola, so all are on the convex hull), running the algorithm, and reading off the sorted order from the output. So O(n log n) is optimal for comparison-based convex-hull algorithms — Graham’s scan and Andrew’s monotone chain both achieve this optimum. (Preparata & Shamos 1985 presents this reduction in detail.)

Algorithms that beat n log n exist when the output is small: Chan’s 1996 algorithm runs in O(n log h) where h is the number of hull vertices. For h = O(1) this is O(n log log n) or even O(n). Graham’s scan, by contrast, is O(n log n) regardless of h.

6. Variants and Sub-Patterns

6.1 Andrew’s Monotone Chain — The Modern Replacement

Convex Hull - Andrew’s Monotone Chain (Andrew 1979) achieves the same O(n log n) complexity but replaces polar-angle sorting with a plain lexicographic sort (by x, breaking ties by y). It then builds the lower and upper hulls in two left-to-right and right-to-left scans, concatenating them. Why is this generally preferred?

  1. No custom comparator. A lexicographic key is just (x, y) — the standard library handles it. No cmp_to_key, no cross inside the comparator.
  2. No anchor selection. Lower-hull and upper-hull splits are implicit in the scan direction.
  3. Cleaner collinear handling. No tail-cleanup needed; the scan naturally drops colinear interior points.
  4. Same O(n log n), with smaller constant because lex-sort is faster than polar-angle sort.

The only reason to teach Graham’s scan first is pedagogical: it makes the connection between polar-angle traversal and “walking around the boundary” vivid, while monotone chain looks more like a clever trick. CLRS Ch. 33.3 teaches Graham first, Andrew as an exercise. Most modern competitive-programming references (e.g., cp-algorithms.com) lead with Andrew.

6.2 Jarvis March (Gift Wrapping) — The Output-Sensitive Sibling

Jarvis march builds the hull one edge at a time by, at each step, finding the point that makes the most counterclockwise turn from the last edge. It runs in O(n h) where h is the hull size. For small h (e.g., a few points on a hull surrounded by many interior points), this beats O(n log n). For large h (h ≈ n, e.g., points on a circle), it degrades to O(n²). Jarvis march does not require sorting — only n “leftmost-turn” tests per hull edge.

6.3 Chan’s Algorithm — The Theoretically Optimal Combination

Chan 1996 cleverly combines Graham (or Andrew) with Jarvis to achieve O(n log h) — optimal in the output-sensitive complexity. It groups input into ⌈n/m⌉ buckets of size m, runs Graham on each in O(m log m), then performs Jarvis-style wrapping across buckets. The trick is choosing m adaptively (you don’t know h ahead of time): try m = 2, 4, 16, 256, … until the wrap completes. Total cost is dominated by the last (successful) try, which is O(n log h).

6.4 Higher-Dimensional Convex Hull

In 3D the hull is a polyhedron with O(n) vertices, edges, and faces (Euler’s formula gives V − E + F = 2). The standard algorithm is Quickhull (Barber, Dobkin, Huhdanpaa 1996) or randomised incremental construction, both O(n log n) expected. In dimension d ≥ 4, the hull can have Θ(n^⌊d/2⌋) faces (the upper-bound theorem), so the problem fundamentally changes character.

6.5 Online and Dynamic Hulls

If points arrive one at a time and you want the hull after each insertion, an online algorithm using a balanced BST gives O(log² n) per update. Fully-dynamic (insertions and deletions) is much harder; Brodal-Jacob 2002 achieves O(log n) per update with a complicated data structure. None of this is interview material; mentioning it impresses without committing.

7. Diagram — The Walk-and-Pop Stack Behaviour

flowchart LR
    P0((P0 anchor)) --> P1((P1 sorted))
    P1 --> P2((P2))
    P2 --> Pi((P_i candidate))
    Pi -->|cross&lt;=0 right turn or colinear| POP[/pop top of stack/]
    POP -->|recheck| Pi
    Pi -->|cross&gt;0 left turn| PUSH[push P_i, advance i]
    PUSH --> Pi2((next P_i+1))

    style POP stroke:#f55
    style PUSH stroke:#5a5

What this diagram shows. The control flow inside the walk-and-pop phase. After Phase 2 produces the polar-angle-sorted sequence P_0, P_1, P_2, …, the algorithm enters the Pi candidate state. For each new candidate, it inspects the top two stack entries (stack[-2] and stack[-1]) together with the candidate P_i and computes their cross product. Red branch (cross ≤ 0): the turn is a right turn or colinear — the current top of the stack cannot be on the hull, so it’s popped, and the candidate is re-tested against the new top. Green branch (cross > 0): the turn is a strict left turn — the current top is (so far) safe, the candidate is pushed, and we move on to the next sorted point. The amortised-O(n) argument hinges on the fact that each input point can be popped at most once (red branch) and pushed at most once (green branch) — so the total number of branch traversals across the whole scan is O(n), even though a single iteration can pop many times in a row when the input “spirals inward”.

8. Pitfalls

  1. Floating-point polar angles. A naive implementation uses atan2 for the polar-angle comparator: this is slow and numerically unstable. Two points at nearly the same angle can sort inconsistently across runs because of round-off, leading to a hull that violates the convexity invariant. Always use the cross-product comparator. See Vector Cross Product §6.5.

  2. Mishandling the collinear-with-anchor case. When two points p, q lie on the same ray from P_0, the polar-angle test is ambiguous (cross(P_0, p, q) = 0). The tie-break must put the closer one first, and the tail-cleanup pass must drop all but the farthest of any colinear-with-anchor suffix. Get either step wrong and you get a hull with interior points as vertices.

  3. Strict vs non-strict popping. <= 0 (drop colinear) versus < 0 (keep colinear on hull) is a genuine specification choice. LeetCode 587 Erect the Fence requires keeping colinear hull-edge points; most textbook descriptions drop them. Read the problem statement carefully.

  4. Off-by-one in the initial pushes. It’s tempting to start the walk-and-pop with just P_0 on the stack and let the first iteration push P_1. But then the first cross test on (stack[-2], stack[-1], P_2) happens when only one point is on the stack, and you have to add a guard. Cleaner to push P_0 and P_1 upfront and start the loop from i = 2. (Our pseudocode pushes three; this is also fine.)

  5. Using slope dy/dx to compare angles. This breaks for vertical lines (division by zero). Cross product handles vertical inputs uniformly. Same lesson as in Vector Cross Product §6.5 and §8.

  6. Anchor-selection ties. “Lowest y, tie-break by lowest x” is unambiguous if all points are distinct. If duplicates exist ((2, −1) appears twice), the algorithm still works, but you should deduplicate up front to avoid pushing the same point twice.

  7. Returning the hull in CW order accidentally. If you flip the comparator’s sign, you sort by polar angle clockwise and produce a CW hull. If a downstream caller (e.g., a rendering pipeline) expects CCW, you get a self-intersecting polygon and silent bugs. Always document the orientation convention; consider asserting polygon_area_doubled(hull) > 0 (CCW) at the end.

  8. Collinear with anchor that come first in the sort. If three points are exactly to the right of P_0 on the same horizontal line, the closer-first tie-break makes the farthest the last to be processed. With strict <= 0 popping, the closer ones get popped — correct. With non-strict < 0 popping, they stay on the hull. Be deliberate.

  9. Numerical overflow on integer inputs. As discussed in Vector Cross Product §5.1, int32 multiplication of differences of coordinates can overflow for large inputs. Cast to int64. Python is immune.

  10. Confusing O(n log n) with O(n log h). Graham’s scan is not output-sensitive; it always sorts all n points. Chan’s algorithm is the output-sensitive cousin. Don’t claim Graham is O(n log h).

9. Common Interview Problems

ProblemSourceNotes
Erect the FenceLeetCode 587Direct convex-hull problem; tests collinear-on-boundary handling
Outer TreesLeetCode 587 (alt name)Same as Erect the Fence
Convex HullHackerRank, etc.Vanilla convex hull
Largest Triangle AreaLeetCode 812The largest triangle with vertices from a point set has all 3 vertices on the hull (use convex hull to prune)
Maximum Distance Pair (Diameter of Point Set)ClassicThe two farthest points are both on the hull; rotating-calipers algorithm
Minimum Bounding RectangleApplicationToussaint’s rotating calipers, runs on the convex hull
Closest Pair on a LineEasierLinear scan after sort; not a hull problem but related
Plane Sweep for Closest PairApplicationSee Closest Pair of Points
Tangent Lines from External PointGeometric queryBinary search on a convex hull

10. Open Questions

  • In practice, how much faster is Andrew’s monotone chain than Graham’s scan on uniformly-random n = 10^6 points? Both are O(n log n); the constant difference is dominated by sort cost, but the polar-angle comparator’s cross call is more expensive than the lex-key comparator’s tuple compare. Benchmark needed.
  • When does Chan’s O(n log h) algorithm become worth the implementation complexity? For h = Θ(n) (random points), Chan offers no asymptotic advantage. For h = O(log n) (e.g., points clustered tightly), Chan is much faster but the constant is large.
  • How does Graham’s scan generalise to non-convex “outer boundary” computation (e.g., alpha-shapes, concave hulls)? These are not the same problem — a concave hull is not unique without a parameter — but algorithms like CCH (concave-convex hull) borrow the polar-angle-and-pop idea.

11. See Also

Graph View