
Technical Report KDBSLABTR9406
Topological Relations in the World of Minimum Bounding Rectangles: a Study with Rtrees
Dimitris Papadias
Department of Computer Science and Engineering
University of California, San Diego
La Jolla, California, USA 920930114
dimitris@cs.ucsd.edu
Yannis Theodoridis*
Department of Electrical and Computer Engineering
National Technical University of Athens
Zographou, Athens, GREECE 15773
theodor@theseas.ntua.gr
Timos Sellis*
Department of Electrical and Computer Engineering
National Technical University of Athens
Zographou, Athens, GREECE 15773
timos@theseas.ntua.gr
Max J. Egenhofer**
National Center for Geographic Information Analysis
University of Maine
Orono, Maine, USA 044695711
max@mecan1.maine.edu
Abstract Recent developments in spatial relations have led to their use in numerous
applications involving spatial databases. This paper is concerned with the retrieval of
topological relations in Minimum Bounding Rectanglebased data structures. We study the
topological information that Minimum Bounding Rectangles convey about the actual
objects they enclose, using the concept of projections. Then we apply the results in Rtrees
and their variations, R+trees and R*trees in order to minimise disk accesses for queries
involving topological relations. We also investigate queries that involve complex spatial
conditions in the form of disjunctions and conjunctions and we discuss possible extensions.
1. INTRODUCTION
The representation and processing of spatial relations has recently gained much attention in Spatial Query Languages (Egenhofer, 1994, Papadias and Sellis, 1994b), Image and Multimedia Databases (Papadias et al., 1994a, Sistla et al., 1994), Geographic Applications (Frank, 1994), Spatial Reasoning (Glasgow, 1994) and Cognitive Science (Glasgow and Papadias, 1992). Several kinds of spatial relations have been defined and used. Egenhofer and Franzosa (1991), for instance, provided a mathematical framework for the definition of topological relations (e.g., inside, overlap), while Papadias and Sellis (1993) defined direction relations (e.g., north, north_east) using representative points. Kainz et al. (1993) modelled order relations
* Work partially supported by a research grant from the General Secretariat of Research and Technology of Greece (PENED
91).
** Work partially supported by the National Science Foundation under grant numbers IRI9309230 and SBR8810917 (for the
National Center for Geographic Information and Analysis), Intergraph Corporation, Environmental Systems Research Institute,
the Scientific Division of the North Atlantic Treaty Organization, and the Maine Mathematics and Science Alliance.