Combining RCC5 Relations with Betweenness Information

1 Introduction

Many cognitive models of categorization rely on spatial representations of meaning in one way or another. In prototype theory [Rosch, 1973], for instance, objects are assigned to a given category if they are closer to the prototypes of that category than they are to the prototypes of other, contrast categories. Building on the ideas from prototype theory, G¨ardenfors [2000] presents evidence that natural categories can be represented as convex regions in a multi-dimensional metric space, called a conceptual space, which is usually assumed to be Euclidean for simplicity. Each dimension in a conceptual space corresponds to a primitive cognitive feature.

Conceptual spaces are a useful metaphor, as semantic relations between categories can thus be identified with qualitative spatial relations between the corresponding regions. Mereological (or part-whole) relations are of particular interest in this context. For example, the assertion that the category furniture subsumes the category table, corresponds to the spatial relationship tablePfurniture, where we identify each category with its conceptual space representation for the

Sanjiang Li

University of Technology Sydney

QCIS, FEIT Australia sanjiang.li@uts.edu.au

ease of presentation. The notation P refers to the part-of relation. Table 1 summarizes the intended meaning of the spatial relations that we will consider in this paper. In addition, we will use PP-1 for the inverse of PP, i.e. aPP-1 b iff aPPb. The relations PP, PP-1 , DR, PO and EQ are jointly exhaustive and pairwise disjoint (JEPD), i.e. exactly one of these relations holds between each pair of regions. These relations are the primitives of the RCC5 calculus, which is an important fragment of the region connection calculus [Cohn et al., 1997].

The computational properties of the RCC5 calculus are well understood. However, for reasoning about semantic relations between categories, RCC5 by itself is too limited. First, category boundaries tend to be vague. To cope with this, [G¨ardenfors and Williams, 2001] proposes to use the eggyolk calculus [Cohn and Gotts, 1996] to reason about categories. In the egg-yolk calculus, vague regions are represented as nested sets of classical regions. Spatial relations between vague regions are then defined in terms of RCC5 relations between the corresponding sets of classical regions. As such, spatial reasoning in the egg-yolk calculus straightforwardly reduces to decision procedures for the RCC5 calculus. Second, the conceptual spaces setting requires regions to be convex. Although this property is not usually considered in decision procedures for the RCC5 calculus, because conceptual spaces tend to be high-dimensional, requiring regions to be convex does not affect consistency or entailment checking procedures, not even for the more expressive RCC8 calculus [Schockaert and Li, 2012]. Third, not all semantic relations of interest correspond to part-whole relations. The notion of betweenness, in particular, plays a central role for interpolation [K´oczy and Hirota, 1993; Dubois et al., 1997;

Schockaert and Prade, 2011], an important form of commonsense reasoning: knowing that b is between a and c, we can infer that properties common to a and c are also valid for b. For example, knowing that bardolino is between beaujolais and valpolicella and that the latter two wines are characterized by low tannins, we can infer that bardolino has low tannins. The validity of interpolation relies on the convexity of regions: if b ⊆ CH(a∪c), writing CH for the convex hull operator, and x is a convex region then from a ⊆ x and c ⊆ x, we can derive b ⊆ x.

In applications, we may be able to learn betweenness information from analysing data; e.g. techniques such as multidimensional scaling can be used to discover the latent geometric structure of a given domain. Subsumption information can be obtained from existing taxonomies, or again from analysing data. There is a need, however, for techniques to reason about subsumption information in the presence of betweenness relations, e.g. to make explicit what can be entailed from known information or to identify inconsistencies when merging information from different sources. For example, knowing that taiga is between tundra and temperateForest, and that taiga subsumes borealForest, we should be able to conclude that borealForest is between tundra and temperateForest. To this end, in this paper we consider an extension of the RCC5 calculus in which assertions of the form bPP(a ⋊⋉ c) can be expressed, where (a ⋊⋉ c) corresponds to CH(a ∪ c), i.e. we want to be able to express that some region is completely, partially, or not at all between two other regions.

The notion of betweenness has only had limited attention in the qualitative spatial reasoning (QSR) literature so far. One notable exception is [Clementini et al., 2010], which proposes a set of 34 JEPD relations that can hold between three regions in the plane, and which are rich enough to express betweenness. A composition table is presented, but no sound and complete procedure for consistency checking is proposed. For points on the real line, the betweenness problem (or total ordering problem) is a well-known problem which consists of deciding whether a set of constraints of the form 'b is between a and c' can be satisfied, where b is between a and c iff a < b < c or c < b < a. The problem is known to be NPcomplete [Opatrny, 1979]. More generally, various authors have looked at combining RCC5 or RCC8 with relations encoding other aspects of space. For example, [Gerevini and Renz, 2002] combines RCC8 relations with size information and [Liu et al., 2009] combines RCC8 relations with qualitative direction calculi. In [Wolter and Zakharyaschev, 2000], RCC8 is extended with region terms, which allow to express that e.g. a is equal to the union of b and c. The idea of using QSR for reasoning about natural language categories has been previously considered by a number of authors. Most notably, this has been discussed at length in [G¨ardenfors and Williams, 2001] but also [Lehmann and Cohn, 1994] propose something along these lines.

The paper is structured as follows. In the next section, we recall some basic results about the RCC5 calculus, and introduce the notations and concepts that will be used throughout the paper. In Section 3 we introduce a number of properties that a consistent RCC5 network with betweenness information should satisfy. Subsequently we show in Section 4 that any network which satisfies these properties can be realized in a Euclidean space by using convex regions.

2 Preliminaries

Let V = {v1, ..., vn} be a set of variables. An RCC5 network over V is a set of constraints of the form

where R5 = {PP,PP-1 ,DR,PO,EQ}. If Rij = {ρ} is a singleton, we write vi ρ vj as an abbreviation for vi {ρ} vj . When specifying an RCC5 network, we usually omit trivial constraints of the form vi R5 vj. Moreover, as Rij completely determines Rji and vice versa, we usually only specify one of them explicitly. For convenience, we use the following abbreviations:

An RCC5 network is called atomic if each Rij = {ρij} is a singleton. For atomic networks, consistency can be decided in O(n3 ) by checking path consistency. Specifically, it suffices to check for each i, j, k whether ρik is among the relations in ρij ◦ ρjk, where the composition ρij ◦ ρjk of ρij and ρjk is defined by the RCC5 composition table, shown in Table 2. For example, Θ = {v1 PP v2, v2 PO v3, v1 EQ v3} is not consistent, because EQ is not among PP ◦ PO = {DR, PO, PP}.

In this paper, we will consider RCC5 networks over an extended set of variables

At the semantic level, vi ⋊⋉vj corresponds to the convex hull of vi ∪ vj. For example, v1 PP(v2 ⋊⋉ v3) means that v1 is entirely between v2 and v3 while (v1 ⋊⋉ v2)PO(v3 ⋊⋉ v4) means that the convex hulls of v1 ∪v2 and of v3 ∪v4 overlap. To express that u is contained in the convex hull of v1∪...∪vk we can introduce fresh variables u2, ..., uk and express that u2 EQ (v1 ⋊⋉ v2), u3 EQ (u2 ⋊⋉ v3), ..., uk EQ (uk-1 ⋊⋉ vk) and uPuk. Indeed, it is clear that ui corresponds to CH(v1∪ ... ∪ vi) for each i.

An RCC5⋊ ⋉network over V is encoded as an RCC5 network over V ⋊ ⋉. A solution to an RCC5⋊ ⋉network Θ over V is an assignment S from the set of variables V to the set of regular closed regions in Rm for some m ≥ 1, such that

• for each constraint of the form vi Rij vj, the relation between S(vi) and S(vj) is among those in Rij;
• for each constraint of the form vi Rij (vj ⋊⋉vk), the relation between S(vi) and CH(S(vj) ∪ S(vk)) is among those in Rij ;
• for each constraint of the form (vi ⋊⋉vj)Rij vk, the relation between CH(S(vi) ∪ S(vj)) and S(vk) is among those in Rij ;
• for each constraint of the form (vi ⋊⋉vj)Rij (vk ⋊⋉vl), the relation between CH(S(vi)∪S(vj )) and CH(S(vk)∪ S(vl)) is among those in Rij.

Note that (2) implies

Betweenness also satisfies the following monotonicity property:

The soundness of the conditions (1)-(5) is obvious. We can also show the following transitivity property.

We will mainly focus on convex solutions in this paper, i.e. solutions S in which S(v) is a convex region for every v. In particular, in this paper we are interested in checking whether an RCC5⋊ ⋉network has a convex solution. We will show that this can be decided in polynomial time for atomic networks, which means that the problem is in NP in general. As consistency checking for RCC5 is NP-hard and is not affected by the requirement that regions be convex, it follows that the problem is NP-complete.

We will say that Θ entails a constraint vi R vj , written Θ |= vi Rvj , if Θ contains a constraint vi R′ vj with R′ ⊆ R, or if such a constraint can be derived from Θ using the RCC5 composition table (i.e. by enforcing path-consistency). To check the consistency of Θ as an RCC5⋊ ⋉network, we first need to check whether Θ is consistent as an RCC5 network, i.e. when we treat expressions of the form vi ⋊⋉vj simply as variables. For example if vi PO(vj ⋊⋉vk) and (vj ⋊⋉vk)PP(vs ⋊⋉vt) are in Θ, then we should have that the relation between vi and (vs ⋊⋉vt) in Θ is either PO or PP (see Table 2). If Θ is consistent when interpreted as an RCC5 network, we will say that Θ is RCC5-consistent. Our aim is to decide when it is possible to realize vi ⋊⋉vj as CH(S(vi) ∪ S(vj)). If this is the case, we will say that Θ is RCC5⋊ ⋉-consistent.

3 Properties of betweenness

In this section, we introduce a number of properties an RCC5consistent RCC5⋊ ⋉network Θ should satisfy to be RCC5⋊ ⋉- consistent, and an additional property Θ should satisfy to have a convex solution. In the next section, we will then show that these conditions are sufficient to guarantee that Θ has a convex solution.

As betweenness is symmetric, for each vi and vj we should have:

A region vi is between itself and any other region:

Proposition 1. Any solution to Θ will satisfy:

Proof. Let Vi, Vj, Vk, Vl, Vs be the realizations of vi, vj, vk, vl, vs in Rm for some m ≥ 1, and let X = CH(Vi ∪Vj ∪Vk ∪Vl ∪Vs). Assume that Vi P (Vk ⋊⋉Vl), Vj P(Vk ⋊⋉Vl) and Vs P(Vi ⋊⋉Vj), then we show that also Vs P(Vk ⋊⋉Vl) must hold. Let us call a point p a vertex of X iff there exists a hyperplane H such that H ∩ X = {p}. If p ∈ Vs then because of Vs P(Vi ⋊⋉Vj) it holds that p ∈ Vi or p ∈ Vj. Indeed, otherwise the hyperplane H separates the point p from Vi ∪ Vj, which means that p and a fortiori Vs cannot be in CH(Vi ∪ Vj).

Suppose that p ∈ Vi; the case where p ∈ Vj is entirely analogous. We then find from vi P(vk ⋊⋉ vl) that p ∈ Vk or Vl, using an entirely analogous argument. It follows that every vertex of X belongs to Vk ∪ Vl, which means that CH(Vk ∪ Vl) = X and Vs ⊆ CH(Vk ∪ Vl).

On the other hand, note that from vj P(vi ⋊⋉ vk) and vk P(vj ⋊⋉ vl) we cannot derive vk P(vi ⋊⋉ vl) or even vk O(vi ⋊⋉vl) in general. A counterexample in 2D is shown in Figure 1.

Conditions (1)-(6) hold for arbitrary regions. If we require regions to be convex, the following condition should additionally hold:

It follows from (7) that when vi P-1 vj we also have vi P-1 (vi ⋊⋉vj), which together with (2) entails:

In particular, we always have

Note that from (7) we can derive (6). Indeed, assume that vi P (vk ⋊⋉vl), vj P (vk ⋊⋉vl) and vs P (vi ⋊⋉vj ) are satisfied. By (7) we have (vi ⋊⋉ vj)P(vk ⋊⋉ vl). By the transitivity of P, vs P(vk ⋊⋉vl) follows from vs P(vi ⋊⋉vj) and (vi ⋊⋉ vj ) P (vk ⋊⋉vl).

Similarly, from (1), (2) and (7) we can derive (5). Indeed, assume that vi Pvj holds. From (2) we know vj P(vj ⋊⋉vk), which together with vi Pvj implies vi P(vj ⋊⋉ vk) by the transitivity of P. From (2) we also have vk P(vk ⋊⋉vj) and because of (1) also vk P(vj ⋊⋉vk). Together with vi P(vj ⋊⋉ vk), it follows from (7) that (vi ⋊⋉vk)P(vj ⋊⋉vk).

However, while (7) only holds for convex regions, (5) and (6) are valid for arbitrary regions.

4 Realizing consistent RCC5⋊ ⋉networks using convex regions

In this section, we show the following result.

Proposition 2. Let Θ be an atomic RCC5⋊ ⋉network which is RCC5-consistent and satisfies (1), (2) and (7). It holds that Θ has a convex solution, and a fortiori that Θ is RCC5⋊ ⋉- consistent.

We then also obtain the following corollary.

Corollary 1. It can be checked in polynomial time whether an atomic RCC5⋊ ⋉network Θ has a convex solution.

Indeed, verifying whether Θ is RCC5-consistent is known to be in P, whereas each of the conditions (1), (2) and (7) can straightforwardly be checked in polynomial time.

In the construction below, we will not explicitly consider constraints of the form (vi ⋊⋉vj)R(vr ⋊⋉vs), as we can safely assume that such constraints are entailed by the other constraints in Θ. Indeed, if this were not the case, we could always introduce a new variable x and add the constraints xEQ(vi ⋊⋉vj) and xR(vr ⋊⋉vs). We furthermore make the following assumptions about Θ:

• If Θ contains the formula vi POvj, then there are variables x, y and z in V such that Θ entails the following constraints: xPvi, xDRvj, yPvj, yDRvi, zPvi, z P vj .
• If Θ contains the formula vi PO(vj ⋊⋉ vk), then there are variables x, y and z in V such that Θ entails the following constraints: xPvi, xDR(vj ⋊⋉vk), yP(vj ⋊⋉ vk), yDRvi, zPvi, zP(vj ⋊⋉vk).
• If Θ contains the formula vi PPvj, then there is an x ∈ V such that Θ entails the constraints xPvj and x DR vi .
• If Θ contains the formula vi PP(vj ⋊⋉vk) then there is an x ∈ V such that Θ entails the constraints xP(vj ⋊⋉ vk) and xDRvi.
• If Θ contains the formula vi PP-1 (vj ⋊⋉vk) then there is an x ∈ V such that Θ entails the constraints xPvi and x DR (vj ⋊⋉vk).

Again we can make these assumptions without loss of generality: if suitable variables do not exist, we can always add new variables and extend Θ without affecting its consistency.

We now present a method to realize a solution for Θ. Our method is incremental. Initially, we assign to each variable vi the interval σ0(vi) = [0, 1]. It is clear that initially the following assertions are valid (m = 0):

Now we consider a sequence of steps, each of which will use the mapping σm from the previous step to construct a mapping σm+1 in a Euclidean space with one additional dimension, i.e. the mapping σm will assign to each variable a regular closed, convex subset of Rm+1 .

At each step, we consider a constraint of the form vi DR(vj ⋊⋉ vk) which is not yet satisfied by σm. We then define a new mapping σm+1 satisfying (P1)-(P3), the constraint vi DR(vj ⋊⋉ vk) as well as any constraint of the form vr DR(vs ⋊⋉ vt) that was already satisfied by σm. For the ease of presentation, let us write σm(vl) = Rl and σm+1(vl) = Ql. The regions Ql will be obtained by using a fixpoint procedure. Initially, if Θ |= vl Pvi, we define Ql as

Otherwise, we define Ql as

To ensure that the regions Ql satisfy all formulas of the form vl P(vr ⋊⋉vs), we subsequently contract these initial representations. In particular, we repeatedly apply the following updates until no further changes occur:

For every formula of the form vl P(vr ⋊⋉ vs) entailed by Θ:

Note that this procedure is monotonic in the sense that in each iteration the set Ql can only become smaller. From the Knaster-Tarski theorem [Tarski, 1955], we then know that this procedure is well-defined, in the sense that there exists a unique greatest fixpoint which can be found by repeated applications of the update rule (10). Below we will show that the mapping σm+1 which is thus obtained satisfies vi DR(vj ⋊⋉ vk), as well as all relevant relations that were already satisfied by σm. First, however, we need to show that the regions Ql are convex and regular closed (and in particular that they are (m+2)-dimensional).

Lemma 1. For every variable vl, it holds that Ql is regular closed and convex.

Proof. It is clear that Ql is a closed region and convex, as it is the intersection of closed and convex regions. To show that dim(Ql) = n+2, and thus that Ql is regular closed, note that for every region Rl, it holds that

Indeed, this is true initially (i.e. before applying the fixpoint procedure) and is invariant under updates of the form (10).

Let us call the region Ql positive if

Note that if (x0, ..., xm+1, θ) ∈ Ql we also have (x0, ..., xm+1, θ∗ ) ∈ Ql for all θ∗ ∈ [0, θ] since (x0, ..., xm+1, 0) ∈ Ql and Ql is convex.

Similarly we call the region Ql negative if

Let N = {l |Θ |= vl Pvi} and P = {l |Θ |= vl P(vj ⋊⋉ vk). Initially, for each l ∈ N, the region Ql is negative but not positive, for each l ∈ P the region Ql is positive but not negative, and for all other l the region Ql is both positive and negative.

• IfQl (at an intermediate stage) is positive, thenCH(Qr∪ Qs) ∩ Ql will be positive as soon as one of Qr and Qs is positive. Indeed, for (x0, ..., xm+1) ∈ Rl there exist (x′0 , ..., x′m+1 ) ∈ Rr and (x′′ 0 , ..., x′′m+1 ) ∈ Rs such that (x0, ..., xm+1) is between (x′0 , ..., x′m+1 ) and (x′′ 0 , ..., x′′m+1 ). Now assume that Qr is positive and thus contains some point (x′0 , ..., x′m+1 , θ′ ) for θ′ > 0. Then clearly there is a θ > 0 such that (x0, ..., xm+1, θ) is between (x′0 , ..., x′m+1 , θ′ ) and (x′′ 0 , ..., x′′m+1 , 0), the latter point being included in Qs. It follows that for each θ∗ ∈ [0, θ], (x0, ..., xm+1, θ∗ ) ∈ CH(Qr ∪Qs). In particular, there therefore must exist some θ∗ ∈ [0, θ] such that (x0, ..., xm+1, θ∗ ) ∈ CH(Qr ∪ Qs) ∩ Ql.

It follows that the only regions Ql which are not positive must be those for which l ∈ N. Indeed, this is clearly true initially. Now assume that Ql is positive and vl P(vr ⋊⋉ vs) is entailed by Θ. If r /∈ N or s /∈ N we know that CH(Qr ∪ Qs) ∩ Ql will be positive. On the other hand, if r ∈ N and s ∈ N, we also have l ∈ N by (7). Hence regions which are initially positive (i.e. the regions which are not in N) will remain positive throughout the procedure.

• Similar as for positive regions, we have that when Ql is negative at any stage of the procedure, then CH(Qt ∪ Qs) ∩ Ql will be negative as soon as one of Qt and Qs is negative.

Initially only regions Ql for l ∈ P are not negative. A region Ql for which l /∈ P can only become not negative if Θ entails a constraint of the form vl P (vj ′ ⋊⋉vk′ ) such that Qj ′ and Qk′ are not negative. From this observation, it is easy to see that whenever Ql is not negative, then there must exist a set of regions u1, ..., um such that for each l′ ≥ 3, ul′ P(us ⋊⋉ut) is entailed by Θ for some s < l′ and t < l′ , where u1 = vj , u2 = vk and um = vl. From Proposition 1 we then obtain that vl P (vj ⋊⋉vk) is entailed by Θ. In particular, we find that we will never arrive at a stage where Ql is not negative when l ∈ N, since we know that vi DR(vj ⋊⋉vk) ∈ Θ and thus also vl DR(vj ⋊⋉vk) for all l ∈ N; in particular Θ does not entail vl P(vj ⋊⋉vk) for any l ∈ N.

• Note that we have not yet excluded the situation where the procedure requires an infinite number of steps to

reach the fixpoint, such that one or more regions become infinitely small.

To see why none of the regions can become infinitely small, first note that the point (0, 0, ..., 0) ∈ Rm+1 is contained in each of the representations Rl. Now consider the point p+ = (0, ..., 0, 1) ∈ Rm+2 . Clearly, each positive region Ql initially contains p+. Moreover, if Ql is updated following (10), we know that either Qr or Qs is also positive. Suppose e.g. that Qr is positive. Then p+ ∈ Ql ∩ Qr and in particular p+ ∈ CH(Qr ∪ Qs) ∩ Ql. It follows that each of the positive regions contains p+ in the final representations. Similarly we can show that each of the negative regions contains p- = (0, ..., 0,-1) in the final representations. Since each region Ql contains either p+ or p- and {(x0, ..., xm+1, 0) | (x0, ..., xm+1) ∈ Rl}, clearly none of the regions can be of dimension n + 1.

Lemma 2. For every formula of the form vr Pvs entailed by Θ, it holds that

Proof. If vr Pvs then by the transitivity of P we have that whenever vs P (vt ⋊⋉vu) is entailed by Θ also vr P (vt ⋊⋉vu) is entailed by Θ. This means that whenever Qs is replaced by CH(Qt∪Qu)∩Qs thenQr is replaced by CH(Qt∪Qu)∩Qr. Hence it is clear that from Rr PRs we obtain Qr PQs.

Lemma 3. If Rr DRRs then we also have

Proof. This is clear, since Qr and Qs are initially disjoint (as they are a "cylindrical" extension of disjoint regions) and the updates only contract the representations.

Lemma 4. If vl P(vr ⋊⋉vs) is entailed by Θ, it holds that

Proof. By construction, after the procedure converges, Ql = CH(Qr ∪Qs) ∩Ql holds whenever vl P (vr ⋊⋉vs) is entailed by Θ, which is equivalent with Ql ⊆ CH(Qr ∪ Qs).

Lemma 5. If vl P-1 (vr ⋊⋉vs) is entailed by Θ, it holds that

Proof. If vl P-1 (vr ⋊⋉vs) is entailed by Θ, then Θ will also entail vl P-1 vr and vl P-1 vs by (3). By Lemma 2 we know that then Qr PQl and Qs PQl. By the convexity of Ql it then follows that CH(Qr ∪Qs)PQl.

Lemma 6. If Rl DRCH(Rr ∪Rs) then also

Proof. This is clear due to the "cylindrical" nature of the initial representations of Ql, Qr and Qs.

Lemma 7. It holds that

Proof. This follows from the observation that Qi and CH(Qj ∪ Qk) are separated by the hyperplane

We can repeat the same procedure until all disjointness constraints of the form vi DR(vj ⋊⋉ vk) are satisfied. This also ensures that disjointness constraints of the form vi DRvj are satisfied, noting that vj is equal to vj ⋊⋉vj due to the convexity of vj. The resulting mapping σ satisfies (P1)- (P3), as well as

It follows that σ is a solution of Θ. Indeed, we already know that constraints of the form vi DRvj and vi DR(vj ⋊⋉ vk) are satisfied, and we moreover have:

• If vi POvj ∈ Θ then also constraints of the formxPvi, xDRvj, yPvj, yDRvi, zPvi, zPvj are in Θ. These latter constraints are all satisfied by the construction method, from which we derive that σ(vi)Oσ(vj), ¬(σ(vi)Pσ(vj)) and ¬(σ(vi)P-1 σ(vj)), i.e. σ satisfies vi PO vj .
• If vi PO(vj ⋊⋉vk) ∈ Θ then we similarly find that this constraint is satisfied by σ.
• If vi PPvj ∈ Θ then also constraints of the form xPvj and xDRvi are in Θ. Since σ(x)Pσvj and σ(x)DRσ(vi) hold, we must have ¬(σ(vi)P-1 σ(vj)). Since we also have σ(vi)Pσ(vj), it follows that σ satisfies vi PPvj.
• If vi PP(vj ⋊⋉vk) or vi PP-1 (vj ⋊⋉vk) in Θ then similarly we find that this constraint is satisfied by σ.
• If vi EQvj ∈ Θ we know that σ(vi)Pσ(vj) and σ(vi)P-1 σ(vj) hence the constraint is satisfied by σ.
• If vi EQ(vj ⋊⋉vk) ∈ Θ then we similarly find that this constraint is satisfied by σ.

In other words, we have constructed a mapping σ which assigns to each variable a convex and regular closed region, and which forms a solution of Θ, thus completing the proof of Proposition 2.

5 Conclusions

We have discussed the problem of deciding the consistency of RCC5-networks extended with betweenness information, where betweenness information is expressed using variables of the form vi ⋊⋉vj corresponding to the convex hull of vi∪vj . In particular, we have shown how consistency can be decided in polynomial time (for atomic networks) when regions are required to be convex. This corresponds to the problem of deciding whether RCC5-networks with betweenness constraints can be realized in a Euclidean conceptual space. These results provide an important stepping stone towards a full calculus for commonsense reasoning based on qualitative representations of conceptual spaces.

From a theoretical perspective, two areas for future work present themselves. First, we may wonder whether the consistency of RCC5-networks with betweenness information may still be decided in polynomial time when we do not require that regions be convex. Second, we may consider the problem of deciding consistency for RCC8 networks with betweenness information. Unfortunately, there seems to be no obvious way of generalizing the presented construction to the case of RCC8 networks. To illustrate this point, we can show that in any solution of a "cycle" of the form Θ = {vi DRvj | 0 ≤ i ̸= j ≤ n} ∪ {vi PP(vi-1 ⋊⋉vi+1) | 1 ≤ i ≤ n - 1} ∪ {vn PP (vn-1 ⋊⋉ v0), v0 PP (vn ⋊⋉ v1)} there is an i such that vi ECvi+1; in any convex solution of Θ there are at least two pairs (i, i + 1) ̸= (j, j + 1) such that vi ECvi+1 and vj ECvj+1 hold. These conditions are necessary but do not appear to be sufficient. In fact, it is not clear that the consistency of RCC8 networks with betweenness information can be decided in polynomial time, even for atomic networks. Note in particular that in the case of RCC8 without the requirement of convexity, reasoning about betweenness is harder than reasoning about an extension of RCC8 with a convex hull operator (given that (vi ⋊⋉vi) is equal to the convex hull of vi), which is known to be a very hard problem [Davis et al., 1999].

Acknowledgements

We thank the three anonymous referees for their invaluable suggestions. The work of Sanjiang Li was partially supported by Australian Research Council (FT0990811, DP120104159) and National Natural Science Foundation of China (61133011, 61228305).