Quadtrees
Definition
Quadtrees are hierarchical spatial data structures that recursively partition a 2D region into four axis-aligned quadrants, refining only where the data or query workload requires it.
Why It Matters
They turn “check every point” spatial workloads into search procedures that can prune large irrelevant regions, which is why they recur in maps, games, GIS, and other systems with local geometric queries.
Formalism / Key Objects
- a root bounding box covering the ambient 2D space
- recursive four-way subdivision into child cells
- leaf nodes that store points or aggregated region summaries
- bounding-box distance and intersection tests used for pruning
Connections
- Closely tied to Nearest-Neighbor Search and range-query workloads.
- Lives naturally under Algorithms and Data Structures but shows up in simulation-heavy AI systems as well.
- Related to other spatial partitioning families such as KD-trees, octrees, and R-trees.
Common Confusions
- Quadtrees are adaptive, but only along fixed midpoint splits rather than arbitrary learned partitions.
- Good average-case pruning does not eliminate worst-case degeneration when data are badly distributed.
- The structure supports several query types; it is not only for nearest-neighbor search.