Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects
J. Nievergelt · The Computer Journal · 1993
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