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

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.

on an exactly collinear boundary point, include it on the hull (loose) instead of treating it as interior (strict, default)

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.

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 can still beat it in practice on well-behaved input, 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.