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

DOI10.1016/j.artint.2011.07.005zbMath1238.68155arXiv1011.0233OpenAlexW2075389410WikidataQ62042747 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

reductionNP-hardnessqualitative spatial reasoningcardinal direction calculusconsistency checking

Mathematics Subject Classification ID

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

Related Items (4)

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

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

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