Consistency checking of basic cardinal constraints over connected regions
Isabel Navarrete, Antonio Morales, Guido Sciavicco · 2007
In this paper we study a recent formal model for qualitative spatial reasoning with cardinal direction relations. We give an O(n4) algorithm to check the consistency of a network of basic cardinal con-straints with variables ranging over the set of con-nected 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(n5), 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 disjunc-tive 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. 1