Andrew's Monotone Chain, in depth: two sorted chains, streaming hulls, the convex hull trick and ROC hulls

Two chains, one turn test

Sort the points by x, breaking ties by y, and remove duplicates. The leftmost point and the rightmost point are always on the hull, and they split it into two pieces. The lower chain runs from left to right along the bottom; the upper chain runs from left to right along the top. Within each chain, x never decreases, which is what monotone means here.

To build the lower chain, walk the sorted points and keep a stack. Before pushing a point, look at the last two stack entries and the new point. If they do not make a strict left (counter-clockwise) turn, the middle entry cannot be on the lower boundary, so pop it and check again. The upper chain is identical with the turn reversed. The turn test is the sign of a 2-by-2 determinant, the cross product of the two edge vectors:

def turn(o, a, b):
    '''> 0 left turn, < 0 right turn, 0 collinear (exact for integers).'''
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def chain(sorted_pts, keep):
    '''One monotone sweep; keep(t) says whether a turn value t is allowed.'''
    out = []
    for p in sorted_pts:
        while len(out) >= 2 and not keep(turn(out[-2], out[-1], p)):
            out.pop()
        out.append(p)
    return out

def lower_chain(pts):
    return chain(pts, lambda t: t > 0)       # strict left turns only

def upper_chain(pts):
    return chain(pts, lambda t: t < 0)       # strict right turns, left to right

def monotone_hull(points):
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    lo, up = lower_chain(pts), upper_chain(pts)
    return lo[:-1] + up[::-1][:-1]           # counter-clockwise, no repeated ends

The sort costs O(n log n). Each sweep is O(n), because every point is pushed once and popped at most once. Using strict comparisons drops collinear points on edges; to keep them, change t > 0 to t >= 0 and the upper test to match, and handle the case where every point lies on one line. That case would otherwise appear twice in the output.

Worked example: ten points

Take ten integer points: (0,0), (1,3), (2,1), (2,2), (3,2), (3,4), (4,0), (4,1), (5,3) and (6,1). Sorted by (x, y) they come in that order. Here is the lower sweep, with each turn value in brackets:

1. Push (0,0) and (1,3). Then (2,1) gives turn((0,0),(1,3),(2,1)) = -5, a right turn, so pop (1,3) and push (2,1).
2. (2,2) gives +2, so push it. (3,2) gives turn((2,1),(2,2),(3,2)) = -1: pop (2,2). Then turn((0,0),(2,1),(3,2)) = +1, so push (3,2).
3. (3,4) gives +2, so push it. Then (4,0) pops three times: (3,4) at -2, (3,2) at -3 and (2,1) at -4. The stack is now (0,0), (4,0).
4. (4,1) gives +4, so push it. (5,3) pops (4,1) at -1 and is pushed (+12). (6,1) pops (5,3) at -5 and is pushed (+4).

The lower chain is (0,0), (4,0), (6,1): ten pushes and seven pops, as the amortised bound promised. The upper sweep gives (0,0), (1,3), (3,4), (5,3), (6,1). Joining them gives the counter-clockwise hull (0,0), (4,0), (6,1), (5,3), (3,4), (1,3). It is a useful regression test, because it exercises a triple pop and a vertical pair at x = 2.

Why sorted chains answer queries fast

Because each chain is sorted by x, many questions about the hull reduce to binary search on a chain in O(log h), where h is the number of hull vertices. Two are worth knowing by heart.

Vertical position. To check whether a point q lies inside the hull, binary-search the lower chain for the edge whose x-range contains q's x, and check that q is on or above it. Do the same on the upper chain, checking that q is on or below. Two searches and two turn tests answer the question without touching the rest of the polygon.

Extreme point in a direction. To find the hull vertex that maximises a dot product a·x + b·y with b > 0, note that it lies on the upper chain. Along that chain, the values rise and then fall, because the edge slopes decrease. So you binary-search for the first edge along which the value stops increasing. With b < 0, use the lower chain. This one primitive powers the next two sections.

An online hull for sorted streams

The sweep inspects only the top of the stack and the newest point. If points arrive already sorted by x, as time-series samples, price ticks, or events from a sorted log do, you can maintain both chains incrementally in amortised O(1) per point and read the current hull at any moment:

class SortedStreamHull:
    '''Hull of a stream whose points arrive in increasing (x, y) order.'''
    def __init__(self):
        self.lo, self.up, self.last = [], [], None

    def push(self, p):
        if self.last is not None and p <= self.last:
            if p == self.last:
                return                       # duplicate: ignore
            raise ValueError("stream is not sorted")
        self.last = p
        for ch, keep in ((self.lo, lambda t: t > 0), (self.up, lambda t: t < 0)):
            while len(ch) >= 2 and not keep(turn(ch[-2], ch[-1], p)):
                ch.pop()
            ch.append(p)

    def hull(self):
        if len(self.lo) <= 2 and self.lo == self.up:
            return list(self.lo)             # zero, one or two points, or all collinear
        return self.lo[:-1] + self.up[::-1][:-1]

The check on ordering is not optional. A single out-of-order point silently produces a non-convex result, and that kind of bug shows up far from its cause. If order cannot be guaranteed, use the general streaming approach, which tests each new point against the current hull and inserts it into a balanced structure in O(log h). The sorted case also parallelises. Split the x-range into shards, build chains per shard, and merge neighbours by concatenating and re-sweeping. Merging two adjacent shards costs time linear in their hull sizes, not their point counts.

The convex hull trick is a lower chain

A large family of dynamic programs has the form dp[i] = min over j of (m_j · x_i + b_j): each earlier state j contributes a line, and state i asks which line is lowest at x_i. Evaluating every line costs O(n) per state and O(n²) in total. The convex hull trick cuts this to O(log n) per query, and it is Andrew's lower chain in disguise.

Treat each line y = m x + b as the point (m, b). Its value at x is the dot product of (m, b) with (x, 1). Minimising a dot product with a vector whose second component is positive selects a vertex of the lower hull of the points. Lines whose points are not on the lower chain are never the minimum for any x. So: sort lines by slope, keep the smallest intercept per slope, run the lower sweep, and answer queries by binary search.

def min_envelope(lines):
    best = {}
    for m, b in lines:                       # equal slopes: only the lowest line matters
        if m not in best or b < best[m]:
            best[m] = b
    return lower_chain(sorted(best.items()))

def query_min(env, x):
    lo, hi = 0, len(env) - 1
    while lo < hi:                           # values along env are unimodal in index
        mid = (lo + hi) // 2
        (m1, b1), (m2, b2) = env[mid], env[mid + 1]
        if m2 * x + b2 < m1 * x + b1:
            lo = mid + 1
        else:
            hi = mid
    m, b = env[lo]
    return m * x + b

Worked example: lines with (m, b) = (-2, 8), (-1, 3), (0, 0), (1, -1), (2, 0) and (0, 2). The last is dominated by (0, 0) and is discarded. The other five form a lower chain, because their consecutive slopes -5, -3, -1 and 1 increase. Querying x = 0 returns -1, from line x - 1. Querying x = 4 returns -1 from -x + 3, and x = -3 returns -6 from 2x. For maximum queries, use the upper chain. When both slopes and queries arrive in sorted order, as in many scheduling and partition problems, replace the binary search with a pointer that only moves forward. Each query is then amortised O(1). If lines arrive with unsorted slopes, a Li Chao tree is simpler than a dynamic hull.

The ROC convex hull is an upper chain

In machine learning the same upper chain decides which classifiers are worth deploying. Plot each candidate classifier, or each threshold of one scoring model, as a point (false positive rate, true positive rate). Add (0, 0) for always-negative and (1, 1) for always-positive. Provost and Fawcett showed that only points on the upper convex hull, the ROC convex hull, can be optimal for some class balance and cost ratio. Any point in between two hull vertices can be achieved by randomly choosing between them, and anything below the hull is beaten everywhere.

Given costs, the best operating point maximises TPR minus s · FPR, where s is the cost of a false positive times the negative prior, divided by the cost of a false negative times the positive prior. That is an extreme-point query on the upper chain:

def roc_hull(points):
    return upper_chain(sorted(set(points) | {(0, 0), (1, 1)}))

def best_operating_point(hull, s):
    lo, hi = 0, len(hull) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        f1 = hull[mid][1] - s * hull[mid][0]
        f2 = hull[mid + 1][1] - s * hull[mid + 1][0]
        lo, hi = (mid + 1, hi) if f2 > f1 else (lo, mid)
    return hull[lo]

With six candidates at (0.1, 0.4), (0.2, 0.55), (0.3, 0.75), (0.4, 0.6), (0.5, 0.8) and (0.6, 0.95), the hull keeps (0, 0), (0.1, 0.4), (0.3, 0.75), (0.6, 0.95) and (1, 1). Three candidates are never worth deploying. At s = 1 the best choice is (0.3, 0.75). At s = 4, the slope of the first hull segment, (0, 0) and (0.1, 0.4) tie, and for any s above 4 the model should not fire at all. Each vertex is optimal over an interval of s. Use exact fractions or integer counts, not rounded rates, so that ties do not flip with floating-point noise. The hull is also closely tied to calibration: Fawcett and Niculescu-Mizil showed that isotonic regression by pool-adjacent-violators groups scores exactly along the hull's segments, so each segment's slope maps to one calibrated probability.

Failure modes

Most bugs in chain-based code come from a short list, and each has a cheap test.

• Unstable sort key. Sorting by x alone leaves equal-x points in arbitrary order, so the chains depend on input order. Always sort by (x, y).
• Overflow in the turn test. With 64-bit integers, coordinates must stay within about 2 to the 30th in magnitude. For larger values use 128-bit arithmetic, Python integers or exact fractions. In the convex hull trick, the products m · x overflow first, so bound those too.
• Mixed collinear policy. One chain keeps collinear points and the other drops them, giving a polygon with a spur. Choose one policy for both chains and test a square with edge midpoints.
• Floating-point ties. Rates and scores computed in floating point produce turn values near zero with random signs. Snap to integers or use exact arithmetic, and see the robustness notes in the deep-dive article.
• Binary search over the whole polygon. Dot-product values are unimodal along one chain, not around the closed polygon. Search the correct chain, or the search can converge on the wrong vertex.
• Unsorted streams. The online class assumes order. Reject out-of-order points rather than silently producing garbage.

Trade-offs

Compared with Graham scan, the monotone chain avoids angle sorting and pivot selection, so it is easier to get exactly right in integer arithmetic. It also produces the two chains directly, and Graham scan does not. Output-sensitive algorithms such as Chan's run in O(n log h). They win only when h is tiny and n is huge, and for most inputs the sort dominates anyway. In dynamic programming the monotone-chain form of the convex hull trick needs sorted slopes. Li Chao trees accept any order at O(log C) per operation over a coordinate range C, at the cost of more memory. For nearest-neighbour or diameter questions you need different tools, such as rotating calipers on the finished hull, or the divide-and-conquer approach in closest pair of points.

What to do next

Use this checklist to put the chain structure to work.

1. Implement turn, the two chain sweeps and monotone_hull with integer coordinates.
2. Add the ten-point example as a regression test, and assert seven pops on the lower sweep.
3. Fuzz against a brute-force hull on small random integer sets with duplicates and collinear points.
4. Decide and document the collinear policy and the output orientation.
5. Bound coordinate magnitudes, or switch to wider integers or fractions where the bound fails.
6. Rewrite one O(n²) min-over-lines DP using min_envelope and query_min.
7. Build the ROC convex hull for your current model's thresholds and pick operating points from real costs.
8. Review the orientation predicate and related primitives in 2D computational geometry.