Some Elemental Operations on Linear Quadtrees for Geographic Information Systems
David J. Abel · The Computer Journal · 1985
Quadtrees appear attractive as an alternative to fixed-cell-size representations for areal entities in geographic information systems. This paper considers some aspects of use of linear quadtrees in such applications. Compaction (reduction of a quadtree to its maximal leaves) is desirable to minimise space requirements and to simplify some basic operations. An algorithm for compaction as an adjunct to quadtree-generating processes is presented, with analysis showing it to be linear with the sizes of the input and compacted quadtrees. Some simple forms of set operations are also described.