The quadtree and octree are hierarchical data structures used to represent spatial data. They are based on the principle of recursive decomposition (similar to divide and con- conquer methods [Aho74]). This book focuses on the use of quadtree and octree representations of region data (in two and three dimensions, respectively) in applications in computer graphics, image processing, and geographic information systems (Gis), as well as computer vision, robotics, pattern recognition, solid modeling, and other areas. For a comprehensive treatment of related hierarchical representations of spatial data including points, lines, rectangles, regions, and volumes, see [Same90a]. To many people, the terms quadtree and octree have taken on a generic meaning synonymous with the term hierarchical data structure. Hierarchical data structures are useful because of their ability to focus on the interesting subsets of the data. This focusing results in an efficient representation and in improved execution times. Thus they are particularly convenient for performing set operations. Many of the operations described can often be performed as efficiently, or more so, with other data structures. Nevertheless, hierarchical data structures are attractive because of their conceptual clarity and ease of implementation. In addition, the use of some of them provides a spatial index. This is very useful in applications involving spatial databases.