Unlike most of this site's other guides, six of the site's eleven 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 five are set aside up front, as five different questions rather than a seventh, eighth, ninth, tenth, and eleventh 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; and 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.) 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.
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.
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.
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.
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.
| Entry | Time | Space | Mechanism | Reach 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 |