Database Systems

Approximation of Spatial Objects


Spatial access methods only exclude objects which do not fullfil the query. For the remaining objects, the exact geometry has to be tested. Tests using the exact geometry of complex objects are computationally expensive and therefore, it is worthwhile to introduce an additional filterstep to reduce the number of false hits and to identify as many final answers as possible. For this purpose, object approximations may be used. An approximation of a spatial object should be as simple as possible and the deviation from the original object should be as small as possible - obviously, two competitive criteria.

A first task in this research area was the analysis and classification of different types of object approximations. An important class of approximations are approximations which are completely containing the original object. The figure shows some examples of container-approximations.


In several studies, we investigated the suitability of several container-approximations with regard to the processing of spatial selections. Important publications in this area are [BKS 93b] and [BK 94b].

HOME Pages: DBS Institute LMU

Contact Institute: info@informatik.uni-muenchen.de
Contact WWW: wwwmaster@informatik.uni-muenchen.de