Reasoning about cardinal directions between extended objects: the NP-hardness result

DOI10.1016/J.ARTINT.2011.07.005MaRDI QIDQ420805zbMATH OpenOpenAlexWikidataFDO

Authors Weiming Liu, Sanjiang Li

Publication date 23 May 2012

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.0233

zbMATH Keywords

cardinal direction calculusconsistency checkingNP-hardnessqualitative spatial reasoningreduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The cardinal direction calculus (CDC) proposed by Goyal and Egenhofer is a very expressive qualitative calculus for directional information of extended objects. Early work has shown that consistency checking of complete networks of basic CDC constraints is tractable while reasoning with the CDC in general is NP-hard. This paper shows, however, if allowing some constraints unspecified, then consistency checking of possibly incomplete networks of basic CDC constraints is already intractable. This draws a sharp boundary between the tractable and intractable subclasses of the CDC. The result is achieved by a reduction from the well-known 3-SAT problem.

Recommendations

• Reasoning about cardinal directions between extended objects
• On the consistency of cardinal direction constraints
• Cardinal directions between spatial objects: the pairwise-consistency problem
• Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra
• scientific article; zbMATH DE number 6747941

Cites work

• Cardinal directions between spatial objects: the pairwise-consistency problem
• Composing cardinal direction relations
• Maintaining knowledge about temporal intervals
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• On the consistency of cardinal direction constraints
• RCC8 binary constraint network can be consistently extended
• Reasoning about cardinal directions between extended objects
• Reasoning about qualitative temporal information
• Reasoning about temporal relations
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Region connection calculus: Its models and composition table

Cited in

(10)

• On the consistency of cardinal direction constraints
• Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra
• Qualitative constraint satisfaction problems: an extended framework with landmarks
• scientific article; zbMATH DE number 7453140 (Why is no real title available?)
• Reasoning about cardinal directions between 3-dimensional extended objects using answer set programming
• scientific article; zbMATH DE number 6747941 (Why is no real title available?)
• Qualitative reasoning about 2D cardinal directions using answer set programming
• Cardinal directions between spatial objects: the pairwise-consistency problem
• On redundant topological constraints
• Reasoning about cardinal directions between extended objects

This page was built for publication: Reasoning about cardinal directions between extended objects: the NP-hardness result

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q420805)