Application of alternative quadtree representations (vlsi, data structures)

The region quadtree, a hierarchical data structure for representing regular partitions of a digitized plane, decomposes non-homogeneous images into four equal quadrants, subquadrants, . . ., until each block is homogeneous. This thesis investigates the quadtree's adaptability to various applications, such as geographic information systems, computer aided design, VLSI design, and image processing. Two methods for adapting the quadtree to specific tasks are investigated. The first makes use of the linear quadtree, which reorganizes the traditional tree-structured quadtree as a sorted list representing the leaf nodes. Previously, little attention has been paid to minimizing the number of searches and insertions performed on this list, which account for the bulk of the execution time in linear quadtree algorithms. Techniques to reduce the number of these operations are presented. These techniques also lead to a new compression scheme for linear quadtrees that is applicable to a variety of data domains. Previously reported linear quadtree compression techniques are efficient only for particular data types. A second method for adapting quadtrees to specific applications is to use new decomposition rules that break the data into manageable subsets. The Quadtree Medial Axis Transform (QMAT) is an example of an existing structure based on such a decomposition rule. Its storage requirements, shift sensitivity, and ability to store color images are studied, and algorithms for its use are presented. Two approaches to using quadtree data structures for storing collections of rectangles are also investigated. The first approach stores representative points for each rectangle in a PR quadtree. The second divides a set of rectangles into subsets by a suitable decomposition rule. A new data structure, termed the RR quadtree, is presented and compared with previously known hierarchical rectangle representations. Algorithms utilizing the RR quadtree are presented.