---
title: Spatial Data Structures
module: Data Structures
moduleNumber: 4
lessonNumber: 8
order: 408
summary: |
  A balanced BST orders keys on a line, but points in the plane have no single
  natural order. Quadtrees subdivide space recursively into quadrants; k-d trees
  split on alternating coordinates at the median. Both make range and
  nearest-neighbour queries fast by carving the plane into boxes a query can
  prune away. Range trees nest a y-tree in an x-tree for fast orthogonal range
  reporting; interval trees index intervals to answer stabbing queries.
topics: [Spatial Data Structures]
sources:
  - book: Skiena
    ref: "§12.6 — Kd-Trees"
  - book: CLRS
    ref: "Ch. 33 — Computational Geometry"
  - book: Erickson
    ref: "Ch. — Data Structures / Geometry"
practice:
  - title: 'K Closest Points to Origin'
    slug: k-closest-points-to-origin
    difficulty: Medium
  - title: 'Count of Smaller Numbers After Self'
    slug: count-of-smaller-numbers-after-self
    difficulty: Hard
  - title: 'Max Points on a Line'
    slug: max-points-on-a-line
    difficulty: Hard
  - title: 'The Skyline Problem'
    slug: the-skyline-problem
    difficulty: Hard
---

A [balanced search tree](/algorithms/data-structures/balanced-trees) 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 $\mathbb{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.[^skiena-kd]

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 $NW$, $NE$,
$SW$, $SE$ — 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).

> **Definition (Point quadtree).** A point quadtree over a square region $R$ is a
> tree where each node owns an axis-aligned square. A leaf holds at most one
> point. An internal node's square is divided at its centre into four equal
> quadrants $NW$, $NE$, $SW$, $SE$, each the region of one child.

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % outer square
  \draw[thick] (0,0) rectangle (5,5);
  % first split: full cross
  \draw[acc, thick] (2.5,0) -- (2.5,5);
  \draw[acc, thick] (0,2.5) -- (5,2.5);
  % subdivide the SW quadrant (dense)
  \draw[acc] (1.25,0) -- (1.25,2.5);
  \draw[acc] (0,1.25) -- (2.5,1.25);
  % subdivide the SW-SW sub-quadrant once more
  \draw[acc] (0.625,0) -- (0.625,1.25);
  \draw[acc] (0,0.625) -- (1.25,0.625);
  % points
  \fill[acc] (0.35,0.35) circle (2.2pt);
  \fill[acc] (0.95,0.40) circle (2.2pt);
  \fill[acc] (1.70,1.80) circle (2.2pt);
  \fill[acc] (3.60,1.20) circle (2.2pt);
  \fill[acc] (3.80,3.90) circle (2.2pt);
  \fill[acc] (1.50,4.10) circle (2.2pt);
  \node[anchor=south west] at (0.05,5.05) {root region};
\end{tikzpicture}
$$

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize, dot/.style={fill=acc, circle, inner sep=1.6pt}]
  \definecolor{acc}{HTML}{2348F2}
  % --- stage one: empty root ---
  \begin{scope}
    \draw[thick] (0,0) rectangle (2.6,2.6);
    \node[anchor=south] at (1.3,2.7) {one cell};
  \end{scope}
  % --- stage two: two points, one split ---
  \begin{scope}[xshift=38mm]
    \draw[thick] (0,0) rectangle (2.6,2.6);
    \draw[acc, thick] (1.3,0) -- (1.3,2.6);
    \draw[acc, thick] (0,1.3) -- (2.6,1.3);
    \node[dot] at (0.55,0.55) {};
    \node[dot] at (1.85,1.95) {};
    \node[anchor=south] at (1.3,2.7) {one split};
  \end{scope}
  % --- stage three: third point forces a deeper split ---
  \begin{scope}[xshift=76mm]
    \draw[thick] (0,0) rectangle (2.6,2.6);
    \draw[acc, thick] (1.3,0) -- (1.3,2.6);
    \draw[acc, thick] (0,1.3) -- (2.6,1.3);
    \draw[acc] (0.65,0) -- (0.65,1.3);
    \draw[acc] (0,0.65) -- (1.3,0.65);
    \node[dot] at (0.35,0.40) {};
    \node[dot] at (0.95,0.95) {};
    \node[dot] at (1.85,1.95) {};
    \node[anchor=south] at (1.3,2.7) {deeper split};
  \end{scope}
\end{tikzpicture}
$$

**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.[^erickson-ds]

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize, dot/.style={fill=black, circle, inner sep=1.4pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % four top quadrants of the region
  \draw[thick] (0,0) rectangle (5,5);
  \draw[thick] (2.5,0) -- (2.5,5);
  \draw[thick] (0,2.5) -- (5,2.5);
  % shade quadrants by their relation to the query
  \fill[black] (2.5,2.5) rectangle (5,5);        % NE skipped
  \fill[green!14]  (0,0) rectangle (2.5,2.5);        % SW fully inside
  \fill[acc!14]   (0,2.5) rectangle (2.5,5);         % NW straddles
  \fill[acc!14]   (2.5,0) rectangle (5,2.5);         % SE straddles
  % redraw grid over fills
  \draw[thick] (0,0) rectangle (5,5);
  \draw[thick] (2.5,0) -- (2.5,5);
  \draw[thick] (0,2.5) -- (5,2.5);
  % the query rectangle
  \draw[acc, very thick, dashed] (0.6,0.6) rectangle (3.4,3.4);
  \node[acc, anchor=north, font=\scriptsize] at (2.5,-0.15) {query rectangle};
  % a few points
  \node[dot] at (1.2,1.4) {};
  \node[dot] at (1.9,0.9) {};
  \node[dot] at (3.9,3.9) {};
  \node[dot] at (0.9,3.05) {};
  % labels
  \node[green, font=\scriptsize] at (1.45,1.85) {inside};
  \node[black, font=\footnotesize] at (3.75,4.6) {\texttt{skipped}};
  \node[acc, font=\scriptsize] at (1.55,4.6) {straddle};
  \node[acc, font=\scriptsize] at (4.0,1.55) {straddle};
\end{tikzpicture}
$$

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.

> **Intuition.** The quadtree is a _spatial_ index, not a balanced one. Its shape
> follows the **geometry of the data**, not its cardinality: the depth in any
> region is however many halvings it takes to separate the points there. Sparse
> regions stay shallow; dense clumps grow deep.

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
$\varepsilon$ apart force $\Theta(\log(1/\varepsilon))$ 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(\text{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.

::impl{algo="point_quadtree"}

## 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.

> **Definition (k-d tree).** A k-d tree over $n$ points in $\mathbb{R}^k$ is a
> binary tree where a node at depth $d$ splits on coordinate $a = d \bmod k$ at a
> value $m$: its left subtree holds points with coordinate $a$ less than $m$, its
> right subtree the rest. Choosing $m$ as the median of the active coordinate
> balances the tree at height $O(\log n)$.

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.

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{accmid}{HTML}{6A82F6}
  \definecolor{acclo}{HTML}{A7B5FB}
  % --- left: the partition of the plane ---
  \begin{scope}
    \draw[thick] (0,0) rectangle (4.6,4.6);
    % root vertical split on x
    \draw[acc, very thick] (2.3,0) -- (2.3,4.6);
    \node[acc, anchor=south] at (2.3,4.65) {split on $x$};
    % second level horizontal splits on y
    \draw[accmid, thick] (0,2.6) -- (2.3,2.6);
    \draw[accmid, thick] (2.3,1.9) -- (4.6,1.9);
    % third level vertical splits on x
    \draw[acclo, thick] (1.1,0) -- (1.1,2.6);
    \draw[acclo, thick] (3.4,1.9) -- (3.4,4.6);
    % points
    \fill (0.6,1.3) circle (1.8pt);
    \fill (1.7,0.9) circle (1.8pt);
    \fill (1.0,3.6) circle (1.8pt);
    \fill (3.2,0.8) circle (1.8pt);
    \fill (2.9,3.0) circle (1.8pt);
    \fill (4.0,3.4) circle (1.8pt);
  \end{scope}
  % --- right: the tree ---
  \begin{scope}[xshift=80mm, yshift=42mm,
    every node/.style={circle, draw, minimum size=7mm, inner sep=0},
    level distance=12mm,
    level 1/.style={sibling distance=24mm},
    level 2/.style={sibling distance=12mm}]
    \node[draw=acc, text=acc, thick] {$x$}
      child {node[draw=accmid, text=accmid, thick] {$y$}
        child {node[draw=acclo, text=acclo, thick] {$x$}}
        child {node {$p$}}
      }
      child {node[draw=accmid, text=accmid, thick] {$y$}
        child {node {$p$}}
        child {node[draw=acclo, text=acclo, thick] {$x$}}
      };
  \end{scope}
\end{tikzpicture}
$$

**Build.** Given all $n$ points, build top-down. At depth $d$ pick the active
coordinate $a = d \bmod 2$, find the **median** of the points by coordinate $a$
(linear time via [quickselect](/algorithms/divide-and-conquer/selection), or by pre-sorting), store it at the node,
and recurse on the two halves. The recurrence $T(n) = 2T(n/2) + O(n)$ solves to
$O(n \log n)$, and because every split is at the median the resulting tree has
height $\lceil \log_2 n \rceil$.

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize, dot/.style={fill=black, circle, inner sep=1.5pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{accmid}{HTML}{6A82F6}
  % --- stage one: split on x ---
  \begin{scope}
    \draw[thick] (0,0) rectangle (3.2,3.2);
    \draw[acc, very thick] (1.6,0) -- (1.6,3.2);
    \node[dot] at (0.7,0.9) {};
    \node[dot] at (1.0,2.4) {};
    \node[dot] at (2.3,0.7) {};
    \node[dot] at (2.6,2.5) {};
    \node[acc, anchor=south, font=\scriptsize] at (1.6,3.25) {split on $x$};
  \end{scope}
  % --- stage two: split each half on y ---
  \begin{scope}[xshift=46mm]
    \draw[thick] (0,0) rectangle (3.2,3.2);
    \draw[acc, very thick] (1.6,0) -- (1.6,3.2);
    \draw[accmid, thick] (0,1.65) -- (1.6,1.65);
    \draw[accmid, thick] (1.6,1.6) -- (3.2,1.6);
    \node[dot] at (0.7,0.9) {};
    \node[dot] at (1.0,2.4) {};
    \node[dot] at (2.3,0.7) {};
    \node[dot] at (2.6,2.5) {};
    \node[accmid, anchor=south, font=\scriptsize] at (0.8,3.25) {split on $y$};
  \end{scope}
\end{tikzpicture}
$$

**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(\sqrt{n} + t)$ in the plane — the $\sqrt n$ comes from the cells the query
boundary crosses.[^clrs-geom]

### 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
caption: $\textsc{NearestNeighbor}(v, q, best)$ — closest stored point to $q$
number: 1
if $v = \text{nil}$ then return $best$
if $\dist(q, point(v)) < \dist(q, best)$ then
  $best \gets point(v)$ // this node beats the incumbent
$a \gets depth(v) \bmod 2$ // active split coordinate
if $q_a < value(v)$ then
  $near \gets left(v),\ far \gets right(v)$
else
  $near \gets right(v),\ far \gets left(v)$
$best \gets \textsc{NearestNeighbor}(near, q, best)$ // descend the likely side first
if $|q_a - value(v)| < \dist(q, best)$ then // splitting line within reach?
  $best \gets \textsc{NearestNeighbor}(far, q, best)$ // only then check the far side
return $best$
```

Visiting the _near_ side first is what makes the bound tight: it usually finds a
good candidate immediately, so the $|q_a - value(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 \ge 5$). Query
$q = (6,3)$.

1. **Root $B(5,4)$**, split on $x = 5$. Distance $\sqrt{(6-5)^2 + (3-4)^2} =
   \sqrt 2 \approx 1.41$; set $best = B$, $r = 1.41$. Since $q_x = 6 \ge 5$, the
   _near_ side is the right subtree; descend there first.
2. **Right child $E(8,1)$**, split on $y = 1$. Distance $\sqrt{4 + 4} = \sqrt 8
   \approx 2.83 > r$, so $E$ does not improve $best$. Since $q_y = 3 \ge 1$, the
   near child is $E$'s right subtree holding $C$.
3. **$C(9,6)$**, a leaf. Distance $\sqrt{9 + 9} = \sqrt{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**.
4. 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 $\sqrt{4+16} \approx 4.47$),
   neither beating $r$.

The answer is $B(5,4)$ at distance $\sqrt 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.

$$
% caption: 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).
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  nd/.style={circle, draw, minimum size=7mm, inner sep=0},
  level distance=13mm,
  level 1/.style={sibling distance=34mm},
  level 2/.style={sibling distance=17mm}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \node[nd, draw=acc, text=acc, very thick] (r) {$x$}
    child {node[nd, draw=acc, text=acc, very thick] (l) {$y$}
      child {node[nd, fill=acc!16, draw=acc, very thick] (leaf) {leaf}
        edge from parent[acc, very thick]}
      child {node[nd, draw=green, text=green, thick] (lr) {$p$}
        edge from parent[green, thick]}
      edge from parent[acc, very thick]
    }
    child {node[nd, draw=red!75!black, text=red!75!black] (rr) {$y$}
      child {node[nd, draw=red!75!black, text=red!75!black] {$p$}
        edge from parent[red!75!black, dashed]}
      child {node[nd, draw=red!75!black, text=red!75!black] {$p$}
        edge from parent[red!75!black, dashed]}
      edge from parent[red!75!black, dashed]
    };
  % near-side descent label
  \node[acc, anchor=south east, font=\scriptsize] at (leaf.north west) {descend near};
  % far subtree pruned
  \node[red!75!black, anchor=west, font=\scriptsize, align=left] at (rr.east) {beyond $r$:\\pruned};
  % far candidate within radius checked
  \node[green, anchor=north, font=\scriptsize, align=center] at (lr.south) {within $r$:\\searched};
\end{tikzpicture}
$$

$$
% caption: 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$ of $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.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % query point and best-so-far radius
  \coordinate (q) at (2.4,2.0);
  \fill[acc] (q) circle (2pt);
  \node[acc, anchor=north] at (2.4,1.85) {$q$};
  \draw[acc, thick] (q) circle (1.3);
  % radius spoke + label, placed in open space upper-left of q
  \draw[acc, thick] (q) -- (1.48,2.92);
  \node[acc, anchor=south east] at (1.55,2.95) {radius $r$};
  % a split line within reach -> must search
  \draw[acc, very thick] (3.5,-0.3) -- (3.5,4.3);
  \node[acc, anchor=west, align=left] at (4.05,2.2) {within $r$:\\search far side};
  % a split line out of reach -> pruned
  \draw[red!75!black, very thick, dashed] (-0.4,3.7) -- (4.6,3.7);
  \node[red!75!black, anchor=west] at (-0.4,4.05) {beyond $r$: pruned};
  % the current best point on the circle
  \fill (1.4,1.15) circle (1.8pt);
  \node[anchor=north east] at (1.4,1.15) {best};
\end{tikzpicture}
$$

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.

::impl{algo="kd_tree"}

## Range trees: faster orthogonal range reporting

The k-d tree answers a rectangle query in $O(\sqrt n + t)$, and the $\sqrt 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.

> **Definition (Range tree).** A 2-D range tree is a balanced BST on the
> $x$-coordinates of the points (the **primary** tree). Every node $v$ of the
> primary tree carries an **associated** balanced BST — the secondary tree — on
> the $y$-coordinates of exactly the points in $v$'s subtree, sorted by $y$.

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)$.

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  nd/.style={circle, draw, minimum size=6mm, inner sep=0, font=\scriptsize},
  can/.style={circle, draw=acc, very thick, fill=acc!12, minimum size=6mm, inner sep=0, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % primary x-tree
  \node[nd] (r) at (0,0) {$x$}
    child {node[nd] {} child {node[can] {}} child {node[can] {}}}
    child {node[nd] {} child {node[can] {}} child {node[nd] {}}}
    [level distance=11mm, sibling distance=22mm];
  \node[anchor=south, font=\scriptsize] at (0,0.5) {primary tree (on $x$)};
  \node[acc, anchor=north, font=\scriptsize] at (0,-3.0) {shaded = canonical subtrees for $[x_1,x_2]$};
  % associated y-tree on one canonical node
  \begin{scope}[xshift=62mm, yshift=-6mm]
    \node[nd, draw=green, thick, text=green] (yr) at (0,0) {$y$}
      child {node[nd, draw=green, text=green] {}}
      child {node[nd, draw=green, text=green] {}}
      [level distance=11mm, sibling distance=16mm];
    \node[green, anchor=south, font=\scriptsize] at (0,0.5) {associated tree (on $y$)};
    \node[green, anchor=north, font=\scriptsize] at (0,-1.9) {answers $[y_1,y_2]$ here};
  \end{scope}
  \draw[->, acc, thick, dashed] (0.9,-2.2) to[bend right=12] (4.6,-0.3);
\end{tikzpicture}
$$

**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).

> **Definition (Interval tree).** Pick the median endpoint $m$ of all interval
> endpoints and store it at the root. Intervals entirely left of $m$ go to the
> left subtree, entirely right to the right subtree; intervals **crossing** $m$
> stay at the root, kept in two sorted lists — one by left endpoint, one by right.
> Recurse on the two sides. The tree has height $O(\log n)$.

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 \le 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 \ge q$, then recurse right;
- if $q = m$, every stored interval at the node contains $q$; report them all.

$$
% caption: 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 $\le q$ and stopping at the first
%          miss; the search then recurses into the left subtree ($<m$).
\begin{tikzpicture}[
  >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % number line
  \draw[thick] (-0.3,0) -- (9.3,0);
  \foreach \x/\lab in {2/2,4.5/m,7/7} \node[anchor=north, font=\scriptsize] at (\x,-0.08) {\lab};
  % center line
  \draw[acc, thick, dashed] (4.5,-0.35) -- (4.5,3.3);
  \node[acc, anchor=south, font=\scriptsize] at (4.5,3.3) {centre $m$};
  % query
  \draw[green, very thick] (3.1,-0.35) -- (3.1,3.3);
  \node[green, anchor=south, font=\scriptsize] at (3.1,3.35) {$q$};
  % intervals crossing m
  \draw[acc, thick] (2.4,0.7) -- (6.3,0.7);   \fill[acc] (2.4,0.7) circle (1.6pt); \fill[acc] (6.3,0.7) circle (1.6pt);
  \draw[acc, thick] (3.6,1.4) -- (5.7,1.4);   \fill[acc] (3.6,1.4) circle (1.6pt); \fill[acc] (5.7,1.4) circle (1.6pt);
  \draw[acc, thick] (1.3,2.1) -- (5.2,2.1);   \fill[acc] (1.3,2.1) circle (1.6pt); \fill[acc] (5.2,2.1) circle (1.6pt);
  % which contain q
  \node[green, anchor=west, font=\scriptsize] at (6.5,0.7) {contains $q$};
  \node[black, anchor=west, font=\scriptsize] at (6.5,1.4) {left end $>q$: skip};
  \node[green, anchor=west, font=\scriptsize] at (6.5,2.1) {contains $q$};
\end{tikzpicture}
$$

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.[^skiena-kd]

## 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(\sqrt 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](/algorithms/data-structures/b-trees): 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](/algorithms/data-structures/b-trees) 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.[^btb-spatial]

## 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(\sqrt 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-kd]: **Skiena**, §12.6 — Kd-Trees: alternating-axis median splits, range search, and nearest-neighbour via branch-and-bound, with the curse-of-dimensionality caveat.
[^clrs-geom]: **CLRS**, Ch. 33 — Computational Geometry: axis-aligned subdivision and the recurrence behind balanced spatial partitions.
[^erickson-ds]: **Erickson**, Ch. — Data Structures: recursive space-partitioning trees and the geometry of pruning a query against a subtree's bounding box.
[^btb-spatial]: 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).