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

DOI10.1016/j.artint.2011.07.005zbMath1238.68155arXiv1011.0233WikidataQ62042747 ScholiaQ62042747MaRDI QIDQ420805

Sanjiang Li, Weiming Liu

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

reduction; NP-hardness; qualitative spatial reasoning; cardinal direction calculus; consistency checking

Mathematics Subject Classification ID

68T27: Logic in artificial intelligence

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra, Qualitative constraint satisfaction problems: an extended framework with landmarks, On redundant topological constraints

Cites Work

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