Topological relationships between complex spatial objects

ABSTRACT

For a long time topological relationships between spatial objects have been a focus of research in a number of disciplines like artificial intelligence, cognitive science, linguistics, robotics, and spatial reasoning. Especially as predicates they support the design of suitable query languages for spatial data retrieval and analysis in spatial databases and geographical information systems (GIS). Unfortunately, they have so far only been defined for and applicable to simplified abstractions of spatial objects like single points, continuous lines, and simple regions. With the introduction of complex spatial data types an issue arises regarding the design, definition, and number of topological relationships operating on these complex types. This article closes this gap and first introduces definitions of general and versatile spatial data types for complex points, complex lines, and complex regions. Based on the well known 9-intersection model, it then determines the complete sets of mutually exclusive topological relationships for all type combinations. Completeness and mutual exclusion are shown by a proof technique called proof-by-constraint-and-drawing. Due to the resulting large numbers of predicates and the difficulty of handling them, the user is provided with the concepts of topological cluster predicates and topological predicate groups, which permit one to reduce the number of predicates to be dealt with in a user-defined and/or application-specific manner.

REFERENCES

• 1: Abler, R. 1987. The National Science Foundation Center for Geographic Information and Analysis. Int. J. Geograph. Inform. Syst. 1, 4, 303--326.
• 2: Thomas Behr , Markus Schneider, Topological Relationships of Complex Points and Complex Regions, Proceedings of the 20th International Conference on Conceptual Modeling: Conceptual Modeling, p.56-69, November 27-30, 2001
• 3: 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 ]
• 4: Eliseo Clementini , Paolino Di Felice, Topological Invariants for Lines, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.38-54, January 1998 [doi>10.1109/69.667085 ]
• 5: Eliseo Clementini , Paolino Di Felice , Gianluca Califano, Composite regions in topological queries, Information Systems, v.20 n.7, p.579-594, Nov. 1995 [doi>10.1016/0306-4379(95)00031-X ]
• 6: 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
• 7: 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
• 8: Davis, J. R. 1998. IBM's DB2 spatial extender: Managing geo-spatial information within the DBMS. Tech. rep., IBM Corporation, Yorktown Heights, NY.
• 9: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: Egenhofer, M. J., Clementini, E., and Di Felice, P. 1994. Topological relations between regions with Holes. Int. J. Geograph. Inform. Syst. 8, 2, 128--142.
• 11: Egenhofer, M. J. and Franzosa, R. 1995. On the equivalence of topological relations. Int. J. Geograph. Inform. Syst. 9, 2, 133--152.
• 12: Max J. Egenhofer, A Formal Definition of Binary Topological Relationships, Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms, p.457-472, June 21-23, 1989
• 13: Egenhofer, M. J. 1993. Definitions of line-line relations for geographic databases. In Proceedings of the 16th International Conference on Data Engineering. 40--46.
• 14: M. J. Egenhofer, Spatial SQL: A Query and Presentation Language, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.86-95, February 1994 [doi>10.1109/69.273029 ]
• 15: Egenhofer, M. J. and Franzosa, R. D. 1991. Point-set topological spatial relations. Int. J. Geograph. Inform. Syst. 5, 2, 161--174.
• 16: Egenhofer, M. J. and Herring, J. 1990a. Categorizing binary topological relations between regions, lines, and points in geographic databases. Tech. rep. 90-12. National Center for Geographic Information and Analysis, University of California, Santa Barbara, Santa Barbara, CA.
• 17: Egenhofer, M. J. and Herring, J. 1990b. A mathematical framework for the definition of topological relationships. In Proceedings of the 4th International Symposium on Spatial Data Handling. 803--813.
• 18: Egenhofer, M. J. and Mark, D. 1995. Modeling conceptual neighborhoods of topological line-region relations. Int. J. Geograph. Inform. Syst. 9, 5, 555--565.
• 19: Martin Erwig , Markus Schneider, Spatio-Temporal Predicates, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.881-901, July 2002 [doi>10.1109/TKDE.2002.1019220 ]
• 20: ESRI. 1995. ESRI Spatial Database Engine (SDE). Environmental Systems Research Institute, Inc., Redlands, CA.
• 21: Freeman, J. 1975. The modelling of spatial relations. Comput. Graph. Image Process. 4, 156--171.
• 22: Gaal, S. 1964. Point Set Topology. Academic Press, New York, NY.
• 23: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 24: Ralf Hartmut Güting, Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.506-527, March 14-18, 1988
• 25: Ralf Hartmut Güting , Markus Schneider, Realms: A Foundation for Spatial Data Types in Database Systems, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.14-35, June 23-25, 1993
• 26: Ralf Hartmut Güting , Markus Schneider, Realm-based spatial data types: the ROSE algebra, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.2, p.243-286, April 1995 [doi>10.1007/BF01237921]
• 27: Informix. 1997. Informix Geodetic DataBlade Module: User's guide. Informix Press, Menlo Park, CA.
• 28: OGC. 1999. OGC Abstract Specification OpenGIS Consortium (OGC). URL: http://www.opengis.org/techno/specs.htm.
• 29: OGC. 2001. OGC Geography Markup Language (GML) 2.0. OpenGIS Consortium (OGC). URL: http://www.opengis.net/gml/01-029/GML2.html.
• 30: Oracle. 1997. Oracle8: Spatial Cartridge. An Oracle technical white paper. Oracle Corporation, Redwood Shores, CA.
• 31: J. A. Orenstein , F. A. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application, IEEE Transactions on Software Engineering, v.14 n.5, p.611-629, May 1988 [doi>10.1109/32.6139 ]
• 32: N. Roussopoulos , C. Faloutsos , T. Sellis, An Efficient Pictorial Database System for PSQL, IEEE Transactions on Software Engineering, v.14 n.5, p.639-650, May 1988 [doi>10.1109/32.6141 ]
• 33: Schneider, M. 1997. Spatial Data Types for Database Systems---Finite Resolution Geometry for Geographic Information Systems. Lecture Notes in Computer Science, vol. 1288. Springer-Verlag, Berlin, Heidelberg, Germany.
• 34: Markus Schneider, A Design of Topological Predicates for Complex Crisp and Fuzzy Regions, Proceedings of the 20th International Conference on Conceptual Modeling: Conceptual Modeling, p.103-116, November 27-30, 2001
• 35: Schneider, M. 2002. Implementing topological predicates for complex regions. In Proceedings of the International Symposium on Spatial Data Handling. 313--328.
• 36: Shekar, S. and Chawla, S. 2003. Spatial Databases: A Tour. Prentice Hall, Englewood Cliffs, NJ.
• 37: Tilove, R. B. 1980. Set membership classification: A unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 874--883.
• 38: Michael F. Worboys , Petros Bofakos, A Canonical Model for a Class of Areal Spatial Objects, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.36-52, June 23-25, 1993

INDEX TERMS

General Terms:
Design, Management, Standardization

Keywords:
9-intersection model, Topological predicate, complex spatial data type, proof-by-constraint-and-drawing, topological cluster predicate, topological constraint rule, topological predicate group