Chan's Algorithm

The convex hull of a thousand scattered points might have only five corners — a thin sliver of a shape with almost everyone else trapped inside it. Every hull algorithm you've likely met, from Graham scan to Andrew's monotone chain, still spends $O(n \log n)$ time sorting all those points, whether the hull turns out to have five vertices or five hundred.

In 1996, Timothy Chan asked a sharper question: why should the running time depend only on how many points went in, when what we actually want depends on how many corners come out? His answer became one of the cleanest tricks in computational geometry — an algorithm that guesses the size of the hull, builds a cheap scaffold of mini-hulls, and gift-wraps across just their corners.

If the guess is too small, the algorithm notices, shrugs, doubles it, and tries again — and it still ends up doing no more work, asymptotically, than if it had known the answer from the start.

Below is a scattering of points split into a handful of small groups (shaded regions). Each group's own mini-hull is drawn first — cheap to compute since each group is tiny. Then the algorithm gift-wraps: starting from the lowest point, it repeatedly asks "which corner, among all the mini-hull corners, is furthest counter-clockwise?" and walks on.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="380" height="300"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="chan" type="button">{{btn_chan}}</button>
  <button id="jarvis" type="button" class="ghost">{{btn_jarvis}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_shuffle}}</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 { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px;
         touch-action: none; max-width: 100%; display: block; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0; min-height: 2.6em; color: #1d3557; }
.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

Press Run Chan's algorithm to watch it stitch the final hull together using only mini-hull vertices as candidates at every step. Press Run plain gift wrap (Jarvis march) to watch the naive version, which re-scans every single point at every step. Watch the candidate-check counter: grouping into mini-hulls means each wrap step only has to look at a handful of shortlisted corners instead of the whole cloud.

How hard is the convex hull, really — once you let the answer's own size into the analysis?

• Sort-based hull algorithms (Graham scan, Andrew's monotone chain) run in $O(n \log n)$ no matter what. That is optimal in the worst case, but wasteful when the hull has only $h \ll n$ vertices.
• Plain gift wrapping (the Jarvis march) instead grows the hull one vertex at a time: at each of the $h$ steps, it scans all $n$ points to find the next corner. That is $O(nh)$ — fast when $h$ is tiny, catastrophic when $h$ is close to $n$.
• Chan's algorithm gets both. Split the $n$ points into groups of size $m$, build each group's mini-hull with Graham scan ($O(m \log m)$ per group, $O(n \log m)$ total), then gift-wrap across the $n/m$ mini-hulls. Each wrap step needs only $O(\log m)$ time per mini-hull (a binary search for its tangent point), so a full wrap of $h$ steps costs $O\!\left(h \cdot \frac{n}{m}\log m\right)$.
• The guessing trick: Chan doesn't know $h$ in advance, so he sets $m = \min(n, 2^{2^{t}})$ for increasing $t = 1, 2, 3, \dots$, re-running the whole thing with a bigger guess whenever the wrap fails to close within $m$ steps. Because the guesses double doubly (squaring each round), the total work across every failed attempt still sums to $O(n \log h)$ — the failed rounds cost barely more than the successful one.
• And $O(n \log h)$ is optimal: it matches a proven lower bound, since sorting $n$ numbers can be reduced to computing the hull of $n$ points that all end up on it ($h = n$), and comparison-based sorting needs $\Omega(n \log n)$ — which becomes $\Omega(n \log h)$ once $h$ is allowed to vary.

So Chan's algorithm is never worse than $O(n \log n)$, and it's dramatically better whenever the hull is small — the best of the sweep and gift-wrap worlds, without ever knowing $h$ ahead of time.

"Don't pay for work whose size the answer doesn't need" is a recurring idea across computing, and Chan's algorithm is one of its cleanest demonstrations:

• Real-time collision detection and graphics: game engines and physics simulators recompute hulls of moving point clouds every frame; when the hull is small relative to the cloud, an output-sensitive method keeps frame times low.
• Geographic and cartographic simplification: outlining a coastline, service area or GPS trace from millions of readings usually produces a hull with only a modest number of corners.
• Robotics and motion planning: bounding a robot's reachable region or an obstacle's silhouette benefits from hull algorithms that scale with the shape's complexity, not the sensor's point count.
• A blueprint for algorithm design: the "guess the answer size, verify, double and retry" pattern — sometimes called output-sensitive doubling — reappears any time an algorithm's ideal running time depends on a quantity ($h$ here) that isn't known until after you've solved the problem.

Learn Chan's algorithm and you've met a general strategy, not just a faster convex hull: make the algorithm's effort track the size of what it actually needs to produce.

Chan's algorithm turns a subtle observation — that the size of the answer can matter as much as the size of the input — into a concrete, practical technique. Small mini-hulls do the cheap local work; a gift wrap across just their corners does the cheap global work; and a doubling guess for $h$ means you never have to know the answer's size to get the running time that assumes you did.

The next time an algorithm looks wasteful because it seems to "do too much" on a simple case, ask whether it's paying attention to the size of its own output. Sometimes, like convex hull itself, the fastest path is not doing less work in general — it's doing exactly as much work as the answer deserves.