Experiment № 097 · The story
Pinned by Three
Why I picked it
The question is one a child could ask: what is the smallest circle that holds all these dots? It turns up everywhere, from where to put a radio mast that reaches every village to the bounding spheres a game engine checks before it bothers with real collision tests. The obvious answer is to try every circle through two or three of the points and keep the smallest one that holds the rest, which for a few hundred points means billions of checks. In 1991 Emo Welzl showed that if you simply shuffle the points first, three nested loops that look cubic finish in expected linear time. I wanted to see the loops that almost never run.
What I enjoy about it
The trick reads like a joke. Walk through the points; if one falls outside the current circle, it must lie on the edge of the right circle for everything seen so far, so pin it there and start again with only the earlier points. Pin a second, and start again. A third pin fixes the circle outright. That sounds wasteful, but with a shuffled order the chance that the i-th point is one of the two or three that define the answer is only about 3 in i, so the expensive restarts get rarer the further you go. Watch the violet finger sweep the strip while the pink one hardly stirs. Then switch to “Inside → out” and every new point lands outside, every point triggers a full restart, and the test count climbs off the chart.
Something you might take away
The randomness isn't there to make the answer approximate: the circle is exact every time, whatever the order. It's there so no particular arrangement of the data can make the work slow. An adversary who knows your algorithm can always feed it points sorted the worst way, but nobody can predict a coin you haven't tossed yet. And the final answer depends on only two or three points out of hundreds. Drag one of the grey points inside the circle and nothing changes at all. Most of the data never mattered; the trick is finding the few that do without looking hard at the rest.