Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

K-d trees: exact nearest depot with plane pruning

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A two-dimensional k-d tree partitions points by alternating east and north coordinates. This static builder sorts each subproblem on its active axis and stores a median as the node, yielding a balanced shape for its input set. An exact nearest query descends the side containing the target first. It may skip the other side only when the squared distance to the splitting plane is strictly greater than the best squared point distance already found. Equal plane distance must still be explored because a point there can win a deterministic tie by depot ID. This program uses ordinary planar coordinates, not geodesic distance on Earth.

Operational case

Depots D-19, D-47, and D-61 have planar coordinates (4, 9), (18, 7), and (12, 22). A request at (16, 9) selects D-47 with squared distance 8. A request at (5, 8) selects D-19 with squared distance 2. Squared distances avoid a square-root operation and preserve nearest ordering. Depot IDs break equal-distance ties. The tree is built for a fixed point set; moving a depot without rebuilding would invalidate the partition boundaries used for pruning.

Working Python program

python
"""Balanced two-dimensional k-d tree with exact nearest-neighbor pruning."""

from dataclasses import dataclass


@dataclass(frozen=True)
class DepotPoint:
    depot_id: str
    east: int
    north: int


@dataclass(frozen=True)
class SpatialNode:
    point: DepotPoint
    axis: int
    left: "SpatialNode | None"
    right: "SpatialNode | None"


def build_spatial_index(points, depth=0):
    if not points:
        return None
    axis = depth % 2
    ordered = sorted(points, key=lambda point: ((point.east, point.north)[axis], point.depot_id))
    middle = len(ordered) // 2
    return SpatialNode(
        ordered[middle], axis,
        build_spatial_index(ordered[:middle], depth + 1),
        build_spatial_index(ordered[middle + 1:], depth + 1),
    )


def nearest(root, east, north):
    best = None

    def visit(node):
        nonlocal best
        if node is None:
            return
        distance_squared = (node.point.east - east) ** 2 + (node.point.north - north) ** 2
        candidate = (distance_squared, node.point.depot_id)
        if best is None or candidate < best:
            best = candidate
        difference = (east - node.point.east, north - node.point.north)[node.axis]
        nearer, farther = (node.left, node.right) if difference < 0 else (node.right, node.left)
        visit(nearer)
        if best is None or difference * difference <= best[0]:
            visit(farther)

    visit(root)
    return None if best is None else (best[1], best[0])


depots = [DepotPoint("D-19", 4, 9), DepotPoint("D-47", 18, 7), DepotPoint("D-61", 12, 22)]
index = build_spatial_index(depots)
print(nearest(index, 16, 9))
print(nearest(index, 5, 8))

Output

Output
('D-47', 8)
('D-19', 2)

Time, space, and tradeoff

Sorting every recursive subproblem costs O(N log² N) time in this simple median builder for N points. The tree stores O(N) nodes; sorting and slicing allocate additional temporary lists, and balanced recursion uses O(log N) stack depth. A nearest query often prunes many branches, but its guaranteed worst-case work is O(N) with O(log N) stack depth for this balanced static tree. Dimensionality, point distribution, and ties strongly affect pruning. For a frequently changing point set, a rebuild policy or a different spatial index is needed. The code's returned distance is squared planar distance, not travel time or road-network distance.

Common Mistakes

  • Do not prune the far side when the split-plane distance equals the best candidate distance and tie-breaking matters.
  • Do not treat latitude and longitude as planar coordinates without an appropriate distance model.
  • Do not promise logarithmic nearest-query time in the worst case.
  • Do not move indexed points in place without rebuilding the tree.

Connected lessons

Apply this structure in the incident search project, then test the index decisions quiz.

Packed R-tree: search intersecting depot rectangles adds a related operation contract.

Spatial hash grids: move points between occupied cells adds another spatial query contract.

Point-region quadtrees: subdivide crowded cells adds another spatial query contract.

Morton ordering: decompose a grid window into code ranges adds another spatial query contract.

Vantage-point trees: nearest depots by a metric radius adds a distinct structure contract to compare.

Priority search trees: report events in a three-sided region adds a related structure with a different operation boundary.

Ball trees: prune exact nearest-depot search with radius bounds examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details