Orthogonal Range Searching: Kd-Trees and Range Trees

Orthogonal Range Searching: Kd-Trees and Range Trees

Part 10 asked whether a point satisfies a small collection of slanted inequalities. This part changes the workload: preprocess many points once, then answer many axis-aligned window queries. Given a set $P$ of $n$ points and a rectangle

$$Q=[x_0,x_1]\times[y_0,y_1],$$

report every $p\in P\cap Q$. Axis alignment looks restrictive, but it models map viewports, database filters, collision broad phases, and the first stage of many spatial joins. It also exposes a central data-structure tradeoff: a small index that prunes approximately, or a larger layered index whose query guarantee is sharper.

Throughout, let $k=|P\cap Q|$. A reporting bound must include $k$: merely writing the answer costs $\Omega(k)$. We therefore separate search overhead from output cost and seek bounds such as $O(\log n+k)$, not the impossible $O(\log n)$ for arbitrarily large output.

Start in One Dimension

Store sorted keys $a_0\le\cdots\le a_{n-1}$. For the closed interval $[L,R]$, binary-search for

• lower_bound(L): the first index $i$ with $a_i\ge L$;
• upper_bound(R): the first index $j$ with $a_j>R$.

Then the answer is exactly the half-open array slice $a[i:j]$. Searching costs $O(\log n)$ and emitting the $k=j-i$ keys costs $O(k)$. This tiny example establishes the pattern used throughout the chapter: locate a small number of canonical subsets whose disjoint union is the answer, then enumerate them.

Boundary conventions are not bookkeeping. This page treats stored points as a multiset and query boxes as closed. Thus duplicate points are reported with their stored IDs, and points on any side or corner count. Internally, half-open index ranges such as [i, j) avoid ambiguity without changing the geometric contract. Empty boxes ($x_0>x_1$ or $y_0>y_1$) return no points. If an application wants half-open geometric boxes—for example, to tile space without double-counting—it must change every containment and pruning comparison consistently.

Kd-Trees: Partition the Space

A two-dimensional kd-tree recursively partitions the point set. At even depths, choose a median by $x$; at odd depths, choose a median by $y$. Store the median point at the node and recurse on the points before and after it. Alternating axes prevents the tree from repeatedly making only vertical or only horizontal cuts. Median selection gives height $O(\log n)$ for a static set; sorting independently at every level gives a simple $O(n\log^2 n)$ build, while presorted lists or linear-time selection can achieve $O(n\log n)$.

Each node represents a cell: the region left by all cuts on the root-to-node path. It is often useful to store the bounding box of the node's actual subtree points, which may be tighter than that cell. A query proceeds by geometric pruning:

1. If the subtree box is disjoint from $Q$, stop.
2. If it lies completely inside $Q$, report the whole subtree (or add its stored count).
3. Otherwise, test the node point and recurse into both children that may intersect $Q$.

The pruning is exact, not heuristic. A disjoint subtree box cannot hide an answer; a contained box cannot hide a non-answer. Equality must match the closed-box policy: boxes are disjoint only when max_x < x0, min_x > x1, max_y < y0, or min_y > y1. Using <= here would incorrectly prune boundary points.

For fixed dimension $d$, a balanced kd-tree uses $O(n)$ space. A standard orthogonal reporting query in 2D takes $O(\sqrt n+k)$ in the worst case; in fixed $d$, the typical bound is $O(n^{1-1/d}+k)$. Its practical strength is different: compact storage, simple traversal, and effective pruning when query windows are selective and data are reasonably distributed. Thin adversarial windows can cross many cells while containing almost nothing.

A Queryable Python Scaffold

This implementation stores a tight subtree box and preserves duplicate records by attaching an ID. It builds with repeated sorting for clarity, so its preprocessing is not the optimal construction.

from dataclasses import dataclass

@dataclass
class Node:
    point: tuple          # (x, y, id)
    axis: int
    left: object = None
    right: object = None
    box: tuple = None     # (xmin, xmax, ymin, ymax), all inclusive

def build_kd(points, depth=0):
    if not points:
        return None
    axis = depth % 2
    pts = sorted(points, key=lambda p: (p[axis], p[1-axis], p[2]))
    m = len(pts) // 2
    node = Node(pts[m], axis,
                build_kd(pts[:m], depth + 1),
                build_kd(pts[m+1:], depth + 1))
    boxes = [(node.point[0], node.point[0], node.point[1], node.point[1])]
    boxes += [c.box for c in (node.left, node.right) if c]
    node.box = (min(b[0] for b in boxes), max(b[1] for b in boxes),
                min(b[2] for b in boxes), max(b[3] for b in boxes))
    return node

def range_report(root, query):
    x0, x1, y0, y1 = query
    if x0 > x1 or y0 > y1:
        return []
    out = []
    def visit(node):
        if node is None:
            return
        xmin, xmax, ymin, ymax = node.box
        if xmax < x0 or x1 < xmin or ymax < y0 or y1 < ymin:
            return
        x, y, point_id = node.point
        if x0 <= x <= x1 and y0 <= y <= y1:
            out.append((x, y, point_id))
        visit(node.left)
        visit(node.right)
    visit(root)
    return out

points = [(2, 5, "a"), (7, 3, "b"), (2, 5, "duplicate"),
          (4, 4, "c"), (9, 8, "d")]
print(range_report(build_kd(points), (2, 7, 3, 5)))

The code could bulk-report a fully contained subtree, but doing so still costs proportional to that subtree's output. For counting, add size to each node and return it immediately on containment.

Range Trees: Layer Canonical Subsets

A 2D range tree starts with a balanced binary search tree on $x$. Every node $v$ stores an associated catalog $A_v$: all points in its subtree sorted by $y$. The primary tree turns $[x_0,x_1]$ into $O(\log n)$ disjoint canonical subtrees. For each such subtree, binary searches in $A_v$ isolate the points with $y\in[y_0,y_1]$.

A balanced primary tree has $O(\log n)$ levels, and each point appears in one catalog per level, so preprocessing and space are $O(n\log n)$. There are $O(\log n)$ canonical nodes; two binary searches per catalog yield $O(\log^2 n+k)$ query time. The structure earns that extra space by replacing the kd-tree's $\sqrt n$ worst-case overhead with polylogarithmic overhead.

The repeated searches are conspicuously similar. Fractional cascading links neighboring catalogs so one initial binary search can be translated into positions in all relevant catalogs, reducing the 2D range-tree query to $O(\log n+k)$ while preserving $O(n\log n)$ space. The deep dive develops those bridge pointers and explains why sampling every other item is enough.

Dimensions and General Point Sets

Neither structure assumes integer coordinates, a grid, or unique positions. It assumes only a total, consistent coordinate order; stable IDs resolve equal coordinates. NaNs are not ordered and should be rejected. Exact integers are ideal, while floating-point coordinates are safe only if construction and queries use the same comparison semantics. Do not introduce an epsilon into tree ordering: a non-transitive comparator can invalidate the tree.

In $d$ dimensions, kd-trees cycle through $d$ axes and retain linear space, but worst-case query overhead degrades to $O(n^{1-1/d})$. A layered range tree recursively adds a range tree for another coordinate, using $O(n\log^{d-1}n)$ space and preprocessing and answering in $O(\log^d n+k)$ without cascading; refinements remove logarithmic factors. This is the curse of dimensionality in structural form: strong exact queries require more layers, while compact partitions lose pruning power.

These are static bounds. Rebuilding after every insertion can dominate query savings; dynamic variants add balancing, catalog-update costs, and usually extra logarithmic factors. Also consider memory locality: a flat kd-tree often outperforms a pointer-heavy range tree on moderate data despite the weaker asymptotic query bound.

Choosing the Index

Estimate $n$, query frequency, expected $k$, dimension, update rate, and memory budget before choosing. Use a sorted array for one coordinate. Prefer a kd-tree when space and engineering simplicity matter, dimensions are small, and typical distributions—not adversarial worst cases—drive performance. Prefer a range tree when data are static, queries are numerous, and predictable orthogonal-query latency justifies duplicated catalogs. Use counting augmentations when only cardinality is needed, and always benchmark with thin, empty, boundary-touching, duplicate-heavy, and full-domain windows.

The next problem changes the stored objects, not merely the query box. Part 12 indexes intervals and segments for stabbing, windowing, intersection, and three-sided queries. The canonical-subset idea survives, but interval trees, segment trees, and priority search trees choose subsets according to how extended objects cross query boundaries.