A New Tractable Subclass of the Rectangle Algebra

1 Introduction

Spatial representation and reasoning concern many ar­ eas of artificial intelligence: computer vision, geographic information , natural language understanding, computer­ aided design, mental imagery, etc. These last ten years, numerous formalisms for reasoning about space were proposed [Egenhofer et al., 1991; Mukerjee et al., 1990; Freska, 1992; Randell et al. , 1992]. We can mention as an example the well-known model of the regions proposed by Cohn, Cui and Randell [Randell et al. , 1992] whose objects are the regions of a topological space and rela­ tions are eight topological relations , and for which Renz and Nebel [Renz et al., 1997] characterize a maximal tractable subclass of relations. Although this formalism is very attractive, it suffers from the impossibility of ex­ pressing orientation relations.

An example which enables this is the rectangle algebra (RA) [Giisgen, 1989; Mukerjee et al., 1990; Balbiani et al., 1998]. It is an extension for the space of the better known model for reasoning about time: the interval alge­ bra (IA) proposed by Allen [Allen , 1983]. The basic ob­ jects of this spatial formalism are the rational rectangles J.-F. Condotta, L. Farinas del Cerro Institut de recherche en informatique de Toulouse

118 route de Narbonne

F-31062 Toulouse Cedex 4, France

{ condotta,farinas }@irit.fr

whose sides are parallel to the axes of some orthogonal basis in a 2-dimensional Euclidean space. Though re­ strictive, it is sufficient for applications in domains like architecture or geographic information. The relations between these objects are the 13 x 13 pairs of atomic relations which can hold between two rational intervals . These relations are very expressive, with them we can express both directional relations such as left-of, right­ of, above, etc., and topological relations such as disjoint , overlap, etc., between two rectangles .

In RA, spatial information are represented by spatial constraint networks which are special constraint satis­ faction problems (CSPs). In these CSPs, each variable represents a rational rectangle and each constraint is rep­ resented by a relation of RA.

Given a spatial constraint network, the main problem is to know whether or not it is consistent, i.e, whether or not the spatial information represented by the network is coherent. Generally, this problem is NP-complete, but we can find subsets of the whole relations of RA for which this problem is polynomial , as in lA [Nebel et al. , 1994; Beek, 1992]. Notably, in [Balbi ani et al., 1998], Bal­ biani et al. presented a tractable set of relations called saturated-preconvex relations. In this paper, we present a new tractable set: the set of strongly-preconvex rela­ tions. This set contains the saturated-preconvex rela­ tions . We also prove that the well-known method, the path-consistency method, is complete for this set. To prove these results, we introduce a new method, called the weak path-consistency method, which is almost the path-consistency method.

The remainder of the paper is organised as follows . In Section 2, we make some recalls about RA, moreover we introduce the weakly-preconvex relations. Section 3 is concerned with some properties of fundamental oper­ ations: composition, intersection and inverse. In Sec­ tion 4, we discusse spatial constraint network and we present the weak path-consistency method. Section 5 is concerned with the tractability results. In section 6, we define the strongly-preconvex relation and Section 7 concludes with suggestions for further extensions.

2 The rectangle algebra

The considered objects are the rectangles whose sides are parallel to the axes of some orthogonal basis in a 2-dimensional Euclidean space. The basic relations be­ tween these objects are defined from the basic relations of the interval algebra (denoted by Bint and represented in the figure 2) in the following way :

Brec constitutes the exhaustive list of the relations which can hold between two ration"al rectangles. For example, in figure 1, two rational rectangles satisfy the basic rela­ t ion (m, p) of Brec. The set of the relations of the rect-

angle algebra is defined as the power set of Brec. Each relation of 2 6 rec can be seen as the union of its basic re­ lations. We obtain 2 169 relations. Let R be a rectangle relat ion of 2 6 r ec, we call the proj ections of R the two relations of 2 13 ;n, , denoted by R1 and R2 and defined by:

Ligozat [Ligozat, 1 994] arranges the basic relations of the interval algebra in a partial order S which defines a lattice called the interval lattice (see fig . 3). From this partial order we define the partial order :::S on Brec : (A, B) :::S (C, D) iff AS C and B S D, with (A, B) , (C, D) E Brec·

(Br ec, :::S) defines a lattice that we call the rectangle lat­ tice. The convex relations of lA and RA correspond to the intervals in the interval lattice and in the rectangle lattice respectively. We can prove that a convex relation R of RA is the cartesian product of its proj ections and that its projections are both convex relations of lA.

For each relation R of lA and RA, there exists a small­ est convex relation ofiA and RA respectively, which con­ tains R. According to Ligozat 's notation, we denote this relation by I(R) (the convex closure of R). We can easily prove the following proposition:

P roposit ion 1 Let R E 2 6 rec be, I(R) = I(Rt) x I(R2).

In [Ligozat, 1994], a basic relation of lA is represented by a region of the Euclidean plane and a relation of lA by the union of the regions representing its basic relations. With this representation two concepts are defined - the dimension and the topological closure of a relation of lA - in the following way:

• the dimension of a basic relation A (see figure 2), denoted by dim( A) , corresponds to the dimension of its representation in the plane, i.e. 0, 1 or 2. The dimension of a relation R is the maximal dimension of its primitives.
• The topological closure of a basic relation A, de­ noted by C(A) is the relation which corresponds to the topological closure of the region of A (see Ta­ ble 1). For a relation R, C ( R) is the union of the topological closure of its basic relations.

These definitions use a geometrical representation of the basic relations , but we shall express them differently. In lA, each basic relation forces zero, one or two endpoint equalities . For example, between two intervals the basic relation eq imposes the first and the second endpoints to be equal whereas the basic relation p imposes no equality. We can use the following definition:

Defin i t ion 1 the dimension of a basic relation A of B;nt is the maximal number of equalities which can be imposed by a basic relation (i.e. 2) minus the number of equalities imposed by the basic relation A.

Table 1: The topological closure of the atomic relations of IA.

Then we can easily extend this definition to RA:

Definition 2 the dimension of a basic relation of Brec is the maximal number of endpoint equalities that a ba­ sic relation can impose between the orthogonal axe pro­ jections of two rectangles {i.e. 4) minus the number of endpoint equalities imposed by the basic relation.

For example, the dimension of the basic relation (m,p) (see figure 1) is 3. The dimension of a relation R of 2 6 r ec is the maximal dimension of its basic relations, and we suppose that the dimension of the empty relation is -1. It is easy to prove the following facts:

Proposition 2

• let (A, B) be a basic relation of B rec, dim((A , B))= dim(A) + dim(B);
• let R E 2 6 r ec be a convex relation, dim( R) dim(RI) + dim(R2).

To extend the definition of the topological closure to RA we use directly the topological closure of the atomic relations of IA (see Table 1) by the following ways:

Definition 3

• let (A, B) E B rec be, C((A, B))= C(A) x C(B) ;
• let R E 2 6 rec be, C(R) = U{C((A,B)): (A , B) E R}.

Although speaking of topological closure doesn't make any sense because we don 't use regions to represent the relations of RA, we shall continue to use the term as in IA. We can prove the following proposition :

Proposition 3

• let R , S E 2 6 rec be, C(R) o C(S) s;; C(R o S);
• let R be a convex relation of2 6 r·c, C(R) = C(RI) X C(R2);
• let R be a convex relation of2 13 r ec, for all (A, B) E R there exists ( C, D) E R such that dim( ( C, D)) = dim(R) and (A, B) E C ((C, D)).

Proof. (Sketch) Ligozat proves the first part of this proposition for two relations of IA. Using this result we can also prove this for RA. The proof of the second part is obvious . To prove the third one, first we prove it for IA by examining the exhaustive list of the convex rela­ tions of IA. And from this result and the first two parts we prove the result for RA. 0

In [Ligozat , 1994], the preconvex relations ofiA are de­ fined in the following way: a relation R of IA is a precon­ vex relation iff dim(I(R) \ R) < dim(R) - an equivalent definition is: R is a preconvex relation iff I(R) s;; C(R). The set of preconvex relations coincides with the set of the well known ORD-Horn relations , which is the maxi­ mal tractable set of IA which contains all basic relations [Nebel et al. , 1994]. Using the convex closure and the dimension of a relation of RA, now, we are ready to de­ fine the preconvex relations in RA. We shall call these relations the weakly-preconvex relations.

Definition 4 Let R E 2 6 rec be, R is a weakly-preconvex relation iff dim(I(R) \ R) < dim(R).

Using proposition 3, we can prove:

Proposition 4 A relation R of RA is a weakly­ preconvex relation iff I ( R) s;; C ( R).

From this proposition it follows that:

Proposition 5 A relation R of RA is a weakly­ preconvex relation iff C(R) is a convex relation.

Proof. Let R be a weakly-preconvex relation of RA. From proposition 4, R s;; I(R) s;; C(R). So, C(R) s;; C(I(R)) s;; C(C(R)). Since C(C(R)) = C(R), we deduce that C(R) = C(I(R)). Given that every convex relation of IA has a convex topological closure [Ligozat , 1996], from propositions 1 and 3 we deduce that C(I(R)) is convex. Let R E 2 6 r ec be such that C(R) is convex. Since R s;; C(R), by definition of I we deduce that I(R) C C(R). o

3 Fundamental operations

The set 2 6 r ·c is enriched with the fundamental relational operations, the binary operations, intersection (n), com­ position (o) and the unary operation inverse (- 1 ). The composition of two basic relations and the inverse of a basic relation in RA can be computed from the same op­ erations in IA in the following way : (A , B) o ( C, D) = (AoC) x (BoD) and (A,B)- 1 = {A- 1 ,B- 1 ). Com­ position between two relations in 2 6 r ec is defined by : R oS = U{(A , B) o (C,D): (A , B) E R , (C, D) E S}. The inverse of a relation in 2 6 r ec is the union of the in­ verse of its basic relations. 2 6 rec is stable for these three operations. Considering a subset of 2 6 r ec, firstly we must look whether this subset is stable for these operations. We can easily prove the following proposition:

Proposition 6 for every relation R , S, T , U E 2 6 ;n, ,

• (R x S) n (T xU) = (R n T) x (S n U);
• (R X S) 0 (T XU) = (R 0 T) X (S 0 U);
• (R x s)- 1 = R- 1 x s- 1 .

Consequently, the set of the convex relations of 2 6 r ec is stable for the operations: intersection , composition and inverse. Hence the set of the convex relations of 2 6 r ec is a subclass of RA. From all this it follows that:

Proposition 7 For all relations RandS E 2 13 r ·c, I(Ro S) s;; I(R) o I(S) .

Indeed, I(R) o I (S) is a convex relation and contains the relation R o S.

Now, let us consider the subset of the weakly­ preconvex relations , we denote this set by W. We have the following result:

Proposition 8 W is stable for the operations o, - 1 but it is not stable for the operation n.

Proof. The proof of the stabili ty of the composition is the same as the one given in [Ligozat , 1994] for the sta­ bility of the preconvex relations of IA: for all relations R, S E W, I(R o S) ~ I(R) o I(S) ~ C(R) o C(S) ~ C(R o S). Hence, R o S is a weakly-preconvex rela­ tion. We notice that for all basic relation (A, B) E B,·ec, we have C((A, B)- 1 ) = C((A, B))- 1 , so for all rela­ tion R E 2 6 rec, C(R- 1 ) = C(R)- 1 . Moreover, ow­ ing to the symetry of the rectangle lattice , we have I (R- 1 ) = I(R)- 1 . From these results, the stabili ty of W for the operation inverse is obvious. D

Unlike the case of IA, the weakly-preconvex relations in RA are not stable for the intersection. We can see it with the following counter-example. Let consider the two weakly-preconvex relations R, S of 2 6 rec defined by R = {(o, o), (eq, s), (s, eq) } and S = {(d , d), (eq, s), (s, eq)} . R n S is the relation { ( eq, s), ( s, eq)} , this relation is not weakly-preconvex. This lack of stability- as we may see in the sequel - will raise some problem.

4 Constraints networks

We start this section wi th some reminders about con­ strain ts networks of RA [Balbiani et al., 1998]. A rect­ angle network N is a structure (V, C), where V = {V1 , ... , Vn} is a set of variables which represent ratio­ nal rectangles, and C is a mapping from V x V to the set 2 6 rec which represent the binary constraints between the rat ional rectangles. C is such that :

• for every i E { 1, .. . , IV I}, C;; = { ( eq, eq)};
• for every i,j E {1 , ... , lVI} , C;j = Cj;- 1 .

An interval network is defined in the same way except that V represents a set of rational intervals and C is to 20·nl.

Let N = (V, C) be a rectangle network, the consis­ tency and the path-consistency of N is defined in the following way:

• N is consistent iff there exists a mapping m from V to the set of rational rectangles such that, for every i, j E { 1, ... , lVI}, there exists a basic relation P such that P E C;1 and m; and m1 satisfy P. We call such a mapping m, a satisfying instanciation of the network N.
• N is path-consistent when, for every i, j E {1, .. . ,1VI}, C;j ::j; {}and for every i,j,k E {1, ... , lVI}, C;1 ~ C;k o Cki·

We have the same definitions for the interval networks. A convex (respectively weakly-preconvex) network is a network which contains only convex relations (respec­ tively weakly-preconvex relations).

We define another property, the weak path­ consistency. A weakly path-consistent network is an al­ most path-consistent network:

Definition 5 A rectangle (or interval) network is weakly path-consistent when, for every i, jE {1 , ... , lVI}, Cij ::j; {} andfor everyi,j , k E {1 , ... ,1VI}, C;j ~ I (Cik o Cki)·

A path-consistent network is obviously weakly path­ consistent , the contrary is not true.

A well-known polynomial method to see whether a network N = (V, C) is consistent , is the path-consistency method [Allen , 1983] . It consits to iterate on the network the triangulation operation: C;i := C;i n ( C;k o Cki) for all i, j , k E { 1, ... , IV I} , until we obtain a stable network. It is sound but not complete as a decision procedure for the issue of the consistency of a network. Indeed, if after applying the method we obtain the empty relation then the network is not consistent , in the contrary case we do not know whether the network is consistent.

Similarly, we define a weaker method that we call the weak path-consistency method . It consists to iterate the weak triangulation operation C;i := C;i n I(Cik o Cki)· The time complexity is the same as the one of the path­ consistency method . Moreover, since (C;k o Ckj) ~ I ( C;k o Ckj), this method is sound but not complete like the path-consistency method.

5 Results of tractability

Let N = (V, C) be a network and m be a satisfying instanciation of N, we shall say that m is maximal iff for all i,j E {1 , ... , lVI} , dim(P) = dim(Cij), with P the basic relation satisfied between m; and mj .

Ligozat [Ligozat, 1994] proves this important theorem:

Theorem 1 Let N be an interval network which con­ tains only preconvex relations, if N is path- consistent then there exists a maximal instanciation of N.

From this theorem we can prove the following lemma :

Lemma 1 Let N = (V, C) be a convex rectangle net­ work, if N is path-consistent then there exists a maximal instanciation of N.

Proof. Let N ' = ( V', C') and N" = (V", C") be two interval networks defined by V = V' = V" and for all i,j E {1 , ... ' lVI} , c:j = (C;j}l and c:; = (Cijh· We can prove that N' and N" are path-consistent ,see [Bal­ biani et al. , 1998]. Moreover they are convex (a fortiori preconvex 1 ). So there exists a maximal instanciation of N' and N", let us call them m' and m" respec­ tively. Let us consider the instanciation m of N such that for every i , j E { 1, . .. , I VI} , m:. is the projection of the rational rectangle m;j onto the horizontal axis and m:j is the projection of m;j onto the vertical axis.

1 We remind that the set of the preconvex relations con­ tains the set of the convex relations in lA.

It is easy to see that m is a satisfying instanciation of N. Moreover , m; (respectively m;') and mj (respectively mj') satisfy a. basic relation A (respectively B) such that dim(A) = dim(Cij) (respectively dim(B) = dim(C:j)) . So m; and mj are such that dim( (A, B)) = dim( C;j) because C;j is a convex relation. So, m is a maximal instanciation of N. 0

Consequently, for the weakly-preconvex relations of 2 6 rec, we have the following result:

Lemma 2 Let N = (V, C) be a weakly-preconvex rect­ angle network, if N zs weakly path-consistent then N is consistent, moreover there exists a maximal instancia­ tion of N.

Proof. Let N' = (V', C') be the rectangle network such that V' = V and for all i , j E {1 , ... , lVI} , c:j = I(G;j) . First , let us prove that N' is a path-consistent network: for all i, j , k E {1 , ... , lVI} we have: C;j ~ I(Cik o Ckj), then J(C;j) ~ I(I(C;k o Ckj)), consequent ly I(G;j) ~ I(Cik o Ckj) and because I(R o S) ~ I(R) o I(S) for all relations R, S E 2 6 rec, we obtain the result I( C;j) ~ I(C;k) o I(Ckj)· So, c:j ~ c:k o C~J' hence N' is path­ consistent.

N' is convex and path-consistent then there exists a maximal instanciation m of N'. For each i, j E { 1, ... , IV I}, m; and mj satisfy a basic relation P of C:j such that dim(P) = c;j. C;j is weakly-preconvex then dim(I(C;j) \ C;j) < C;j. Moreover, remind that c:j = I(C;j) , consequently P E C;j and dim(P) = dim(C;j)· Hence, m is also a maximal instanciation of the rectangle network N . 0

Because a path-consistent network is also weakly path­ consistent too , this lemma is true as well for a weakly­ preconvex network N which is path-consistent instead of weakly path-consistent.

When we apply the path-consistency method from a weakly-preconvex network, we are not sure to ob­ tain a weakly-preconvex network , because the set of the weakly-preconvex relations is not stable for the operation intersection, likewise with weak path­ consistency met hod because the intersection between a weakly-preconvex relation and a convex relation is not always a weakly-preconvex relation. For exam­ ple, the intersection between the weakly-preconvex re­ lation { ( d, d) , ( eq, s), ( s , eq)} and the convex relation {(s, s), (eq, s), (s, eq) , (eq, eq)} is {(s, eq), (eq, s)} which is not weakly-preconvex. Hence, despite the previ­ ous lemma, we cannot assert that the path-consistency method or the weak path-consistency method are de­ cision procedures for the issue of the consistency of a rectangle network which contains only weakly-preconvex relations. But we can characterise some subsets of 2 6 r· c for which it works:

Theorem 2 (Main result) Let E C W , stable for the intersection with the convex relations.

The weak path- consistency method is a decision proce­ dure for the issue of the consistency of a rectangle net­ work which contains Just constraints in E.

Proof. From the previous lemma the proof is direct. Let N be a rectangle network whose constraints are in E. After applying the weak path-consistency method from N, we obtain a network N' whose constraints are always in E and consequently which is weakly-preconvex. Moreover , N' is equivalent to N , so if N ' contains the empty relation then N' and N are not consistent. Else, from the previous lemma we deduce that there exists a maximal instanciation of N' and consequently N' and N are consistent. 0

Moreover, we can assert that path-consistency method is also complete for rectangle networks whose relations are in such a set E.

Let us denote by F the closure of a set F of relations by the operations intersection, composition and inverse. Nebel and Bi.irckert [Nebel et al., 1994] show that from an interval network whose constraints are in F we can construct, in polynomial time, another interval network whose constraints are in F and such that the former network is consistent if and only if the latter is consistent. We can prove the same thing in RA. Hence, if E is a set of rectangle relations having the properties of the previous theorem, then the problem of the consistency of the networks whose relations belong to E is a polynomial problem.

6 The strongly-preconvex relations

In this section, first , we are going to define a new set with the properties of theorem 2: the set of the strongly­ preconvex relations of RA. Then, we shall prove that this set is the maximal set for these properties.

The strongly-preconvex relations of RA are defined by:

Definition 6 Let R be a relation of 2 6 rec, R is a strongly-preconvex relation if, and only if, for all con­ vex relations S, R n S is a weakly-preconvex relation.

The universal relation of 2 6 rec is a convex relation, from this we deduce that a strongly-preconvex relation is a weakly-preconvex relation. We denote the set of the strongly-preconvex relations by S. The convex relations are stable for the intersection and are weakly-preconvex relations. So, they belong to S. What is more:

Proposition 9 If R , S E S then R n SEW.

Proof. First , we are going to prove that I(C(RnS) ) =

C(RnS). Let us denote I(C(RnS)) by T. We have R n S ~ T , so R n S ~ T n R and R n S ~ Tn S. Consequently T ~ I(C(Tn R)) and T ~ I(C(Tn S)). Because R and S are strongly-preconvex relations and T is a convex relation, T n R and T n S are two weakly-preconvex relations. Consequently C(Tn R) and C (T n S) are two convex relations hence, T ~ C (T n R) and T ~ C(T n S). When we compute the topological closure of a relation, we add only basic relations of lower dimension. So, dim(T) = dim(C(Tn R)) and dim(T) = dim(C(TnS)). Le P be a basic relation such PET and dim( P) = dim(T). From the previous results we deduce that P E C(T n R) , P E C(T n S), and dim(P) = dim(C(T n R)) = dim(C(T n S)). So, as T n R and Tn S are weakly-preconvex relations, P E TnR and P E T n S , hence P E C ( R n 5). Let Q be any basic relation belonging to T , from proposition 3, we can deduce too that Q E C(R n 5). Hence T ~ C(R n 5).

C ( R n 5) ~ I ( C ( R n 5)) ~ C ( R n 5) , so R n S is a weakly-preconvex relation of 2 6 rec . 0

Moreover, we can prove the following result:

Proposition 10 S is stable for the intersection with the convex relations of 2 6 r ec.

Proof. Let R and S be two relations of 2 6 r ec such that R is a strongly-preconvex relation and S a convex relation. Let us prove that R n Sis a strongly-preconvex relation. Let T be any convex relation , we have : (R n 5) n T = Rn(SnT) . SnT is a convex relation too. R is a strongly­ preconvex relation, we can deduce that R n (5 n T) is a weakly- preconvex relation , hence R n S is a strongly­ preconvex relation. 0

Consequently, we can apply theorem 2 on the set S . From the last two propositions we can easily prove that S is stable for the intersection. S is stable for the inverse operation too. But we have not yet succeeded in proving the composition stability, so perhaps S = S. Moreover , let E be a set with the properties of theorem 2, we can easily prove that E ~ S. From all this it follows :

Theorem 3 S is tractable and S is the maximal set in­ cluded in W and stable for the intersection with the con­ ve:r relations.

Hence, S is the maximal set with the properties of theorem 2.

A saturated-preconvex relation of 2 6 r ·c corresponds to the cartesian product of two preconvex relations of 2 6 ·nt [Balbiani et al. , 1998]. By using this and the fact that the set of the saturated-preconvex relations is stable for the intersection [Balbiani et al., 1998], from proposition 3 we can prove that the set of the saturated-preconvex relations is a subset of S . Moreover, it is a proper subset of S. For example, let us consider the relation {(o , o) , (s, eq) , (eq, s ), (s , s)} which is strongly-preconvex but not saturated-preconvex, So, now S is the largest known set to be a tractable set which contains the basic relations. This result provides also another proof of the tractability of saturated-preconvex relations.

7 Conclusion

The subclass generated by the set of the strongly­ preconvex relations is now the biggest known tractable set of RA which contains the 169 atomic relations. An open question is: is this subclass a maximal tractable subclass which contains the atomic relations ?

Another future development is to extend RA to a greater dimension than two. For dimension n (n ~ 3), the considered objects will be the blocks whose sides are parallel to the axes of some orthogonal basis in a n­ dimensional Euclidean space. The atomic relations be­ tween these obj ects are the 13n relations obtained by the cartesian product of atomic relations of IA. A first at­ tempt shows that the previous tractability results of RA can be easily extended to this structure.