Dimension-refined topological predicates

ABSTRACT

Topological predicates, as derived from the 9-intersection model, have been widely recognized in GIS, spatial database systems, and many other geo-related disciplines. They are based on the evaluation of nine Boolean predicates checking the intersections of the boundary, interior, and exterior of a spatial object with the respective parts of another spatial object for inequality to the empty set. In this paper, we replace each Boolean predicate, which is a topological invariant, by another topological invariant. This new invariant is given as a function yielding the dimension of the respective intersection in the 9-intersection matrix, resulting in a dimension matrix. The goal of this paper is to determine the definition and semantics of all predicates that can be derived from this matrix for all combinations of spatial data types. It turns out that these dimension-based predicates are special refinements of the aforementioned topological predicates; hence, we call them dimension-refined topological predicates. We show that these predicates allow us to pose a class of more fine-grained topological queries.

REFERENCES

• 1: Eliseo Clementini , Paolino Di Felice, A comparison of methods for representing topological relationships, Information Sciences—Applications: An International Journal, v.3 n.3, p.149-178, May 1995
• 2: Eliseo Clementini , Paolino Di Felice, A model for representing topological relationships between complex geometric features in spatial databases, Information Sciences: an International Journal, v.90 n.1-4, p.121-136, April 1996 [doi>10.1016/0020-0255(95)00289-8]
• 3: Eliseo Clementini , Paolino Di Felice , Peter van Oosterom, A Small Set of Formal Topological Relationships Suitable for End-User Interaction, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.277-295, June 23-25, 1993
• 4: Zhan Cui , Anthony G. Cohn , David A. Randell, Qualitative and Topological Relationships in Spatial Databases, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.296-315, June 23-25, 1993
• 5: M. J. Egenhofer and J. Herring. Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases. Technical Report 90-12, National Center for Geographic Information and Analysis, University of California, Santa Barbara, 1990.
• 6: M. Schneider. Spatial Data Types for Database Systems - Finite Resolution Geometry for Geographic Information Systems, volume LNCS 1288. Springer-Verlag, Berlin Heidelberg, 1997.
• 7: M. Schneider and T. Behr. Topological Relationships between Complex Spatial Objects. Technical Report 011, University of Florida, Department of Computer & Information Science & Engineering, 2004.
• 8: R. B. Tilove. Set Membership Classification: A Unified Approach to Geometric Intersection Problems. IEEE Trans. on Computers, C-29:874--883, 1980.
• 9: E. W. Weisstein, editor. CRC Concise Encyclopedia of Mathematics. Chapman & Hall/CRC, Boca Raton, 2nd edition, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Design

Keywords:
GIS, SPAL2D, dimension, spatial databases, topological predicates