On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus
Abstract
The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question of the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the “Region Connection Calculus” RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.
Cite
Text
Renz and Nebel. "On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus." International Joint Conference on Artificial Intelligence, 1997. doi:10.1016/S0004-3702(99)00002-8Markdown
[Renz and Nebel. "On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus." International Joint Conference on Artificial Intelligence, 1997.](https://mlanthology.org/ijcai/1997/renz1997ijcai-complexity/) doi:10.1016/S0004-3702(99)00002-8BibTeX
@inproceedings{renz1997ijcai-complexity,
title = {{On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus}},
author = {Renz, Jochen and Nebel, Bernhard},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1997},
pages = {522-527},
doi = {10.1016/S0004-3702(99)00002-8},
url = {https://mlanthology.org/ijcai/1997/renz1997ijcai-complexity/}
}