1. Formal Invariant — Axis-Cycling Partitioning & Bounding-Box Pruning
Invariant 1: k-d Tree Axis-Alternating Median Split
In a $k$-dimensional k-d Tree, a node at depth $d$ splits its point set along axis $a = d \bmod k$ at the median coordinate pivot[a] (selected in $O(m)$ via std::nth_element). Every point in the left subtree has $p[a] \le \text{pivot}[a]$, and every point in the right subtree has $p[a] \ge \text{pivot}[a]$. Because each point set is halved at every level, the tree is perfectly balanced with height $\lceil \log_2 N \rceil$ and builds in $O(N \log N)$ time.
Invariant 2: Branch-and-Bound Nearest Neighbor Pruning
During Nearest Neighbor search for query point $Q$ with current best squared distance $D_{\text{best}}^2$, let $\delta = Q[a] - \text{pivot}[a]$ be the signed perpendicular distance to the splitting hyperplane. We always search the near child first, and we prune the far child completely whenever $\delta^2 \ge D_{\text{best}}^2$!
2. Taxonomy of Multidimensional Spatial Indexes
(Disjoint Regions)"] Spatial --> DataPart["Data-Partitioning
(Bounding Hierarchies)"] Spatial --> SpaceFill["Space-Filling Curves
(2D/3D -> 1D Linearization)"] SpacePart --> KDTree["k-d Tree
Alternating Axis Median Split
O(N^{1-1/k} + K) Range Query"] SpacePart --> Quadtree["Quadtree / Octree
4-way / 8-way Regular Quadrant Split"] DataPart --> RTree["R-Tree / R*-Tree
Paged Minimum Bounding Rectangles (MBR)
PostGIS / SQLite R*Tree"] SpaceFill --> Morton["Z-Order (Morton) & Hilbert Curves
Bit Interleaving (BMI2 _pdep_u64)"]
3. Space-Filling Curves & Hardware Bit Interleaving (_pdep_u64)
Single-Cycle Morton Encoding via x86 BMI2 PDEP
The 2D Z-Order (Morton) code of $(x, y) \in [0, 2^{32}-1]^2$ places the bits of $x$ at even bit positions ($0, 2, 4, \dots$) and the bits of $y$ at odd bit positions ($1, 3, 5, \dots$). On modern x86-64 CPUs with BMI2, _pdep_u64(x, 0x5555555555555555ULL) | _pdep_u64(y, 0xAAAAAAAAAAAAAAAAULL) computes the 64-bit Morton key in 6 CPU cycles! Sorting an array of points or BVH triangles by their Morton code clusters spatially adjacent objects into the same cache lines and disk pages.
4. Complexity Matrix
Trace 2D cross-product orientation tests cross(O, A, B) = (Ax-Ox)(By-Oy) - (Ay-Oy)(Bx-Ox) to prune clockwise interior vertices and detect sweep-line segment intersections.
Invariant & State
| Spatial Structure | Build Time | Orthogonal Range Query | Nearest Neighbor (Average / Worst) |
|---|---|---|---|
| 2D k-d Tree (Static Balanced) | O(N log N) | O(sqrt(N) + K) | O(log N) avg / O(N) worst |
| $k$-D k-d Tree ($k$ dimensions) | O(N log N) | O(N^{1 - 1/k} + K) | O(2^k log N) avg |
| Quadtree (Depth $D$, Spread $\Phi$) | O(N * D) | O(D + K) | O(D) avg |
| R-Tree (Disk Page Fanout $B$) | O(N log_B N) | O(log_B N + K/B) avg | O(log_B N) avg (Best-First) |
5. Production-Grade C++20 Implementation (Morton Z-Curve & Static 2D k-d Tree Core)
#include <cstdint>
#include <vector>
#include <algorithm>
#include <limits>
// Portable O(1) 64-bit Morton (Z-Order) bit interleaving for 32-bit x, y
inline uint64_t split_by_1(uint32_t a) {
uint64_t x = a;
x = (x | (x << 16)) & 0x0000FFFF0000FFFFULL;
x = (x | (x << 8)) & 0x00FF00FF00FF00FFULL;
x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0FULL;
x = (x | (x << 2)) & 0x3333333333333333ULL;
x = (x | (x << 1)) & 0x5555555555555555ULL;
return x;
}
inline uint64_t morton_encode_2d(uint32_t x, uint32_t y) {
return split_by_1(x) | (split_by_1(y) << 1);
}
// Why orthogonal range query in a 2D k-d tree takes O(sqrt(N) + K):
// Any axis-aligned vertical or horizontal boundary line of the query box
// intersects at most 2 of the 4 grandchildren at depth + 2:
// T(N) = 2 * T(N / 4) + O(1) ===> T(N) = O(sqrt(N))!Production Pitfall — The Curse of Dimensionality in High-Dimensional k-d Trees ($k > 20$)
In a $k$-dimensional k-d Tree, the orthogonal range query bound $O(N^{1 - 1/k})$ approaches $O(N)$ as $k$ grows, and a hypersphere of radius $r$ touches almost all $2^k$ orthants around a query point! When $k \ge 20$ (e.g., 768-D or 1536-D LLM vector embeddings), exact k-d Trees visit nearly 100% of the tree and run slower than a brute-force SIMD linear scan. For high-dimensional vectors, always use **Approximate Nearest Neighbor (ANN)** indexes such as **HNSW** (Hierarchical Navigable Small World graphs) or **IVF-PQ** (Inverted File with Product Quantization).