Thought Toys · Strategy & computation · Exhibit 51

Cross one line, and its territory closes

Every point on this map belongs to whichever dot is nearest to it — that's the dot's territory. Slide the amber dot from outside a crowd of eight toward its center and watch the instant its territory, which reached out forever, snaps shut into a walled-in cell.

Nearest-neighbor territories — drag any dot, or click empty space to add one explorerother sites

Its cell reaches out to infinity in at least one direction.

↳ your turn — drag any dot on the map, or click empty space to add one

What you're seeing

Every point on this map belongs to whichever dot is nearest to it. Collectively, those territories tile the whole plane without gaps or overlaps — this tessellation is called a Voronoi diagram, and the same idea locates a city's nearest hospital, a cell's nearest neighbor in a tissue sample, or a cell tower's coverage area. Nine dots sit on the map: eight form a loose crowd, and one — amber — is yours to move.

Drag the slider and the amber dot sweeps from well outside the crowd toward its center. While it's outside, its territory reaches out in some direction forever — unbounded, open country. The instant it crosses the crowd's outer edge, that territory snaps shut: every direction now runs into some other dot's territory first. You can also grab any dot directly with the mouse, including the crowd itself, or click empty space to drop a new one.

The rule, exactly. A site's territory is unbounded if and only if the site lies on the convex hull of the whole site set — the shape you'd get by stretching a rubber band around every dot; hull sites sit on that outer boundary, the rest sit inside it. Boundedness is tested here two independent ways: by convex-hull membership (the monotone-chain algorithm), and by sampling 720 points around a circle 200× the configuration's radius and checking which site is nearest at each. Verified in node (improve/verify/51-voronoi.js): across 25 random configurations of 5–14 sites, the two methods agree on every single site; sweeping a dragged point from far outside a fixed triangle to its centroid crosses the hull boundary exactly once, exactly where a convex region's geometry requires. Negative control: jittering a deep-interior point by up to 15 units across 200 independent trials never once puts it on the hull — moving around inside the crowd, however you move, never unbounds a territory that's actually enclosed.

Also in Strategy & computation: Catch one error, miss the next →

All 23 in Strategy & computation
  1. 10The evolution of trust
  2. 23Sorting algorithms
  3. 24PageRank & the random surfer
  4. 25Huffman coding
  5. 26Dijkstra's shortest path
  6. 27Nash equilibria
  7. 33The learning-rate cliff
  8. 36A* pathfinding
  9. 37Braess's paradox
  10. 44Diffie–Hellman key exchange
  11. 45Preferential attachment
  12. 46Aliasing & the Nyquist limit
  13. 47The secretary problem
  14. 49Freeze too fast, stay stuck
  15. 51Cross one line, and its territory closes — you are here
  16. 56Catch one error, miss the next
  17. 57Why more processors stop helping
  18. 58Why a busy line explodes
  19. 59The set that's only sure when it says no
  20. 60The fit that memorizes instead of learns
  21. 61When the wire breaks, pick one
  22. 67Better at both, and still better off trading
  23. 69Everyone was consistent. The vote wasn't.

← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 51.