© 1993 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects
Informatik, ETH Zurich, Ch-8092, Zurich, Switzerland
The design of spatial data structures has made great strides in recent years in response to be increasing importance of applications such as CAD that require great efficiency in spatial database technology and in computational geometry. The variety of spatial data structures and retrieval algorithms known suggests that it is difficult or impossible to design general purpose structures that perform well across the entire spectrum of objects to be stored and queries to be processed—generality comes at the cost of performance and increased algorithm complexity. Thus simple algorithms that perform efficiently on a restricted class of problems are clearly of interest.
The guard file is a new data structure, with its access and update algorithms, designed to answer stabbing and intersection queries on a dynamic collection of spatial objects that satisfy a shape constraint. The objects stored must be ‘fat’ in a technical sense, namely convex with an aspect ratio (width/length) 
f, where f is a constant characteristics of the class, 0<f1. The collection of objects is pre-processed so every object is attached to a cell or to some vertices (‘guards’) of a hierarchical grid that tessellates space. The retrieval and update algorithms are simple and use standard data structures (radix tree). For restricted classes of objects, such as aligned regular polygons, efficiency may be enhanced by designing a suitable spatial grid tailored to the particular type of objects stored. We present examples, general results that related guard grids to the fatness f of objects, and experimental results for the 2-d case. All the relevant concepts generalize readily to multi-dimensional space, though the theory becomes more complicated.
Received June 1992. revised October 1992.