Consistency Checking of Basic Cardinal Constraints over Connected Regions
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 495-499.
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.
@inproceedings{ijcai2007p78,
title = {Consistency Checking of Basic Cardinal Constraints over Connected Regions},
author = {Navarrete, Isabel and Morales, Antonio and Sciavicco, Guido},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {495--499},
year = {2007},
url = {https://ijcai.org/proceedings/2007/78},
}
TY - CPAPER TI - Consistency Checking of Basic Cardinal Constraints over Connected Regions AU - Navarrete, Isabel AU - Morales, Antonio AU - Sciavicco, Guido T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 495 EP - 499 UR - https://ijcai.org/proceedings/2007/78 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
