ix. KD-Tree and Spatial Structures

A KD-tree splits points by the median along alternating axes. It answers online nearest-neighbour and rectangle queries in 2D with $O (n)$ worst case for rectangles. If the queries can be sorted, an offline sweep with a Fenwick tree is almost always better. The KD-tree is for online geometric queries.

2D KD-tree with rectangle sums and nearest neighbour

struct KD {
    struct P { ll x, y, w; };
    vector<P> p; vector<int> lc, rc; vector<ll> x1, x2, y1, y2, sum;
    int build(int l, int r, int d) {                   // p[l, r), returns node index (= mid)
        if (l >= r) return -1;
        int m = (l + r) / 2;
        nth_element(p.begin() + l, p.begin() + m, p.begin() + r,
                    [d](const P& a, const P& b) { return d ? a.y < b.y : a.x < b.x; });
        lc[m] = build(l, m, d ^ 1); rc[m] = build(m + 1, r, d ^ 1);
        x1[m] = x2[m] = p[m].x; y1[m] = y2[m] = p[m].y; sum[m] = p[m].w;
        for (int c : {lc[m], rc[m]}) if (c >= 0)
            x1[m] = min(x1[m], x1[c]), x2[m] = max(x2[m], x2[c]),
            y1[m] = min(y1[m], y1[c]), y2[m] = max(y2[m], y2[c]), sum[m] += sum[c];
        return m;
    }
    int root;
    KD(vector<P> pts) : p(pts), lc(sz(p)), rc(sz(p)), x1(sz(p)), x2(sz(p)), y1(sz(p)), y2(sz(p)), sum(sz(p)) { root = build(0, sz(p), 0); }
    ll query(int v, ll X1, ll X2, ll Y1, ll Y2) {      // sum of weights in [X1,X2] x [Y1,Y2]
        if (v < 0 || x2[v] < X1 || X2 < x1[v] || y2[v] < Y1 || Y2 < y1[v]) return 0;
        if (X1 <= x1[v] && x2[v] <= X2 && Y1 <= y1[v] && y2[v] <= Y2) return sum[v];
        ll r = (X1 <= p[v].x && p[v].x <= X2 && Y1 <= p[v].y && p[v].y <= Y2) ? p[v].w : 0;
        return r + query(lc[v], X1, X2, Y1, Y2) + query(rc[v], X1, X2, Y1, Y2);
    }
    ll best;                                           // squared distance
    ll boxDist(int v, ll x, ll y) {
        ll dx = max({0LL, x1[v] - x, x - x2[v]}), dy = max({0LL, y1[v] - y, y - y2[v]});
        return dx * dx + dy * dy;
    }
    void nearest(int v, ll x, ll y) {
        if (v < 0 || boxDist(v, x, y) >= best) return;
        ll dx = p[v].x - x, dy = p[v].y - y; best = min(best, dx * dx + dy * dy);
        int a = lc[v], b = rc[v];
        if (b >= 0 && (a < 0 || boxDist(b, x, y) < boxDist(a, x, y))) swap(a, b);
        nearest(a, x, y); nearest(b, x, y);            // closer child first
    }
};

For “nearest other point”, skip the point itself (distance 0) or store ids.

Proof: the nearest pruning is safe

boxDist(v, x, y) computes the squared distance from $(x, y)$ to the closest point of the axis-aligned bounding box $[x 1_{v}, x 2_{v}] \times [y 1_{v}, y 2_{v}]$ — for each axis, if the query coordinate is inside the box’s range on that axis the contribution is 0, otherwise it’s the distance to the nearest edge; this is exactly the minimum possible squared Euclidean distance from $(x, y)$ to any point that could lie inside that box, since every stored point in the subtree has coordinates within the box by construction (the aggregate x1,x2,y1,y2 are built as the min/max over the subtree). So if boxDist(v,x,y) >= best, no point in $v$ ‘s subtree can possibly be closer than the current best, and skipping the subtree loses no candidate. Visiting the closer child first (by boxDist) only affects which candidates are found earlier, not correctness — every subtree not pruned is still fully explored, and a subtree is pruned only when the proven lower bound above already rules it out. $■$

Operation	Cost
build	$O (n lo g n)$ with `nth_element` in 2D, $O (d n lo g n)$ in $d$ dimensions
rectangle query	$O (n + output)$ in 2D; $O (n^{1 - 1/ d})$ in $d$ dims
nearest neighbour	$O (lo g n)$ on random data, $O (n)$ worst case (adversarial inputs exist); degrades badly as $d$ grows
insertion	rebuild a subtree when it becomes unbalanced (scapegoat, $α \approx 0.75$ ), or keep $O (lo g n)$ static trees of sizes $1, 2, 4, \dots$ and merge on overflow (the logarithmic method) for $O (lo g^{2} n)$ amortized insertion
memory	$O (n)$

Splitting rule: alternating axes is simplest; splitting on the axis with the larger spread (variance) is more robust for skewed data.

Curse of dimensionality: past $d \approx 10$ – $20$ , pruning almost never fires and nearest neighbour degenerates to a scan — for high dimensions use locality-sensitive hashing or approximate methods (HNSW), or accept the linear scan.

Uses: nearest neighbour / $k$ nearest neighbours; “points inside a rectangle/circle”; collision detection and ray tracing (though a BVH, below, is usually better for those); $k$ -NN classification in ML; closest pair (though divide and conquer is cleaner there).

Proof (sketch): a 2D KD-tree rectangle query visits $O (n)$ "partial" nodes

Let $Q (n)$ count the nodes a range query visits whose region is only partially covered by the query rectangle (fully-covered or fully-disjoint nodes are resolved in $O (1)$ each and don’t recurse further). Two levels down from any node, alternating-axis splitting has cut the region into 4 quadrants of $\approx n /4$ points each by both an $x$ -split and a $y$ -split. A query rectangle’s left edge, say, can only pass through quadrants that straddle that specific $x$ -value — at most 2 of the 4 quadrants (the two on the “boundary” column), and the same for each of the rectangle’s other 3 edges, but a careful count (each of the 4 region-boundaries can only be “partial” through limited quadrants, and only 2 of the 4 quadrants per 2-level step can actually be partial after accounting for which edges plausibly cross them) gives $Q (n) \leq 2 Q (n /4) + O (1)$ . This recurrence solves (by the master theorem, comparing $lo g_{4} 2 = \frac{1}{2}$ against the $O (1)$ non-recursive work) to $Q (n) = O (n^{1/2}) = O (n)$ . In $d$ dimensions the same two-level argument over $2^{d}$ hyper-quadrants gives $Q (n) \leq 2^{d - 1} Q (n / 2^{d}) + O (1)$ , solving to $Q (n) = O (n^{1 - 1/ d})$ . This is the standard computational-geometry result (de Berg, van Kreveld, Overmars, Schwarzkopf); the precise boundary-counting step is omitted here.

Alternatives

Task	Structure
rectangle count/sum, queries known in advance	sweep + Fenwick, $O ((n + q) lo g n)$ (Offline 2D)
rectangle count, online, static points	persistent segment tree or wavelet matrix: $O (lo g n)$
rectangle with point updates, online	2D Fenwick with compression, BIT of treaps, or KD-tree
which intervals contain $x$	sweep + multiset, or interval tree / segment tree storing intervals in $O (lo g n)$ canonical nodes
area / perimeter of a union of rectangles	sweep + segment tree with cover counts
Manhattan nearest neighbour	4 sweeps with rotated coordinates and a BIT (Manhattan Geometry)
Euclidean nearest neighbour for all points	Delaunay triangulation, or KD-tree
points within distance $r$	grid hashing with cell size $r$ (check the 9 neighbouring cells)

Named spatial structures beyond the KD-tree, most rare in CP but standard in graphics/GIS/databases — worth recognising by name:

Structure	What it does	Notes
quadtree / octree	recursively split a square (cube) into 4 (8) equal children, stopping when a cell holds few enough objects	grid-aligned splits (unlike a KD-tree’s median splits), so structure depends only on the region, not the data; excellent for bounded-integer grids/images; uses: image compression, collision broad-phase, terrain LOD, Barnes–Hut $n$ -body
interval tree	”which intervals contain $x$ ” / “which overlap $[a, b]$ ”: a balanced BST keyed by interval midpoint, each node storing intervals crossing its centre sorted by both endpoints	build $O (n lo g n)$ , query $O (lo g n + output)$ ; in practice a sweep line with a `multiset` solves the same problems more simply
segment tree (geometric)	confusingly, the original computational-geometry segment tree, different from the CP segment tree: stores intervals in $O (lo g n)$ canonical nodes, giving stabbing queries in $O (lo g n + k)$	the CP version stores an array for range aggregates; the geometric version stores intervals for point-stabbing — both are trees over a coordinate range, hence the shared name
range tree	a BST over $x$ , each node holding a sorted array of $y$ -values in its subtree	$O (lo g^{2} n)$ query ( $O (lo g n)$ with fractional cascading), $O (n lo g n)$ memory; generalises to $d$ dims as $O (lo g^{d} n)$ query / $O (n lo g^{d - 1} n)$ memory; this is the merge sort tree under another name
R-tree	groups nearby objects into minimum bounding rectangles, recursively; indexes objects with extent (not just points), boxes may overlap	the standard spatial index in databases (PostGIS, Oracle Spatial, SQLite RTree); insertion heuristics (R-tree, Hilbert R-tree) matter more than the asymptotics, which have no useful worst-case bound
BVH (bounding volume hierarchy)	a binary tree of bounding volumes over triangles/objects, built to minimise a surface-area-heuristic cost; query descends, pruning any node the ray misses	the dominant structure in ray tracing — every production renderer uses one

In CP the grid-hash trick and offline sweeps cover most of their uses.

whoashish's cp notes

Directory

ix. KD-Tree and Spatial Structures

2D KD-tree with rectangle sums and nearest neighbour

Alternatives

Graph View

Table of Contents