### Technical Report No. 24, July 1990 - Abstract

**Bruno Becker, Peter Widmayer:**

*Spatial Priority Search: An Access Technique for Scaleless Maps*

In geographic information systems, an important goal is the maintenance
of seamless, scaleless maps.
The amount of detail desired on a map decreases with decreasing scale.
Cartographic techniques called *generalization*
define the representations of geographic objects, depending on the
scale.
While generalization as a whole is considered an art, simple automatic
generalization techniques exist for simple geometric objects.
For polygonal lines and polygons, simplification techniques assign
priorities to points.
A map at a desired scale is then obtained by ignoring all points
of sufficiently low priority.
This implies that a geometric object appears on a map only if its
priority
is high enough, and also that an object is represented only by
those of its defining points that have sufficiently high priority.
In addition to the totally free choice of the representation scale of
retrieved
data, a seamless access to an arbitrary map should be supported.
The efficiency of retrieving a map of some area at a certain scale
ideally should only depend on the amount of data retrieved.

In this paper, we present algorithms and a fully adaptive data structure that efficiently supports insertions, deletions, updates and geometric queries at an arbitrary location for an arbitrary scale. Our data structure adapts to dynamically changing data in such a way that objects outside the query area or of irrelevant priority do not influence the efficiency of the query substantially. The structure is of broader interest, because it supports general proximity queries with priority threshold for non-zero size geometric objects. Furthermore, we show how to partition polygon corner points of different priorities such that they can be stored in the structure with practically no redundancy, and polygons for any priority threshold can be reassembled easily. A performance evaluation of our implementation with topographic data reveals that a performance gain of a high factor can be achieved with the structure under realistic assumptions.

report24.ps.gz