The Goblin Quadtree
The Goblin quadtree is a new and simple data structure for representing spatial information. It stores a single pointer for each block of four nodes and average values at non-terminal nodes, enabling efficient depth-first traversal to any given level. The pointers are easy to generate and use, as de...
| Published in: | The Computer Journal |
|---|---|
| Main Author: | |
| Format: | Text |
| Language: | English |
| Published: |
Oxford University Press
1988
|
| Subjects: | |
| Online Access: | http://comjnl.oxfordjournals.org/cgi/content/short/31/4/358 https://doi.org/10.1093/comjnl/31.4.358 |
| Summary: | The Goblin quadtree is a new and simple data structure for representing spatial information. It stores a single pointer for each block of four nodes and average values at non-terminal nodes, enabling efficient depth-first traversal to any given level. The pointers are easy to generate and use, as demonstrated by algorithms for building and displaying Goblin quadtrees. The features of this new representation make it particularly suitable for geographic data. The concept of using a dominant value as the average value is explored, and is shown to be advantageous for quadtree display and storage. |
|---|