Introduction

Hammer a handful of nails into a wooden board, then snap a rubber band around the whole bunch and let go. The band pulls tight, touching only the outermost nails and ignoring everything in the middle. The shape it forms is the convex hull โ€” the smallest convex polygon that contains every point.

"Convex" just means the outline never caves inward: pick any two points inside, and the straight line between them stays inside. The hull is the tightest such boundary you can draw around your cloud of points.

It sounds like a craft project, but it's one of the foundational questions of computational geometry. And unlike many problems on this site, this one has a happy ending โ€” we know how to solve it fast, and we know exactly how fast is even possible.

Build the Hull

Below is a scatter of points. The shaded outline is their convex hull โ€” the rubber band stretched around them. Drag any point and watch the hull recompute instantly. Add or shuffle points and notice which ones land on the boundary and which get swallowed inside.

<p class="hint">The shaded outline is the <b>convex hull</b> โ€” the rubber band stretched around every point. <b>Drag</b> any dot to reshape it. Points on the boundary are red; points swallowed inside are gray. Checking a hull is easy; finding it is the interesting part.</p>
<canvas id="cv" width="360" height="280"></canvas>
<div class="status" id="status">Drag a point, or pick an action below.</div>
<div class="btns">
  <button id="solve" type="button">Solve (Graham scan)</button>
  <button id="brute" type="button" class="ghost">Brute force</button>
  <button id="shuffle" type="button" class="ghost">Shuffle 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: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Convex hull = the smallest convex polygon containing every point (the rubber
// band around the nails). Finding it is in P: Graham scan / Andrew's monotone
// chain sort the points then sweep, running in O(n log n) โ€” provably optimal,
// since any hull algorithm can be made to sort. Brute force is the slow O(n^3)
// way: test every pair of points to see if it is a hull edge.
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, R = 7;

function rnd(){ return [
  [60,60],[300,50],[330,210],[70,230],[180,140],
  [200,70],[120,180],[260,160],[150,90],[240,210]
].map(([x,y]) => [x + (Math.random()*40-20), y + (Math.random()*40-20)]); }
let pts = rnd();

// 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]); }

// Andrew's monotone chain: sort by x (then y), build lower then upper hull.
function hull(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 onHull(p,h){ return h.some(q=>sameKey(p,q)); }

let highlight = null; // for brute-force flash

function draw(){
  ctx.clearRect(0,0,W,H);
  const h = hull(pts);
  // hull polygon
  if(h.length>=3){
    ctx.beginPath();
    ctx.moveTo(h[0][0],h[0][1]);
    for(let i=1;i<h.length;i++) ctx.lineTo(h[i][0],h[i][1]);
    ctx.closePath();
    ctx.fillStyle='rgba(29,53,87,0.10)';
    ctx.fill();
    ctx.strokeStyle='#1d3557'; ctx.lineWidth=2; ctx.stroke();
  }
  if(highlight){ ctx.beginPath(); ctx.moveTo(highlight[0][0],highlight[0][1]);
    ctx.lineTo(highlight[1][0],highlight[1][1]); ctx.strokeStyle='#e63946';
    ctx.lineWidth=2; ctx.stroke(); }
  // points
  for(const p of pts){
    ctx.beginPath(); ctx.arc(p[0],p[1],R,0,7);
    ctx.fillStyle = onHull(p,h) ? '#e63946' : '#9aa3ad';
    ctx.fill(); ctx.strokeStyle='#fff'; ctx.lineWidth=2; ctx.stroke();
  }
  return h;
}
function setStatus(t){ document.getElementById('status').textContent=t; }

// โ”€โ”€ dragging โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let dragIx = -1;
function pos(e){ const r=cv.getBoundingClientRect();
  const t=e.touches?e.touches[0]:e;
  return [ (t.clientX-r.left)*(W/r.width), (t.clientY-r.top)*(H/r.height) ]; }
function pick(e){ const [x,y]=pos(e);
  for(let i=0;i<pts.length;i++){ const dx=pts[i][0]-x, dy=pts[i][1]-y;
    if(dx*dx+dy*dy <= (R+4)*(R+4)) return i; } return -1; }
function down(e){ dragIx=pick(e); if(dragIx>=0){ highlight=null; e.preventDefault(); } }
function move(e){ if(dragIx<0) return; const [x,y]=pos(e);
  pts[dragIx]=[Math.max(R,Math.min(W-R,x)), Math.max(R,Math.min(H-R,y))];
  const h=draw(); setStatus(fmt('Hull updated โ€” %length% points on the boundary.', { length: h.length })); e.preventDefault(); }
function up(){ dragIx=-1; }
cv.addEventListener('mousedown',down); window.addEventListener('mousemove',move); window.addEventListener('mouseup',up);
cv.addEventListener('touchstart',down,{passive:false}); cv.addEventListener('touchmove',move,{passive:false}); cv.addEventListener('touchend',up);

// โ”€โ”€ buttons โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.getElementById('solve').addEventListener('click',()=>{
  const h=draw();
  setStatus(fmt('Graham scan: sorted %length% points, swept the boundary in O(n log n). %length2% on the hull.', { length: pts.length, length2: h.length }));
});
document.getElementById('brute').addEventListener('click',()=>{
  // O(n^3): for each ordered pair, check if all other points lie on one side.
  let tests=0, edge=null;
  for(let i=0;i<pts.length && !edge;i++) for(let j=0;j<pts.length;j++){
    if(i===j) continue; let allLeft=true;
    for(let k=0;k<pts.length;k++){ if(k===i||k===j) continue; tests++;
      if(cross(pts[i],pts[j],pts[k])<0){ allLeft=false; break; } }
    if(allLeft){ edge=[pts[i],pts[j]]; break; } }
  highlight=edge; draw();
  setStatus(fmt('Brute force found one hull edge after ~%tests% point tests (O(nยณ) overall). Graham scan needs far fewer.', { tests: tests }));
});
document.getElementById('shuffle').addEventListener('click',()=>{
  pts=rnd(); highlight=null; const h=draw();
  setStatus(fmt('New points. Hull has %length% vertices.', { length: h.length }));
});
draw();
Result
Console

Notice the asymmetry between checking and finding. Given a finished hull, verifying it is easy โ€” confirm every other point sits on the inner side of each edge. Finding the hull from scratch means sorting the points and sweeping around them. Press Solve (Graham scan) to watch the algorithm pick the boundary in order, and Brute force to see the slow way: testing every pair of points to ask "is this an edge of the hull?"

The Real Complexity

How hard is the convex hull, really?

  • Brute force asks, for every pair of points, "could the segment between them be a hull edge?" โ€” which requires checking all the other points against that line. That's about n2n^{2} pairs times n checks, or O(n3)O(n^{3}). Workable for a few points, painful for thousands.
  • The smart way is to sort the points and sweep. Graham scan (Ronald Graham, 1972) sorts the points by angle, then walks around them keeping only left turns. Andrew's monotone chain (A. M. Andrew, 1979) sorts by x-coordinate and builds an upper and lower hull. Both run in O(nlogโกn)O(n \log n) โ€” the sort dominates; the sweep is just linear.
  • It's in P โ€” comfortably tractable, unlike the traveling salesman problem next door in geometry.
  • And here's the beautiful part: O(nlogโกn)O(n \log n) is optimal. You can prove a matching ฮฉ(n log n) lower bound: any algorithm that computes the hull can be turned into a sorting algorithm, and sorting by comparisons provably needs at least n log n steps. So no cleverness will ever beat n log n in the general case.

That two-sided result โ€” a fast algorithm and a proof that nothing can be faster โ€” is rare and precious. Most problems give us only an upper bound (the best we've found so far). Here, the ceiling and the floor meet.

Where It Matters

"Find the outer boundary of a set of points" turns out to be a workhorse subroutine across computing:

  • Collision detection: game engines and physics simulators wrap complex objects in their convex hulls so they can test for overlaps cheaply instead of comparing every triangle.
  • Image and shape recognition: the hull of a detected blob gives a compact summary of its shape โ€” used to spot gestures, fingertips, or defects on a part.
  • Geographic information systems: drawing the smallest region that contains a set of GPS readings, sightings, or service points.
  • Statistics and data analysis: the hull marks the extreme observations and underpins methods like "convex peeling" for outlier detection.
  • Robotics and path planning: hulls simplify obstacles and the robot's own footprint into manageable convex shapes.

Because the hull is so often a first step, its O(nlogโกn)O(n \log n) speed matters: a fast, optimal subroutine keeps the bigger pipeline fast too. It sits in the same well-solved corner of geometry as sorting and searching-style problems where we know the exact cost.

Conclusion

The convex hull is the gentle counterexample on a site full of intractable monsters. A child's rubber-band intuition turns into a precise algorithm, and that algorithm is not merely fast โ€” it is provably the fastest possible, sorting and sweeping in O(nlogโกn)O(n \log n).

That's why geometers love it. Most hard problems leave us forever wondering whether a better method is hiding around the corner. The convex hull settles the question: the rubber band snaps tight in n log n time, and there is no shortcut waiting to be found. Sometimes, computer science gives you a clean, complete answer โ€” and that is worth celebrating.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

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