| 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: (1) a formal semantics for quadtree algorithms, (2) improved algorithms for manipulating the standard region quadtree, and (3) adaptations of the quadtree methodology to the task of representing polygonal maps.; The first portion of this thesis provides a formal semantics for quadtree algorithms, simultaneously overviewing and unifying previous research in this field. Such a semantics has many usages. It forms a basis for correctness proofs of quadtree algorithms. It provides a foundation for automatic derivation of variations of quadtree algorithms. It guides comparison of quadtree algorithms with algorithms based on other hierarchical data structures.; In the next portion of this thesis, the worst-case behavior of standard region (and line) quadtree algorithms is investigated. An improvement in the worst-case performance results from usage of a quadtree normalization algorithm that calculates a good placement of an image on the digitization grid. This normalization algorithm is first developed in order to show that a quadtree can be constructed from a chain code in time proportional to the length of the chain code. The algorithm is then modified to allow the building of a normalized quadtree from an arbitrary quadtree in time proportional to the size of the two quadtrees. Algorithms for connected-component analysis and quadtree-to-chain-code conversion on normalized quadtrees are developed that execute in time proportional to the number of nodes in the normalized quadtree.; In the last portion of this thesis, we consider the problem of how to adapt the quadtree methodology to the task of representing polygonal maps. Three approaches for representing polygonal maps are presented. First, we analyze the storage reduction that results from performing common subtree elimination on a quadtree that represents a polygonal map. Next, we consider how to use point quadtrees to store a Voronoi tessellation of a polygonal map. Finally, we develop a quadtree variant, called a PM quadtree, that provides a compact representation that is easy to both access and update. |
