Introduction

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(nlog⁡n)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.

Sub-Hulls Beat a Plain Gift Wrap

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">Colored regions are <b>mini-hulls</b> built from small groups of points. <b>Run Chan’s algorithm</b> to gift-wrap using only mini-hull corners as candidates; <b>Run plain gift wrap</b> to see the naive version scan every single point at every step. Watch the candidate-check count.</p>
<canvas id="cv" width="380" height="300"></canvas>
<div class="status" id="status">Pick an action below to build the hull.</div>
<div class="btns">
  <button id="chan" type="button">Run Chan’s algorithm</button>
  <button id="jarvis" type="button" class="ghost">Run plain gift wrap (Jarvis march)</button>
  <button id="shuffle" type="button" class="ghost">Reshuffle points</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chan’s algorithm groups n points into small clusters, builds each cluster’s
// mini-hull cheaply (Graham scan), then gift-wraps the FINAL hull using only
// the mini-hull corners as candidates at each step -- far fewer than scanning
// all n points, which is what plain gift wrapping (Jarvis march) has to do.
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, R = 5;
const GROUP_SIZE = 8; // points per mini-hull group; this is Chan’s guessed parameter "m"
const GROUP_COLORS = ['#e63946','#2a9d8f','#e9a13b','#6a4c93','#3a86ff','#c9184a','#118ab2'];

// fixed demo point set -- a small 6-vertex outer hull with interior clutter
const BASE_POINTS = [
  [30,160],[130,25],[300,45],[365,170],[260,275],[90,260],
  [140,110],[190,150],[150,180],[220,120],[240,180],[180,90],[120,160],
  [260,140],[210,200],[100,120],[160,220],[280,100],[70,180],
  [200,110],[230,150],[170,140],[130,190],[250,200],[110,150],
  [190,210],[160,120],[220,190],[80,140],[300,130],
  [145,135],[175,165],[205,135],[235,165],[165,195],[195,105],
  [125,225],[255,225],[215,165],[135,155],[245,145],[175,225],
  [95,190],[285,150],[155,105],[225,205],[105,165],[265,180],
  [185,175],[145,205],[215,115],[65,155],
];
let points = BASE_POINTS.map(p => p.slice());

// cross product of (O->A) x (O->B); >0 = left turn (counter-clockwise)
function cross(o,a,b){ return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]); }

// Graham-scan style hull builder, reused both for mini-hulls and the final hull
function hullOf(P){
  if(P.length < 3) return P.slice();
  const s = P.slice().sort((p,q)=> p[0]-q[0] || p[1]-q[1]);
  const lower=[];
  for(const p of s){ while(lower.length>=2 && cross(lower[lower.length-2],lower[lower.length-1],p)<=0) lower.pop(); lower.push(p); }
  const upper=[];
  for(let i=s.length-1;i>=0;i--){ const p=s[i]; while(upper.length>=2 && cross(upper[upper.length-2],upper[upper.length-1],p)<=0) upper.pop(); upper.push(p); }
  lower.pop(); upper.pop();
  return lower.concat(upper);
}
const sameKey = (a,b)=> Math.abs(a[0]-b[0])<1e-6 && Math.abs(a[1]-b[1])<1e-6;

function groupsOf(P, size){
  const gs = [];
  for(let i=0;i<P.length;i+=size) gs.push(P.slice(i,i+size));
  return gs;
}
function lowestPoint(P){
  let best = P[0];
  for(const p of P){ if(p[1] > best[1] || (p[1]===best[1] && p[0]<best[0])) best = p; }
  return best;
}

let mode = null; // ’chan’ or ’jarvis’, controls what draw() renders
let miniHulls = [];
let finalHull = [];
let checkCount = 0;

function draw(){
  ctx.clearRect(0,0,W,H);
  // draw each mini-hull as a shaded, colored region (Chan mode only)
  if(mode === 'chan'){
    miniHulls.forEach((h, i) => {
      if(h.length < 2) return;
      ctx.beginPath();
      ctx.moveTo(h[0][0], h[0][1]);
      for(let k=1;k<h.length;k++) ctx.lineTo(h[k][0], h[k][1]);
      if(h.length >= 3) ctx.closePath();
      ctx.fillStyle = GROUP_COLORS[i % GROUP_COLORS.length] + '22';
      ctx.strokeStyle = GROUP_COLORS[i % GROUP_COLORS.length];
      ctx.lineWidth = 1.4;
      if(h.length >= 3) ctx.fill();
      ctx.stroke();
    });
  }
  // draw the final stitched hull in dark blue
  if(finalHull.length >= 2){
    ctx.beginPath();
    ctx.moveTo(finalHull[0][0], finalHull[0][1]);
    for(let k=1;k<finalHull.length;k++) ctx.lineTo(finalHull[k][0], finalHull[k][1]);
    ctx.closePath();
    ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 2.6; ctx.stroke();
  }
  // draw every point; ones on the final hull are dark, others gray
  const onFinal = (p) => finalHull.some(q => sameKey(p,q));
  for(const p of points){
    ctx.beginPath(); ctx.arc(p[0],p[1],R,0,7);
    ctx.fillStyle = onFinal(p) ? '#1d3557' : '#9aa3ad';
    ctx.fill(); ctx.strokeStyle='#fff'; ctx.lineWidth=1.4; ctx.stroke();
  }
}
function setStatus(t){ document.getElementById('status').textContent = t; }

// Plain gift wrap (Jarvis march): at every step, scan ALL n points to find the next hull corner.
function runJarvis(){
  mode = 'jarvis'; miniHulls = [];
  const start = lowestPoint(points);
  const hull = []; let p = start; let checks = 0; let guard = 0;
  do {
    hull.push(p);
    let q = null;
    for(const cand of points){
      if(sameKey(cand,p)) continue;
      checks++;
      if(q === null || cross(p,q,cand) < 0) q = cand;
    }
    p = q; guard++;
  } while(!sameKey(p,start) && guard < points.length + 2);
  finalHull = hull; checkCount = checks;
  draw();
  setStatus(fmt('Plain gift wrap: scanned all %n% points at every step -- %checks% candidate checks total to find the %h%-vertex hull.', { n: points.length, h: hull.length, checks: checks }));
}

// Chan-style wrap: at every step, scan only the mini-hull corners (not all n points) to find the next hull corner.
function runChan(){
  mode = 'chan';
  const groups = groupsOf(points, GROUP_SIZE);
  miniHulls = groups.map(hullOf);
  const start = lowestPoint(points);
  const hull = []; let p = start; let checks = 0; let guard = 0;
  do {
    hull.push(p);
    let q = null;
    for(const h of miniHulls){
      for(const cand of h){
        if(sameKey(cand,p)) continue;
        checks++;
        if(q === null || cross(p,q,cand) < 0) q = cand;
      }
    }
    p = q; guard++;
  } while(!sameKey(p,start) && guard < points.length + 2);
  finalHull = hull; checkCount = checks;
  draw();
  const totalMiniVerts = miniHulls.reduce((a,h)=>a+h.length,0);
  setStatus(fmt('Chan’s algorithm: split into %groups% mini-hulls (%cand% corners total instead of %n% points) -- only %checks% candidate checks to find the same %h%-vertex hull.', { n: points.length, h: hull.length, groups: groups.length, cand: totalMiniVerts, checks: checks }));
}

document.getElementById('chan').addEventListener('click', runChan);
document.getElementById('jarvis').addEventListener('click', runJarvis);
document.getElementById('shuffle').addEventListener('click', () => {
  // jitter each point a little so the demo stays interesting across runs
  points = BASE_POINTS.map(([x,y]) => [
    Math.max(R, Math.min(W-R, x + (Math.random()*24-12))),
    Math.max(R, Math.min(H-R, y + (Math.random()*24-12))),
  ]);
  mode = null; miniHulls = []; finalHull = [];
  draw();
  setStatus('Pick an action below to build the hull.');
});

draw();
Result
Console

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.

The Real Complexity

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

So Chan's algorithm is never worse than O(nlog⁡n)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 hh ahead of time.

Where It Matters

"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 (hh 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.

Conclusion

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 hh 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/chans-algorithm/Content licensed under CC BY-NC 4.0.