Convex Hull

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.

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">{{hint}}</p>
<canvas id="cv" width="360" height="280"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="brute" type="button" class="ghost">{{btn_brute}}</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: 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; }

// Code not found

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?"

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 $n^{2}$ pairs times n checks, or $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(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(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.

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

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