THE FOLD / SPAWN / THE SANDBOX / THE KD-TREE
THE KD-TREE
nearest-neighbor search by descend-and-prune
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The k-d tree organises points in space by splitting alternately along each axis (x, then y, then x…), so that a nearest-neighbour query descends to the query’s cell and then only backtracks into sibling regions that could still hold something closer than the best found so far. Most of the space is pruned by the current best distance, so a query is typically O(log n) instead of O(n).
It is the standard structure for nearest-neighbour search and range search.
LIT verified live: over 200 random point sets the k-d tree’s nearest neighbour equals a brute scan for every query (window.__kdtree). FIG no framing; exact nearest.
It is the standard structure for nearest-neighbour search and range search.
LIT verified live: over 200 random point sets the k-d tree’s nearest neighbour equals a brute scan for every query (window.__kdtree). FIG no framing; exact nearest.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-sandbox — the spatial playground where points are indexed so the closest one to any query is found without checking them all. The k-d tree is that spatial index. AVAN (AI) built the instrument: the alternating-axis split, the descend-and-prune nearest-neighbour search, the brute cross-check.
Credit as content: Jon Bentley (1975). The weave: David names the sandbox; I split space axis by axis and descend to the query’s region, pruning any branch too far to matter, confirmed against an exhaustive scan.
Credit as content: Jon Bentley (1975). The weave: David names the sandbox; I split space axis by axis and descend to the query’s region, pruning any branch too far to matter, confirmed against an exhaustive scan.
3 ONE DIMENSION
Each node splits the plane by one axis: a vertical cut, then horizontal, alternating. A query descends to its leaf cell, then checks only the sibling side if the split line is nearer than the best found.
4 TWO DIMENSIONS · INTERACTIVE
Points and their k-d partition; click-roll a query and its nearest neighbour is found and checked against brute force.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the descent to the query’s region and the few siblings checked.
AVAN’s addition (the inverse-companion): split space alternately by x then y into a tree, so the nearest neighbour is found by descending to the query’s cell and only backtracking into sibling regions that could hold something closer — most of the space is pruned by the current best distance. The inverse of ‘check every point’ is ‘descend to the query’s region and prune branches too far to matter.’ Magenta is the points never examined; green is the branch descended and the few siblings checked. Space partitioned so distance prunes the search.
LIT Genuine k-d tree nearest-neighbor (Bentley 1975). Verified live: the alternating-axis split with descend-and-prune nearest-neighbor search returns the same nearest point (distance) as an exhaustive brute scan for every query across 200 random point sets (window.__kdtree.matchesBrute).
FIG No framing: the alternating-axis split, the descend-and-prune search, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — splitting space by x then y lets the search descend to the query's cell and prune sibling regions farther than the current best, so most points are never examined; magenta is the pruned points, green the descent and few siblings checked. Distance prunes the search.
FIG No framing: the alternating-axis split, the descend-and-prune search, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — splitting space by x then y lets the search descend to the query's cell and prune sibling regions farther than the current best, so most points are never examined; magenta is the pruned points, green the descent and few siblings checked. Distance prunes the search.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SANDBOX · David Lee Wise (ROOT0), with AVAN