DEVBOOK

Quadtree

6 min read

EditReport

A quadtree divides a 2D domain into as many as four regions per node. In point-region (PR) and region quadtrees, a split produces NW, NE, SW, SE child regions. Empty quadrants may remain implicit rather than allocating child objects. An overfull point bucket or a mixed pixel block splits again until each leaf satisfies its stopping rule. Routing a point at (x, y) through those regions tends to place spatial neighbors in the same or adjacent leaves.

A quadtree is a spatial-partitioning tree, not a balanced search tree. It has no rotation or fill invariant like an AVL Tree or a B-tree. Point-quadtree depth depends on insertion order and placement. PR-quadtree depth follows clustering inside a fixed root region and needs an explicit minimum cell size, coordinate limit, or overflow rule. Region-quadtree depth follows raster resolution. In return, spatial queries can prune whole regions that do not intersect the search.

Family shape: recursively partition a 2D domain into four child regions → route or aggregate spatial data within those regions → prune regions that cannot intersect a query. PR and region quadtrees split rectangular bounds into equal NW/NE/SW/SE quadrants when a bucket overflows or a raster block is mixed. A point quadtree instead splits at each stored point into generally unequal quadrants.

Visualization

Only the overfull northeast leaf subdivides; the other three root quadrants retain their bounds and contents. The inserted points are then routed into the four new child regions, so resolution increases locally where the data is dense.

Complexity
  • Build: O(nh)
n
number of stored points
h
actual tree depth induced by insertion order or point distribution
v
nodes visited or intersected by a spatial query
k
points returned by a spatial query
s
tree nodes allocated under the chosen depth and empty-child policy

Point operations follow actual depth h; no relationship between h and n is structural. For a PR quadtree, h is capped only when the implementation defines a finite root region and a minimum cell size, finite coordinate precision, or another terminal overflow rule. A region quadtree over a 2^r × 2^r raster instead has h ≤ r. Persistent space follows allocated nodes s, which depends on depth and whether empty children are materialized. A range query depends on both visited nodes v and returned points k.

The point-quadtree worst case comes from insertion order and spatial placement, just as an ordinary binary search tree can become a chain. The PR-quadtree worst case comes from repeated subdivision of one region; coincident points cannot be separated by geometry, so the implementation must keep an overflow bucket or stop at a declared depth. Coordinate resolution bounds depth only when coordinates are quantized and the split arithmetic respects that finite domain.

Variants

The family varies along two decisions: what triggers a split and what a leaf stores.

  • Point quadtree (Finkel & Bentley, 1974). Each inserted point becomes an internal node and splits the plane at its own coordinates into four (generally unequal) quadrants — a direct 2D generalization of a Binary Search Tree. Its nodes do not carry fixed rectangular bounds unless the implementation adds them. Shape depends on insertion order, so a bad order degrades it.
  • Point-region (PR) quadtree. Decouples splitting from the data. Space is cut into four equal quadrants regardless of point coordinates. A leaf bucket splits only when it exceeds capacity (often one point). Internal nodes are pure spatial subdivisions. Leaves hold the points. The shape depends only on where the points are, not the order they arrived.
  • Region quadtree (image/raster). The domain is a 2ⁿ × 2ⁿ grid and each node covers a square block. A uniform block (all one color/value) is a leaf. A mixed block splits into four equal sub-blocks. Used for image compression and spatial occupancy — large empty or solid areas collapse to a single node.

Operations and Use Cases

In a PR quadtree, insert, search, and delete follow the target’s quadrant down to a leaf. A point-quadtree lookup can stop at an internal node that stores the matching point, while deletion may require subtree reconstruction or another explicit repair strategy. Spatial queries earn the extra structure by pruning subtrees:

  • 2D range query — descend, skipping any quadrant whose rectangle does not intersect the query window. Report points in the surviving leaves.
  • Nearest-neighbor — best-first / branch-and-bound over quadrants, pruning a quadrant once its bounding box is farther than the current best.
  • Collision detection (broad phase) — objects sharing a cell (or an adjacent one) are collision candidates, replacing an all-pairs scan with a handful of local comparisons.
  • Image compression — a region quadtree merges uniform blocks into single leaves.
  • Geospatial and simulation — subdividing a map into cells for level-of-detail, terrain, or particle systems. The 3D cousin (the octree, eight children) drives Barnes–Hut n-body approximation.

Quadtree Vs Geohash

A Geohash encodes a point as a sortable prefix in a fixed grid. A PR or region quadtree subdivides cells only where more resolution is needed. Geohash fits existing sorted indexes, cache keys, and shard prefixes. Quadtrees fit mutable in-memory work that needs explicit region bounds, local subdivision, collision broad-phase, or sparse raster compression.

Adjacent points can fall into different geohash prefixes, so proximity queries inspect neighboring cells and filter candidates by exact geometry or distance. An adaptive PR quadtree avoids one global cell size but still needs a depth or cell-size limit for coincident points. Paged durable storage usually belongs in the database’s spatial index unless the fixed-prefix key is itself the requirement. Geohash covers the encoding and its boundary algorithm. Indexes covers the wider database-index tradeoff.

Recursive Subdivision Diagram

References

Graph View

Backlinks