Split a cloud of points with alternating axis-aligned planes — x, then y, then x — and nearest-neighbour search stops being a scan of every point and becomes a walk down a tree that prunes whole regions. The catch that makes it correct: the first leaf you land in is usually not the answer, so the backtrack is the algorithm.
THE TECHNIQUE split on alternating axes, then backtrack
Build: at each level pick the split axis by depth (x, y, x, ...) and split at the median, so every node’s plane cuts its region in two. Search q: descend to the leaf whose region holds q, keep it as the current best, then climb back up — at each parent, only dip into the sibling if q’s distance to the splitting plane is less than the current best radius. Click to move the query point; the true nearest turns green. live demo
HISTORY & CREDIT the search was there in 1975; the PROOF is 1977
“The famous logarithmic nearest-neighbour search is all in the 1975 paper” — Bentley’s 1975 did give an NN search, but with an proven merely empirical O(log n); the optimized tree and the actual proof everyone cites are Friedman-Bentley-Finkel 1977. cited
1974 · Finkel & Bentley publish the point quadtree — the direct 2-D ancestor, splitting each region into 2k children at once. 1975 · Jon Louis Bentley coins the k-d tree (his Stanford undergraduate work, BS 1974; the paper itself, from UNC, won 2nd place in ACM’s 1975 student competition): one record per node, split axis cycling by depth, a binary split — with region, partial-match, exact-match, and a nearest-neighbour search of empirically O(log n). 1977 · Friedman, Bentley & Finkel give the optimized tree (split on the dimension of max spread, points in leaf buckets) and the rigorous proof of expected-logarithmic NN time via the bounds-overlap-ball test — the version people actually cite. the retrofit · “a k-d tree is a special case of a BSP tree” is backwards — BSP trees came in 1980, five years after the k-d tree.
The “k” is a variable, not an acronym — Bentley wrote 2-d tree and 3-d tree for specific cases. 1975 search, 1977 proof
RECOMMEND FOR I-13 the numeric spine runs; the nodes are the wall
Squared distance keeps it in f64 — no sqrt needed to compare, so the search arithmetic runs on the compiler:
$ i13 run kd.i13 # query q=(8,5) among 6 points
q_leaf = 16 # first leaf (8,1) -- NOT the nearest
q_best = 2 # backtrack finds (9,6) at distance^2 = 2 (the answer)
Recommend: BUILD (recursion + median + comparisons) and SEARCH (recursive descent, backtrack, dx*dx+dy*dy) are exactly the arithmetic-and-recursion kernels I-13 runs — the grounded run above proves the first leaf (16) is corrected to the true nearest (2). The wall is the same one three trees hit this campaign: each internal node references a left and right child — PS-015, shared with AVL (072), red-black (073), the trie (074). The fix is the node arena (left[], right[], axis[] + coordinate arrays), the move that closed heap-on-array (PS-005 / 062). Note: a second, quieter want — the points are pairs (x,y), and I-13 arrays hold f64 only, so the point set is parallel x[] / y[] arrays (PS-014 kin), not an array of tuples.