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

NP-hardnessreductionqualitative spatial reasoningcardinal direction calculusconsistency checking

Mathematics Subject Classification ID

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

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)

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

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)