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 irregularshaped 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.
Consistency Checking of Basic Cardinal Constraint over Connected Regions
SCIAVICCO, Guido
2007
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 irregularshaped 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.I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
