Doctoral Thesis, FernUniversität Hagen, 1995

**Abstract:** In various application fields there is a need to manage
and process *geometric* or *spatial* data, that is, data related
to *space*. For this purpose *spatial database systems* are designed
which are full-fledged database systems with additional capabilities for
representing, querying, and manipulating spatial data. Such systems provide
the underlying database technology needed to support applications such
as *geographical information systems*. *Spatial data types* like
*point*, *line*, and *region* provide a fundamental abstraction
for modelling the structure of geometric entities, their relationships,
properties, and operations. Their definition and implementation is probably
the most fundamental issue in the development of spatial database systems.
In this thesis we introduce a system of spatial data types, or a *spatial
algebra*, which is called *ROSE algebra* and which avoids many
of the deficiencies of current approaches. The development of the ROSE
algebra consists of three steps:

The first step introduces the concept of a *realm* as a *discrete*
geometric basis underlying one or more spatial data types. A realm is a
finite set of points and non-intersecting line segments over a discrete
grid and conceptually describes the complete underlying geometry of a particular
application space in two dimensions. The idea is to construct the geometries
of spatial objects by composing them from points or segments in the realm.
As a basis for the design of spatial data types very often Euclidean space
is used or implicitly assumed. A point in the plane is then represented
by a pair of real numbers. Unfortunately, in practice there are no real
numbers available in computers but only finite approximations. This leads
to many problems in geometric computation. The realm concept solves these
problems of numerical robustness and topological correctness below and
within the realm layer. In particular, it solves the line segment intersection
problem over a discrete grid and enforces geometric consistency of related
spatial objects. Furthermore, it enables one to formally define quite general
spatial data types or algebras on top of it that enjoy nice closure properties
not only in theory but also in computational practice.

The second step deals with the formal definition of the *ROSE algebra*
itself which is defined on top of realms and offers *realm-based*
spatial data types to represent point, line, and region features in the
plane together with a comprehensive set of spatial operations. The ROSE
algebra has a number of interesting features: It (i) offers (values of)
data types of a very general structure, (ii) has a complete formal definition
of the semantics of types and operations, (iii) has realms as a discrete
geometric basis which allows for a numerically correct and robust implementation
of types and operations in terms of integer arithmetic, (iv) treats consistency
between distinct spatial objects with common parts, and (v) has a general
object model interface which allows it to cooperate with different kinds
of database systems. Moreover, concepts of the ROSE algebra are used to
formally define *spatial objects with undetermined boundaries*.

The third step relates to the *ROSE system* as an implementation
of the ROSE algebra. This system realizes the algebra's types and operations
by providing efficient data structures and new *realm-based geometric
algorithms* defined over a discrete grid. The main techniques used are
parallel traversal of objects, plane-sweep, and graph algorithms. All algorithms
are analysed with respect to their worst case time and space requirements.
Due to the realm properties, these algorithms are relatively simple, efficient,
and numerically completely robust. In contrast to traditional work on algorithms,
the focus is not on finding the most efficient algorithm for each single
problem, but rather on considering a spatial algebra as a whole, and on
reconciling the various requirements posed by different algorithms within
a single data structure for each type.

(No full Postscipt version available. Printed copy available from the author on request.)

Last change: October 21, 1998, Markus Schneider