Consistency Checking of Basic Cardinal Constraints over Connected Regions

Isabel Navarrete, Antonio Morales, Guido Sciavicco

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.