| Spatial databases are systems that integrate in a single framework a series of tools and techniques for the processing of spatial and non-spatial data. In particular, the handling of spatial information requires appropriate representation schemes and efficient geometric algorithms. In this work, we present a representation scheme for a class of geometric objects that include rasters and orthogonal polygons in any number of dimensions. We show that this scheme permits the efficient implementation of many geometric operations, and demonstrate how they can be used in the context of spatial databases to speed up the processing of queries. These concepts were put into practical use in a testbed spatial database system called SAND, which is described in detail. |
