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.
- The
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.
- Applications
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
catalogs.
- Displaying a Voxel-Based Object Via Linear Octrees, Gargantini et al., Proc.
SPIE 1986.
- Fast
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
orthogonal partition.
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.
- Image
pyramids and trees, quadtree data structures for
binary tree predictive image coding.
- Octree-based methods in mesh generation, from Steve Owen's
Meshing
Research Corner.
- 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.
- Parallel
n-body simulations using hierarchical octree representations of space.
- Parallel octree mesh generation project,
Ralf Diekmann, Paderborn.
- Partition
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.
- Quadtree
constants. Steven Finch investigates the expected behavior of random
quadtrees.
- Quadtree references from Michael Ley's bibliography of database systems and logic programming.
- A Quadtree Structured Video-phone Codec, L. Hanzo and A. Schober,
Southampton.
- Real-time
octree generation from rotating objects
(abstract
or full
paper).
R. Szeliski of DEC uses octrees in computer vision.
- US
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
painting order.
Patent 5123084 describes a similar nearest-first octree graphics method.
Patent
5222201 also concerns octree graphics methods, and describes
a heuristic for speeding up the conversion of objects into octree
representations.
- US Patents
5134480,
5228098,
5444489,
5446806,
5452104,
and
5469212
describe video and image coding methods based on quadtrees.
- US
Patent 5459831 covers the use of quadtrees to perform the range
queries needed for object selection in graphical user interfaces.
- US
Patent 5461712 uses quadtrees to allocate memory to different
objects in a windowing system.
- The
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.
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.
