Consistency Checking of Basic Cardinal Constraints over Connected Regions
Abstract
In this paper we study a recent formal model for qualitative spatial reasoning with cardinal direction relations. We give an O(n^4) algorithm to check the consistency of a network of basic cardinal constraints with variables ranging over the set of connected regions homeomorphic to the closed unit disk (which includes a wide variety of irregular-shaped regions). To the best of our knowledge, this was an open problem. A previous algorithm for a domain that includes also disconnected regions works in $O(n^5)$, but, for the problem we consider here, such an algorithm cannot be used. Using the new algorithm we also show that the problem of deciding the consistency of a network of disjunctive cardinal constraints with variables ranging over the set of connected regions is $NP$-Complete. Our main contribution is based on results from the field of combinatorial geometry.
Cite
Text
Navarrete et al. "Consistency Checking of Basic Cardinal Constraints over Connected Regions." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Navarrete et al. "Consistency Checking of Basic Cardinal Constraints over Connected Regions." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/navarrete2007ijcai-consistency/)BibTeX
@inproceedings{navarrete2007ijcai-consistency,
title = {{Consistency Checking of Basic Cardinal Constraints over Connected Regions}},
author = {Navarrete, Isabel and Morales, Antonio and Sciavicco, Guido},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {495-500},
url = {https://mlanthology.org/ijcai/2007/navarrete2007ijcai-consistency/}
}