Modifications of the binary space partitioning tree for geographic information systems
conference paper
We present a Reactive Data Structure, that is, a spatial data structure with detaillevels. The two properties, spatial organization and detail levels, are the basis for a Geographic Information System with a multi-scale database. A reactive data structure is a novel type of data structure catering to multiple detail levels with rapid responses to spatial queries. It is presented here as a modification of the binary space partitioning tree that includes detail levels. This tree is one of the few spatial data structures that does not organize space in a rectangular manner. An application of the reactive data structure in thematic mapping is given. A prototype system is being implemented. An important result of this implementation is that it shows that binary space partitioning trees of real maps have O(n) storage space complexity in contrast to the theoretical worst case O(n2), with n the number of line segments in the map.
TNO Identifier
94235
Publisher
E.S. International Communucations
Source title
Visuda 89 - Proceedings of the international conference and exhibition on visual computing for defense, government and large projects, CIP Porte Maillot, Paris, France, 13-16 june 1989
Place of publication
Paris
Pages
Session 4.2