Recent Developments in Linear Quadtree-based
Geographic Information Systems

Hanan Samet, Cliff Shaffer, Randal C. Nelson
Yuan-Geng Huang, Kikua Fujimura, and Azriel Rosenfeld
Department of Computer Science
University of Maryland, University of Rochester
Rochester, NY 14627

Abstract: The status of an ongoing research effort to develop a geographic information system based on a variant of the linear quadtree is presented. This system uses quadtree encodings for storing area, point, and line features. Recent enhancements to the system are presented in detail. This includes a new hierarchical data structure for storing linear features that represents straight lines exactly and permits updates to be performed in a consistent manner. The memory management system was modified to enable the representation of an image as large as 16384 x 16384 pixels. Improvements were also made to some basic area map algorithms which yield significant efficiency speedups by reducing node accesses. These include windowing, set operations with unaligned images, a polygon expansion function, and an optimal quadtree building algorithm which has an execution time that is proportional to the number of blocks in the image instead of the number of pixels.