Experiment № 074 · The story
Nothing but Left Turns
Why I picked it
The convex hull is the first thing anyone builds in computational geometry, and it's the quiet dependency under half of what I've already made here — Voronoi cells, Delaunay-ish triangulations, collision shapes, the bounding box you throw away and regret. I'd been putting it off because "rubber band around some dots" sounds too obvious to be worth a day. Then I reread Ronald Graham's 1972 note. It is one page. The entire algorithm is the sign of a single number: (b−a) × (c−b), positive if you turned left, negative if you turned right. Sort the points once around the lowest one, walk them in order, and every time you turn right, take the middle point back off. What's left is provably the hull. No trigonometry — even the sort is done with the same cross product — and no special cases. I wanted to watch that on screen rather than believe it on paper.
What I enjoy about it
The popping. Watch the scan push a point that clearly looks like a corner, keep it for three or four more steps, and then suddenly back out over it as the chain straightens. That "for now" is where the whole proof lives, and it's also where the running time hides: the inner while loop looks like it could run forever, but every point is pushed exactly once and can be popped at most once, so the entire scan is linear no matter what the cloud looks like. All the n log n is in the sort, and nowhere else. The other joy is switching to gift wrapping and dragging the cloud from a disc to a thin ring. Same points, same answer, and its cost goes from the cheapest method on the panel to hundreds of times the worst — because it pays per corner it finds, and a ring is nothing but corners.
Something you might take away
Two things, and the second one has saved me more often. First: a loop nested inside a loop is not automatically quadratic. Count how many times the inner body can happen in total, not how long it might run once, and a scary-looking scan collapses to linear. Second: an algorithm's cost can depend on its answer, not just its input. Gift wrapping is O(n·h) — free when the hull is a triangle, brutal when everything is a corner. Output-sensitive algorithms are the ones worth remembering, because they let you pick based on the shape of the answer you expect rather than the size of the pile you started with.