{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T04:32:44Z","timestamp":1791174764215,"version":"4.1.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>\n            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\n            <jats:italic>complex spatial data types<\/jats:italic>\n            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\n            <jats:italic>complex points<\/jats:italic>\n            ,\n            <jats:italic>complex lines<\/jats:italic>\n            , and\n            <jats:italic>complex regions<\/jats:italic>\n            . 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\n            <jats:italic>proof-by-constraint-and-drawing<\/jats:italic>\n            . Due to the resulting large numbers of predicates and the difficulty of handling them, the user is provided with the concepts of\n            <jats:italic>topological cluster predicates<\/jats:italic>\n            and\n            <jats:italic>topological predicate groups<\/jats:italic>\n            , which permit one to reduce the number of predicates to be dealt with in a user-defined and\/or application-specific manner.\n          <\/jats:p>","DOI":"10.1145\/1132863.1132865","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"39-81","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":164,"title":["Topological relationships between complex spatial objects"],"prefix":"10.1145","volume":"31","author":[{"given":"Markus","family":"Schneider","sequence":"first","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Behr","sequence":"additional","affiliation":[{"name":"FernUniversit\u00e4t Hagen, Hagen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693798708927819"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference on Conceptual Modeling. 56--69","author":"Behr T.","unstructured":"Behr , T. and Schneider , M . 2001. Topological relationships of complex points and complex regions . In Proceedings of the International Conference on Conceptual Modeling. 56--69 . Behr, T. and Schneider, M. 2001. Topological relationships of complex points and complex regions. In Proceedings of the International Conference on Conceptual Modeling. 56--69."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(95)00289-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.667085"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(95)00031-X"},{"key":"e_1_2_1_6_1","series-title":"Lecture Notes on Computer Science","volume-title":"Proceedings of the 3rd International Symposium on Advances on Spatial Databases","author":"Clementini E.","unstructured":"Clementini , E. , Di Felice , P. , and van Oosterom , P. 1993. A small set of formal topological relationships suitable for end-user interaction . In Proceedings of the 3rd International Symposium on Advances on Spatial Databases . Lecture Notes on Computer Science , vol. 692 , Springer , Berlin, Germany , 277--295. Clementini, E., Di Felice, P., and van Oosterom, P. 1993. A small set of formal topological relationships suitable for end-user interaction. In Proceedings of the 3rd International Symposium on Advances on Spatial Databases. Lecture Notes on Computer Science, vol. 692, Springer, Berlin, Germany, 277--295."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes on Computer Science","volume":"692","author":"Cui Z.","unstructured":"Cui , Z. , Cohn , A. G. , and Randell , D. A . 1993. Qualitative and topological relationships . In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes on Computer Science , vol. 692 , Springer, Berlin, Germany, 296--315. Cui, Z., Cohn, A. G., and Randell, D. A. 1993. Qualitative and topological relationships. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes on Computer Science, vol. 692, Springer, Berlin, Germany, 296--315."},{"key":"e_1_2_1_8_1","volume-title":"IBM's DB2 spatial extender: Managing geo-spatial information within the DBMS. Tech. rep","author":"Davis J. R.","unstructured":"Davis , J. R. 1998. IBM's DB2 spatial extender: Managing geo-spatial information within the DBMS. Tech. rep ., IBM Corporation , Yorktown Heights, NY . Davis, J. R. 1998. IBM's DB2 spatial extender: Managing geo-spatial information within the DBMS. Tech. rep., IBM Corporation, Yorktown Heights, NY."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_1_10_1","first-page":"128","article-title":"Topological relations between regions with","volume":"8","author":"Egenhofer M. J.","year":"1994","unstructured":"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 . 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.","journal-title":"Holes. Int. J. Geograph. Inform. Syst."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693799508902030"},{"key":"e_1_2_1_12_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms","author":"Egenhofer M. J.","unstructured":"Egenhofer , M. J. 1989. A formal definition of binary topological relationships . In Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms . Lecture Notes in Computer Science , vol. 367 . Springer-Verlag , Berlin, Germany , 457--472. Egenhofer, M. J. 1989. A formal definition of binary topological relationships. In Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms. Lecture Notes in Computer Science, vol. 367. Springer-Verlag, Berlin, Germany, 457--472."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 16th International Conference on Data Engineering. 40--46","author":"Egenhofer M. J.","year":"1993","unstructured":"Egenhofer , M. J. 1993 . Definitions of line-line relations for geographic databases . In Proceedings of the 16th International Conference on Data Engineering. 40--46 . Egenhofer, M. J. 1993. Definitions of line-line relations for geographic databases. In Proceedings of the 16th International Conference on Data Engineering. 40--46."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273029"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693799108927841"},{"key":"e_1_2_1_16_1","unstructured":"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.  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."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 4th International Symposium on Spatial Data Handling. 803--813","author":"Egenhofer M. J.","unstructured":"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 . 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."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693799508902056"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1019220"},{"key":"e_1_2_1_20_1","volume-title":"ESRI Spatial Database Engine (SDE)","unstructured":"ESRI. 1995. ESRI Spatial Database Engine (SDE) . Environmental Systems Research Institute, Inc. , Redlands, CA . ESRI. 1995. ESRI Spatial Database Engine (SDE). Environmental Systems Research Institute, Inc., Redlands, CA."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(75)80007-4"},{"key":"e_1_2_1_22_1","volume-title":"Point Set Topology","author":"Gaal S.","unstructured":"Gaal , S. 1964. Point Set Topology . Academic Press , New York, NY . Gaal, S. 1964. Point Set Topology. Academic Press, New York, NY."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/352958.352963"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Extending Database Technology. 506--527","author":"G\u00fcting R. H.","year":"1988","unstructured":"G\u00fcting , R. H. 1988 . Geo-relational algebra: A model and query language for geometric database systems . In Proceedings of the International Conference on Extending Database Technology. 506--527 . G\u00fcting, R. H. 1988. Geo-relational algebra: A model and query language for geometric database systems. In Proceedings of the International Conference on Extending Database Technology. 506--527."},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Realms: A foundation for spatial data types in database systems. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases","author":"G\u00fcting R. H.","year":"1993","unstructured":"G\u00fcting , R. H. and Schneider , M . 1993 . Realms: A foundation for spatial data types in database systems. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases . Lecture Notes in Computer Science , vol. 692 . Springer-Verlag , Berlin, Germany , 14--35. G\u00fcting, R. H. and Schneider, M. 1993. Realms: A foundation for spatial data types in database systems. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science, vol. 692. Springer-Verlag, Berlin, Germany, 14--35."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01237921"},{"key":"e_1_2_1_27_1","volume-title":"Informix Geodetic DataBlade Module: User's guide","author":"Informix","unstructured":"Informix . 1997. Informix Geodetic DataBlade Module: User's guide . Informix Press , Menlo Park, CA . Informix. 1997. Informix Geodetic DataBlade Module: User's guide. Informix Press, Menlo Park, CA."},{"key":"e_1_2_1_28_1","unstructured":"OGC. 1999. OGC Abstract Specification OpenGIS Consortium (OGC). URL: http:\/\/www.opengis.org\/techno\/specs.htm.  OGC. 1999. OGC Abstract Specification OpenGIS Consortium (OGC). URL: http:\/\/www.opengis.org\/techno\/specs.htm."},{"key":"e_1_2_1_29_1","volume-title":"OGC Geography Markup Language (GML) 2.0","unstructured":"OGC. 2001. OGC Geography Markup Language (GML) 2.0 . OpenGIS Consortium (OGC) . URL: http:\/\/www.opengis.net\/gml\/01-029\/GML2.html. OGC. 2001. OGC Geography Markup Language (GML) 2.0. OpenGIS Consortium (OGC). URL: http:\/\/www.opengis.net\/gml\/01-029\/GML2.html."},{"key":"e_1_2_1_30_1","volume-title":"Oracle8: Spatial Cartridge. An Oracle technical white paper","author":"Oracle","unstructured":"Oracle . 1997. Oracle8: Spatial Cartridge. An Oracle technical white paper . Oracle Corporation , Redwood Shores, CA . Oracle. 1997. Oracle8: Spatial Cartridge. An Oracle technical white paper. Oracle Corporation, Redwood Shores, CA."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.6139"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.6141"},{"key":"e_1_2_1_33_1","series-title":"Lecture Notes in Computer Science","volume-title":"Spatial Data Types for Database Systems---Finite Resolution Geometry for Geographic Information Systems","author":"Schneider M.","unstructured":"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. 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."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/647524.728350"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56094-1_23"},{"key":"e_1_2_1_36_1","volume-title":"Spatial Databases: A Tour","author":"Shekar S.","year":"2003","unstructured":"Shekar , S. and Chawla , S . 2003 . Spatial Databases: A Tour . Prentice Hall , Englewood Cliffs, NJ . Shekar, S. and Chawla, S. 2003. Spatial Databases: A Tour. Prentice Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675470"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science","volume":"692","author":"Worboys M. F.","unstructured":"Worboys , M. F. and Bofakos , P . 1993. A canonical model for a class of areal spatial objects . In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science , vol. 692 . Springer-Verlag, Berlin, Germany, 36--52. Worboys, M. F. and Bofakos, P. 1993. A canonical model for a class of areal spatial objects. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science, vol. 692. Springer-Verlag, Berlin, Germany, 36--52."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132865","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132863.1132865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132863.1132865"],"URL":"https:\/\/doi.org\/10.1145\/1132863.1132865","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}