k-d Tree

A binary space-partitioning tree that organizes points in k dimensions for nearest-neighbor and range search.

Splitting space by axis

A k-d tree recursively partitions a set of k-dimensional points by axis-aligned hyperplanes. Each level splits on a different coordinate axis (cycling through them), placing the median point at the node and dividing the rest into a left (below) and right (above) subtree. Building from n points takes O(n log n) with median selection, and the balanced tree has depth O(log n).

Nearest-neighbor search

Kronos motion — space economy

To find the nearest point to a query, descend to the leaf whose region contains the query, record the best distance so far, then backtrack. At each node, the other subtree is explored only if the splitting plane is closer than the current best distance; otherwise it is pruned. For low dimensions this gives roughly O(log n) expected queries, but performance degrades toward linear as dimension grows (the curse of dimensionality).

Range and nearest queries

python

def nearest(node, target, depth, best):
    if node is None:
        return best
    d = dist2(target, node.point)
    if d < best.d2:
        best.d2, best.point = d, node.point
    axis = depth % k
    diff = target[axis] - node.point[axis]
    near, far = (node.left, node.right) if diff < 0 else (node.right, node.left)
    best = nearest(near, target, depth+1, best)
    if diff*diff < best.d2:            # hypersphere crosses the plane
        best = nearest(far, target, depth+1, best)
    return best

Uses and limits

Nearest-neighbor and k-nearest-neighbor search in graphics, robotics, and machine learning.
Orthogonal range search and range counting on point sets.
Effective for low to moderate dimension (up to a few dozen); above that, approximate methods (LSH, HNSW) win.
Related structures: ball trees, R-trees, and quadtrees/octrees for spatial data.

Geometry connection

k-d trees are a spatial companion to computational geometry primitives, trading exact combinatorial structure for fast average-case spatial queries.