Reasoning about topological and cardinal direction relations between 2-dimensional spatial objects

Anthony G. Cohn*, Sanjiang Li, Weiming Liu, Jochen Renz

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    28 Citations (Scopus)

    Abstract

    Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from multiple calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculi was very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning, the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. We consider two different interpretations of the RCC8 algebra, one uses a weak connectedness relation, the other uses a strong connectedness relation. In both interpretations, we show that reasoning with topological and directional information is decidable and remains in NP. Our computational complexity results unveil the significant differences between RA and CDC, and that between weak and strong RCC8 models. Take the combination of basic RCC8 and basic CDC constraints as an example: we show that the consistency problem is in P only when we use the strong RCC8 algebra and explicitly know the corresponding basic RA constraints.

    Original languageEnglish
    Pages (from-to)493-532
    Number of pages40
    JournalJournal of Artificial Intelligence Research
    Volume51
    DOIs
    Publication statusPublished - 14 Oct 2014

    Fingerprint

    Dive into the research topics of 'Reasoning about topological and cardinal direction relations between 2-dimensional spatial objects'. Together they form a unique fingerprint.

    Cite this