A Quadtree for Global Information Storage

The hierarchical data structure known as a quadtree has advantages fur geographic data storage. In this structure a two-dimensional geometric region is recursively decomposed into quadrants. Each of the four quadrants becomes a node in the quadtree. A larger quadrant is a node at a higher hierarchical level of the quadtree, and smaller quadrants appear at lower levels. The advantage of this structure is that the regular decomposition provides for simple and efficient data storage, retrieval, and processing. The simplicity stems front the geometric regularity of the decomposition into squares, and the efficiency is obtained try storing only those nodes containing data of interest. A comprehensive review of quadtrees can be found In Samet (1984). Most of the applications of quadtrees to date have been to binary images (e.g., Klinger and Dyer 1976), but there have also been recent algorithmic developments that yield results similar to those used in geographic data processing. These include computation of geometric properties such as area calculation, centroid determination, comparison of images (Shneier 1981), connected component labeling, neighbor detection (Samet 1981a, b), distance transforms (Samet 1982), image segmentation, data smoothing (Ranade and Shneier 1981), and edge enhancement (Ranade 1981). Because of these advances, several investigators (Samet 1984, Peuquet 1984, Mark and Lauzon 1985) have proposed the use of quadtrees for geographic information storage. Additional work useful for this purpose has included the development of procedures for the conversion of data from raster to quadtree format (Dyer, Rosenfeld, and Samet 1980). The storage efficiency of quadtrees has been calculated (Dyer 1982) and enhanced by using linear coding techniques (Gargantini 1982). The possibility of using artificial intelligence to improve a very large quadtree-based geographical information system has even been considered (Chen 1984, 1985; Smith and Pazner 1984). Clearly this is an area of active research and promise.