Spatial Data Structures

A balanced search tree is built on one assumption: the keys are totally ordered, so a single comparison sends a query left or right. Points in the plane break that assumption. There is no order on $R^{2}$ that makes both all points in this rectangle and the point nearest to $q$ cheap — sort by $x$ and two points far apart in $y$ end up adjacent; sort by $y$ and the reverse. A spatial data structure stores points so that geometry, not a one-dimensional key, guides the search: it partitions space into boxes, and a query that lands in one box can ignore every box it cannot possibly intersect.¹

Two partitions dominate. A quadtree splits each square into four equal quadrants, recursively, until each cell is simple. A k-d tree splits on one coordinate at a time — $x$ , then $y$ , then $x$ again — always at the median, so the tree stays balanced. The quadtree is splitting space into a fixed grid; the k-d tree is splitting the points into equal halves. That difference is what makes one degrade on clustered data while the other does not.

Quadtrees: recursive subdivision of space

A point quadtree stores a set of 2-D points by recursively cutting an axis-aligned square into four equal sub-squares — the four quadrants $N W$ , $N E$ , $S W$ , $S E$ — until every cell holds at most one point. Each internal node owns a square region and has up to four children, one per quadrant; each leaf holds at most one point (or, in a bucket variant, up to $b$ points before it splits).

A point quadtree over six points. The root square splits into four quadrants; any quadrant that still holds more than one point splits again. The dense lower-left clump forces extra levels of subdivision while the sparse upper area stays a single cell.

Subdividing quadrant by quadrant as points are inserted. Stage one is the empty root region. Stage two inserts two points into the lower-left, forcing one cut into four quadrants. Stage three adds a third point that collides in the lower-left sub-square, forcing a second cut there. Each cut appears only where a cell would otherwise hold more than one point.

Insert. To insert a point $p$ , descend from the root: at each internal node decide which of the four quadrants contains $p$ (two coordinate comparisons against the node's centre) and recurse into that child. When you reach an empty leaf, store $p$ there. If you reach a leaf that already holds a point $q$ , split that leaf into four quadrants and re-insert both $p$ and $q$ into the appropriate sub-quadrants — repeating until they fall into different cells. Search for an exact point is the same descent without the split.

Region query. To report every stored point inside a query rectangle $Q$ , descend from the root but prune: at a node owning square $S$ ,

if $S$ is disjoint from $Q$ , return nothing — that whole subtree is skipped;
if $S$ lies entirely inside $Q$ , report every point in the subtree;
otherwise $S$ straddles the boundary of $Q$ , so recurse into all four children.²

A region query (the dashed rectangle) against the quadtree's cells. A cell disjoint from the query is skipped whole (grey); a cell entirely inside the query reports all its points without further descent (green); a cell straddling the query boundary is recursed into (blue). Only the straddling cells cost any deeper work.

The pruning is what makes the query fast: a query touching a small corner of the plane visits only the handful of cells along that corner, not the whole tree.

That last sentence is also the quadtree's weakness. Because it always cuts a square exactly in half regardless of where the points lie, two points a distance $ε$ apart force $Θ (log (1/ ε))$ levels of subdivision before they separate — the tree depth depends on the coordinates, not just on $n$ . A tightly clustered set, or points near-collinear at fine scale, can drive the height far beyond $log n$ , so quadtree operations are $O (depth)$ with no worst-case bound tied to $n$ alone. Splitting the points in half instead of the space avoids this; that is the k-d tree.

point_quadtree.pypython

from __future__ import annotations

from collections.abc import Iterator
from typing import NamedTuple, Optional

class Point(NamedTuple):
  """
    A 2-D point: its x and y coordinates.\n
  """
  x: float
  y: float

class Rectangle(NamedTuple):
  """
    An axis-aligned rectangle given by its inclusive bounds.\n
    A point lies inside when its coordinates fall within both ranges.\n
  """
  min_x: float
  min_y: float
  max_x: float
  max_y: float

  def contains(self, point: Point) -> bool:
    """
      Whether `point` lies within this rectangle (boundaries included).\n
    """
    return (
      self.min_x <= point.x <= self.max_x
      and self.min_y <= point.y <= self.max_y
    )

  def covers(self, other: Rectangle) -> bool:
    """
      Whether this rectangle wholly contains `other`.\n
    """
    return (
      self.min_x <= other.min_x
      and self.min_y <= other.min_y
      and other.max_x <= self.max_x
      and other.max_y <= self.max_y
    )

  def intersects(self, other: Rectangle) -> bool:
    """
      Whether this rectangle and `other` share any area or boundary.\n
    """
    return not (
      other.min_x > self.max_x
      or other.max_x < self.min_x
      or other.min_y > self.max_y
      or other.max_y < self.min_y
    )

class QuadNode:
  """
    One quadtree node owning the square `region`.\n
    A leaf stores at most one `point` and has no children. An internal node\n
    has four children — north-west, north-east, south-west, south-east —\n
    splitting `region` at its centre, and carries no point of its own.\n
  """

  def __init__(self, region: Rectangle) -> None:
    self.region: Rectangle = region
    self.point: Optional[Point] = None
    self.north_west: Optional[QuadNode] = None
    self.north_east: Optional[QuadNode] = None
    self.south_west: Optional[QuadNode] = None
    self.south_east: Optional[QuadNode] = None

  @property
  def is_leaf(self) -> bool:
    """
      Whether this node has no children (so it may hold a point).\n
    """
    return self.north_west is None

  def quadrant_of(self, point: Point) -> QuadNode:
    """
      The child node whose quadrant contains `point`. Two comparisons\n
      against the region centre pick north/south and east/west.\n
    """
    # compare against the region centre to fix north/south and east/west.
    mid_x: float = (self.region.min_x + self.region.max_x) / 2
    mid_y: float = (self.region.min_y + self.region.max_y) / 2
    is_north: bool = point.y >= mid_y
    is_east: bool = point.x >= mid_x

    # pick the matching child (internal nodes only).
    if is_north:
      child = self.north_east if is_east else self.north_west
    else:
      child = self.south_east if is_east else self.south_west
    assert child is not None  # only called on internal nodes
    return child

  def subdivide(self) -> None:
    """
      Split this leaf's square into four equal quadrant children.\n
    """
    # split the square at its centre.
    mid_x: float = (self.region.min_x + self.region.max_x) / 2
    mid_y: float = (self.region.min_y + self.region.max_y) / 2

    # northern quadrants (upper half).
    self.north_west = QuadNode(
      Rectangle(self.region.min_x, mid_y, mid_x, self.region.max_y)
    )
    self.north_east = QuadNode(
      Rectangle(mid_x, mid_y, self.region.max_x, self.region.max_y)
    )

    # southern quadrants (lower half).
    self.south_west = QuadNode(
      Rectangle(self.region.min_x, self.region.min_y, mid_x, mid_y)
    )
    self.south_east = QuadNode(
      Rectangle(mid_x, self.region.min_y, self.region.max_x, mid_y)
    )

  def children(self) -> tuple[QuadNode, QuadNode, QuadNode, QuadNode]:
    """
      The four children in NW, NE, SW, SE order (internal nodes only).\n
    """
    assert (
      self.north_west is not None
      and self.north_east is not None
      and self.south_west is not None
      and self.south_east is not None
    )
    return (
      self.north_west,
      self.north_east,
      self.south_west,
      self.south_east,
    )

class PointQuadtree:
  """
    A set of 2-D points indexed by recursive subdivision of a square.\n
    Insert descends to the leaf the point belongs in and subdivides any leaf\n
    that already holds a different point. Membership is the same descent.\n
    `query_range` reports every stored point inside a query rectangle,\n
    pruning subtrees the rectangle cannot reach.\n
  """

  def __init__(self, boundary: Rectangle) -> None:
    """
      Build an empty quadtree spanning `boundary`. Every inserted point\n
      must fall within this square.\n
    """
    self.root: QuadNode = QuadNode(boundary)
    self._size: int = 0

  def insert(self, point: Point) -> bool:
    """
      Add `point` to the tree. Returns False if `point` lies outside the\n
      boundary or an identical point is already stored. Descend to the\n
      target leaf; subdivide and push both points down while a leaf would\n
      otherwise hold two distinct points.\n
    """
    if not self.root.region.contains(point):
      return False

    node: QuadNode = self.root
    while not node.is_leaf:
      node = node.quadrant_of(point)

    if node.point is None:  # empty leaf — store here.
      node.point = point
      self._size += 1
      return True
    if node.point == point:  # duplicate — nothing to do.
      return False

    # leaf already holds a different point: subdivide until they separate.
    resident: Point = node.point
    node.point = None
    while True:
      node.subdivide()
      target_for_new: QuadNode = node.quadrant_of(point)
      target_for_old: QuadNode = node.quadrant_of(resident)
      if target_for_new is not target_for_old:
        target_for_new.point = point
        target_for_old.point = resident
        self._size += 1
        return True
      node = target_for_new  # collided again — descend and split deeper.

  def __contains__(self, point: Point) -> bool:
    if not self.root.region.contains(point):
      return False

    # descend to the leaf the point would occupy and check it.
    node: QuadNode = self.root
    while not node.is_leaf:
      node = node.quadrant_of(point)
    return node.point == point

  def query_range(self, query: Rectangle) -> list[Point]:
    """
      Every stored point lying inside `query`. Skip a subtree whose square\n
      is disjoint from `query`; report a subtree whose square lies wholly\n
      inside `query`; otherwise recurse into all four children.\n
    """
    found: list[Point] = []

    def descend(node: QuadNode) -> None:
      if not query.intersects(node.region):
        return  # disjoint — prune the whole subtree.
      if query.covers(node.region):
        found.extend(self._points_in(node))  # contained — report all.
        return
      if node.is_leaf:
        if node.point is not None and query.contains(node.point):
          found.append(node.point)
        return
      for child in node.children():
        descend(child)

    descend(self.root)
    return found

  def _points_in(self, node: QuadNode) -> Iterator[Point]:
    """
      Every point stored in the subtree rooted at `node`.\n
    """
    if node.is_leaf:
      if node.point is not None:
        yield node.point
      return
    for child in node.children():
      yield from self._points_in(child)

  def __iter__(self) -> Iterator[Point]:
    return self._points_in(self.root)

  def __len__(self) -> int:
    return self._size

k-d trees: split on alternating coordinates at the median

A k-d tree ( $k$ -dimensional tree; here $k = 2$ ) is a binary tree in which each internal node splits the remaining points by a single coordinate, and the splitting coordinate cycles with depth: the root splits on $x$ , its children split on $y$ , the grandchildren on $x$ again, and so on. At each node the split is at the median value of the active coordinate, so each child receives half the points — which forces height $O (log n)$ no matter how the points are distributed.

Geometrically, each split is an axis-aligned line (a hyperplane in higher dimensions): a vertical cut at the root, horizontal cuts at the next level, vertical again below that. The cuts nest, carving the plane into rectangular cells — one per leaf — each containing a single point.

A k-d tree and the matching partition of the plane. The root splits on

x

at the median (a vertical line); the next level splits on

y

(horizontal lines); the level below splits on

x

again. Each tree node is one axis-aligned cut, and the leaves correspond to the cells of the partition.

Build. Given all $n$ points, build top-down. At depth $d$ pick the active coordinate $a = d mod 2$ , find the median of the points by coordinate $a$ (linear time via quickselect, or by pre-sorting), store it at the node, and recurse on the two halves. The recurrence $T (n) = 2 T (n /2) + O (n)$ solves to $O (n log n)$ , and because every split is at the median the resulting tree has height $⌈ log_{2} n ⌉$ .

Building a k-d tree by alternating the split axis. Stage one cuts on

x

at the median (vertical line), splitting the points into a left and a right half. Stage two cuts each half on

y

at its own median (horizontal lines). The split axis cycles

x

then

y

then

x

, halving the point set at every level.

Range search. Reporting the points in a query rectangle $Q$ works just like the quadtree's, pruning on the cell each node owns: skip a subtree whose region is disjoint from $Q$ , report a subtree whose region lies wholly inside $Q$ , and recurse otherwise. A range query touching $t$ output points costs $O (n + t)$ in the plane — the $n$ comes from the cells the query boundary crosses.³

Nearest-neighbour search with branch-and-bound

The k-d tree's signature query is nearest neighbour: given a query point $q$ , find the stored point closest to it. The naive scan is $O (n)$ ; the k-d tree does it in $O (log n)$ expected time on well-distributed data by branch-and-bound — descend to the leaf $q$ belongs in to get a first candidate, then unwind, only entering the other side of a split if a closer point could possibly hide there.

The pruning test is geometric. At a node splitting coordinate $a$ at value $m$ , the far subtree lies entirely on the far side of the line $a = m$ . The closest that any far-side point could be to $q$ is the perpendicular distance from $q$ to that line, $∣ q_{a} - m ∣$ . If that distance already exceeds the best distance found so far, no point over there can beat the current best — so we skip the entire far subtree. Otherwise the far side might hold something closer, and we recurse into it too.

Algorithm 1:

\textsc{NearestNeighbor}(v, q, best)

— closest stored point to

q

1
if $v = \text{nil}$ then return $best$
2
if $\dist(q, point(v)) < \dist(q, best)$ then
3
$best \gets point(v)$
this node beats the incumbent
4
$a \gets depth(v) \bmod 2$
active split coordinate
5
if $q_a < value(v)$ then
6
$near \gets left(v),\ far \gets right(v)$
7
else
8
$near \gets right(v),\ far \gets left(v)$
9
$best \gets \textsc{NearestNeighbor}(near, q, best)$
descend the likely side first
10
if $|q_a - value(v)| < \dist(q, best)$ then
splitting line within reach?
11
$best \gets \textsc{NearestNeighbor}(far, q, best)$
only then check the far side
12
return $best$

Visiting the near side first is what makes the bound tight: it usually finds a good candidate immediately, so the $∣ q_{a} - v a l u e (v) ∣$ test fails at most far-side nodes and prunes them away. The same branch-and-bound extends to $k$ nearest neighbours (keep a bounded max-heap of the best $k$ , prune against its worst distance) and to approximate nearest neighbour (multiply the bound by a slack factor to prune more aggressively).

A worked query. Take the five points $A (2, 3)$ , $B (5, 4)$ , $C (9, 6)$ , $D (4, 7)$ , $E (8, 1)$ built into a k-d tree with $B (5, 4)$ at the root (split on $x$ ), $A$ and $D$ in the left subtree ( $x < 5$ ), $E$ and $C$ in the right ( $x \geq 5$ ). Query $q = (6, 3)$ .

Root $B (5, 4)$ , split on $x = 5$ . Distance $(6 - 5)^{2} + (3 - 4)^{2} = 2 \approx 1.41$ ; set $b es t = B$ , $r = 1.41$ . Since $q_{x} = 6 \geq 5$ , the near side is the right subtree; descend there first.
Right child $E (8, 1)$ , split on $y = 1$ . Distance $4 + 4 = 8 \approx 2.83 > r$ , so $E$ does not improve $b es t$ . Since $q_{y} = 3 \geq 1$ , the near child is $E$ 's right subtree holding $C$ .
$C (9, 6)$ , a leaf. Distance $9 + 9 = 18 \approx 4.24 > r$ ; no improvement. Unwind to $E$ : its far subtree lies below $y = 1$ , at perpendicular distance $∣ q_{y} - 1∣ = 2 > r = 1.41$ — pruned.
Unwind to the root. Its far subtree is the left side, $x < 5$ , at perpendicular distance $∣ q_{x} - 5∣ = 1 < r = 1.41$ — the circle crosses the splitting line, so the left side could hide something closer and must be searched. It holds $A (2, 3)$ (distance $4$ ) and $D (4, 7)$ (distance $4 + 16 \approx 4.47$ ), neither beating $r$ .

The answer is $B (5, 4)$ at distance $2$ . The search touched $B, E, C$ , and the left subtree; the bound at step 3 pruned $E$ 's lower half, which a linear scan would have to examine.

Branch-and-bound on the tree itself. The search first descends the near side at each split (solid blue) to the leaf

q

belongs in, fixing a first candidate. It then unwinds: a far subtree whose splitting line lies beyond the current radius is pruned (red, crossed out); a far subtree within the radius is searched (green check).

Nearest-neighbour pruning. The descent finds a candidate at distance

r

(the circle). At a split line, the far subtree is entered only if the line lies within

r

q

— i.e. the circle crosses it. Here the dashed line is farther than

r

, so that whole side is pruned; the solid line is within

r

, so it must be searched.

The pruning is only effective in low dimensions. As $k$ grows the perpendicular distance $∣ q_{a} - m ∣$ to any single splitting line shrinks relative to the typical point-to-point distance, so the bound rarely fires and the search degrades toward the $O (n)$ scan — the curse of dimensionality. Beyond roughly a dozen dimensions, exact k-d nearest neighbour offers little over brute force, and practitioners switch to approximate methods. In two or three dimensions, though, the k-d tree is the standard answer.

kd_tree.pypython

import heapq
from collections.abc import Iterator, Sequence
from typing import NamedTuple, Optional

# the plane is two-dimensional; split axes cycle x (0), y (1), x (0), ...
DIMENSIONS: int = 2

class Point(NamedTuple):
  """
    A 2-D point: its x and y coordinates.\n
  """
  x: float
  y: float

  def coordinate(self, axis: int) -> float:
    """
      The value of this point on `axis` — x when axis is 0, y when 1.\n
    """
    return self.x if axis == 0 else self.y

class Rectangle(NamedTuple):
  """
    An axis-aligned query rectangle given by its inclusive bounds.\n
  """
  min_x: float
  min_y: float
  max_x: float
  max_y: float

  def contains(self, point: Point) -> bool:
    """
      Whether `point` lies within this rectangle (boundaries included).\n
    """
    return (
      self.min_x <= point.x <= self.max_x
      and self.min_y <= point.y <= self.max_y
    )

def squared_distance(first: Point, second: Point) -> float:
  """
    The squared Euclidean distance between two points. Squared because\n
    comparing distances never needs the square root, which only adds cost\n
    and rounding error.\n
  """
  delta_x: float = first.x - second.x
  delta_y: float = first.y - second.y
  return delta_x * delta_x + delta_y * delta_y

class KDNode:
  """
    One k-d tree node: the `point` stored here, the `axis` it splits on,\n
    and links to the left and right subtrees. Points whose coordinate on\n
    `axis` is below the node's fall left; the rest fall right.\n
  """

  def __init__(self, point: Point, axis: int) -> None:
    self.point: Point = point
    self.axis: int = axis
    self.left: Optional[KDNode] = None
    self.right: Optional[KDNode] = None

  def __repr__(self) -> str:
    return f"KDNode({self.point!r}, axis={self.axis})"

class KDTree:
  """
    A balanced 2-D point index supporting range search and (k-)nearest\n
    neighbour queries. Built once from a fixed point set by repeatedly\n
    splitting on the median of the cycling coordinate.\n
  """

  def __init__(self, points: Sequence[Point]) -> None:
    """
      Build the tree from `points`. Duplicate points are kept. The root\n
      splits on x, the next level on y, and so on, each at the median of\n
      the active coordinate, giving height O(log n) and O(n log n) build.\n
    """
    self._size: int = len(points)
    self.root: Optional[KDNode] = self._build(list(points), depth=0)

  def _build(self, points: list[Point], depth: int) -> Optional[KDNode]:
    """
      Recursively build a subtree from `points`. Sort by the active\n
      coordinate, take the median as this node, and recurse on the halves.\n
    """
    if not points:
      return None

    # sort by the active coordinate and pick the median as this node.
    axis: int = depth % DIMENSIONS
    points.sort(key=lambda point: point.coordinate(axis))
    median: int = len(points) // 2

    # recurse on the lower and upper halves to form the subtrees.
    node: KDNode = KDNode(points[median], axis)
    node.left = self._build(points[:median], depth + 1)
    node.right = self._build(points[median + 1:], depth + 1)
    return node

  def __contains__(self, target: Point) -> bool:
    def search(node: Optional[KDNode]) -> bool:
      if node is None:
        return False
      if node.point == target:
        return True

      split: float = node.point.coordinate(node.axis)
      probe: float = target.coordinate(node.axis)
      # strictly-less goes left, strictly-greater goes right; an exact tie
      # on the split coordinate could sit on either side, so check both.
      if probe < split:
        return search(node.left)
      if probe > split:
        return search(node.right)
      return search(node.left) or search(node.right)

    return search(self.root)

  def query_range(self, query: Rectangle) -> list[Point]:
    """
      Every stored point inside `query`. At each node, descend a side only\n
      when the splitting line allows some of its region to fall within the\n
      query band on the active axis — pruning the rest.\n
    """
    found: list[Point] = []

    def descend(node: Optional[KDNode]) -> None:
      if node is None:
        return
      if query.contains(node.point):
        found.append(node.point)

      split: float = node.point.coordinate(node.axis)
      low: float = query.min_x if node.axis == 0 else query.min_y
      high: float = query.max_x if node.axis == 0 else query.max_y

      # the left subtree holds coordinates at or below the split (ties at
      # the median may sit left), so visit it whenever the query band
      # reaches the split, and the right whenever the band reaches above.
      if low <= split:
        descend(node.left)
      if split <= high:
        descend(node.right)

    descend(self.root)
    return found

  def nearest(self, query: Point) -> Optional[Point]:
    """
      The stored point closest to `query`, or None if the tree is empty.\n
      Branch-and-bound: descend to the leaf `query` belongs in for a first\n
      candidate, then unwind, entering a far subtree only when the\n
      splitting line lies nearer than the best distance found so far.\n
    """
    neighbours: list[Point] = self.k_nearest(query, 1)
    return neighbours[0] if neighbours else None

  def k_nearest(self, query: Point, count: int) -> list[Point]:
    """
      The `count` stored points closest to `query`, nearest first.\n
      Keep a bounded max-heap of the best candidates keyed by negated\n
      distance; prune a far subtree once the heap is full and the\n
      splitting line is farther than the heap's worst distance.\n
    """
    if count <= 0 or self.root is None:
      return []

    # max-heap of (-squared_distance, tie_breaker, point); the largest
    # distance sits at the top so we can evict it when a closer point wins.
    best: list[tuple[float, int, Point]] = []
    tie_breaker: int = 0

    def consider(point: Point) -> None:
      nonlocal tie_breaker
      distance: float = squared_distance(query, point)
      if len(best) < count:
        heapq.heappush(best, (-distance, tie_breaker, point))
        tie_breaker += 1
      elif -distance > best[0][0]:  # closer than the current worst.
        heapq.heapreplace(best, (-distance, tie_breaker, point))
        tie_breaker += 1

    def worst_distance() -> float:
      """
        The squared distance of the current farthest candidate, or
        infinity while the heap still has room for more.
      """
      if len(best) < count:
        return float("inf")
      return -best[0][0]

    def descend(node: Optional[KDNode]) -> None:
      if node is None:
        return
      consider(node.point)

      offset: float = (
        query.coordinate(node.axis) - node.point.coordinate(node.axis)
      )
      near: Optional[KDNode] = node.left if offset < 0 else node.right
      far: Optional[KDNode] = node.right if offset < 0 else node.left

      descend(near)  # the side query falls in — likely holds the best.
      # only cross the splitting line if a closer point could hide beyond.
      if offset * offset < worst_distance():
        descend(far)

    descend(self.root)
    ordered: list[tuple[float, int, Point]] = sorted(
      best, key=lambda entry: -entry[0]
    )
    return [point for _, _, point in ordered]

  def __iter__(self) -> Iterator[Point]:
    def walk(node: Optional[KDNode]) -> Iterator[Point]:
      if node is not None:
        yield node.point
        yield from walk(node.left)
        yield from walk(node.right)

    return walk(self.root)

  def height(self) -> int:
    """
      The number of edges on the longest root-to-leaf path; -1 when empty.\n
      Median splitting keeps this at floor(log2 n).\n
    """

    def depth(node: Optional[KDNode]) -> int:
      if node is None:
        return -1
      return 1 + max(depth(node.left), depth(node.right))

    return depth(self.root)

  def __len__(self) -> int:
    return self._size

Range trees: faster orthogonal range reporting

The k-d tree answers a rectangle query in $O (n + t)$ , and the $n$ term hurts when the query is thin and reports few points. A range tree trades space for a sharper query bound: $O (log^{2} n + t)$ in the plane, at a cost of $O (n log n)$ storage instead of $O (n)$ . It is built by nesting one balanced search tree inside another.

A rectangle query $[x_{1}, x_{2}] \times [y_{1}, y_{2}]$ runs in two stages. First, search the primary ( $x$ ) tree for the split node where the paths to $x_{1}$ and $x_{2}$ diverge; the points with $x \in [x_{1}, x_{2}]$ are precisely those in a set of $O (log n)$ canonical subtrees hanging off the two search paths. Rather than walk each subtree, consult its associated $y$ -tree and report the points whose $y$ falls in $[y_{1}, y_{2}]$ — a 1-D range query costing $O (log n + t_{v})$ . Summed over the $O (log n)$ canonical subtrees, the query is $O (log^{2} n + t)$ .

A 2-D range tree. The primary tree (left) is a balanced BST on

x

. The query

[x_{1}, x_{2}]

selects

O (log n)

canonical subtrees along the two search paths (shaded). Each such subtree carries an associated BST on

y

(right); the

[y_{1}, y_{2}]

query runs inside it, so only points in the rectangle are reported.

Fractional cascading removes one log factor. If the associated structures are linked so that a position found in one $y$ -list transfers in $O (1)$ to the next, the $O (log n)$ repeated $y$ -searches collapse to a single $O (log n)$ search plus $O (1)$ hops, giving $O (log n + t)$ per query. The construction generalizes to $d$ dimensions at $O (n log^{d - 1} n)$ space and $O (log^{d - 1} n + t)$ query time — the standard answer when range reporting must be fast and the points are static.

Interval trees: which intervals contain a point

The structures so far index points. A different question indexes intervals on the line: given $n$ intervals $[l_{i}, r_{i}]$ and a query value $q$ , report every interval that contains $q$ (a stabbing query). This shows up in scheduling (which reservations are live at time $q$ ), computational geometry (segment intersection), and genome analysis (which features span a locus).

A stabbing query for $q$ descends from the root. At a node with center $m$ , every interval crossing $m$ is a candidate:

if $q < m$ , scan the node's list sorted by left endpoint from the smallest, reporting each interval with $l_{i} \leq q$ and stopping at the first that fails (all later ones start even further right), then recurse left;
if $q > m$ , scan the list sorted by right endpoint from the largest, reporting each with $r_{i} \geq q$ , then recurse right;
if $q = m$ , every stored interval at the node contains $q$ ; report them all.

An interval-tree stabbing query. The root centre

m

holds the intervals crossing it, kept sorted by both endpoints. For a query

q < m

the left-endpoint list is scanned from the left, reporting intervals whose left end is

\leq q

and stopping at the first miss; the search then recurses into the left subtree (

< m

Each node scan reports $k_{v}$ hits in $O (k_{v} + 1)$ time, and the descent visits $O (log n)$ nodes, so a stabbing query costs $O (log n + t)$ for $t$ reported intervals. Build is $O (n log n)$ and space is $O (n)$ . When the query is itself an interval and you want every stored interval overlapping it, the same tree works with an overlap test at each node. Skiena's segment-tree and interval-tree treatments cover the reporting variants in full.¹

Choosing a spatial structure

These structures index geometry so that a query prunes what it cannot reach; they differ in what they cut and what they index.

Quadtree. Splits space into a fixed quadrant grid. Simple, supports easy dynamic insert/delete, and natural for images and uniformly-spread data. But its depth tracks the coordinates of the points, so clustered or near-coincident data blows up the height — no $O (log n)$ guarantee.
k-d tree. Splits the points at the median on alternating axes, forcing height $O (log n)$ regardless of distribution. Build is $O (n log n)$ , range search $O (n + t)$ , nearest neighbour $O (log n)$ expected in low dimensions. Less natural to update incrementally (medians shift), and it succumbs to the curse of dimensionality in high $k$ .
Range tree. Nests a $y$ -tree inside an $x$ -tree to answer rectangle reporting queries in $O (log^{2} n + t)$ (or $O (log n + t)$ with fractional cascading), at $O (n log n)$ space. Best when queries are frequent, thin, and the point set is static.
Interval tree. Indexes intervals rather than points, answering stabbing and overlap queries in $O (log n + t)$ with $O (n)$ space — the tool when the data are ranges and the question is what covers $q$ .

In short: the quadtree halves the space, the k-d tree halves the data. Use the quadtree when the points are well-spread and updates must be cheap; the k-d tree when a balance guarantee and fast nearest-neighbour queries matter in two or three dimensions; the range tree when range reporting on static points must be as fast as possible; and the interval tree when the objects themselves are intervals.

Spatial indexing at scale

The structures here are in-memory and low-dimensional; production spatial systems push past both limits.

R-trees and the database index. The R-tree (Guttman, 1984) is the spatial analogue of the B-tree: each node stores the bounding rectangles of its children and fans out wide so the tree is short and disk-friendly. It is what backs SPATIAL INDEX in PostGIS, SQLite's R*Tree module, and most GIS systems, indexing not just points but arbitrary shapes by their bounding boxes. Its refinements, the R*-tree and bulk-loaded STR-tree, tune how rectangles are grouped to minimize overlap, the spatial equivalent of keeping a B-tree's nodes full.

Trading exactness in high dimensions. The k-d tree's curse of dimensionality is real: past roughly $10$ - $20$ dimensions, nearest-neighbour search degrades to scanning almost everything. The standard workaround is approximate nearest neighbour. Locality-sensitive hashing (Indyk and Motwani, 1998) hashes nearby points to the same bucket with high probability; graph-based indexes like HNSW (Malkov and Yashunin, 2016) navigate a small-world graph. Both are what vector databases use to search millions of embeddings in milliseconds.

Flattening space to one dimension. A different trick maps 2-D or 3-D points onto a single space-filling curve, Z-order (Morton) or Hilbert, so that points close in space are usually close along the curve. Then an ordinary 1-D B-tree index answers spatial range queries approximately, which is how many key-value stores add geospatial lookups without a dedicated spatial tree. In graphics, the same recursive-subdivision idea becomes the bounding volume hierarchy that makes ray tracing tractable.⁴

Takeaways

Points in the plane have no single natural order, so we index them by partitioning space into boxes and pruning boxes a query cannot reach.
A quadtree recursively splits each square into four equal quadrants until cells are simple. Insert descends and splits a full leaf; region query prunes subtrees disjoint from / contained in the query rectangle.
The quadtree's depth follows the geometry of the data: sparse regions stay shallow, clustered points force deep subdivision — so it has no worst-case $O (log n)$ bound.
A k-d tree splits the points on alternating coordinates at the median, forcing height $O (log n)$ . Build $O (n log n)$ ; range search $O (n + t)$ .
Nearest neighbour uses branch-and-bound: descend to the candidate leaf, then enter the far side of a split only when the perpendicular distance to the splitting line is below the best distance found.
k-d pruning fails in high dimensions (curse of dimensionality); both point structures work best in 2-D and 3-D.
A range tree nests a $y$ -tree in an $x$ -tree for orthogonal range reporting in $O (log^{2} n + t)$ ( $O (log n + t)$ with fractional cascading), using $O (n log n)$ space.
An interval tree indexes intervals, not points, and answers stabbing queries (which intervals contain $q$ ) in $O (log n + t)$ with $O (n)$ space.

Skiena, §12.6 — Kd-Trees: alternating-axis median splits, range search, and nearest-neighbour via branch-and-bound, with the curse-of-dimensionality caveat. ↩ ↩²
Erickson, Ch. — Data Structures: recursive space-partitioning trees and the geometry of pruning a query against a subtree's bounding box. ↩
CLRS, Ch. 33 — Computational Geometry: axis-aligned subdivision and the recurrence behind balanced spatial partitions. ↩
Guttman, R-trees: a dynamic index structure for spatial searching (1984); Indyk & Motwani, Approximate nearest neighbors (LSH, 1998); Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using HNSW graphs (2016). ↩