Home▸Algorithms & AI▸K-D Trees: Fast Nearest-Neighbor Search in Multidimensional Space

🌲 K-D Trees: Fast Nearest-Neighbor Search in Multidimensional Space

See how k-d trees recursively slice space along alternating axes to answer 'find the nearest point' queries in roughly O(log n) time instead of scanning every point.

Algorithms & AI3DModerate60 FPS

The simulation builds a k-d tree over a set of 2D points, drawing each recursive split as a line across the plane, then lets you place a query point and watch the search descend the tree, backtrack, and prune branches that cannot possibly contain a closer point than the current best.

🔬 What It Demonstrates

🎮 How to Use

Add or randomize a set of points to build the tree, click anywhere to drop a query point, and step through the search to see which branches get explored and which get pruned, with the current best distance shown as an expanding circle around the query.

💡 Did You Know?

K-d trees were introduced by Jon Bentley in 1975, and although the pruning-based search can be dramatically faster than brute force in low dimensions, its average query cost creeps back toward O(n) once the number of dimensions climbs into the hundreds, a limitation known as the curse of dimensionality.

⚙ Under the hood

Watch a k-d tree's recursive splits partition a point set, then follow a nearest-neighbor query descend and backtrack, pruning branches that cannot hold a closer point.

kd-treenearest neighbor searchspatial data structurespace partitioningalgorithmscomputational geometry

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install