Cairn
algorithms · computational geometry · O(n log n) average, O(n²) worst

↩ back to Convex Hull

Quickhull

The site's third Convex Hull entry, and a genuinely different shape of algorithm from both Graham Scan's sort-then-sweep and Jarvis March's one-vertex-at-a-time wrap: Quickhull is divide-and-conquer, the same strategy as its sorting namesake. Find the two most extreme points in x — guaranteed hull vertices, no test needed — and split every other point onto whichever side of that line it falls on. Then, for each side: find the single point farthest from the line (also a guaranteed hull vertex), which cuts the remaining points into two smaller sub-problems and throws some of them away entirely as now-provably interior. Recurse until every remaining edge has no points left outside it. Same cross-product primitive as the other two pages, same eleven points — this page's own step trace below independently confirms the identical eight-vertex hull, I → A → C → D → E → F → G → H.

Try it

The same eleven points as Graham Scan and Jarvis March, including the same collinear trio — A, B, and C — along the hull's bottom edge. Press Step or Run to watch the recursion: start with the leftmost and rightmost points (both guaranteed extreme, no test needed), then repeatedly find whichever remaining point is farthest from the current baseline edge, confirm it as a hull vertex, and split what's left into two smaller groups — one per new edge — before recursing into each. Any point that lands in neither group is now provably interior and fades out. The checkbox controls what happens to a point that sits exactly on a baseline, neither definitively inside nor outside — see Pitfalls for why both the question and the answer match Graham Scan's own strict/loose checkbox exactly.

hull size: 0
Press Step or Run.

Why it works

Same test as Graham Scan and Jarvis March, used for a third purpose: cross(o, a, b) = (a.x−o.x)(b.y−o.y) − (a.y−o.y)(b.x−o.x) is positive on one side of line o→a, negative on the other, exactly zero on it. Graham Scan uses the sign to test whether a boundary turns the right way; Jarvis March uses it to compare two candidates; Quickhull uses its magnitude — the point with the largest cross(a, b, p) is provably the single farthest point from line a→b, and provably a hull vertex, because nothing can be more extreme than the most extreme point in that direction.

Once that farthest point C is found for baseline a→b, every other candidate falls into exactly one of three buckets: strictly left of a→C (recurse there), strictly right of C→b (recurse there), or inside triangle a-C-b — provably interior, since no point that far inside a triangle can ever be more extreme than that triangle's own corners in any direction it spans. That third bucket is the whole speed argument: an interior point is discarded once and never looked at again, unlike Graham Scan's sort, which touches every point at least once no matter where it ends up.

One more thing worth noticing, verified directly against this page's own step trace rather than assumed: the recursion always processes left, then the farthest point itself, then right — the exact same shape as an in-order traversal of a binary search tree. Just like an in-order BST traversal visits keys in sorted order without any explicit sort step, Quickhull's in-order recursion visits hull vertices in correct boundary order without any explicit sort step either — confirmed by the fact that the hull array above is built directly in yield order, with zero reordering afterward, and still comes out as I → A → C → D → E → F → G → H.

Reference implementation

function convexHull(points, loose = false) {
  const pts = Array.from(new Set(points.map(p => JSON.stringify(p))), s => JSON.parse(s));
  if (pts.length < 3) return pts; // fewer than 3 points: no polygon, see Pitfalls

  function cross(o, a, b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
  }

  function findHull(candidates, a, b) {
    if (candidates.length === 0) return [];
    let far = null, maxCross = -Infinity;
    for (const p of candidates) {
      const c = cross(a, b, p);
      if (c > maxCross) { maxCross = c; far = p; }
    }
    if (loose ? maxCross < 0 : maxCross <= 0) return []; // nothing outside a→b: it's a hull edge
    const left = candidates.filter(p => p !== far &&
      (loose ? cross(a, far, p) >= 0 : cross(a, far, p) > 0));
    const right = candidates.filter(p => p !== far &&
      (loose ? cross(far, b, p) >= 0 : cross(far, b, p) > 0));
    // in-order: left of a→far, then far itself, then right of far→b — see Why it works
    return [...findHull(left, a, far), far, ...findHull(right, far, b)];
  }

  let minX = pts[0], maxX = pts[0];
  for (const p of pts) {
    if (p.x < minX.x || (p.x === minX.x && p.y < minX.y)) minX = p;
    if (p.x > maxX.x || (p.x === maxX.x && p.y > maxX.y)) maxX = p;
  }
  const rest = pts.filter(p => p !== minX && p !== maxX);
  const upper = rest.filter(p => cross(minX, maxX, p) > 0);
  const lower = rest.filter(p => cross(maxX, minX, p) > 0);
  return [minX, ...findHull(upper, minX, maxX), maxX, ...findHull(lower, maxX, minX)];
}

Pitfalls

An exactly collinear boundary point silently drops out as "interior" unless the partition test is loosened — the exact same question Graham Scan's strict/loose checkbox asks, with the exact same answer on this page's own point set. Point B sits precisely on the line through A and C (the three share this demo's bottom edge). Verified directly against the shipped algorithm: with the strict partition (cross(...) > 0), once C is confirmed farthest from A's baseline, B fails both the "left of A→C" test and the "right of C→b" test — cross(A, C, B) = 0, so it qualifies for neither bucket and is discarded as interior, giving the same eight-vertex hull as Graham Scan's strict mode. Loosen both tests to >= 0 (and the "nothing left outside" guard to < 0, so a zero-height farthest point still counts as found) and B survives into the right bucket, gets found there on its own, and lands correctly between A and C — a nine-vertex hull, exactly matching Graham Scan's own loose-mode vertex count and even which extra point it adds. Neither choice is a bug; a hull is a well-defined region either way. But it's the same design question surfacing a second time through completely different code, not a coincidence — both algorithms have to decide what "on the boundary but not a corner" means.

Worst case is O(n²), and — like Quicksort's own worst case — it's an unlucky split, not malformed input. Checked by construction, not just asserted: points placed along a steeply bowing curve, spaced so each successive point is only barely farther out than the one before it, force the farthest-point step to land next to one end of the remaining set on every single recursive call instead of near the middle — the same "always-unlucky pivot" shape as Quicksort's own worst case, geometric instead of numeric. Counting every cross() evaluation across the whole run, this construction's op count divided by n² converges rather than shrinks as n grows — 0.49 at n=20, 0.31 at n=80, 0.27 at n=320, 0.24 at n=1,280 — exactly the signature of true quadratic growth. A genuinely mixed input (points scattered randomly inside a disc, most of them interior, only a handful ever reaching the hull) measured with the identical counter instead shrinks toward zero at the same sizes — 0.25, 0.07, 0.02, 0.005 — consistent with the average-case O(n log n) shape, not the worst case.

Fewer than three points, or every point exactly collinear, isn't a polygon — same edge case as Graham Scan and Jarvis March, same fix (the reference implementation's early return). Checked directly: four collinear points strung along one line correctly collapse to just the two extremes, a two-point degenerate result, the same shape both other pages' own collinear edge cases land on.

Measuring against Monotone Chain

The Complexity section below says this page's average case "can still beat [Monotone Chain] in practice on well-behaved input" — true, but with no number behind "can still beat," the same unquantified shape several past sessions have fixed elsewhere on this site. Measured directly here instead: both pages' own shipped convexHull functions, lightly instrumented to count every cross() call (Quickhull) or cross()-plus-sort-comparator call (Monotone Chain) — the real primitive each algorithm spends its time on, not a reimplementation — run against the identical random point set, scattered inside a disc the same way this page's own Pitfalls section already does for its average-case claim (most points land interior, only a handful ever reach the hull). Correctness checked first across 500 random trials, normalized for starting vertex and winding direction: zero mismatches between the two hulls before trusting either op count.

Monotone Chain's up-front sort touches every point at least once no matter where it ends up, exactly the mechanism Why it works above already names as Quickhull's advantage over a sort-based approach — and the gap it produces grows with n rather than staying fixed, because discarding an interior point early saves more total work the more layers of recursion there are left to skip:

Wall-clock shows the same direction but a smaller, noisier gap — roughly 1.1×–1.6× at sizes from 1,000 to 500,000 in one Node run, not cleanly monotonic the way the op count is — array allocation and GC pauses (both pages' filter/slice calls build fresh arrays at every level) add noise an op count never sees. The op count is the more honest number to cite for the mechanism itself; the wall-clock gap is real but smaller. Try it below with a fresh random point set at a size of your choosing.

Pick a point count, then press Measure — it scatters that many random points inside a disc, runs both pages' own shipped convexHull functions on the identical set, and counts real cross()/comparator calls for each.

Complexity

Time: O(n log n) on average — the same shape as Quicksort's own average case, and for the same reason: when the farthest-point step splits the remaining candidates roughly evenly between left and right, recursion depth is O(log n) and each level does O(n) total work across all of its calls combined, exactly like Quicksort's average-case partition recurrence. Worst case is O(n²) when the split is maximally uneven instead — see Pitfalls for the measured construction and numbers. Space: O(n) for the recursion, since every call filters its candidates into new arrays rather than mutating in place (the same tradeoff Quicksort's own Complexity section notes for an in-place partition scheme, just not made here) — plus O(h) for the returned hull itself, where h is the number of hull vertices, matching Jarvis March's output-only footprint rather than Graham Scan's sorted-list-plus-stack. A fourth entry, Chan's Algorithm, skips the recursive-split risk this page's own worst case runs into: it never recurses, instead running Graham Scan on small fixed-size groups and gift-wrapping across the results, for a guaranteed O(n log h) with no adversarial input shape to trigger a quadratic blowup. A fifth entry, Monotone Chain, reaches Graham Scan's own guaranteed O(n log n) by a different sort — this page's own average case beats it on well-behaved input by a real, measured margin that grows with n (1.2× the primitive op count at n=20, 2.9× at n=80,000 — see Measuring against Monotone Chain above), at the cost of the worst-case risk above. A sixth entry, Divide-and-Conquer Convex Hull, is also divide-and-conquer, but recurses on the input itself rather than a single growing hull — splitting the points in half and merging two independently solved hulls through their tangent lines, instead of narrowing one boundary edge against the farthest remaining point — and reaches the guaranteed bound this page trades away. See Choosing a Convex Hull Algorithm for a side-by-side comparison of all six.