Some Elemental Operations on Linear Quadtrees for Geographic Information Systems
Open Access
- 1 January 1985
- journal article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 28 (1) , 73-77
- https://doi.org/10.1093/comjnl/28.1.73
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: