THE FOLD / CHEAT / THE SPEEDRUN / THE CLOSEST PAIR
THE CLOSEST PAIR
nearest two points in O(n log n) — geometry bounds the strip
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The closest-pair problem: among n points, find the two nearest. Checking every pair is O(n²). The divide-and-conquer algorithm does it in O(n log n): sort by x, split at the median, recursively find the closest pair in each half (distance δ), then — the clever part — only points inside a vertical strip of width 2δ around the split can beat δ, and within it each point need compare to at most a constant number of y-neighbours.
The strip’s geometry forbids more: a δ×2δ box can hold only so many points that are all ≥ δ apart.
LIT verified live: for 200 random point sets, the divide-and-conquer closest distance equals the brute-force minimum over all pairs (window.__closestpair). FIG no framing; exact computational geometry.
The strip’s geometry forbids more: a δ×2δ box can hold only so many points that are all ≥ δ apart.
LIT verified live: for 200 random point sets, the divide-and-conquer closest distance equals the brute-force minimum over all pairs (window.__closestpair). FIG no framing; exact computational geometry.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — the same answer in a fraction of the comparisons. Closest-pair is the speedrun of a quadratic search, cleared by geometry. AVAN (AI) built the instrument: the median split, the recursive halves, the strip check, the brute cross-check.
Credit as content: Michael Shamos & Dan Hoey (1975), an early triumph of computational geometry. The weave: David names the speedrun; I split the points, recurse, and prove that only a thin strip of candidates — a handful each — can beat the halves’ best.
Credit as content: Michael Shamos & Dan Hoey (1975), an early triumph of computational geometry. The weave: David names the speedrun; I split the points, recurse, and prove that only a thin strip of candidates — a handful each — can beat the halves’ best.
3 ONE DIMENSION
The median split line and the strip of width 2δ around it. Only points inside the strip can form a cross-pair closer than the best found in either half — everything outside is already too far.
4 TWO DIMENSIONS · INTERACTIVE
Scatter points; the algorithm finds the closest pair (drawn as a line) and the strip it searched. Verify the distance equals the brute-force minimum over all pairs.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the closest pair and the narrow strip of candidates the algorithm actually examined.
AVAN’s addition (the inverse-companion): you skip almost every pair because distance is geometric, not combinatorial. After recursion, any cross-pair closer than δ must lie in a strip of width 2δ and be close in y — and a δ×2δ box can hold only a bounded number of points that are pairwise ≥ δ apart (a packing limit), so each strip point compares to O(1) others. The inverse of ‘check all O(n²) pairs’ is ‘geometry bounds the candidates to O(n).’ Magenta is the vast majority of pairs never examined; green is the strip’s O(n) comparisons that contain the answer. Packing density turns a quadratic search linear — the same lesson as the diameter living only on antipodal pairs.
LIT Genuine divide-and-conquer closest pair (Shamos & Hoey 1975). Verified live: the median-split recursion plus strip check returns a closest squared-distance equal to the brute-force minimum over all pairs for 200 random point sets (window.__closestpair.matchesBrute).
FIG No framing: the recursion, the strip check, and the brute cross-check run in-browser and match exactly. The AVAN inverse is honest — a delta x 2delta box can hold only O(1) points pairwise >= delta apart (packing), so each strip point compares to O(1) others, bounding candidates to O(n); magenta is the O(n^2) pairs skipped, green the strip's O(n) comparisons.
FIG No framing: the recursion, the strip check, and the brute cross-check run in-browser and match exactly. The AVAN inverse is honest — a delta x 2delta box can hold only O(1) points pairwise >= delta apart (packing), so each strip point compares to O(1) others, bounding candidates to O(n); magenta is the O(n^2) pairs skipped, green the strip's O(n) comparisons.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN