Consistency Checking of Basic Cardinal Constraints over Connected Regions

1 Introduction

It is widely accepted that spatial reasoning plays an important role in various artificial intelligence applications, such as geographic information systems (GISs), robot navigation, computer vision, etc. Algebraic approaches formalize spatial reasoning as constraint satisfaction problems (CSPs), which can be classified depending on the type of relations between variables representing objects of some topological (or Euclidean) space. A first broad distinction can be made between quantitative and qualitative formalisms; we are interested here in qualitative calculi for spatial reasoning [Cohn and Hazarika, 2001; Sharma et al., 1994], which allow a machine to represent and reason with spatial objects making abstractions from quantitative (or metric) knowledge. Moreover, qualitative spatial models can be classified in directional [Frank, 1996] and topological [Renz and Nebel, 1998]; the present work falls in the former category.

Different directional (or orientational) spatial reasoning formalisms have been studied for different types of objects (regions). Our work in based on a formalism, presented in [Skiadopoulos and Koubarakis, 2004], for cardinal direction relations between connected and irregular-shaped regions, which can be used to model areas in various interesting applications [Goyal, 2000]. The model we consider is very expressive since it overcomes some of the limitations of point-based [Ligozat, 1998] and box-based [Mukerjee and Joe, 1990; Balbiani et al., 1998] approximation formalisms with cardinal directions [Frank, 1996]. As a practical example [Skiadopoulos and Koubarakis, 2005], in a point-based approximation, Spain is northeast of Portugal, while in a box-based model Portugal is contained in Spain; most people would agree that none of this representation is accurate, since Spain lies partially at the northwest, at the north, at the northeast, at the east and at the southeast of Portugal.

The present work is organized as follows. In Section 2 and 3 we briefly introduce some definitions and an algorithm (given in [Skiadopoulos and Koubarakis, 2005]) which decides the consistency of a network of basic cardinal constraints where variables represent either connected or disconnected regions of the Euclidean space R2 . In Section 4 we exploit some results from combinatorial geometry which are essential for what we accomplish in Section 5; that is, the design of a consistency checking algorithm for a network of basic cardinal constraints over connected regions. We prove the correctness of the algorithm, we analyze its complexity and we show that the same problem for disjunctive constraints is NP-complete, before concluding.

2 A Formal Model for Cardinal Relations

In this section, we shortly revise the main definitions of Skiadopoulos and Koubarakis's formalism [2005] for qualitative spatial representation and reasoning with cardinal direction relations. The model is based on previous results for cardinal relations [Goyal, 2000; Goyal and Egenhofer, 2000].

Let REG be the set of regions of R2 that are homeomorphic to the closed unit disk; each region is closed, connected and have connected boundaries. The set of all finite unions of regions in REG is denoted by REG∗ ; regions in REG∗ may be disconnected and have holes.

Let a = a1∪· · ·∪ak ∈ REG∗ , such that each ai ∈ REG, and consider the orthogonal axes of the space R2 . The symbols a-x (resp., a+x ) and a-y (resp., a+y ) denote the infimum (resp., the supremum) of the projection of each region ai on the x-axis and y-axis. The minimum bounding box of region a, denoted mbb(a), is the box formed by the straight lines x = a-x , x = a+x , y = a-y , y = a+y . Any box with area greater than 0 will be called non-trivial box. We will refer to a-x , a+x , a-y , a+y as the endpoints of mbb(a). By considering the axes of mbb(b), where b is called the reference region, the space is divided into 9 areas that are represented by the tile-symbols B, S, SW, W, NW, N, NE, E, SE (see Figure 1). Tile-areas are closed, unbounded (except for B(b)), pairwise disjoint (or with a non-trivial box intersection) and their union is R2 . An expression like R1:R2: . . . :Rk, where 1 < k ≤ 9 and such that each Ri is a tile-symbol will be called a multitile-symbol, and it denotes the union of the corresponding tile-areas.

A basic cardinal relation (BC-relation, for short) is a binary relation, denoted by a tile or a multitile-symbol R = R1: · · · :Rk, that is defined as:

A formula a R b where a, b are variables ranging over REG∗ and R is a BC-relation is a basic cardinal constraint (BCconstraint, for short) 1 .

When R is a tile-symbol we have that a R b ⇔ a ∈ R(b), which can be equivalently expressed as a conjunction of binary order constraints between the endpoints of mbb(a) and mbb(b), that is, as a set of binary constraints of the point algebra (PA) [van Beek, 1992]. This fact can be used to define the satisfiability of a BC-constraint, as follows. A BCconstraint aR1: · · · :Rk b is satisfiable iff there is an assignment of regions in REG∗ to the primary variable a, the reference variable b and the component variables of a w.r.t. b, that is, ab1 , . . . , abk , in such a way that the following constraints hold:

• order constraints: ab1 R1 b ∧ · · · ∧ abk Rk b;
• union constraint: a = ab1 ∪ · · · ∪ abk .

The set of BC-relations over REG∗ is denoted by D∗ and contains Σ9i=1 (9i ) = 511 elements. Elements in the set 2D∗ are called cardinal relations, and they can be used to represent indefinite information, since they may be disjunctive.

An interesting restriction of this model can be obtained by constraining regions variables to range over REG. In this case, the set of BC-relations is denoted by D, and contains only 218 out of the 511 elements of D∗ . For example, there are no regions a, b in REG such that aE:W b holds, so E:W /∈ D. As in the previous case, 2D denotes the set of all cardinal relations over REG.

1 Sometimes we will use Ra,b for denoting the cardinal relation between variables a and b.

In order to solve spatial reasoning tasks with cardinal constraints, one can use a binary constraint network [Dechter, 2003] with a set of variables V representing regions of REG∗ (resp., REG) and a set of constraints C based on the opportune set of cardinal relations between variables. The main problem is, as usual, determining whether the network is consistent or not. A network N with variables V = {a1, . . . , an} over REG∗ (resp. REG) is consistent iff there exists a solution given by an n-tuple (α1, . . . , αn) ∈ (REG∗ )n (resp. REGn) such that all cardinal constrains in C are satisfied by the assignment ai = αi, ∀1 ≤ i ≤ n. In the next section we deal with the "easiest" case consisting of a network with BC-constraints only.

3 Consistency of BC-constraints over REG∗

In [Skiadopoulos and Koubarakis, 2005] the authors present an ad-hoc algorithm (which will be called here SK-CON) for consistency checking of a network of basic cardinal constraints with variables ranging over REG∗ . Such an algorithm is quite complicated, and, in our view, it presents at least two important problems: 1) its time complexity is high, i.e, O(n5 ), and 2) it is not guaranteed to work when the domain is restricted to the set REG of connected regions. The algorithm takes as input a network N with a set C of BCconstraints from D∗ , a set V with n variables (ranging over REG∗ ), and it returns 'Consistent' if N is consistent; otherwise it returns 'Inconsistent'. Let us briefly summarize the idea of the three steps (S1, S2, S3) of the algorithm 2 .

Begin of SK-CON

S1 Translation:

• For each Cba ∈ C of the form aR1: · · · :Rk b, consider the set of component variables S ba = {ab1, . . . , abk }, and map Cba into a set of order constraints Oba between the endpoints of mbb(a), mbb(b) and mbb(abi ) for each component variable abi ∈ S ba. Notice that the constraints in Oba are logically implied by the spatial configuration expressed by Cba;
• Form a point algebra CSP (PA-CSP) with the set of constraints CO = ⋃a,b∈V Oba and the set of variables V O defined as the set of all endpoint variables obtained from the previous step.

S2 Order constraint checking:

• Solve the PA-CSP with CSPAN algorithm [van Beek, 1992] and, if possible, obtain a solution σO for the order constraints, otherwise return 'Inconsistent';
• Derive a maximal solution μO , by considering, for each pair of variables a, b and each abi ∈ S ba , the solution-box αbi for abi , and extending it in all possible directions until it touch whatever line, from the solution-boxes for the mbbs of variables a and b, is closer to it. (See Example 1).
• S3 Union constraint checking: Check if a solution for the network N can be obtained upon the maximal

2 It is worth noticing that this algorithm takes, with examples and partial results, fourteen pages to be presented. We here introduce some small changes in the original notation for the sake of clarity.

solution μO . This control is performed by using the function GLOBALCHECKNTB, which decides if the set of union constraints CU derived from the set of BCconstraints C can also be satisfied. If so, the algorithm returns 'Consistent'; otherwise it returns 'Inconsistent'.

End of SK-CON

It is worth noticing that step S1 introduces new variables in such a way that the PA-CSP works actually with O(n2 ) variables. Thus, since CSPAN has quadratic time-complexity, the complexity of step S2 is O(n4 ). At the same time, the function GLOBALCHECKNTB takes into consideration each variable a ∈ V in turn, and it checks if the sets Σb1 a , . . . ,Σbm a of maximal solutions corresponding to each set S bi a of component variables of a w.r.t any reference variable bi ∈ V , satisfy or not the following predicate:

Non-Trivial Box (NTB):

For all σ ∈ Σb1 a ∪ · · · ∪ Σbm a there exists a tuple (σ1, . . . , σm) ∈ Σb1 a ×· · ·×Σbm a such thatmbb(σ)∩ mbb(σ1) ∩ · · · ∩mbb(σm) is a non-trivial box.

Predicate NTB holds iff function CHECKNTB (Σb1 a , . . . ,Σbm a ) returns 'True':

Function CHECKNTB (Σb1 a , . . . ,Σbm a ) For every s in Σb1 a ∪ · · · ∪Σbm a Do Q = {s}; For every Σ′ in {Σb1 a , . . . , Σbm a } Do Q′ = ∅; For every s′ in Σ′ and every q in Q Do If mbb(s′) ∩ mbb(q) is a non-trivial box Then Q′ = Q′ ∪ {mbb(s′ ) ∩ mbb(q)}; If Q′ = ∅ Return 'False' Q = Q′ ; Return 'True';

This function works in O(n4 ) and it is called for each variable a ∈ V . Hence step 3 of the SK-algorithm is O(n5 ), which gives the overall time complexity of the algorithm.

Satisfiability of NTB for variable a ∈ V supposes that there is an assignment a = α so that for each reference variable bi, with aR1i: · · · :Rki b, there is also an assignment abi 1i = αbi 1i , . . . , abi ki = αbi ki for its component variables such that union constraint fromCbi a is satisfied, that is, α = αbi 1i ∪ · · · ∪ αbi ki and the order constraints in Obi a are also satisfied. GLOBALCHECKNTB guarantees that such an assignment is posible for any variable and hence, there is an assignment ai = αi, (αi ∈ REG∗ ) for each ai ∈ V such that order and union constraints in CO and CU are satisfied and thereby all BC-constraints are satisfied and the network is consistent.

Example 1 ([Skiadopoulos and Koubarakis, 2005]) Let C be the following set of BC-constraints on region variables a, b and c: {aB:N:Eb, aB:S:Wc, bSWc}. Figure 2 shows mmb(α),mmb(β),mmb(γ) found for variables a, b and c, respectively. When considering aB:N:Eb the maximal solutions for component variables of a is the set Σba = {αb1 , αb2 , αb3} and when considering a B:S:W c is Σca = {αc1 , αc2 , αc3}.

4 Cardinal Constraints and Helly-type theorems

In order to design a consistency algorithm for a network of BC-constraints over REG we will keep the first 2 steps of the algorithm SK-CON, while we will substitute the last step with a more efficient method, which, as we will show, is suitable for constraints in D. We will accomplish such a result with the help of Helly-type theorems of combinatorial geometry [Eckoff, 1993].

Helly's theorem (in its original formulation) states that if F = {K1, . . . ,Kn} is a family of convex sets in a ddimensional Euclidean space Ed, and for every choice of (d + 1) of these sets, being (d + 1) ≤ n, there exists a point that belongs to all the chosen sets, then there exists a point that belongs to all the sets K1, . . . ,Kn, that is, ⋂ F ̸= ∅. This result gave rise to a whole family of theorems (called Helly-type theorems) that present the same logical structure, and include those in which it is shown that the fact that every subfamily of k sets meets a certain property P implies that the whole family meets the same property P . The constant k is called the Helly number.

The key idea is to find out whether our problem, that is, the consistency of BC-constraints over REG, is expressible, at least in part, as the problem of checking whether a family of sets in R2 , namely, the family Fa = {Σb1 a , . . . ,Σbm a } of sets of maximal solutions for component variables of a w.r.t any of its reference variables bi, satisfies the predicate NTB, in such a way that a Helly-type theorem of number 3 is applicable. If it is so, one can find an O(n3 ) function for deciding if the whole family satisfies the predicate NTB, under the hypothesis that such property can be checked, for any 3-members subfamily, in constant time. The following generalization of Helly's theorem turned out to be a very useful result:

Helly's Topological Theorem: Let F be a finite family of closed sets in Rd such that the intersection of every k members of F is a cell, for k ≤ d, and it is nonempty for k = d + 1. Then ⋂ F is a cell.

For the case d = 2, the expression "⋂ F is a cell" means that the intersection is a region homeomorphic to the closed unit disk, that is, it belongs to REG. Thus, before using this theorem we need to prove a sufficient condition to assure that the intersection of any two sets of Fa belongs to REG.

A common technique in CSP is using composition of relations for constraint propagation in order to decide consistency or just to prune the search space. In [Skiadopoulos and Koubarakis, 2004] a composition operation ◦ for cardinal relations is defined, but it turns out to be a weak composition, in the sense that it only guarantees that, if aR1 b and bR2 c holds, then aR1 ◦ R2 c also holds. An algebraic closure algorithm for a network of binary constraints is essentially a path-consistency algorithm based on a weak composition operator [Renz and Ligozat, 2005]. Such an algorithmmakes the input network A-closed. Unfortunately, a BC-constraint network over REG may be A-closed but not consistent 3 . The following is an example (borrowed from [Skiadopoulos and Koubarakis, 2004]) of an inconsistent BC-network which is A-closed:

Example 2 Consider the following set of BCconstraint between the variables a, b, c, and d: {a B:SW:W:N: NE b, a B:SW:W:E:SE c,a B:SW:W:E: SE d, b B:S:SW:W:E:SE c, b S:SW d, d B:W:NW:N: NE:E c}. This network is A-closed but inconsistent.

Nevertheless, an A-closure procedure can still be useful for us, as we will see now. If the domain for regions is REG and the set of constraints is D, then each set Σbi a of the family Fa obtained in step 2 of the algorithm SK-CON is, by construction, a region of REG (see again Example 1). Obviously, this is not true if the constraints belong to (D∗ - D).

Lemma 1 If a network N with constraints in D is A-closed, then for any variable a and any subset B ⊆ Fa with |B| = 2, the intersection ⋂ B is a region of REG.

Proof. If N is A-closed, by definition, there is a solution for any 3 variables (i.e., one can draw 3 regions satisfying all the constraints), which, in general, does not imply that a solution for any 2 variables can be extended to a solution for 3 variables (this may not be true when using a weak composition). In particular, there is a partial solution for variable a and any other two bi, bj. Since Σbi a is a maximal connected region w.r.t the relation Ra,bi between variable a and variable bi, and similarly for Σbj a w.r.t the relation Ra,bj , then Σbi a ⋂ Σbj a must be a region from REG, otherwise we would have that (Ra,bi ◦ Rbi,bj ) ∩ Ra,bj = ∅, or (Ra,bj ◦ Rbj,bi ) ∩Ra,bi = ∅, which contradicts the assumption of N being A-closed. □

Example 3 Consider the set of BC-constraint showed in Example 1. The A-closure algorithm detects that such set is inconsistent because (B:N:E ◦ SW) ∩ B:S:W = ∅. So aB:S:Wc is not feasible. Figure 2 shows that Σba ⋂ Σca is the union of two disconnected regions I1 and I2.

Still, we cannot directly apply Helly's topological theorem, because we can prove that the intersection of two sets of the family Fa is a region from REG but, when considering a third set of the family, the nonempty intersection condition only implies that the intersection of all sets of Fa is a region of REG. What we need is that the intersection is a region not only connected but also with a special shape compatible the with binary constraints between primary variable a, and the reference variables b1, . . . , bm. Nevertheless, we can state a Helly-type theorem for the family Fa and the predicate NTB with Helly number 3.

3 The details on this point are omitted due to space limitation.

Theorem 1 Let Fa = {Σb1 a , . . . ,Σbm a } be the family of sets of the maximal solutions for component variables of a w.r.t any of its reference variables bi in an A-closed BC-network N over REG. If for every subfamily B ⊆ Fa, with |B| = 3, NTB holds for B, then NTB holds for Fa.

Proof. First, notice that, for every subfamily with |B| = 2, we have that ⋂ B ∈ REG, by Lemma 1, and when |B| = 3, since predicate NTB guarantees that ⋂ B ̸= ∅ then, by Helly's topological theorem, we have that ⋂ Fa ∈ REG. It remains to show that NTB holds for Fa. Let us proceed by induction.

Suppose that NTB holds for every subfamily Bk = {Σb1 a , . . . ,Σbk a } of size k, and consider the intersection Ik = Σb1 a ∩ · · · ∩ Σbk a . By Helly's topological theorem, Ik is a connected region and, since NTB holds for B by induction hypothesis, this implies that indeed Ik is the maximal partial solution for variable a w.r.t variables b1, . . . , bk, so that all BC-constraints Cbi a from the subnetwork N, with variables a, b1, . . . , bk, are satisfied. This is true because Ik is the non-disjoint union (since Ik is connected) of all tuples (σ1, . . . , σk) ∈ Σb1 a × · · · × Σbk a for which mbb(σ) ∩ mbb(σ1) ∩ · · · ∩ mbb(σm) is a non-trivial box, for every σ ∈ Σb1 a ∪ · · · ∪ Σbk a . Hence, if we add a new set Σbk+1 a to Bk, forming a subfamily Bk+1, then we have that Ik ∩Σbk+1 a is also a connected region from REG (by Helly's topological theorem) and it also satisfies predicate NTB, since Ik is a maximal partial solution for a w.r.t. variables b1, . . . bk, as we said above. Otherwise Σbk+1 a contains a convex subset σ′ , which corresponds to a maximal solution-box for some component variable abk+1 i of a w.r.t bk+1, so that that σ′ has not a non-trivial box intersection with some solution-box of other component variable abp j of a w.r.t variable bp of the subnetwork Nk restricted to variables a, b1, . . . bk. This means that the constraints between 3 variables, namely a, bp and bk+1, are not satisfied. But this is not possible under the assumption that N is A-closed. Hence NTB holds for Bk+1, and so NTB holds for the family Fa, as we wanted to prove. □

5 Consistency of BC-constraints over REG

In this section we present an O(n4 ) algorithm for consistency checking of a BC-constraint network over the set of connected regions REG. Such a problem, to the best of our knowledge, was still open. A restricted case, solved in [Cicerone and Felice, 2004], is the pairwise-consistency problem, that is, deciding if one relation Ri,j is consistent with Rj,i, which has the primary and reference variables interchanged. We can solve here the consistency problem of the overall network, not only the pairwise-consistency with two variables. Our algorithm will make use of the following subparts:

• An algebraic closure algorithm (AC, for short), which uses the operations of (weak) composition, inverse, and intersection of relations [Skiadopoulos and Koubarakis, 2004];
• Step 1 and 2 of the algorithm SK-CON (see Section 3).

• A procedure for the global check of NTB through the function CHECKNTB of SK-CON applied to every three sets, as Theorem 1 suggests.

Our algorithm, called REG-BCON, takes as input a network N with a set C of BC-constraints from D, and a set V with n variables (ranging over REG), and it returns 'Consistent' if N is consistent; otherwise it returns 'Inconsistent'. In what follows, we briefly summarize the structure of REG-BCON.

Begin of REG-BCON

• S0 Preprocessing: Apply AC to N, and if N is not Aclosed return 'Inconsistent';
• S1 Translation: (Step 1 of SK-CON).
• S2 Order constraint checking: (Step 2 of SK-CON).
• S3 Union constraint checking: Check if NTB holds for any variable, that is,

For each variable a ∈ V Do For every tuple (bi, bj, bk) of variables in V Do If 3CHECKNTB (Σbi a ,Σbj a ,Σbk a ) returns 'False' Then Return 'Inconsistent'; Return 'Consistent';

End of REG-BCON

Clearly, the function 3CHECKNTB has exactly the same structure of function CHECKNTB (of the algorithm SKCON), with the only exception that it is called over 3 sets instead of (at most) n sets.

Theorem 2 Algorithm REG-BCON correctly decides whether a network of BC-constraints over REG is consistent.

Proof. The correctness of the algorithm follows from Theorem 1 and from the correctness of algorithm SK-CON. The latter establishes that the set of BC-constraints is consistent if and only if 1) the set of order constraints CO has a maximal solution μO ; 2) a solution for the network N can be obtained upon the maximal solution μO , that is, the union constraints in CU are also satisfied.

We can now proceed exactly as in the case of SK-CON, but for the case of a network of BC-constraints over REG. In fact, if algorithm REG-BCON returns 'Inconsistent', then there is no solution for the network. This may happen either when the network is not A-closed (step 1), or when order constraints are not satisfied (step 2), or when union constraints are not satisfied (step 3). Otherwise, the network is consistent because there is a maximal solution that satisfies order and union constraints by correctness of step 2 and by Theorem 1. Indeed, for every variable a there is a consistent assignment, which is precisely a = ⋂ Fa, since Theorem 1 guarantees that ⋂ Fa is a region fromREG for which NTB holds. □

Theorem 3 Algorithm REG-BCON is O(n4 ).

Proof. Step 0 is O(n3 ) due to the time complexity of algorithm AC and the fact that all constraints are basic (see [van Beek, 1992] for similar case). Step 1 is O(n2 ) and step 2 is O(n4 ), as we discuss in Section 3. But now step 3 is O(n4 ) since 3CHECKNTB works in constant time. Hence REG-BCON is O(n4 ). □

A deeper analysis would reveal that 3CHECKNTB performs no more than 81 elementary operations of intersection of boxes. So, to be precise, our algorithm is O(81 × n4 ), but algorithm SK-CON is O(81 × n5 ). The constant k = 81 may be decreased taking into account that any region Σbi a is the union of at most 3 line-connected convex sets. By lineconnected we mean that there is a vertical or horizontal line joining two regions. Step 2 of the algorithm can be modified so that when it obtains a set of maximal solutions Σba, the solution-boxes of Σba may be joined to form a new set Γba of at most 3 convex sets. For instance, if aB:N:Eb and Σba = {αb1, αb2, αb3}, as in Figure 2, αb1, αb2 may be joined into one convex set, since they corresponds to adjacent tiles B, N. This is just a matter of comparing the endpoints of mbb(αb1 ), mbb(αb2), as it is done for the intersection of boxes. Thereby, step 3 only has to make 3 × 3 intersection operations.

The process of joining adjacent tiles can also be exploited to obtain a solution for any variable a. To do so, function 3CHECKNTB has to be redesigned so that a set data structure is used instead of the queue Q, which contains the intersections of non-trivial boxes. This is possible because, as we know by Theorem 1, the intersection of partial solutions for any four variables is a region of REG.

We argue that there is no cubic time-complexity algorithm that solves the same problem. This is due to the non-convex nature of BC-constraints. A solution for the set of component variables of a w.r.t variable b, i.e. Σba , may be concave, and so, it is not representable as a set of point algebra constraints, unless the region is partitioned in convex components, as it is the case. Constraints of Example 2 represents a subnetwork of four variables for which NTB predicate is false. A BCnetwork of n variables may have a subnetwork like this, for which there is no way of detecting the inconsistency trough algebraic closure or checking the union constraints for any subnetwork of three variables.

Finally, we focus our attention to the problem of deciding the consistency of a network with (disjunctive) cardinal constraints over REG.

Theorem 4 The problem of deciding the consistency of a network N with constraints in 2D and region variables over REG is NP -complete.

Proof. Deciding the consistency of N is in NP, since a nondeterministic algorithm first guesses a basic constraint for each disjunctive one appearing in N, obtaining a network N ′ where each constraint belongs to D, and then it applies our polynomial algorithm REG-BCOM to check the consistency of N ′ . In order to prove that our problem is NP-complete, the reduction of the problem 3SAT to the problem of satisfiability of a set of cardinal constraints with variables over REG∗ , shown in [Skiadopoulos and Koubarakis, 2005], will suffice, since in such a reduction only regions over REG and constraints in 2D are used. □

6 Conclusion and Future Work

In this paper we have considered a very expressive formal model for spatial reasoning with cardinal relations. We have presented an algorithm for consistency checking of a basic cardinal constraint network over a set of connected regions. Such a problem, to the best of our knowledge, was still open. The consistency problem has been previously solved for the case of region variables over the set of finite unions of connected regions in time O(n5 ), but the method cannot be directly applied to the case considered here. We have devised an O(n4 ) algorithm by adapting the existing one for disconnected regions and by exploiting Helly's topological theorem, which gives us the key to decide if a solution can be obtained for a set of basic cardinal constraints. Moreover, the theorem has also been useful for suggesting how to decrease the time-complexity and for the task of finding a solution of the network.

For future work, we first point out that the following question remains unanswered so far: given that the consistency problem when considering the set of cardinal constraints is NP-complete, as we have proved, is it possible to find a subclass, which includes non-basic cardinal constraints, such that the consistency problem is still tractable? In fact, a tractable disjunctive subclass has been identified [Navarrete and Sciavicco, 2006] for the special case of rectangular cardinal relations, i.e., those that express relations between rectangles (a type of convex region). It is interesting to knowwhat happen when the domain includes non-convex regions.

It is worth to observe that the same consistency problem we have considered may be solved with a non-constructive method, i.e., an algorithm that uses the operations of the algebra. One of the problem of the model is that the underlaying algebra has not some desirable properties for an Euclideanexact reasoning with cardinal relations [Frank, 1996]. Possible extensions of the model, which express more accurately the exact position between two regions and includes the definition of a relational algebra, would be interesting for some applications.

Acknowledgment

This work was supported by the Spanish Ministry of Education and Science (MEC) and the European Regional Development Fund of the European Commission (FEDER) under project MEDICI (TIC2003-09400-C04-01). Special thanks to Miguela Iniesta and Francisco Balibrea for their comments about the use of Helly's topological theorem.