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.
Agricultural Non-Point Source Pollution Model claims to be using
Voronoi diagrams as a basis for spatial subdivision, but appears to
actually be using quadtrees.
of the linear quadtree to astronomical databases, P. Barrett, NASA.
Encoding astronomical coordinates with quadtrees can provide significant
improvements in efficiency when accessing sources near a given direction
and can aid in the correlation of positions from different astronomical
- Displaying a Voxel-Based Object Via Linear Octrees, Gargantini et al., Proc.
hierarchical methods for the n-body problem, CS 267, Berkeley, 1995.
- Galaxy formation with n-body simulations.
J. K. Salmon et al. study galaxy formation by simulating systems of
roughly 10^7 particles, using codes based on a k-D-tree-like recursive
This page also briefly mentions applications of related
octree techniques to molecular dynamics, fluid dynamics, physical chemistry,
data compression, visualization, and data mining.
- Grid Evolution for Oxidation Simulation. Sahul, McKenna, and Dutton (in this paper from the NUPAD V Conf.) use adaptive quadtree meshes to simulate semiconductor oxidation.
pyramids and trees, quadtree data structures for
binary tree predictive image coding.
- Octree-based methods in mesh generation, from Steve Owen's
- My own research on
quadtrees and related hierarchical decompositions.
- Object Representation by Means of Nonminimal Division Quadtrees and Octrees.
This paper by Ayala et al., in ACM Trans. on Graphics,
describes quadtree methods in solid modeling.
n-body simulations using hierarchical octree representations of space.
- Parallel octree mesh generation project,
Ralf Diekmann, Paderborn.
based point pattern analysis methods for investigation of spatial
structure of various stellar populations, L. Pásztor, ADASS '94.
Processing and display of medical three dimensional arrays of numerical
data using octree encoding, Amans and Darrier, Proc. SPIE, 1985.
- QMG, a quadtree-based 2d and 3d mesh generator by Steve Vavasis of Cornell.
constants. Steven Finch investigates the expected behavior of random
- Quadtree references from Michael Ley's bibliography of database systems and logic programming.
- A Quadtree Structured Video-phone Codec, L. Hanzo and A. Schober,
octree generation from rotating objects
R. Szeliski of DEC uses octrees in computer vision.
Patent 3602702 covers the quadtree subdivision of a viewing plane to perform hidden surface removal in computer graphics.
Patent 4694404 covers the use of octrees to implement a nearer-object-first
Patent 5123084 describes a similar nearest-first octree graphics method.
5222201 also concerns octree graphics methods, and describes
a heuristic for speeding up the conversion of objects into octree
- US Patents
describe video and image coding methods based on quadtrees.
Patent 5459831 covers the use of quadtrees to perform the range
queries needed for object selection in graphical user interfaces.
Patent 5461712 uses quadtrees to allocate memory to different
objects in a windowing system.
Well-Separated Pair Decomposition and its Applications,
Paul Callahan's Johns Hopkins Ph.D. thesis
on hierarchical space decomposition
and its applications to n-body simulation.
Geometry in Action,
a collection of applications of computational geometry.
from a common source file.