Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Convex Hull Algorithm

Unlike most of this site's other guides, six of the site's twelve Convex Hull entries don't split by which question they answer — Graham Scan, Jarvis March, Quickhull, Monotone Chain, Divide-and-Conquer Convex Hull, and Chan's Algorithm all compute the exact same polygon. (The other six are set aside up front, as six different questions rather than a seventh through twelfth way to answer this guide's own: Rotating Calipers doesn't build a hull at all, it assumes one already exists and finds its diameter; Convex Hull Trick has no point set anywhere in sight, it finds the maximum of many linear functions at a query point instead; Melkman's Algorithm does build a hull from a point set, but only for a point set that's already the ordered boundary of a simple polygon — the one assumption every entry below has to earn the hard way, by sorting or wrapping or recursing, gets handed over for free, in exchange for not working on a plain unordered bag of points at all; the Akl–Toussaint Heuristic doesn't answer this guide's question either way — it's a preprocessing filter that throws away points before any of the six below even start, never itself deciding what the hull is; Convex Layers answers a bigger version of the question instead of a different one — not just the outer hull, but every nested hull out to the interior, by calling one of the six below over and over on whatever points remain; and Dynamic Convex Hull drops the one assumption every entry below shares without ever saying so out loud — that the full point set is sitting there, known and complete, before the first answer is computed — and asks for the current hull after every single one-at-a-time insertion instead.) The first five, run on this site's own shared 11-point demo set, all land on the identical 8-vertex hull (or the identical 9-vertex hull, with collinear boundary points included — see below), by five genuinely different mechanisms: sort every point by angle and sweep, wrap around the outside one vertex at a time, divide and conquer by recursively finding the farthest point from a baseline, sort every point by plain coordinate and sweep twice, or divide the input in half and merge two independently solved hulls through their shared tangent lines. Chan's Algorithm is a sixth mechanism again, and a different kind of different — it doesn't compete with the other five so much as combine two of them (Graham Scan's sort, Jarvis March's wrap) behind a self-tuning parameter, so it gets its own question below rather than slotting into the mechanism/cost question the other five answer. So this guide splits three questions deep, cheapest to check first.

Is the hull small relative to the input?

Jarvis March is the one whose cost depends on the answer, not just the input size: O(nh), where h is the number of points that actually end up on the hull. Its own page measured this directly rather than just citing the bound — point-comparisons scaled roughly linearly with n when the hull was pinned to a fixed 3-vertex triangle (54, 114, 234, 474, 954 across doubling input sizes), but roughly quadratically when every point sat on the hull instead (a circle, so h = n: 360, 1,520, 6,240, 25,280). If most of the input is expected to be interior — a scattered cloud with only a handful of extreme points — Jarvis March is cheaper than either alternative below and never has to hold onto a point that doesn't end up on the hull, giving it the smallest footprint of the three at O(h) space. If the hull could plausibly include most of the input (points already arranged near-convex, or genuinely unpredictable), that same O(nh) becomes its own worst case, and one of the other two is the safer default.

But what if you don't actually know h in advance?

Jarvis March's question assumes the caller can guess, ahead of time, whether the hull will be small. Often they can't. Chan's Algorithm removes the guess: it splits the input into groups, builds each group's mini-hull with Graham Scan, then gift-wraps Jarvis-March-style across just the mini-hulls — using a group size m that starts small and doubles whenever a wrap attempt fails to close within m steps. Its own page measured this directly on a 16-point set with a real 7-vertex hull: the guess-and-double loop needs exactly three rounds (m = 2, fails; m = 4, fails; m = 8, succeeds) before landing on the answer, matching ⌈log₂ h⌉ rounds rather than a guess made once and lived with. The total cost across every round, failed guesses included, comes out to O(n log h) — provably never worse than either Graham Scan's flat O(n log n) or Jarvis March's O(nh), and strictly better than both whenever the hull is neither tiny nor huge. The price isn't speed, it's code: three algorithms' worth of moving parts (a sort-and-sweep, a wrap, and a restart loop tying them together) where the other three entries each need only one. Reach for it when n is large enough that the log-factor gap is worth that complexity; for most everyday input sizes, one of the simpler three below is easier to get right and fast enough regardless.

Otherwise: does a guaranteed bound beat typical-case speed?

Once the hull's size relative to the input isn't a known advantage, the choice is between Graham Scan (or its close relative Monotone Chain, see below) and Quickhull — and it's the identical shape as Choosing a Comparison Sort's own worst-case- guarantee-versus-typical-speed question, right down to one of the two algorithms literally being named after the sorting algorithm it mirrors.

Graham Scan's cost is dominated entirely by one up-front angle sort, so it's O(n log n) every time, regardless of how the points happen to be arranged — no input shape can push it worse. Quickhull reaches the same average-case O(n log n) by a completely different route (fixing the two x-extreme points, then recursively finding the single farthest point from the current baseline and splitting what's left), and its own Complexity section is explicit that this is "the same shape as Quicksort's own average case, and for the same reason" — when the farthest-point split lands roughly in the middle of the remaining candidates, each recursion level does O(n) total work across O(log n) levels. But an unlucky split degrades it to O(n²), the same way an unlucky pivot does to Quicksort — verified by construction on Quickhull's own page: a steeply bowing, adversarially-spaced point set forces the split to land next to one end of the remaining set on every recursive call, and the op-count-to-n² ratio measurably converges rather than shrinks as n grows (0.49 → 0.31 → 0.27 → 0.24 across four doublings) — the real signature of quadratic growth, not just a plausible-looking curve. A genuinely mixed, mostly-interior point cloud measured the same way shrinks toward zero instead (0.25 → 0.07 → 0.02 → 0.005), confirming the average case really does hold on typical input. Reach for the guaranteed-bound side of this question when the input could be adversarial or the bound has to be guaranteed; reach for Quickhull when the input is well-behaved and its practical speed — discarding entire regions of points early, the same edge Quicksort has over Merge Sort — is worth more than the guarantee.

Monotone Chain doesn't add a new branch to this question — it reaches the exact same guaranteed O(n log n) as Graham Scan, by replacing the angle sort with a plain coordinate sort and running two sweeps instead of one. The two are close enough that this site's own point set lands both on the identical 8-vertex hull (9-vertex in loose/collinear-inclusive mode), just discovered in different vertex order. The real difference is implementation, not asymptotics: Graham Scan needs a pivot chosen up front and an atan2 call per comparison, plus a distance tiebreak for angle ties; Monotone Chain needs neither a pivot nor any trigonometry, at the cost of running the sweep twice instead of once. Reach for whichever one a codebase's other geometry code already leans on — there's no case where one is asymptotically better than the other.

Divide-and-Conquer Convex Hull reaches the same guaranteed O(n log n) a third way: the identical up-front coordinate sort as Monotone Chain, but no sweep over the sorted list at all afterward. Instead, every point starts as its own trivial one-point hull, and neighboring hulls merge upward in pairs — through a pair of tangent lines found by walking a pointer around each hull, at most O(|L| + |R|) steps per merge — until one hull remains. The three land on the same guarantee by genuinely different routes (one sort plus one sweep, one sort plus two sweeps, one sort plus a merge tree), which matters for where the constant factor goes rather than the asymptotics: Graham Scan spends its per-comparison cost on trigonometry, Monotone Chain spends it on a second full pass, and Divide-and-Conquer Convex Hull spends it on tangent-finding at every merge instead of any per-point comparison. Reach for it over the other two mainly for the shape of the computation itself — it's the one that parallelizes cleanly, since every merge at a given level is independent of every other merge at that level, the same property that makes Merge Sort (rather than an in-place sort) the right comparison to reach for when sorting needs to split across multiple workers.

The same boundary-point question, answered five times by different code

All four from-scratch sweep/wrap pages independently confront the identical design question — does an exactly collinear point sitting on the hull's edge count as a vertex? — and, checked directly against each shipped demo rather than assumed from the family resemblance, land on the exact same answer. On this site's shared point set, point B sits precisely on the straight line between A and C. Graham Scan's strict mode pops it (cross(...) <= 0 treats dead-straight the same as a wrong turn) for an 8-vertex hull; its loose mode (cross(...) < 0, strictly negative only) keeps it for 9. Quickhull's strict partition test fails B against both the "left of A→C" and "right of C→B" checks (cross(A, C, B) = 0 exactly), discarding it as interior for the same 8-vertex result — loosening both tests to >= 0 recovers B in the correct position for the same 9-vertex result, matching Graham Scan's own loose mode down to which extra vertex gets added. Monotone Chain uses the identical cross(...) <= 0 pop rule as Graham Scan, applied during its upper-hull pass rather than a single sweep, and lands on the same answer for the same reason: B is popped in strict mode for the same 8-vertex hull, kept in loose mode for the same 9-vertex one. Neither Jarvis March page nor any of the other three treats this as a bug either way — a hull is a well-defined region regardless of whether a boundary point that isn't a corner gets named as a vertex — but it's worth knowing that whichever choice a caller needs (fewer vertices to store and redraw, or every boundary point accounted for), all four algorithms can be made to agree on it.

Divide-and-Conquer Convex Hull lands on the identical answer — B dropped in strict mode, kept for the same 9-vertex hull in loose mode — but reaches it by a structurally different route, not a fifth copy of the same <=-vs-< flip. Its merge step already has to pick one side of a tangent line to discard, over and over as the merge tree climbs, and a point can be dropped by a merge whose tangent lines don't yet reflect the whole final hull — reopening that per-merge choice can't be done with a single comparison swap the way the other four manage it. Its own page runs loose mode as a separate final pass instead: walk the strict hull's own edges once, after it's fully built, and re-insert any original point sitting exactly on one. Same answer, but the other four decide a boundary point's fate once, at the moment they touch it; this one only knows for certain after the whole hull is finished.

One pitfall doesn't repeat across all four, though, and it's a sharper one than the boundary-point choice: both Jarvis March and Monotone Chain have a tiebreak that isn't optional, on the same sort-order-dependence shape, even though the two tiebreaks sit in different places. Jarvis March's own page found that skipping its angle-tie tiebreak entirely — not choosing the farther or nearer point, just doing nothing when two candidates tie exactly — doesn't just change which points get named as vertices, it makes the result depend on the order points were supplied in, which a correct geometric algorithm should never do. The same offline 8-point counterexample (reused from Graham Scan's own collinear check) lands on a valid 4-vertex hull in one input order and an invalid 6-vertex result that fails a direct containment check in another. Monotone Chain's own page found the same failure shape one step earlier, in the coordinate sort itself rather than the sweep: skipping the secondary y tiebreak when two points share the same x lets a stable sort's input order leak into the result — on a four-point counterexample (a vertical segment plus one point off to the side), two of three tested input orders still happen to land on a valid hull by luck, but the third drops a genuine corner and keeps an interior boundary point instead, failing a direct containment check. Graham Scan's and Quickhull's own collinear choices are legitimate either way; Jarvis March's and Monotone Chain's tiebreaks aren't optional.

Race them yourself

The sections above state each entry's complexity class and name Jarvis March's own dependence on h and Chan's own trade of speed for code — worth watching actually happen rather than taking on faith. This runs the exact reference implementations from Graham Scan, Jarvis March, Quickhull, Monotone Chain, Divide-and-Conquer Convex Hull, and Chan's Algorithm, unmodified, in your own browser, against the same freshly generated point set, timed with performance.now() — the same reason the minimum-spanning- tree race times instead of counting: all six do real, heavy enough work (a sort, a recursive merge, a group-and-wrap) that timing is the honest measure. The shape choice below matters as much as point count — a scattered cloud keeps the hull size h small no matter how many points are generated, while points placed on a circle make every single point a hull vertex, so h = n.

Press "Run race" to time all six reference implementations on the same freshly generated point set.

On a scattered cloud, where a uniform point set keeps h small (around 12-30 across the sizes above) regardless of n, every entry is genuinely O(n log n)-or-better in practice and the gaps are all constant-factor, not asymptotic — but they're real and consistent. Measured at 4,000 points, best-of-seven: Quickhull (~6 ms) and Jarvis March (~7 ms) are fastest here, Monotone Chain and Graham Scan close behind (~7-10 ms), and Divide-and-Conquer Convex Hull and Chan's Algorithm are consistently the slowest of the six, by roughly 1.3-2×, at every size tested — not because either is a worse asymptotic class (both are genuinely O(n log n) here, like the rest), but because each pays its per-point cost somewhere heavier than a single comparison: Divide-and-Conquer spends it on tangent-finding at every merge (named above), and Chan's spends it on building and gift-wrapping across many small Graham Scan groups instead of one flat sort.

On points placed on a circle, where h = n by construction, the gap stops being a mild constant factor for two of the six. Jarvis March's own O(nh) bound degenerates to O(n²) exactly as its own page warns — measured at 4,000 points, roughly 15-20× slower than Graham Scan, Quickhull, or Monotone Chain, which stay flat. More surprising: Chan's Algorithm is slower still — regularly the single slowest entry raced here once h is large, even behind Jarvis March, in the exact scenario its guess-and-double scheme exists to help with. The reason isn't a bug, it's the already-documented demo simplification named on Chan's own page: textbook Chan's finds each group's tangent point with an O(log m) binary search, but this site's own reference implementation uses a plain O(m) linear scan instead. When h is small that costs almost nothing extra; when h approaches n, the guess-and-double loop has to grow its group size m up near n too before a wrap attempt finally closes, and every one of those ~n wrap steps now costs O(n) instead of O(log n) to find its tangent — the one case the algorithm's own design is meant to remove the guesswork from is also the one case where this page's own constant-factor shortcut costs the most. Divide-and-Conquer Convex Hull, by contrast, stays a clean O(n log n) in both shapes, just with the same ~1.3-2× tax over the three sort-based entries it already carries on the cloud shape above — its tangent-finding cost per merge doesn't care whether h is small or large. All six agree on the exact same hull area in every run; a mismatch would mean a real bug in this page's own code, not an expected outcome.

Side by side

EntryTimeSpaceMechanismReach for it when
Graham Scan O(n log n), always O(n) sort by angle from a pivot, then sweep with a stack input could be adversarial; the bound has to be guaranteed
Jarvis March O(nh) O(h) wrap outward, one hull vertex at a time the hull is expected to be small relative to the input
Quickhull O(n log n) average, O(n²) worst O(n) recursion + O(h) divide and conquer on the farthest point from a baseline input is well-behaved; typical speed matters more than the guarantee
Monotone Chain O(n log n), always O(n) sort by (x, y) coordinate, then sweep twice — lower chain, then upper chain same guarantee as Graham Scan, without a pivot or any trigonometry
Divide-and-Conquer Convex Hull O(n log n), always O(n) sort by (x, y) coordinate, then merge single-point hulls upward through tangent lines same guarantee again, and the shape that splits cleanly across parallel workers
Chan's Algorithm O(n log h) O(n) Graham Scan on small groups, Jarvis-March-style wrap across the results, guess-and-double group size h is unknown ahead of time and n is large enough for the log-factor gap to matter