Geometry in Action

Quadtrees and Hierarchical Space Decomposition

The basic principle of a quadtree is to cover a planar region of interest by a square, then recursively partition squares into smaller squares until each square contains a suitably uniform subset of the input; for instance this can be used to compress bitmap images by subdividing until each square has the same color value. This and related partitions have many applications in computational geometry and geometric applications, including data clustering, shape representation, n-body simulation in astronomy and molecular modeling, and mesh generation.

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file.