Convex Hull Algorithm: Graham Scan and Monotone Chain, Every Detail

Stretch a rubber band around a set of nails hammered into a board and let go. It snaps to the smallest possible convex polygon that contains all the nails. That polygon is the convex hull. Two implementations dominate practice: Graham Scan (Ronald Graham, 1972) and Andrew's Monotone Chain (A.M. Andrew, 1979). Both run in O(n log n). That bound is tight, and we will prove why.

What "Convex" Actually Means

A polygon is convex if the line segment between any two points inside it stays entirely inside it. The convex hull of a point set is the smallest convex polygon that contains every point. It is also the intersection of all half-planes containing every point, and the shape you trace when you follow the outermost boundary without ever bending inward.

Three equivalent views: rubber band, half-plane intersection, outermost boundary trace. They all describe the same shape. The implementations below use the third.

The Only Math You Need Is One Formula

Both algorithms rely on exactly one geometric primitive: the 2D cross product. Given three points O, A, B, compute:

cross(O, A, B) = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)

This is the z-component of the 3D cross product of vectors OA and OB. Its sign tells you the turn direction when walking O to A to B:

• Positive: left turn (counter-clockwise). B is to the left of the directed line O to A.
• Zero: collinear. O, A, B lie on a line.
• Negative: right turn (clockwise). B is to the right of the directed line O to A.

Geometrically, the absolute value is twice the signed area of triangle OAB.

You never need atan2. You never need floating-point trigonometry. The cross product is integer arithmetic when your input coordinates are integers, which makes it exact.

Positive means counter-clockwise. Negative means clockwise. Zero means you have a collinearity problem.

The Part That Bites Everyone Once

With coordinates up to 10^9, each factor in the cross product can reach 2 x 10^9. The product of two such factors reaches 4 x 10^18, which overflows a 32-bit integer (max ~2.1 x 10^9). Always use 64-bit integers for the cross product. Python has arbitrary precision and is immune. JavaScript's float64 is safe up to 2^53, so coordinates larger than ~3 x 10^7 can silently produce wrong results there.

One missing L suffix in C, one wrong type annotation in Java, one silent wrong answer on the judge. Use 64-bit.

Graham Scan: Sort by Angle, Scan Once

Ronald Graham published this in 1972 in Information Processing Letters (volume 1, pages 132-133).

Step 1: Find the pivot. Pick p0, the point with the lowest y-coordinate. Break ties by lowest x. This point is guaranteed to be on the hull.

Step 2: Sort by polar angle. Sort all remaining points by their counter-clockwise angle from p0. Do not use atan2. Use the cross product comparator instead: a comes before b if cross(p0, a, b) > 0 (a is clockwise from b, so a has a smaller angle). When two points are collinear with p0 (cross == 0), sort by distance from p0 ascending, with one exception described below.

Step 3: Handle the collinear tail. After sorting, find the last run of points that are collinear with each other and with p0 (all at the same maximum polar angle). Reverse their order within that run. This ensures the farthest point in that direction is processed last, which is needed for correctness when the hull has collinear final vertices.

Step 4: Stack scan.

push p0
push sorted[0]
for each remaining point p in sorted order:
    while stack.size >= 2 and cross(stack[-2], stack[-1], p) <= 0:
        pop stack
    push p

The stack invariant: every three consecutive points on the stack form a strict counter-clockwise turn. When a new point creates a non-CCW turn (zero or clockwise), the middle point is definitively not on the hull and gets popped.

After the loop, the stack contains the hull vertices in CCW order starting from p0.

Monotone Chain: Two Passes, No Angles

A.M. Andrew published this in 1979, also in Information Processing Letters (volume 9, pages 216-219). It is the algorithm most competitive programmers reach for by default.

Step 1: Sort lexicographically. Sort all points by x-coordinate, breaking ties by y. Remove duplicates.

Step 2: Build the lower hull. Scan left to right. For each point p:

while hull.size >= 2 and cross(hull[-2], hull[-1], p) <= 0:
    pop hull
push p

The lower hull, after this pass, is the bottom boundary of the convex hull from leftmost to rightmost point.

Step 3: Build the upper hull. Scan right to left over the same sorted array, applying the identical stack logic. This produces the top boundary from rightmost back to leftmost.

Step 4: Combine. The final hull is lower[:-1] + upper[:-1]. Removing the last element of each avoids duplicating the two extreme endpoints where the lower and upper hulls meet.

Two passes over the sorted array. Same stack logic each time. The leftmost and rightmost points are shared, so trim one duplicate off each before concatenating.

Why Monotone Chain Beats Graham Scan

Graham Scan needs a careful polar-angle comparator and the collinear-tail reversal. Monotone Chain needs only a lexicographic sort and the stack logic, repeated twice. No trigonometry. No special-case tail reversal. Both algorithms are O(n log n), but Monotone Chain has a smaller constant and fewer correctness pitfalls. The implementations below all use Monotone Chain.

How Fast Is Each Operation?

Why O(n log n) Is the Floor (and It Can Sort)

This is you, after discovering that computing a convex hull IS sorting in disguise. Congratulations. You've been sorting all along.

O(n log n) lower bound: Map each real number x_i to the point (x_i, x_i^2). These n points lie on a parabola, which is strictly convex. So every point is on the convex hull. The hull read left-to-right gives the x_i in sorted order. Since comparison-based sorting requires O(n log n) comparisons (there are n! orderings and lg(n!) ≈ n lg n), computing the convex hull of n points must also take O(n log n) comparisons. This is the classical reduction from Preparata and Shamos. For a refresher on why sorting cannot beat this floor, see Merge Sort vs Quick Sort.

Why the scan is O(n): Each of the n points is pushed onto the stack exactly once. Each point can be popped at most once. Total push and pop operations combined: at most 2n. Therefore the scan loop, despite having a nested while, is O(n) amortized. The O(n log n) total complexity comes entirely from the sort.

Strict Hull vs Boundary-Inclusive Hull

The default (strict hull) uses <= 0 in the pop condition. Points collinear with their neighbors are ejected, giving the minimal vertex set.

For problems that want all points on the hull boundary, use < 0 instead. Only clockwise turns cause a pop; collinear points stay. LeetCode 587 "Erect the Fence" is exactly this variant: you need every tree on the fence perimeter, including the ones standing on a straight edge.

Do not mix the conditions between the lower and upper passes. Whatever you choose, use it consistently in both.

Why a Popped Point Cannot Be on the Hull

When you pop point B because the turn A to B to C is not a strict left turn, you are observing that B is on or to the right of the directed line from A to C. Every future point to be processed has x-coordinate at least as large as C (in Monotone Chain) or polar angle at least as large as C (in Graham Scan). Therefore, B is "inside" the region bounded by A, C, and all future points.

More formally, B lies in the half-plane defined by line AC that does not contain the exterior. Any convex polygon with vertices from the point set cannot use B as a vertex without A or C also being present, because B is dominated by A and C. So B is safely removed.

The algorithm is a bouncer. Points that break the CCW invariant get removed immediately. They cannot come back. That's the whole proof.

One Structure, Every Language

The function below implements Andrew's Monotone Chain. It returns the hull vertices in counter-clockwise order, starting from the leftmost-bottommost point. The <= 0 condition excludes interior collinear points (strict hull). To include boundary collinear points, change every <= 0 to < 0.

def convex_hull(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
    pts = sorted(set(points))
    if len(pts) <= 1:
        return pts

    def cross(O, A, B):
        return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

    lower: list[tuple[int, int]] = []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    upper: list[tuple[int, int]] = []
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    return lower[:-1] + upper[:-1]

What Problems Actually Need This

Minimum perimeter fence. You have a set of points and want the shortest closed curve enclosing all of them. The convex hull boundary is that curve. Its perimeter is the sum of edge lengths around the hull.

Farthest pair of points. The maximum distance between any two points in a set is always achieved by two points on the convex hull. After building the hull in O(n log n), the rotating calipers technique (Shamos, 1978) finds the farthest pair in O(n). Maintain two antipodal points where parallel tangent lines touch the hull, then rotate both tangent lines together until you have checked every antipodal pair.

Point in convex polygon. Given a convex hull with k vertices and many query points, determine for each query whether it is inside. Build the hull once in O(k log k). Answer each query in O(log k) using binary search: pick a vertex, divide the hull into triangles radiating from it, binary search for the sector the query falls in, then run one cross product test.

Smallest enclosing rectangle. The minimum-area rectangle enclosing a point set has one edge flush with an edge of the convex hull. Rotating calipers finds it in O(n) after building the hull.

Collision detection and physics. Game engines and physics simulators represent convex rigid bodies as convex hulls of their control points. Intersection tests between convex bodies (GJK algorithm) work exclusively on the hull vertices.

Robot motion planning. Configuration-space obstacles are often described as Minkowski sums of convex polygons, which requires computing convex hulls of the resulting point sets.

Five Signals You Need a Convex Hull

1. Points in 2D, and you need the "outermost" ones. Any problem asking for a minimum enclosing boundary, minimum perimeter, or "which points form the outer ring" is directly a hull problem.

2. Maximum distance between any two points. The farthest pair always lies on the hull. If a brute-force O(n^2) pass is too slow, build the hull first.

3. "Fence" or "enclosure" language. Problems explicitly asking you to place a fence, rope, or boundary around a set of objects are usually asking for the convex hull perimeter or the hull vertices.

4. Polar angle sort around a fixed point. Problems like "count points visible from a lighthouse" or "order planets by observation angle" use the same polar angle sort that Graham Scan uses. You often do not need the full hull, just the sort.

5. Half-plane intersection queries. Any problem that tests whether a query point is inside a region defined by a set of constraints, where the region happens to be convex, can use binary search on the hull.

Worked Example 1: LeetCode 587, Erect the Fence

Problem: given tree positions as 2D integer points, return all points that lie on or inside the minimum perimeter fence enclosing all trees.

Why the hull: the fence IS the convex hull. The problem asks specifically for which trees touch the fence, meaning trees that are hull vertices AND all collinear points on hull edges.

Which variant: because we need boundary collinear points, use < 0 in the pop condition. The <= 0 version ejects collinear trees that stand on a straight fence section.

def outer_trees(trees):
    trees = [tuple(t) for t in trees]
    pts = sorted(set(trees))
    n = len(pts)
    if n <= 2:
        return list(set(trees))

    def cross(O, A, B):
        return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])

    lower, upper = [], []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
            lower.pop()
        lower.append(p)
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
            upper.pop()
        upper.append(p)

    return list(set(lower[:-1] + upper[:-1]))

The only change from the strict hull: < 0 instead of <= 0. Everything else is identical.

Worked Example 2: Maximum Distance Between Any Two Cities

Problem: given n cities as 2D coordinates, find the maximum Euclidean distance between any two of them.

Naive brute force is O(n^2). The farthest pair always consists of two hull vertices. Once you have the hull, rotating calipers gives O(k) where k is the hull size.

import math

def max_distance(points):
    hull = convex_hull(points)  # CCW order
    k = len(hull)
    if k == 1:
        return 0.0
    if k == 2:
        dx, dy = hull[1][0]-hull[0][0], hull[1][1]-hull[0][1]
        return math.sqrt(dx*dx + dy*dy)

    # Rotating calipers: O(k)
    j = 1
    best = 0.0
    for i in range(k):
        while True:
            nx = (j + 1) % k
            dx1 = hull[nx][0] - hull[i][0]
            dy1 = hull[nx][1] - hull[i][1]
            dx2 = hull[j][0] - hull[i][0]
            dy2 = hull[j][1] - hull[i][1]
            if dx1*dx1 + dy1*dy1 > dx2*dx2 + dy2*dy2:
                j = nx
            else:
                break
        dx = hull[j][0] - hull[i][0]
        dy = hull[j][1] - hull[i][1]
        best = max(best, math.sqrt(dx*dx + dy*dy))
    return best

Total: O(n log n) to build the hull, O(k) for the calipers sweep. For n = 10^5, this is millions of times faster than brute force.

The "Convex Hull Trick" Is a Different Algorithm with a Confusing Name

The "Convex Hull Trick" in dynamic programming has nothing to do with computing a convex hull. It is a technique for optimizing DP recurrences involving a minimum (or maximum) over a set of linear functions at a query point. The name comes from the fact that the lower envelope of a set of lines looks like a convex polygon from below. Not because it uses any convex hull algorithm.

If your DP problem has a recurrence of the form dp[i] = min over j of (m[j] * x[i] + b[j]), that is the DP trick (the when to use dynamic programming guide covers how to tell). If your problem has 2D points and asks about the outermost boundary, that is the geometric convex hull. They share a name and nothing else.

Quick Reference

• The convex hull is the smallest convex polygon containing a point set. Rubber band around nails is accurate.
• The cross product (A-O) x (B-O) tells you the turn direction at O, A, B in O(1). Positive is CCW, zero is collinear, negative is CW.
• Graham Scan (1972) sorts by polar angle and scans with a stack. Requires careful handling of the collinear tail.
• Andrew's Monotone Chain (1979) sorts lexicographically and makes two passes (lower hull, upper hull). Simpler and preferred in practice.
• The scan is O(n) amortized: each of n points is pushed and popped at most once.
• O(n log n) is a tight lower bound: a convex hull algorithm can sort, so sorting's lower bound applies.
• Use <= 0 for the strict hull (no collinear boundary points). Use < 0 to include boundary collinear points (LeetCode 587).
• With coordinates up to 10^9, use 64-bit integers. Python is immune. JavaScript float64 loses precision above ~3 x 10^7 in the cross product.
• The farthest pair of points always lives on the convex hull. Rotating calipers finds it in O(n) after building the hull.
• The "Convex Hull Trick" in DP is a completely different algorithm with a misleading name.

If you want to drill problems like LeetCode 587 under realistic interview conditions, SpaceComplexity gives you a voice-based mock interviewer that asks follow-up questions, checks your complexity analysis, and scores your response on the same rubric a real interviewer would use.

Further Reading

• Convex hull algorithms (Wikipedia): overview of all major algorithms with complexity table
• Convex hull construction (cp-algorithms): detailed pseudocode, collinear variants, and competitive programming notes
• Convex Hull (GeeksforGeeks): step-by-step tutorial with diagrams for both Graham Scan and Monotone Chain
• Convex Hull (Sedgewick, algs4): Princeton's treatment with Java code and interactive visualizer
• Point inside convex polygon (cp-algorithms): O(log n) query after hull construction