Graham Scan

Scatter a handful of points on a page and ask for the convex hull — the tightest rubber band that wraps them all — and you need a plan for which points to keep and in what order to connect them. In 1972, mathematician Ronald Graham published a strikingly clean plan, now called the Graham scan.

The idea is almost sneaky in its simplicity: pick the lowest point as an anchor, sort every other point by the angle it makes with that anchor, and then walk through the sorted list carrying a stack. Each time the last three points on the stack would force a right turn, the middle one cannot be on the hull — pop it and check again. Keep going until only left turns remain.

No angles are ever recomputed mid-walk, no point is revisited more than a couple of times, and the sort dominates the running time: O(n log n), and provably as fast as any comparison-based algorithm can do this job.

Click anywhere on the canvas to drop points. Once you have at least three, press Run Graham scan to watch it work: it finds the lowest point, sorts the rest by angle around it, then walks the sorted order one step at a time, popping the stack every time a right turn shows up.

<p class="hint">{{hint_para}}</p>
<canvas id="board" class="board" width="560" height="360"></canvas>
<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="step" type="button">{{btn_step}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</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; }
.board { width: 100%; max-width: 560px; height: auto; aspect-ratio: 560 / 360; background: #f4f6f8;
         border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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: not-allowed; }

// Code not found

Use Step to go one point at a time and see exactly when a pop happens — that's the moment the algorithm realizes a previously "promising" point was actually tucked inside the hull all along.

Graham scan's cost splits cleanly into two pieces:

• The sort. Pick the point with the lowest $y$-coordinate (breaking ties by lowest $x$) as the pivot $p_0$. Sort the remaining $n-1$ points by the polar angle they make with $p_0$, which costs $O(n \log n)$ with any comparison sort.
• The scan. Walk the sorted points, keeping a stack of hull candidates. For each new point, test whether the last two stack entries and the new point form a right turn using the sign of a 2D cross product:

  $$(p_1 - p_0) \times (p_2 - p_0) = (x_1 - x_0)(y_2 - y_0) - (y_1 - y_0)(x_2 - x_0)$$

  A non-positive result means a right turn (or straight line) — pop the middle point and test again with the new top of the stack. A positive result means a left turn — push the new point and move on.

The scan is $O(n)$ overall, not $O(n^2)$, because every point is pushed exactly once and popped at most once — a classic amortized-analysis argument, the same trick that keeps a stack-based bracket matcher linear.

That leaves $O(n \log n)$ total, and this is not just a good algorithm — it is an optimal one. Any comparison-based convex hull algorithm needs $\Omega(n \log n)$ time in the worst case, because sorting itself can be reduced to computing a hull (arrange points on a parabola $y = x^2$ and the hull order is the sorted order). Graham scan meets that lower bound exactly, putting it in the same company as the sorting lower bound that any comparison sort must respect.

Wrapping a point cloud in its tightest boundary shows up constantly once you start looking:

• Collision detection and physics engines: convex shapes are cheap to test for overlap, so games and simulators wrap complex objects in their convex hull as a fast first check.
• Geographic information systems: drawing the outer boundary of a set of sensor readings, GPS pings or territory markers is a direct convex hull query.
• Pattern recognition and image processing: the hull of a cluster of feature points gives a robust outline for shape matching, even when a few points are noisy.
• Robot motion planning: hulls of obstacles simplify path-finding, since avoiding a convex shape is far easier to reason about than avoiding an arbitrary polygon.

Learn Graham scan and you've learned the template for a whole family of geometric algorithms: reduce the input to a good order, then sweep it once with a simple local test — the same spirit behind building a minimum spanning tree by sweeping edges in sorted order.

Graham scan is a small masterpiece of algorithm design: reduce a geometric question to a sort, then answer it with one linear pass and a stack that only ever pushes or pops. No point is ever examined more times than the amortized analysis allows, and the whole thing lands exactly on the $\Omega(n \log n)$ floor that any comparison-based hull algorithm must respect.

So the next time you see an outline snapped tight around a scatter of points, remember it might just be a sorted angle list and a stack quietly throwing away every point that tried to poke outward and got left behind by a right turn. It's the same instinct that runs through the convex hull problem as a whole — order first, then sweep.