skip to main content
10.1145/1097064.1097098acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
Article

Dimension-refined topological predicates

Published: 04 November 2005 Publication History

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]
E. Clementini and P. Di Felice. A Comparison of Methods for Representing Topological Relationships. Information Sciences Applications, 3(3):149--178, 1995.
[2]
E. Clementini and P. Di Felice. A Model for Representing Topological Relationships between Complex Geometric Features in Spatial Databases. Information Systems, 90(1-4):121--136, 1996.
[3]
E. Clementini, P. Di Felice, and P. van Oosterom. A Small Set of Formal Topological Relationships Suitable for End-User Interaction. 3rd Int. Symp. on Advances in Spatial Databases, LNCS 692, pp. 277--295, 1993.
[4]
Z. Cui, A. G. Cohn, and D. A. Randell. Qualitative and Topological Relationships. 3rd Int. Symp. on Advances in Spatial Databases, LNCS 692, pp. 296--315, 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.

Cited By

View all
  • (2023)Defining and designing spatial queries: the role of spatial relationshipsGeo-spatial Information Science10.1080/10095020.2022.216392427:6(1868-1892)Online publication date: 17-May-2023
  • (2020)CODI: A multidimensional theory of mereotopology with closure operationsApplied Ontology10.3233/AO-200233(1-61)Online publication date: 1-Jul-2020
  • (2020)Spatial Information Retrieval in Digital EcosystemsProceedings of the 12th International Conference on Management of Digital EcoSystems10.1145/3415958.3433038(10-17)Online publication date: 2-Nov-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systems
November 2005
306 pages
ISBN:1595931465
DOI:10.1145/1097064
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. GIS
  2. SPAL2D
  3. dimension
  4. spatial databases
  5. topological predicates

Qualifiers

  • Article

Conference

CIKM05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Defining and designing spatial queries: the role of spatial relationshipsGeo-spatial Information Science10.1080/10095020.2022.216392427:6(1868-1892)Online publication date: 17-May-2023
  • (2020)CODI: A multidimensional theory of mereotopology with closure operationsApplied Ontology10.3233/AO-200233(1-61)Online publication date: 1-Jul-2020
  • (2020)Spatial Information Retrieval in Digital EcosystemsProceedings of the 12th International Conference on Management of Digital EcoSystems10.1145/3415958.3433038(10-17)Online publication date: 2-Nov-2020
  • (2018)Spatial Plateau Algebra: An Executable Type System for Fuzzy Spatial Data Types2018 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)10.1109/FUZZ-IEEE.2018.8491565(1-8)Online publication date: Jul-2018
  • (2018)Efficient Implementation Techniques for Topological Predicates on Complex Spatial ObjectsGeoinformatica10.1007/s10707-007-0035-y12:3(313-356)Online publication date: 24-Dec-2018
  • (2016)A conceptual model of fuzzy topological relationships for fuzzy regions2016 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)10.1109/FUZZ-IEEE.2016.7737976(2271-2278)Online publication date: Jul-2016
  • (2016)Topological Relationships Between MapsMap Framework10.1007/978-3-319-46766-5_7(81-94)Online publication date: 5-Oct-2016
  • (2016)A Formal Model of Maps as a Fundamental TypeMap Framework10.1007/978-3-319-46766-5_2(15-26)Online publication date: 5-Oct-2016
  • (2012)Region-Based Theories of SpaceQualitative Spatio-Temporal Representation and Reasoning10.4018/978-1-61692-868-1.ch001(1-62)Online publication date: 2012
  • (2012)A Formalization of Topological Relations Between Simple Spatial ObjectsAdvances in Spatial Data Handling10.1007/978-3-642-32316-4_5(61-75)Online publication date: 3-Nov-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media