In this thesis, several aspects of quadtree representations are analyzed. The quadtree is a hierarchical variable-resolution data structure suitable for representing the geometric objects of computer graphics, the polygonal maps of computer cartography, and the digitized images of computer vision.
The analysis of quadtrees is presented in three parts:
A) a formal semantics for quadtree algorithms,
B) improved algorithms for manipulating the standard region quadtree, and
C) adaptations of the quadtree methodology to the task of representing polygonal maps.