Combining Topological and Directional Information for Spatial Reasoning

1 Introduction

Originating from Allen's work on temporal interval algebra (IA) [Allen, 1983], the qualitative approach to temporal as well as spatial information is popular in Artificial Intelligence and related research fields. This is mainly because in many applications precise numerical information is usually unavailable or not necessary.

While Allen's interval algebra is the principal formalism of qualitative temporal reasoning, there are more than a dozen of formalisms that deal with different aspects of space in qualitative spatial reasoning (QSR). Spatial relations are usually classified as topological, directional, and metric. Metric relations have a nature of semi-quantitative and fuzziness. In this paper, we are concerned with topological and directional relations between plane regions.

Most earlier research on topological and directional relations focuses on one single aspect. The most influential formalism for topological relations is the Region Connection Calculus (RCC) [Randell et al., 1992]. As for directional relations, there are several well-known formalisms, e.g. [Frank, 1991; Goyal and Egenhofer, 2001].

∗This work was partly supported by the Alexander von Humboldt Foundation, the National Natural Science Foundation of China (60305005, 60673105, 60321002), and a Microsoft Research Professorship.

In natural language and many practical applications, topological and directional relations are used together. For example, when describing the location of Titisee, a famous tourist sight in Germany, we might say "Titisee is in the Black Forest and is east of the town of Freiburg."

In this paper we extend the RCC8 constraint language to deal with topological as well as directional information. We first formalize the four cardinal directional relations between plane regions, viz. west, east, north, south, and then define nine basic relations by using the usual relational operations of intersection and complementation.

An important reasoning problems is to decide when a network of topological and directional constraints is satisfiable (or consistent). Given a network of topological (RCC8) constraints Θ and a network of directional constraints Δ, we try to decide when the joint network Θ ⊎ Δ is satisfiable.

Since topological and directional information is not independent, Θ ⊎ Δ may be unsatisfiable despite that both Θ and Δ are satisfiable. Our main result states that, if topological constraints are all in one of the three maximal tractable subclasses of RCC8 [Renz, 1999], then the satisfiability of the joint network can be determined by considering the satisfiability of two related networks in, resp., RCC8 and the rectangle algebra (RA), where RA is the two-dimensional counterpart of IA [Balbiani et al., 1999].

The rest of this paper proceeds as follows. Section 2 introduces basic notions and well-known examples of qualitative calculi. The cardinal direction calculus DIR9 is introduced in Section 3. Section 4 describes and proves the main result. A new subclass, Amax, of IA is identified, which is closed under converse, intersection, and composition. We show satisfiable interval networks over Amax has a maximal instantiation in the sense of [Ligozat, 1994]. Section 5 concludes the paper.

2 Qualitative calculi

The establishment of a proper qualitative calculus is the key to the success of the qualitative approach to temporal and spatial reasoning. This section introduces basic notions and examples of qualitative calculi (cf. [Ligozat and Renz, 2004]).

2.1 Basic notions

Let U be the universe of temporal/spatial/spatial-temporal entities, and set Rel(U) to be the set of binary relations on U. With the usual relational operations of intersection, union, and complement, Rel(U) is a Boolean algebra.

A finite set B of nonempty relations on U is jointly exhaustive and pairwise disjoint (JEPD for short) if any two entities in U are related by one and only one relations in B. Write 〈B〉 for the subalgebra of Rel(U) generated by B. Clearly, relations in B are atoms in the algebra 〈B〉. We call 〈B〉 a qualitative calculus on U, and call relations in B basic relations of the calculus.

There are several general (but optional) restrictions on the choice of B. Write idU for the identity relation on U. For a relation α ∈ Rel(U), write α∼ for the converse of α, which is defined as (x, y) ∈ α∼ iff (y, x) ∈ α. Many qualitative calculi require the identity relation idU to be a basic relation. In this paper, we relax this restriction, and require that (i) idU is contained in one basic relation; and (ii) B is closed under converse, i.e. if α is a basic relation, then so is α∼.

Note that the composition of two relations in 〈B〉 is not necessarily in 〈B〉. For α, β ∈ 〈B〉, the weak composition [Ligozat and Renz, 2004] of α and β, written as α ◦w β, is defined to be the smallest relation in 〈B〉 which contains α◦β.

An important reasoning problem in a qualitative calculus is to determine the satisfiability or consistency of a network Γ of constraints of the form xγy, where γ is a relation in 〈B〉. A constraint network Γ = {viγijvj}ni,j=1 is satisfiable (or consistent) if there is an instantiation {ai}ni=1 in U such that (ai, aj) ∈ γij holds for all 1 ≤ i, j ≤ n.

Consistency of a network can be approximated by using an O(n3 ) time path-consistency algorithm (PCA). A network Γ = {viγijvj}ni,j=1 is path-consistent if (i) γii is the basic relation in B that contains idU; (ii) ∅ ̸= γij = γji∼; and (iii) γij ⊆ γik ◦w γkj for all i, j, k.

The essence of a PCA is to apply the following rules for any three i, j, k until the network is stable.

If the empty relation occurs during the process, then the network is inconsistent, otherwise the resulting network is pathconsistent.

2.2 Interval algebra and rectangle algebra

The interval algebra IA [Allen, 1983] is generated by a set Bint of 13 basic relations between time intervals (see Table 1). IA is closed under composition, i.e. the compositionof any two interval relations is in IA. Nebel and B¨urckert [Nebel and B¨urckert, 1995] identified a maximal tractable subclass H of IA, called ORD-Horn subclass, and showed that applying PCA is sufficient for deciding satisfiability for H.

Ligozat [Ligozat, 1994] introduced a partial order ⪯ on Bint (see Fig. 1), and termed (Bint,⪯) the interval lattice. For α, β ∈ Bint, we write [α, β] for the union of relations between α and β. Note that [α, β] is nonempty iff α ⪯ β. For example, [o, oi] is the relation ∪{o, s, f, d, eq, di, fi, si, oi}. An interval relation is called convex if it is of the form [α, β]

with α, β ∈ Bint. For α ∈ Bint, dim(α), the dimension of α, is defined [Ligozat, 1994] (see Table 1). The dimension of a non-basic relation is the maximal dimension of its basic relations.

The following convex relations are of particular importance in this paper:

The rectangle algebra (RA) is the two-dimensional counterpart of IA. RA is generated by a set of 169 JEPD relations between rectangles. 1 Write Brec for this set, i.e.

For a rectangle r, write Ix(r) and Iy(r) as, resp., the xand y-projection of r. The basic rectangle relation between two rectangles a, b is α ⊗ β iff (Ix(a), Ix(b)) ∈ α and (Iy(a), Iy(b)) ∈ β. The dimension of a basic rectangle relation α ⊗ β is defined as dim(α ⊗ β) = dim(α) + dim(β). The dimension of a non-basic rectangle relation is defined to be the maximal dimension of its basic relations.

Note that if S is a tractable subclass of IA, then S ⊗ S = {α ⊗ β : α, β ∈ S} is also tractable in RA. A tractable subclass of RA larger than H⊗H is also obtained in [Balbiani et al., 1999], where H is the ORD-Horn subclass of IA.

1 In this paper we always assume that the two sides of a rectangle are parallel to the axes of some predefined orthogonal basis in the Euclidean plane.

2.3 RCC8 algebra

A plane region (or region) is a nonempty regular closed subset of the real plane. The relations in Table 2 and the converses of TPP and NTPP form a JEPD set [Randell et al., 1992]. These are RCC8 basic relations. Write Btop for this set. The RCC8 algebra is 〈Btop〉. We write P and PP, resp., for TPP ∪ NTPP ∪ EQ and TPP ∪ NTPP.

Renz [Renz, 1999] showed that there are only three maximal tractable subclasses of RCC8 that contain all basic relations. These subclasses are denoted as ̂H8, C8,Q8. For these subclasses, applying PCA is sufficient for deciding the satisfiability of a network, and there is an O(n2 ) algorithm for finding an atomic refinement of any path-consistent network.

3 The Cardinal Direction Calculus DIR9

For a bounded plane region a, define supx(a) = sup{x ∈ R : (∃y)(x, y) ∈ a}, infx(a) = inf{x ∈ R : (∃y)(x, y) ∈ a}. The definitions of infy(a) and supy(a) are similar. We call M(a) = Ix(a)×Iy(a) the minimum bounding rectangle (MBR) of a, where Ix(a) = [infx(a), supx(a)] and Iy(a) = [infy(a), supy(a)] are the x- and y-projection of a.

For two bounded plane regions a, b, if supx (a) < infx(b), then we say a is west of b and b is east of a, written as aWb and bEa; and if supy(a) < infy(b) then we say a is south of b and b is north of a, written as aSb and bNa.

When a is neither west nor east of b, then Ix(a) ∩ Ix(b) ̸= ∅. In this case, we say a is in x-contact with b, written as aCxb. Similarly, if a is neither north nor south of b, then we say a is in y-contact with b, written as aCyb.

The Boolean algebra generated by N,S,W,E, written as DIR9, has nine atoms (see Table 3). Although it is very simple, DIR9 is sufficient for expressing directional information in many situations. Moreover, DIR9 is a subclass of RA.

Remark 3.1. Let B3 int be the JEPD set {p, ⋒, pi}. The algebra 〈B3 int 〉 is in fact the interval algebra A3 studied in [Golumbic and Shamir, 1993]. Let H3 = {p, ⋒, pi, p ∪ ⋒, ⋒ ∪ pi, ⊤}, where ⊤ is the universal relation. Note that H3 = A3 ∩H. Golumbic and Shamir proved that H3 is a maximal tractable subclass of A3. Since A3 ⊗A3 is exactly DIR9 (see Table 3), H3⊗H3 is a tractable subclass of DIR9. 2 It will be our future work to find maximal tractable subclasses of DIR9.

2 It is worth noting that the intersection of DIR9 and N is H3 ⊗ H3, where N is the new tractable subset of RA of [Balbiani et al., 1999].

4 Main result

Suppose V = {vi}ni=1 is a collection of spatial variables, Θ = {θij}ni=1 and Δ = {δij}ni=1 are, resp., a topological (RCC8) and a directional (DIR9) constraint network over V . Our problem is when the joint network Θ ⊎ Δ is satisfiable.

Without loss of generality, in this section we assume (i) θii = EQ for all i and EQ ̸= θij = θ∼ ji for all i ̸= j; and (ii) δii = CC and δij = δ∼ ji for all i, j.

The following example shows that topological and directional constraints are not independent.

Example 4.1. Let V = {v1, v2}, θ12 = EC, δ12 = NC. Both Θ and Δ are trivially satisfiable. For any two regions a, b, if aECb, then by a∩b ̸= ∅we knowM(a)∩M(b) ̸= ∅, hence aNCb cannot hold. Therefore Θ ⊎ Δ is inconsistent.

Given Θ and Δ, we define an RCC8 network Θ and an RA network Δ as follows:

Note that θij ⊆ θij and δij ⊆ δij for any two i, j. This means Θ is a refinement of Θ and Δ is a refinement of Δ (in RA).

Lemma 4.1. Θ⊎Δ is satisfiable iff Θ⊎Δ is satisfiable.

As for Example 4.1, by δ12 = NC we know θ12 = EC ∩ DC = ∅. Therefore the joint network is inconsistent.

The main contribution of this paper is to show that if Θ is a path-consistent RCC8 network over one of the three maximal tractable subclasses of RCC8, viz. ̂H8, C8, Q8, then Θ⊎Δ is satisfiable iff Θ and Δ are satisfiable.

To prove this result, we need two further lemmas.

For r = [x-, x+] × [y-, y+] and ϵ > 0, we write r + ϵ for [x- ϵ/2, x+ + ϵ/2] × [y- ϵ/2, y+ + ϵ/2]. For two rectangles r1, r2, if no edges of r1 are in line with any edge of r2, then we can expand the two rectangles a little without changing their rectangle relation. In general, we have

Lemma 4.2. Let {ri = [x-i , x+i ] × [yi , y+ i ]}ni=1 be a collection of rectangles, where no two points in either X =

{x-i , x+i }ni=1 or Y = {yi , y+ i }ni=1 are identical. Set ϵ to be the smaller one of min{|x-x′ | : x ̸= x′ , x, x′ ∈ X} and min{|y - y′ | : y ̸= y′ , y, y′ ∈ Y }. Suppose {ai}ni=1 is a collection of bounded plane regions such that ri ⊂ M(ai) ⊂ ri + ϵ/4. Then the basic rectangle relation betweenM(ai) andM(aj) is the same as that between ri and rj for any i, j.

For an RCC8 basic network Θ and a collection of rectangles {ri}ni=1 , if {ri}ni=1 is in a sense 'compatible' with Θ, then a realization {a∗i }ni=1 of Θ can be found such that M(a∗i ) is almost identical with ri for each i.

Definition 4.1. A collection of rectangles {ri}ni=1 are compatible with an RCC8 basic network Θ = {viθijvj}ni,j=1 if for any i, j we have

• If θij = EQ, then ri = rj;
• If θij ̸=DC, then ri ∩ rj is a rectangle, i.e. the interior of ri ∩ rj is nonempty;
• If θij ⊆PP, then ri is contained in the interior of rj .

Lemma 4.3. Let Θ = {viθijvj}ni,j=1 be a satisfiable RCC8 basic network. Suppose {ri}ni=1 is a collection of rectangles that are compatible with Θ. Then we have a realization {a∗i }ni=1 of Θ such that each a∗i is a bounded region and ri ⊂ M(a∗i ) ⊂ ri + ϵ/4, where ϵ > 0 is the positive number as defined in Lemma 4.2.

Proof. The proof is similar to that given for RCC8 (cf. [Renz, 1998; Li, 2006b; Li and Wang, 2006]). First, we define l(i), the ntpp-level of vi, inductively as follows:

• l(i) = 1 if there is no j such that θji =NTPP;
• l(i) = k +1 if there is a variable vj such that (a) l(j) = k and θji = NTPP, and (b) θmi = NTPP implies l(m) ≤ k for any variable vm.

Write Eik (k = 1, · · · , 4) for the four corner points of ri. For i ̸= j, if θij is EC or PO, then choose two new points Pij and Pji in the interior of ri ∩ rj. Set N to be the set of these points, and set δ to be the smallest distance between two points in N. Clearly 0 < δ < ϵ. For each point P in N, construct a system of squares {p-, p+, p(1) , · · · , p(n)} as in Fig. 2, where p(n) is a square centered at P with the length of δ/2, and p- and p+ are two smaller squares that meet at P .

Now we construct n bounded regions {a∗i }ni=1 as follows.

• ai = ⋃4k=1 e(1) ik ;
• a′i = ai ∪ ⋃{p(-) ij ∪p(+) ji : θij = EC}∪ ⋃{p(1) ij ∪p(1) ji : θij = PO};
• a′′ i = a′i ∪ {a′k : θki is TPP or NTPP};
• a∗i = a′′ i ∪ ⋃{p(l(i)) : p ∈ N and (∃j)[θji = NTPP and p(1) ∩ a′′ j ̸=∅]}.

Then {a∗i }ni=1 is a realization of Θ. Moreover, we have ri ⊂ M(ci) ⊂ ri + δ/4 ⊂ ri + ϵ/4.

Now we prove our main result.

Theorem4.1. Let Θbe a path-consistent RCC8 network over ̂H (or C8, Q8), and let Δ be a DIR9 network. Then Θ ⊎ Δ is satisfiable iff Θ and Δ are satisfiable.

Proof. We take ̂H8 as an example. The proofs for the other two maximal tractable subclasses are similar.

Suppose Θ and Δ are satisfiable. Since Θ is a pathconsistent network over ̂H8, we can construct an atomic RCC8 network Θ∗ as follows [Renz, 1999].

• if DC⊆ θij , then set θ∗ ij =DC;
• else if EC⊆ θij, then set θ∗ ij = EC;
• else if PO⊆ θij , then set θ∗ ij = PO;
• else if TPP ⊆ θij, then set θ∗ ij = TPP;
• else if θij =NTPP then set θ∗ ij = NTPP;
• else if TPP∼ ⊆ θij then set θ∗ ij = TPP∼;
• else if θij =NTPP∼ then set θ∗
• ij = NTPP∼.

By θ∗ ij ⊆ θij for any i, j, we knowΘ∗ is an atomic refinement of Θ and Θ. Moreover, for any two i, j, θij ⊆ P iff θ∗ ij ⊆ P.

We claim that the satisfiable RA network Δ has a realization {ri}ni=1 that is compatible with Θ∗. In other words, Θ∗ and {ri} satisfy the conditions of Lemma 4.3. Since the proof is quite complex, we defer it to the next subsection.

Now, by Lemma 4.3 we can find a realization {ci}ni=1 of Θ∗ such that ri ⊂M(ci) ⊂ ri +ϵ/4. By Lemma 4.2, {ci} is also a realization of Δ. Therefore, Θ ⊎ Δ is satisfiable.

Recall that applying PCA is sufficient for deciding satisfiability for RCC8 subclasses ̂H8, C8, and Q8, and for RA subclass H ⊗ H. We have the following corollary, where H3 is defined in Remark 3.1.

Corollary 4.1. Let Θbe an RCC8 network over either one of ̂H8, C8, Q8, and let Δ be a DIR9 network over H3⊗H3. Then deciding the satisfiability of Θ ⊎ Δ is of cubic complexity.

Proof. It is of quadratic complexity to compute Θ and Δ. Note that Δ is a rectangle network over Amax⊗Amax ⊂ H⊗ H, and applying PCA to Θ and Δ is of cubic complexity.

The next example shows, however, if Θ is not over any one of ̂H, C8, and Q8, then the result may not hold.

Example 4.2. Let V = {v1, v2, v3}, θ12 = θ13 = DC, θ23 = TPP ∪ TPP∼, δ12 = NC, δ13 = CW, δ23 = CC. Both Θ and Δ are satisfiable, but not Θ ⊎ Δ.

4.1 Maximal instantiation of rectangle networks

For an RCC8 network Θ and a DIR9 network Δ, suppose Θ and Δ are satisfiable, and Θ∗ is the atomic refinement of Θ constructed in the proof of Theorem 4.1. We show Δ has a rectangle realization {ri}ni=1 that is compatible with Θ∗ .

We first define an auxiliary subclass Amax of IA.

Definition 4.2. An interval relation α is in Amax if

• α is convex;
• m ⊆ α only if o ⊆ α, and mi ⊆ α only if oi ⊆ α;
• s ⊆ α only if d ⊆ α, and si ⊆ α only if di ⊆ α;
• f ⊆ α only if d ⊆ α, and fi ⊆ α only if di ⊆ α.

Note that all Amax relations except eq are of dimension 2. By the definition of Amax, it is easy to see that Amax is closed under converse and intersection. The following lemma further asserts that Amax is closed under composition.

Lemma 4.4. If α, β ∈ Amax, then α ◦ β ∈ Amax.

Proof. (Sketch.) Since the composition of two convex relations is still convex, α ◦ β is convex too.

If m ⊆ α ◦ β, then there exist two basic relations a, b such that a ⊆ α, b ⊆ β, and m ⊆ a ◦ b. By checking the composition table of IA [Allen, 1983], we have o ̸⊆ a ◦ b iff (i) a = m and b ∈ {s, eq, si}; or (ii) a ∈ {f, eq, fi} and b = m. By a ⊆ α ∈ Amax and b ⊆ β ∈ Amax, we know o ⊆ α or o ⊆ β. By the composition table we have o ⊆ o ◦ b or o ⊆ a ◦ o, hence o ⊆ α ◦ β. This means m ⊆ α ◦ β only if o ⊆ α ◦ β. Symmetrically, we can show mi ⊆ α ◦ β only if oi ⊆ α ◦ β. The proofs for the remaining four cases are similar. In this way we know α ◦ β is also in Amax.

We next characterize when a composition of two relations in Amax can contain eq.

Lemma 4.5. For two interval relations α, β ∈ Amax, if eq ⊆ α ◦ β, then eq ⊆ α∩ β or [o, oi] ⊆ α ◦ β.

Proof. By Lemma 4.4 we know α ◦ β is in Amax. If eq ∈ α◦β, then there exist two basic relations a, b such that a ⊆ α, b ⊆ β, and eq ⊆ a ◦ b. This is possible iff b is the converse of a. Suppose a ̸= eq. There are two possible situations. If a ∈ {p, o, d, di, oi, pi}, then by the composition table we know [o, oi] ⊆ a ◦ b. If a ∈ {m, s, f, fi, si,mi}, then a ◦ b is f ∪ eq ∪ fi or s ∪ eq ∪ si. Since α ◦ β ∈ Amax, we know d, di are contained in α ◦ β. Checking Fig. 1, we know [o, oi] is the smallest convex relation which contains both d and di. Therefore [o, oi] is contained in the convex relation α◦β.

The following lemma characterizes when an eq relation can be obtained as the intersection of two relations in Amax.

Lemma 4.6. For two Amax relations α ̸= eq and β ̸= eq, if α ∩ β = eq, then α = β∼ and α is either ⋐ or ⋑.

Proof. If α is neither ⋐ nor ⋑, then [o, oi] is contained in α. Note that in this case, by α ∩ β = eq, we have β = eq. This is a contradiction. So α is ⋐ or ⋑. The same conclusion also holds for β. Clearly, α is the converse of β.

We will next show when a ⋐ or ⋑ relation can be generated by the composition of two Amax relations.

Lemma 4.7. For two Amax relations α ̸= eq and β ̸= eq, if α ◦ β =⋐, then α = β =⋐; if α ◦ β =⋑, then α = β =⋑.

Proof. By Lemma 4.5 we know eq ⊆ α ∩ β. Since α is not eq, either ⋐ or ⋑ is contained in α. The same conclusion holds for β. By α ◦ β =⋐ and eq ⊆ α ∩ β, we know α and β can only be ⋐.

As a corollary of the above two lemmas, we have

Corollary 4.2. For three Amax relations α ̸= eq, β ̸= eq, γ ̸= eq, α ∩ β ◦ γ = eq iff α = β∼ = γ∼ and α is ⋐ or ⋑.

Since [o, oi] is the smallest convex relation in Amax which strictly contains ⋐, we have the following result.

Lemma 4.8. For α, β ∈ Amax, if α ∩ β =⋐, then either one is ⋐; if α ∩ β =⋑, then either one is ⋑.

Let Γ = {viγijvj}ni,j=1 be a rectangle (or interval) network, and let {ai}ni=1 be a realization of Γ. We say {ai} is a maximal instantiation of Γ iff dim(γij) is equal to the dimension of the basic relation between ai and aj for all i, j [Ligozat, 1994; Balbiani et al., 1999].

Theorem 4.2 ([Ligozat, 1994]). Let Λ be an interval network that contains only preconvex relations. If Λ is pathconsistent, then there is a maximal instantiation of Λ. 3

The path-consistency condition in the above theorem is necessary. For example, if Λ is the constraint network {x ⋐ y ⋐ z ⋐ x}, then Λ is satisfiable but has no maximal instantiation: by applying PCA we obtain x eq y eq z eq x.

But when only relations in Amax are concerned, we have the following result.

Theorem 4.3. Let Λ be an interval network that contains only relations in Amax. Suppose Λ is satisfiable and for all i, j, k we have (a) λij = eq iff i = j; (b) λij = λ∼ji ; (c) λik =⋐ ∧λkj =⋐→ λij =⋐. Then Λ has a maximal instantiation.

Proof. Suppose by applying PCA the network will be stable after m steps. We prove by induction that at no step this introduces new ⋐ or ⋑ or eq constraints. This means that, for each step 1 ≤ p ≤ m, λpij ∈ {eq,⋐,⋑} only if λpij = λij , where λpij is the relation between xi and xj after the p-th step.

Suppose this holds for p ≥ 1. We show it holds for step p + 1. Note that λp+1 ij = λpij ∩ λpik ◦ λpkj for some k or λp+1 ij = λpij ∩ λpji ∼. We take the first case as an example.

If λp+1 ij = eq, then byCorollary 4.2we knowλpik = λpkj = λpij ∼ is ⋐ or ⋑. By the induction hypothesis we know λik = λkj = λji are all ⋐ or ⋑. This contradicts the third condition. Therefore λp+1 ij ̸= eq.

If λp+1 ij =⋐̸= λpij , then by Lemma 4.8 we have λpik ◦ λpkj =⋐. But according to Lemma 4.7, this is possible iff both λpik and λpkj are ⋐. By the induction hypothesis and the third condition, we know λik = λkj =⋐ and λij =⋐. This is a contradiction. Hence λp+1 ij ̸=⋐.

3 We remind here that a convex relation is preconvex, and an interval relation is preconvex iff it is an ORD-Horn relation.

Similarly, we can show that if λij ̸=⋑, then λp+1 ij ̸=⋑.

Now, since Λ is satisfiable, applying PCA on Λ will obtain a path-consistent network Λ∗ , which is still over Amax and satisfies the following condition: For any i ̸= j, λ∗ij is contained in λij and of dimension 2. By Theorem 4.2 we know Λ∗ , hence Λ, has a maximal instantiation.

Since each λij (i ̸= j) is of dimension 2, by the above theorem, we know Λ has a realization {Ii = [x-i , x+i ]}ni=1 such that x-i , x+i , x-j , x+j are different for any i ̸= j.

Theorem 4.4. Suppose Θ is an RCC8 network, and Δ is a DIR9 network. If Δ is satisfiable, then Δ has a maximal instantiation.

Proof. Suppose {ai}ni=1 is a realization of Δ. Define an interval network Δ′ = {viδ′ij vj}ni,j=1 as follows. For all i set δ′ii = eq⊗eq. For all i ̸= j, if δij ∈ {⋐⊗⋐,⋑ ⊗⋑} then set δ′ij = δij; otherwise, set δ′ij to be the basic DIR9 relation in which ai and aj are related.

We note that Δ′ satisfies (i) δ′ii = eq⊗eq; (ii) δ′ij = δ′ji∼; (iii) δ′ik =⋐⊗⋐ ∧ δ′kj =⋐⊗⋐→ δ′ij =⋐⊗ ⋐.

Moreover, each δ′ij has the form λxij ⊗ λyij , where λxij , λyij are interval relations in Amax. Write Λx = {xiλxij xj}ni,j=1 and Λy = {yiλyij yj}ni,j=1 . For all i ̸= j we have dim(λxij ) = dim(λyij ) = 2 and dim(δ′ij ) = 4.

It is easy to see that Δ′ is satisfiable iff both Λx and Λy are satisfiable. Since they satisfy the conditions given in Theorem 4.3, both Λx and Λy have maximal instantiations. Suppose Ix = {I x i }ni=1 and Iy = {I y i }ni=1 are, resp., maximal instantiations of Λx and Λy. Set ri = I x i ×I y i for i = 1, · · · , n. Then I = {ri}ni=1 is a rectangle realization of Δ′ , hence a realization of Δ and Δ. For i ̸= j, the basic relation between ri and rj is of dimension 4. Therefore I is maximal.

By the definition of Δ and the maximality of I (as constructed above), we know I is compatible with Θ∗.

Theorem4.5. SupposeΘ is a path-consistent RCC8 network over either of ̂H8, C8, Q8, and suppose Δ is a DIR9 network. Let Θ∗ be the atomic refinement of Θ as in the proof of Theorem 4.1. If Θ and Δ are satisfiable, then Δ has a realization that is compatible with Θ∗.

5 Conclusion

In this paper, we have investigated the interaction between topological and directional constraints. We have showed that, for the three maximal tractable subclasses of RCC8, the problem of deciding the satisfiability of a joint network of topological and directional constraints can be reduced to two simple satisfiability problems in RCC8 and RA.

An earlier attempt to combining topological and directional information was reported in [Li, 2006a], where we introduced a hybrid calculus that combines DIR9 with RCC5. A preliminary result was obtained, which states that the consistency of atomic networks in the hybrid calculus can be decided in polynomial time.

Sistla and Yu [Sistla and Yu, 2000] considered a similar problem of reasoning about spatial relations in picture retrieval systems, where mereological relations inside, outside, overlaps, and directional relations left, above, behind are considered. The constraint language considered there is rather restrictive. It can express neither genuine topological relations (e.g. tangential proper part and externally connected to) nor negations of some relations (e.g. neither left nor right).