Andrew's Monotone Chain

A convex hull algorithm that sorts points by coordinate and builds the lower and upper hulls in one linear pass each.

Coordinate sort, not angle sort

Andrew's monotone chain computes the convex hull by sorting all points by x (then y), then constructing the lower hull left to right and the upper hull right to left. Each pass keeps only left turns, using the same cross-product turn test as Graham scan but avoiding polar-angle sorting and its floating-point pitfalls.

Two chains

Kronos motion — classical

Sweeping left to right builds the lower boundary; sweeping right to left builds the upper boundary. Concatenating them (dropping the repeated endpoints) yields the full hull in counterclockwise order. Because the points are sorted once, each chain is a single linear pass, and the total cost is dominated by the O(n log n) sort.

Full implementation

python

def convex_hull(pts):
    pts = sorted(set(pts))
    if len(pts) <= 2:
        return pts
    def half(points):
        h = []
        for p in points:
            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]

Why it is preferred

No trigonometry; integer coordinates give exact orientation tests.
Simple to reason about and to make robust against collinear and duplicate points.
Same O(n log n) complexity as Graham scan with smaller constants in practice.

Extensions

The same left/right sweeping idea generalizes to the line-sweep paradigm for intersection and closest-pair problems. In 3D, convex hulls require incremental or divide-and-conquer methods rather than a simple chain.