Euclidean and Mereological Qualitative Spaces: A Study of SCC and DCC

1 Introduction

In the symbolic approach to Artificial Intelligence (AI) the expression 'qualitative spaces' points to formal systems suitable to reasoning with imprecise, incomplete and subjective information. Important examples in the area of spatial knowledge representation, the subject of this paper, can be found in the overviews like [Cohn and Renz, 2007; Vieu, 1997]. Our interest is general but in this work we concentrate mainly on the representation of orientation and directional information and put at the center of our analysis two well known systems: the Single Cross Calculus (SCC) and the Double Cross Calculus (DCC) of Freksa [1992].

The quantitative vs. qualitative distinction of spaces for spatial information has three motivations. One, already anticipated, refers to (i) the imprecise knowledge a (human or artificial) agent may have of the space in which she lives, (ii) the local perspective she has of the space and (iii) her limited reasoning capacity. Given these assumptions, the goal in this area is to find formal frameworks suitable for managing the information available with particular emphasis on systems motivated by or at least compatible with cognitive arguments [Cohn and Renz, 2007].

On the other hand, computational issues motivate the interpretation of the term 'quantitative' as pointing to (explicit or implicit) metric systems [Pratt, 1999] like the Real space ℜn or the Euclidean space E n . These two systems are quantitative in the sense that they both provide a complete characterization of spatial information and, in particular, of the notion of distance.

∗The author thanks Carola Eschenbach for comments on an early version of the paper.

Another standard classification in space representation distinguishes formalisms based on the notion of point and those based on the notion of extended region, usually identified by open regular sets. These are sets that equal the topological interior of their own closure, that is, they satisfy equation A = [A]◦ . A classical example of the first type of systems is Euclidean geometry [Tarski, 1959]. An example of a region-based space is classical extensional mereology [Simons, 1987]. 1

Both point-based and region-based qualitative spaces usually come in families. A family is a claster of theories that exploit the same intuitive notions by extending a core theory or by providing definitionally equivalent versions of it. Often the relationships within a family reduce to some form of refinement like in the case of RCC-5, RCC-8, RCC15 and RCC-23 [Cohn et al., 1997] or similarity like the Star Calculus and Opram [Renz and Mitra, 2004; Dylla and Wallgr¨un, 2007]. Only a few works relate or at least classify large classes of spaces, e.g., orientation calculi [Dylla and Wallgr ¨un, 2007] and mereogeometry [Borgo and Masolo, 2009]. The open challenge today is to find a coherent landscape suitable to relate region-based and point-based spaces. A proper understanding of the classification of qualitative spaces cannot be reached without a comprehensive comparison of these two important classes. The purpose of this work is to show that, at a closer look, even spaces that rely on disparate geometries can end up formalizing the "same" notions, a result suggesting that new relationships may be undisclosed by a systematic comparison of systems in the two classes.

The classification problem we are tackling has its roots in the wider goal of providing optimal and reliable information exchanges between different representation schemata as needed in confederated database, in human-computer interaction and in multi-agent systems. An important byproduct of this research is the possibility to generalize (and likely extend) well known techniques for qualitative reasoning. This generalization may open the way to extend families of algorithms today confined within a specific class of spaces.

1 Points and extended regions can coexist in the same formal system. A further distinction that we do not pursue here, separates spaces made out of atomic regions and spaces with only atomless regions, see the work of Masolo and Vieu [1999].

2 Cross Calculi: the Euclidean Grounds

SCC and DCC of Freksa [1992] are Euclidean systems in the sense that they are point-based and their interpretation is constrained to the standard two-dimensional Euclidean space (E 2 ). To distinguish these systems from those based on mereology that we will study in next section, we will refer to the systems of Freksa as SCCE and DCCE .

The formalizations of SCCE and DCCE rely on a relational language and a very constrained class of models. They are introduced for a restricted type of inferences, namely, inferences on entities' location within a class of partitions of the space. In order to compare SCCE and DCCE to other formal systems, we first extend the language as needed to make explicit the overall expressive power that underlies these approaches. The formalization is given to clarify the formal bases of the languages and does not contradict the qualitative status of these systems as we will see.

The Single and the Double Cross Calculus use points and orthogonal lines to partition the space in a finite number of locations or geometrical loci (these are points, lines and extended regions). Given distinct points x, y, z, we write Ortho(x, y, z) for "the line through points x and y is orthogonal to the line through points y and z". Note that the standard alignment relation (Align) can be defined by

and betweenness (Btw) by

Thus, the implicit language 2 of SCCE and of DCCE consists of the relation Ortho and three constants a, b, c satisfying Ortho(a, b, c). In SCCE the role of a and c is functional to the space orientation while b identifies the center of reference: a allows to distinguish back/front, c left/right (Fig. 1). DCCE adds the orthogonal line through a refining SCCE's partition of the space. We write {a, b}E for the SCCE frame of Fig. 1 and, when indicated, for the DCCE frame as well.

Scott [1956] showed that a system that can identify rightangles, e.g. by including the Ortho relation, is equivalent to Euclidean geometry. Thus, SCCE and DCCE rely on a set of relations and properties that are proper of a quantitative system. They are however qualitative spaces in the sense that their explicit languages are much weaker, they lack the expressivity to fully represent even a property like alignment. The proper language of SCCE consists only of the nine relations that identify the relative position of an entity in the provided partition of the space: being straight-front of b (i.e., being in region S0 of Fig. 1), being right-front of b (being in region S1), being right-neutral of b (being in region S2), and so on. Analogously, the language of DCCE has fifteen relations. Note that SCCE and DCCE cannot talk about lines, angles or distance except indirectly via these relations. Furthermore, the orthogonality condition on the lines is not formally forced by the theory itself, it is imposed as a semantic constraint on the models.

2 'Implicit' because it is the language needed to express the syntactic and semantic constraints on which these systems rely. In contrast, we use 'explicit' for the actual languages of SCCE and DCCE .

The deductive power of SCCE and DCCE is then relative to the identification of an entity's location especially when information is gathered from more than one reference frame. The inferences that can be drawn from the combination of two frames centered at the same point b are collected in so called composition tables. An example of the information one finds in a composition table is: if c is right-front of b in {a, b}E and p is right-neutral of b in {c, b}E, then p is left-front of b in {a, b}E .

3 Cross Calculi: the Mereological Grounds

In this section we look for a mereological system in the twodimensional space with the right expressive power to model the Single and Double Cross Calculi.

We begin with a system, equivalent to one presented by Cohn in [1995], that we call mereoconvexity or M+Cv, where M is classical extensional mereology with sum, product and complement operators, and Cv is the convexity predicate. At first sight our choice might seem arbitrary since, one argues, SCCE and DCCE are first of all about orthogonally intersecting lines and M+Cv seems to be unrelated to this. In the mereological perspective, a line is the boundary of a halfplane, thus what we should look for is a mereological primitive for half-plane regions and an operator to split them in congruent halves in order to get right angles. We prove here that convex mereology is indeed such a system. There are alternative theories in mereology, as we will see, but M+Cv is preferred for its historical role in the knowledge representation and reasoning community and for the cognitive immediacy of the convexity property.

Our first goal is to show that "being a half plane" (HP) and "being a stripe of finite width" (Str) are alternative predicates that can be used to formalizeM+Cv. The fact that these predicates can be defined in mereology by the convexity predicate (Cv) is postponed to the next section for presentation clarity. Here we show that the predicates HP and Str can each define Cv. The formal proof that these definitions do the job in the domain of open regular regions of ℜ2 is routine [Borgo and Masolo, 2009].

x is convex if for each region y that properly contains x, there is a half plane that contains x but not y.

For the other case, we first define the predicates Fnt ("being finite") and FCv ("being finite and convex") by saying that x is finite if it is included in the intersection of two stripes (provided their intersection is not a stripe itself), and if x is finite then it is also convex if for each region y that properly contains x, there is a stripe that contains x but not y.

Finally, we rely on a well-known property of convex sets: a set x is convex if its intersection with any finite convex set is convex as well.

• Cv(x) ≜ ∀y((O(x, y) ∧ FCv(y)) → FCv(x · y))

Lemma 1 M+Cv is a subtheory of M+HP and of M+Str.

3.1 The Cross Calculus Grounds in Mereoconvexity

In this part of the paper we concentrate on the mereological counterpart of SCCE. The constructions and the proofs for DCCE are more involved since there are more relations to model but all the needed elements are developed in this paper.

The definitions of HP (half-plane) and C (connection) given below, as well as the definition of Fnt (finite region) given in the previous section, are new formalizations in the mereoconvexity language of notions indirectly captured by I. Pratt in [1999]. Pratt carried out his work in the restricted domain of finite polygons and provided a formalization that is constrained to that domain. Although some of his results hold in the full domain of regular regions, one obtains them only by analytical arguments on the natural model(s), in the sense used by Borgo and Masolo in [2009], or more precisely by considering the limit of approximating polygons. This technique leaves us in the dark regarding, for instance, how to define specific relations in the object language. In particular, Pratt's definition of connection works in the polygon domain and does not generalize to standard mereological universes like that of open regular regions DO. This is unsatisfactory if the aim is to compare theories' expressiveness. Thus, we have to recast every notion and result directly in the object language interpreted in the mereological domain DO (this choice ensures generality because definitions in DO are easily adapted to a variety of important domains as shown by Borgo and Masolo in [2009]). In this way, the simplicity and the cognitive values of these notions become evident and so the expressivity of the language. Our exploitation of the mereological viewpoint, as opposed to relying on the reconstruction of point-based notions (like line and parallelism), shows that mereological properties and notions are indeed easy to grasp both formally and cognitively.

• The universe is the region that contains any other region 3 U(x) ≜ ∀y.P(y, x) (the universe)
• A cut is a partition of the universe in two convex regions Cut(x, y) ≜ Cv(x) ∧ Cv(y) ∧ x + y = U ∧ ¬Oxy (complementary half-planes)
• A half-plane is any region forming a cut HP(x) ≜ ∃y.Cut(x, y) (half-plane)
• A stripe is a convex region which is not a half-plane but can be added to one to obtain a strictly bigger half-plane Str(y) ≜ Cv(y) ∧ ¬HP(y) ∧ ∃x.HP(x) ∧¬P(y, x) ∧HP(x+ y) (stripe)

From these definitions, we have

Lemma 2 M+HP and M+Str are subtheories of M+Cv. Theorem 3 M+ HP, M+ Str and M+Cv are equivalent theories.

(The proofs are done via geometrical arguments on the models in ℜ2 . The theorem is thus independent of axiomatization provided the predicates are interpreted as intended.)

• A stripe extends a half-plane if it does not overlap the half-plane and their sum is a half-plane
• ExtHP(y, x) ≜ Str(y) ∧HP(x) ∧ ¬O(x, y) ∧HP(x+ y)

We can now define the topological relation of connection C. Informally, two regions are connected if the closure of their interpretations in the Euclidean space share at least a point. In mereoconvexity one can identify a point by a pair of intersecting (non-parallel) half-planes. Since two such planes individuate four distinct cone-like regions, say a, b, c, and d, to verify that two regions x and y are connected, it suffices to check the existence of intersecting half-planes such that each convex region that overlaps all a, b, c, and d must also overlap x and y. Here is the formalization:

Using these relations, M+Cv can partition the mereoconvexity space in finite regions in a way that resembles SCCE on the Euclidean space. By matching Euclidean lines with mereological stripes, the following relation SpDivCv identifies the suitable partitions of the mereological space. Informally, xi is the region playing the role Ri in Fig. 2 and corresponding to Si in Fig. 1. The formulation constrains the xi's to be convex, to be all connected to xB, to cover the whole space without overlapping and to form two pairs of stripe and half-plane each satisfying ExtHP. Let I = {B, 0, 1, . . . , 7},

3 In general the existence of the universe U must be forced with an axiom but in our case this is not necessary because of the complement operator.

We write {A, B}Cv for a SCC reference frame in M+Cv.

3.2 The Double Cross Grounds inMereogeometry

Combining the results of Scott [1956] and Pratt [1999], SpDivCv cannot force stripes to be congruent or to meet at right angles. However, what really makes SpDivCv (and any other relation inM+Cv) unsuitable to match SCCE is the set of regions that are generated in the intersection of two frames. In Fig. 3 we see that an entity located in D (formally, a region for which identical location of D holds) can be straightfront, left-neutral, right-neutral, straight-back, identical location of B or any combination of these (indeed, D overlaps all the stripes of {A,B}Cv). More generally, since inferences in these frames are affected even by small changes in the B, D overlapping area, one would think possible to standardize how B and D overlap. However, this seems not possible since the two regions, although somehow constrained in shape, may be of considerably different size. This comparison proves that the inference power of mereological SCC, or SCCM, in {A,B}Cv is much weaker with respect to that of SCCE in {a, b}E. .. ..

...

We overcome the frame interaction problem by requiring region B to be a maximal sphere in the area covered by the stripes, Fig. 4. In DCCM this constraint holds for region A as well, Fig. 5. We also posit that the stripes must be of the same width (congruent) and intersect at right angles. Fig. 6 is then the counterpart in SCCM of Fig. 3.

Let Sph be the predicate "being a sphere". Since mereology augmented with Sph is a full mereogeometry, cf. [Borgo and Masolo, 2009], then M+Sph is a mereological equivalent to Euclidean geometry. In particular, congruence and right angles are formally definable inM+Sph.

Our conclusion, further motivated below, that a full mereology is needed to formalize SCC in mereology should not come as a surprise: after all to define SCCE we had to resort to (full) Euclidean geometry.

Now we will face two remaining issues: the explicit language of SCCM (and DCCM) and the formal relationship between SCCE and SCCM.

4 Where is the entity located?

Now that we have captured the structure of SCCM in mereogeometry, we have all the formal elements to translate formulas of SCCE into formulas of SCCM and vice versa.

Before looking at the composition table of these systems, we push the analysis further to study the notion of entity location in SCC and DCC. The SCCE assumption that entities

..

..

...

Figure 6: SCCM: example of frame interaction (cf. Fig. 3).

are represented by points requires the pre-semantic individuation of a single point which functions as "the entity location". This is not so in SCCM where the entity location is the actual region the entity occupies. Can we make explicit the relation between the two ways to localize entities? There are two strategies to enrich the SCCM expressivity on this topic: to rely on atoms or to introduce a location relation.

The first solution requires us to work in an atomic mereogeometry and to isolate a fragment of the system that behaves like SCCE if we substitute atoms for points. Although worth consideration, we do not follow this approach since it would force us to take the partitioning of the space provided by atoms as the underlying grid of the system and to put on a subsidiary level the mereological structure. Also, little is known about full atomic mereogeometries.

The second solution consists in introducing a new relation to formally relate arbitrary regions and points or, in other terms, to formalize a notion of "pointed region" in SCCM. At first, this technique seems unrealistic for the lack of any suitable notion of point in mereogeometry. However, taking advantage of the fact that SCCM works with finite partitions of the space only, it turns out that all we need is a relationship that, given a region and any finite partition of it, consistently picks out one and only one of the subregions. Informally, consider an extended 4 entity A located in region Ar of E 2 , and denoted in SCCE by constant a. Let point p of E 2 be the interpretation of a, thus p ∈ Ar. What we need in SCCM is a relation, that we dub Pivot, such that if the open regular regions B1, . . . ,Bn partition Ar in mereological terms, then Pivot(Ar, Bi) holds for one and only one i such that p ∈ [Bi] (we need the closure operator since the Bi are open). 5

Generally speaking, the association that relates an entity to a single point of SCCE lays outside the scope of SCCE itself. Instead SCCM takes the extension of the entities at face value. We use the Pivot relation to make explicit the relationship between a region and its SCCE representative and, in this way, fill the gap between the two entity representation views. The precise formalization of the Pivot relation depends on the way we choose representatives in SCCE (or DCCE for what it matters): indeed there are several location relations like the geometric orthocentric relation, the barycenter relation (assuming the domain is that of material entities), and the relation associating a building to its main entrance (assuming this is the domain at stake).

We now augment the signature of SCCM with the binary Pivot relation and provide a minimal axiomatization with the assumption that the relation is further formalized according to the chosen location relation in SCCE . We call the resulting language SCCM+Pivot and read Pivot(X, Y ) as "the pivot of X is located in Y " or, equivalently, "XPivot is in Y ".

Axioms:

The pivot of a region is located in the region itself.

4 If the entity to model is itself point-wise, SCCE takes its point location and SCCM an arbitrary region with that point location as "core", see below.

5 To simplify the notation, here we do not distinguish the constants in the language of SCCM from their interpretations in E 2 .

For any partition of X in finite regions, the XPivot is in one and only one of the partitioning regions.

If the XPivot is in Y and also in Z, then it is in their overlapping region (which must exist).

Theorem 4

Note that relation Pivot is not transitive in general.

We need to be clear on the expressiveness SCCM+Pivot. Pivot does not force the domain to contain points, nor allows to construct points out of regions. Nonetheless, if we assume that regions have a point-wise "core", no matter how one splits a region in two parts, Pivot will identify the part that contains the core. In other words, we can get as closely as we wish to the point-wise representative of a region but always using extended regions only.

5 SCCE and SCCM: two of a kind

In sections 2 and 3.2 we gave the explicit languages of SCCE and of SCCM. The interpretation of the primitives of SCCE is standard in Euclidean geometry, that of SCCM is standard in mereogeometry [Borgo and Masolo, 2009]. The relationship between the two (explicit) SCC theories is given by a systematic translation of formulas in the language of SCCE into formulas of SCCM and vice versa. Then, relation Pivot allows us to verify that the translation is truth-preserving. However, since the focus is the study of the relationship and inferential power in SCC frames, we now look at formulas in the implicit languages of SCCE and SCCM.

Let us use lowercase variables for points in SCCE and uppercase variables for regions in SCCM, we write tIE for the point in E 2 that is the interpretation of the term t of SCCE and T IM for the open regular region in E 2 that is the interpretation of the term T of SCCM. Given a frame {a, b}E and a frame {A,B}M with aIE the center of ball AIM and bIE the center of ball BIM , an atomic formula Rel(b, x) in SCCE is translated to formula Rel′ (B,X) in SCCM (and vice versa) with Rel,Rel′ as follows:

6 Results

After an analysis of the formal aspects on which SCC an DCC rely, we have analyzed and defined the elements needed to model these calculi in mereology. We now draw some formal results to support the claim that the SCCM system is the mereological counterpart of SCCE.

The first result connects the models for these calculi. These models are all in E 2 where regions are interpreted as regular sets of points. What can we say about the models for SCCE and those of SCCM? Let {A,B}M be a SCCM frame, we write {A,B}wM to indicate that w is the radious of region B (this determines the width of all the stripes and, at least in DCCM, the size of region A as well). Then, {A,B}w/n M is the frame {A′ ,B′ }M in which B and B′ have same center and the radious of B′ is 1/n of that of B. Also, for any ball X ⊆ E 2 , we write cX for the center of X, then

Note that the limit, for w going to 0, of the stripes of {A,B}M is not the empty region since E 2 is compact and in the frames each stripe contains the corresponding line (a quasi-closed set) of the Euclidean frame {cA, cB}E, from which the theorem. Also, the theorem can be generalized to include the regions themselves (not just those that form the frame) by assuming: limw→0 X = XPivot (i.e. xIE ). The reader should notice that the limit of a region Ri as part of the frame is different from the limit of the same region as element of the space, e.g., for R0 the first limit gives a half-line, the latter a point. Analogously, for region B the two limits can lead to different points.

The next result shows that SCCE and SCCM have a common kernel at the deduction level. The two systems are really the same calculus modulo some domain constrains. For the sake of simplicity, we state it using constants R0, . . . , R7 of Fig. 4 and, similarly, constants R′0 , . . . ,R′7 for the partition relative to {C, B}M. We write {A, B}M ≈B {C, B}M whenever the two frames generate the same partition of the space perhaps with A and C belonging to different stripes. Also, let ˆR = R0 +R2 +R4 +R6, then

Theorem 6 The composition table of SCCE is the composition table of SCCM when regions are limited as follows:

• If {A,B}M≈B {C,B}M, then X satisfies P(X, B) ∨ (∨0≤i≤7 P(X, R′i ))
• otherwise X satisfies P(X,B) ∨ P(X,R′1 ) ∨ P(X,R′3 ) ∨ P(X,R′5 ) ∨ P(X, R′7 ) ∨ P(X, R′0 \ ˆR) ∨ P(X, R′2 \ ˆR) ∨ P(X, R′4 \ ˆR) ∨ P(X, R′6 \ ˆR)

In short, the composition tables are the same if we consider only regions that are entirely contained in one component of the {C,B}M partition and do not overlap any of the eight finite quasi-triangular regions around B generated by frames which are not in the same ≈B class, cf. Fig. 6.

A final statement in mathematical fashion sums up the overall picture we unveiled. For any regular region X ⊆ E 2 , we write PntX to denote the point of X for which the following holds: PntX ∈ Y iff Pivot(X, Y ). Pnt is the punctualization relation and is the Euclidean counterpart of the mereological Pivot relation: to each element (region or point) to model in SCCE, Pnt associates a unique point in the SCCE domain. Then,

Mutatis mutandis, these results hold for DCCE and DCCM.