QuickHull

Scatter a handful of points on a page and imagine stretching a rubber band around all of them, then letting it snap tight. The shape it traces — using only the outermost points as corners — is the convex hull. Every other point ends up trapped inside.

Computing that shape sounds like it should require checking every point against every other, but there is a shortcut with a delightfully simple idea: find the point that sticks out the farthest from a line, use it to slice the problem into two smaller pieces, and repeat. That is QuickHull, and its structure is a close cousin of quicksort — pick a pivot, split, recurse.

The reward is an algorithm that, for typical scattered inputs, wraps $n$ points in about $O(n \log n)$ time, discarding huge chunks of the input at every step without ever looking at them again.

Below is a random cloud of points. Press Step to watch QuickHull work one recursive call at a time: it finds the point farthest from the current edge, draws the two new edges to it, and discards every point that now sits inside the triangle. Press Run to completion to see the whole hull carved out at once.

<p class="hint">{{hint_para}}</p>
<svg id="canvas" class="canvas" viewBox="0 0 300 220" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.canvas { width: 100%; max-width: 320px; height: 235px; background: #f4f6f8; border: 1px solid #cdd9e3;
           border-radius: 8px; display: block; }
.pt { fill: #8a94a3; }
.pt.discarded { fill: #d7dbe0; }
.pt.hull { fill: #1d3557; }
.pt.farthest { fill: #e63946; }
.edge { stroke: #1d3557; stroke-width: 2; fill: none; }
.edge.active { stroke: #e63946; stroke-width: 1.6; stroke-dasharray: 4 3; }
.tri { fill: #e63946; fill-opacity: .08; stroke: none; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Watch how fast the candidate set shrinks. A single farthest point can throw away dozens of others in one shot — that is the whole trick behind QuickHull's speed on typical inputs.

QuickHull's recursion looks like this: given a line segment and a set of points known to lie on one side of it, find the farthest point $p$ from that line, then recurse on the points outside segment (a, p) and outside segment (p, b), discarding everyone inside triangle (a, p, b).

• Finding the farthest point among $m$ candidates costs $O(m)$ — one linear scan.
• On well-behaved, roughly-uniform point sets, each recursive split tends to throw away a constant fraction of the remaining points, giving a recurrence close to $T(n) = 2T(n/2) + O(n)$, which resolves to the familiar $O(n \log n)$ — exactly like quicksort's average case.
• The hull itself only has $h$ points (often $h \ll n$), and a refined analysis shows QuickHull actually runs in $O(n \log h)$ on average, adapting to how "round" versus "spiky" the input is.
• Worst case is $O(n^2)$. If the points are arranged so the farthest-point split is always maximally lopsided — for instance, points densely packed along a slight curve — QuickHull degenerates just like quicksort does on an already-sorted array with a bad pivot rule.

This is the same story as P vs NP-adjacent algorithm design in miniature: an algorithm can be provably worst-case bad and still be the practical champion, because the bad inputs are rare and the good case is so cheap. Other convex hull algorithms guarantee $O(n \log n)$ always — Graham scan sorts by angle first, divide-and-conquer hull merges recursively like merge sort — trading QuickHull's occasional worst case for a fixed sort-then-sweep cost every time.

Finding the tightest boundary around a set of points is one of computational geometry's most reused building blocks:

• Collision detection and physics engines: game and robotics engines approximate complex shapes with their convex hulls because hull-vs-hull collision tests are far cheaper than exact-mesh tests.
• Geographic information systems: drawing the outer boundary of a set of GPS points — a country's territorial extent, a delivery zone, a wildlife range — is a direct convex hull computation.
• Statistics and outlier detection: the hull's corner points are exactly the "extreme" observations in a dataset, useful for spotting outliers or defining a feasible region in optimization.
• A building block for richer structures: Delaunay triangulation and Voronoi diagrams can both be derived from convex hull computations via a clever lift into one higher dimension.

Learn QuickHull and you've learned the divide-and-conquer pattern behind a large slice of computational geometry — the same pivot-and-recurse idea that powers closest pair of points.

QuickHull turns a geometric question — what is the tightest shape around this cloud of points? — into the same recursive rhythm as quicksort: pick an extreme, split the world in two, throw away what you no longer need, repeat. That rhythm is why it is usually so fast, and why, on the right adversarial input, it can be just as slow as the algorithm it imitates.

The next time you see a shrink-wrapped outline around a scatter of dots — in a game engine, a map, or a dataset — remember that some of the fastest algorithms in computational geometry work by relentlessly asking one question: which point sticks out the most?