k-d Trees

Suppose you have a million points scattered across a map and someone drops a pin. Which point is closest? The obvious answer is to measure the distance to all million and keep the smallest. It works, but it is brute force — every query touches every point.

The k-d tree, invented by Jon Louis Bentley in 1975, does something cleverer. It organizes the points by repeatedly slicing space along one axis at a time: split by the x-coordinate, then by the y-coordinate, then x again, alternating as you go down the tree. Each cut puts roughly half the points on each side.

Once space is carved up this way, a search can prune: if an entire region lies farther away than the best point found so far, the whole branch is skipped without ever looking inside. This is not a guess or a heuristic — the geometry guarantees nothing better hides in there.

Below are points split into a k-d tree, with the alternating cut lines drawn in. Click anywhere to drop a query point and search for its nearest neighbor. Cells the search actually visited light up; the ones it pruned — proved too far to matter — stay dim.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="420" height="320"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="reshuffle" type="button">{{btn_new_points}}</button>
  <button id="bruteforce" type="button" class="ghost">{{btn_compare_brute}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #fbfdff; cursor: crosshair; display: block; max-width: 100%; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice how few cells the search needs to open. A brute-force scan would touch every point; the k-d tree usually examines a small fraction and skips the rest. The denser and higher-dimensional the data, though, the harder pruning becomes — a tension we unpack next. See also closest pair of points.

The k-d tree is a solved, well-understood structure — no open problem here, just sharp tradeoffs.

• Building it takes $O(n \log n)$: at each level you split the points by the median along one axis, and there are about log n levels.
• A query on a balanced tree runs in $O(\log n)$ on average in low dimensions — the pruning you saw in the demo means most branches are never opened.
• The worst case is $O(n)$. If the query sits awkwardly, the search may still have to visit every cell. Pruning can fail; it is never guaranteed to save work.
• The curse of dimensionality. As the number of dimensions d grows, points spread out so evenly that almost no branch can be safely skipped. Past roughly d ≈ 20, a k-d tree often degrades to scanning nearly everything — no faster than brute force.

So a k-d tree does not change what nearest-neighbor search costs in the abstract; it exploits structure in low dimensions to avoid the work in practice. The same branch-and-bound idea — "rule out a whole region with one cheap test" — is the engine behind countless optimization searches.

"Find what is near this point" is one of the most common questions in computing, and the k-d tree is its classic answer:

• Machine learning: the k-nearest-neighbor classifier and many clustering steps lean on fast neighbor lookups.
• Computer graphics: ray tracers and photon mapping use k-d trees (and cousins like BVHs) to find which surfaces a ray might hit.
• Robotics and motion planning: planners such as RRT query "nearest existing node" thousands of times while growing a tree through space.
• Databases and GIS: spatial indexes answer range queries — "all the cafés inside this rectangle" — by pruning the same way.
• Simulation: N-body and particle codes use k-d trees to find nearby interacting particles instead of checking every pair.

Understand the k-d tree and you understand spatial indexing in general — the family of structures, alongside motion planning, that make "search near me" instant.

The k-d tree hides a simple, powerful idea: carve space one axis at a time, then refuse to look where the answer cannot be. Building the tree costs $O(n \log n)$, and in the plane a query becomes a tidy $O(\log n)$ walk that ignores most of the data — exactly the pruning you watched in the demo.

Its limit is just as instructive. In high dimensions the cuts stop helping and search collapses back toward brute force. That tension — a structure that is brilliant until the geometry turns against it — is why spatial search is still an active engineering art, and why the half-century-old k-d tree remains one of the cleanest examples of trading preprocessing for query speed.