---
title: "Consistency Checking of Basic Cardinal Constraints over Connected Regions"
authors:
  - "Isabel Navarrete"
  - "Antonio Morales"
  - "Guido Sciavicco"
doi: ""
url: "https://ijcai.org/proceedings/2007/78"
pdf: "https://ijcai.org/proceedings/2007/0078.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "495-499"
track: ""
keywords:
---

# Consistency Checking of Basic Cardinal Constraints over Connected Regions

Isabel Navarrete, Antonio Morales, Guido Sciavicco

*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.