Experiment № 083 · The story
Farther Than the Wall
Why I picked it
Because I wanted to draw the moment a program decides not to look. Finding the nearest of a thousand points is the most boring loop in the world — measure all thousand, keep the smallest — and Jon Bentley's 1975 k-d tree gets the same answer, exactly the same answer, after about thirty measurements. There is no approximation and no luck in that. Every point in the tree is also a wall: it cuts its region in half, alternating between a vertical cut and a horizontal one as you descend. The picture that falls out looks like a Mondrian drawn by a mob — dense where the points crowd, wide and calm where they don't — and I find it genuinely beautiful that the picture is the index. Then a query arrives, drops through the walls to the little cell it lands in, and starts walking back up asking one question at each wall: could anything on the other side possibly beat what I already have?
What I enjoy about it
The question has a one-line answer, and it is the whole algorithm. Everything behind a wall is at least as far away as the wall itself, because the shortest way there crosses it. So if the perpendicular distance to the wall is bigger than my current best, that entire half — a hundred points, a thousand, a subtree I never look inside — cannot contain a winner, and I skip it without a single distance calculation. Watch the rose regions switch off one after another as it climbs, and read the note in the panel: the wall is 14.2% away, my best is 3.1% — 218 points behind it can't win. It is proof, not heuristics. And it is fragile in exactly one direction: turn the neighbours dial up, and the circle it has to defend grows, so fewer walls clear the bar and the skipping quietly stops paying. The pruning is an argument about geometry, and you can watch the argument get harder.
Something you might take away
Look at the panel in the bottom-right corner. It builds the same tree over 2000 random points in 2, 3, 4, 6, 8, 12 and 16 dimensions and reports how many points each search actually measures. In the plane it is about 1%. At eight dimensions it is a quarter of them, at twelve it is four fifths, and by sixteen the tree is measuring essentially every point — the brute-force loop with extra bookkeeping and worse cache behaviour. Nothing is broken — the geometry simply turns on you. In high dimensions almost all of a box's volume hugs its boundary, so the query is close to nearly every wall, so nearly every wall must be crossed. That is the curse of dimensionality with a number attached, and it is why modern vector search gave up on exactness and went to approximate methods like HNSW. The general lesson I keep: a data structure is a claim about the shape of your data, and it is worth knowing which shapes make the claim false. The second one: everything behind that wall is at least as far as the wall is a bound you can prove in a sentence, and one provable bound in the right place is worth any amount of cleverness.