🌲 Quadtree

The maximum depth of a PR quadtree is bounded by the resolution of the coordinate system. For 32-bit floating-point coordinates in a unit square, the minimum distinguishable distance is about 10⁻⁷, so the tree can reach at most ~23 levels before two "distinct" points occupy the same leaf. For integer coordinates in a 1024×1024 grid, the maximum depth is 10 (since 2¹⁰ = 1024). In practice, very deep trees only form when many points cluster in a tiny area; the average depth for a uniform point set is O(log n).

Yes. Insertion traverses from the root to the appropriate leaf in O(depth) time, splitting the leaf if it exceeds capacity. Deletion removes the point and, if the parent's total point count falls below the merge threshold, collapses the four child nodes back into the parent leaf. Both operations are O(log n) average for uniformly distributed points. Frequent insertions and deletions in a clustered point set may require periodic rebuilding to prevent severe imbalance.

An octree is the 3D generalisation: each node subdivides its cube into eight equal sub-cubes (octants). Octrees are widely used in 3D game engines, ray tracing acceleration, and LiDAR point-cloud processing. The same algorithmic principles apply — range queries, nearest-neighbour search, and collision broadphase all benefit from the spatial hierarchy. In practice, 3D BVH (Bounding Volume Hierarchy) trees often outperform octrees for dynamic scenes because they adapt to point distribution rather than using fixed midpoint splits.

Quadtree image coding recursively divides an image into quadrants. If all pixels in a quadrant fall within a threshold of a single colour value, the quadrant is stored as a single leaf node with that colour — no per-pixel storage needed. Otherwise the quadrant is subdivided again. This produces a lossless (at threshold=0) or lossy (threshold>0) compression scheme. Fractal image compression (used in some early CD-ROM games) is a related technique. Modern codecs (HEVC, AV1) use quadtree-like coding unit (CU) hierarchies to partition frames into variable-size blocks for entropy coding.

Nearest-neighbour search starts at the root and descends into the child quadrant containing the query point, maintaining a "current best" candidate. On the way back up the recursion, each sibling quadrant is checked: if the minimum possible distance from the query to the quadrant (its closest corner distance) is less than the current best, the quadrant must be searched — otherwise it is pruned. In practice this visits O(log n) nodes for uniformly random data, though worst-case (adversarial point placement) is O(n).

A k-d tree (k-dimensional tree, Bentley 1975) is a binary space-partitioning tree that cycles through coordinate axes for its splits, choosing the median point along the current axis as the split value. For 2D data a k-d tree alternates between x-splits and y-splits. Unlike a PR quadtree, a k-d tree always balances perfectly (O(log n) depth for n points), but it has worse cache performance and is harder to update dynamically. Empirically, k-d trees outperform quadtrees for static point sets and lower dimensions; quadtrees are preferred for dynamic 2D data and collision broadphase.

The Z-order (Morton) curve maps 2D coordinates to a 1D index by interleaving the bits of the x and y coordinates: for x = b₁b₂b₃ and y = c₁c₂c₃, the Morton code is b₁c₁b₂c₂b₃c₃. This linearisation preserves spatial locality: points close on the Z-order curve are spatially nearby in 2D. The Morton code of a point is exactly the path from root to leaf in a PR quadtree encoded as a binary string. Database systems (e.g., DynamoDB, Google S2) use Morton or Hilbert curves to index spatial data in 1D B-trees, achieving quadtree-equivalent query performance with standard index structures.

Yes — the region quadtree stores which cells (pixels) are "inside" a polygon by subdividing until cells are entirely inside, entirely outside, or at the resolution limit (then stored as partially-covered). Vector quadtrees insert line segments or polygons by testing each level of subdivision for intersection. Storing large polygons naïvely causes duplication across many nodes; R-trees (Guttman, 1984) are generally preferred for rectangle and polygon indexing in GIS because they bound objects tightly and avoid redundant multi-node storage.