Exploiting Coherence In Spatial Database Queries

Mihai Pop, Johns Hopkins University

Many applications require the handling of moving objects. We concentrate on the special case when a query object is moving and we want to repeatedly answer queries throughout the motion. In particular, we examine segment dragging queries, where a query segment is being translated in a collection of two-dimensional points. We also examine a generalization of segment dragging in three dimensions where a query plane moves arbitrarily in a collection of points. In both cases our algorithms report the points hit by the moving object. We exploit the fact that queries are related and therefore the information computed in answering one query can be used when answering the following one. We also present the first non-trivial algorithm for computing silhouettes of polyhedral models, problem that has many practical applications.