Multidimensional Mereotopology with Betweenness

1 Introduction

Within Qualitative Spatial Reasoning, theories of topological and mereological relations are abundant, but most of these are restricted to one class of 'foundational' entities of uniform dimension: usually either points or regions (cf. [Cohn & Hazarika, 2001] for an overview). However, humans can easily reason about the relationships between entities of various dimensions. Commonsense reasoning should achieve the same; e.g. for representing (sketch) maps on which, e.g., streets or rivers border areas such as city blocks and meet in points such as intersections or bridges. Ultimately, we want to model directions similar to those humans often give: "Follow 6th Ave. towards the hospital, at the first light after the river turn right into Main St. Follow it through the park until you see the store on the left." Continuous incidence geometry (and all of its extensions) which captures contact amongst entities regardless of their dimension seems like a natural fit but is too strong because it makes the following two assumptions:

• (a) Two distinct points determine a unique line (line axiom);
• (b) For two distinct entities A,B of equal dimension in a higher-dimensional space, there exists two more entities C, D of the same dimension so that C is in between A and B, and B is between A and D (continuity axiom). 1

These exclude interpretations of, e.g., roads, rivers, or railways as lines 2 , since such linear features commonly intersect

∗This work has been supported by the Natural Sciences and Engineering Research Council of Canada under grant no. 327729.

1 (a) implies that A, B, C, and D are in fact incident with a unique common entity of the next highest dimension.

2 'Line' as used in the paper includes straight lines and curves.

Michael Gr ¨uninger

Department of Mechanical and Industrial Engineering

University of Toronto

gruninger@mie.utoronto.ca

in more than two points. Even if Main St. intersects, e.g., Ring Rd. twice, both are distinguishable by other intersections they have not in common. Moreover, models of everyday space are often only interested in a few meaningful entities (such as intersections or bridges) and not in the infinitely many points forced to exist by continuous geometry.

We design a multidimensional theory of space that allows such intuitive, map-like, representations of commonsense space as models. Though its main application will be in modelling 2- and 3-dimensional space, the general axiomatization is independent of the number of dimensions. We start with a na¨ıve concept of relative dimensionality which suffices to compare and distinguish dimensions of entities but requires no heavy mathematical apparatus such as number theory or point-set topology. Together with containment and contact - that can hold between entities regardless of their dimension - we give an intuitive classification of contact as three jointly exhaustive and pairwise disjoint relations that differ only in the relative dimension between the two entities in contact. The generality of this multidimensional mereotopology is demonstrated by extending it to two prominent mereotopologies - the Region Connection Calculus (RCC) [Cohn et al., 1997] and the INCH Calculus [Gotts, 1996]. Extending the theory to k-partite incidence structures verifies that we indeed abstract n-dimensional incidence geometry as desired.

A notion of relative position significantly broadens the expressiveness of the theory, in particular for describing maps or directions. As primitive we choose 'betweenness', a quaternary relation only constrained by the relative dimension amongst the involved entities. Unlike relations such as 'left of' or 'behind', 'between' is independent of the observation point. Integrated into our multidimensional mereotopology we obtain 'betweenness mereotopology', a qualitative abstraction of ordered incidence geometry that still avoids the geometric assumptions (a) and (b). Despite its simplicity, such an extension of multidimensional mereotopology by relative position has not been studied before. Many standard geometries such as affine or Euclidean geometry are extensions of the 'betweenness mereotopology'.

1.1 Background and related work

Qualitative representations of space that allow for multiple dimensions have received little attention, mainly focusing on multidimensional mereotopology (see [Galton, 2004] for an overview). Our work is most closely related to the INCH calculus [Gotts, 1996] using the single primitive INCH(x,y) with the meaning of 'x includes a chunk (equi-dimensional part) of y'. It is capable of defining both kinds of strong contact (partial overlap and incidence) but cannot capture superficial contact, e.g. when two equi-dimensional regions only share part of the boundary. Though we have drawn inspiration from the INCH calculus, our works differs in that we use relative dimension and dimension-independent containment as primitives. Only subsequently we define dimension-dependent mereotopological predicates with tighter constraints regarding the relative dimension of the involved entities. Galton [1996; 2004] discusses related logical accounts of dimension-independent mereotopology; but those focus on the definability of dependent lower-dimensional entities, in particular boundaries, in a top-down approach to mereotopology.

Mereotopological relations have also been defined using the intersection approach in which relations are classified according to the intersection of interiors, boundaries and exteriors of entities. [Clementini et al., 1993; Egenhofer &Herring, 1991; McKenney et al., 2005] distinguish various point-point, point-line, point-area, line-line, line-area, and area-area contact relations; e.g. [McKenney et al., 2005] distinguish 61 line-line relations alone. Such large sets of relations are impractical for automated reasoning or for interactions with humans. Moreover, only [McKenney et al., 2005] explicitly define dimension in their framework, but using the topological definition of Lebesgue covering dimension.

Despite extending mereotopology with 'betweenness' , our work has little in common with [Tarski, 1956] or other mereogeometries - equi-dimensional mereotopologies extended by geometric primitives such as congruence or equidistance [Borgo & Masolo, 2010]. We are primarily interested in qualitative weakening of geometry and less concerned with the reconstruction of full Euclidean geometry which requires additional geometric primitives in our theory. Moreover, entities of all dimensions are treated equally as first-order entities in our theory. (Linear) orderings of points on lines as explored by, amongst others, [Eschenbach & Kulik, 1997] are capable of defining betweenness, but rely on a direction as implied by 'oriented lines'. Moreover, their work is restricted to orderings of points on lines. Hence, it is a special case of our multidimensional and undirected betweenness relation.

2 A na¨ıve theory of relative dimension

Various notions of dimension have been employed within theories of qualitative space. We want to axiomatize 3 dimension in the weakest possible way which is still suitable for defining spatial relations that are limited to entities of certain (relative) dimensions; e.g. we want to express that A has a higher dimension than B or that the intersection of A and B is of a dimension lower than A and B. But it is unnecessarily restrictive to e.g. require that dimensions can be added or subtracted or to restrict the total number of distinct dimensions. The sought axiomatization should be just strong enough to allow us to compare the dimensions of spatial entities.

3 Throughout the paper we use unsorted first-order logic with equality and ¬,∧,∨,→,↔ as the usual connectives. Variables range over 'spatial entities' of unique and uniform (across its parts) dimensions. Sentences are labelled '[module]-[type][number]' with types: axiom (A), definition (D), theorem (T), extension (E), mapping (M). We maintain the numbering from [Hahmann & Gr¨uninger, 2011].

For this purpose we reuse core ideas from the definitions of small and large inductive dimensions [Engelking, 1995], but remove all unnecessary restrictions and the original heavy topological apparatus. Our theory of linear dimension, Tld = {D-A1-D-A6, D-D1-D-D5} weakly axiomatizes the primitive relation x < y meaning 'x has a lower dimension than y'. < is a strict partial order (irreflexive, asymmetric, transitive). D-D1 defines x =dim y as an equivalence relation (reflexive, symmetric, transitive) expressing that 'x and y are of equal dimension'. Then, two entities are always dimensionally comparable, i.e. there is a linear order over the equivalence classes defined by =dim. The theory Tld = is a more compact axiomatization of one of the theories proposed in [Hahmann & Gr¨uninger, 2011]. We further include ZEX from [Gotts, 1996]) to denote a potential (unique) zero entity of lowest dimension (D-A4, D-A5), it is mainly of interest for the relationships to other mereotopologies. D-A6 ensures that there is a unique lowest dimension apart from that of ZEX. D-D2 to D-D5 are simple, but convenient definitions. In most applications some maximum dimension exists as captured by D-E2. A further natural restriction - though unnecessary for our results - is that to discrete dimensions (D-E5, D-E6).

(D-A1) x ≮ x (< irreflexive) (D-A2) x < y→y ≮ x (< asymmetric) (D-A3) x < y∧y < z→x < z (< transitive) (D-A4) ZEX(x)∧ZEX(y)→x = y (unique ZEX) (D-A5) ZEX(x)∧¬ZEX(y)→x < y (ZEX has minimal dim.) (D-A6) ∃x[¬ZEX(x)∧∀y(y < x→ZEX(y))] (a lowest dim.) (D-D1) x =dim y↔x ≮ y∧y ≮ x (equal dimension) (D-D2) x ≤ y↔x < y∨x =dim y (lesser or equal dim.) (D-D3) MaxDim(x)↔∀y(x ≮ y) (maximal-dimensional entity) (D-D4) MinDim(x)↔¬ZEX(x)∧∀y(y < x→ZEX(y)) (minimal non-zero dimension) (D-D5) x ≺ y↔x < y∧∀z[z ≤ x∨y ≤ z] (next highest dimension) (D-E2) ∃x(MaxDim(x)) (bounded ≡ a maximal dim.) (D-E5) ¬MaxDim(x)→∃y(x ≺ y) (next highest dim. exists) (D-E6) ¬ZEX(x)∧¬MinDim(x)→∃y(y ≺ x) (next lowest dim.) While Tld is agnostic about the existence of ZEX, Z-A1 or NZ-A1 force or prevent a zero entity. (Z-A1) ∃xZEX(x) (existence of a ZEX) (NZ-A1) ¬ZEX(x) (no ZEX exists)

3 Mereotopological relations

For a theory of qualitative space, we also need a spatial primitive. We choose the dimension-independent (not restricting the involved entities to specific dimensions) mereological primitive of containment, denoted by Cont(x, y), and then define a dimension-independent topological relation of contact, denoted by C(x,y). Afterwards, we show how three types of contact can be distinguished by the relative dimension of the involved entities, justifying our initial choice of containment as an adequate primitive; see [Hahmann & Gr¨uninger, 2011] for some more details omitted here. The resulting theory generalizes other mereotopologies as discussed in Section 4.

3.1 Dimension-independent spatial relations

What parthood is to equi-dimensional mereotopology, containment is to dimension-independent mereotopology. In its point-set interpretation, we say 'y contains x', i.e. Cont(x,y), if every point in space occupied by x is also occupied by y, that is, the set of points covered by x is a subset of the points covered by y. In the intended topological models, all entities are assumed to be closed, i.e. to include their boundaries, just as in the RCC. An entity can contain not only a (smaller) entity of the same dimension (equi-dimensional parthood), but also a lower-dimensional entity. E.g. a 2D-surface may contain another 2D-surface, a line, or a point. An entity is different from the set of lower-dimensional entities it contains. Containment is a non-strict partial order; the zero entity neither contains nor is contained in any other region (C-A4).

(C-A1) ¬ZEX(x)→Cont(x,x) (Cont reflexive) (C-A2) Cont(x,y)∧Cont(y,x)→x = y (Cont antisymmetric) (C-A3) Cont(x,y)∧Cont(y,z)→Cont(x,z) (Cont transitive) (C-A4) ZEX(x)→∀y(¬Cont(x,y)∧¬Cont(y,x))

Now contact C is definable in terms of containment (C-D), resembling the definition for overlap O in RCC. C is reflexive, symmetric and monotone with respect to Cont (C-T4). The reverse of C-T4 is not entailed, but posited as C-A5 (weaker than C-A5 in [Hahmann & Gr¨uninger, 2011] to not enforce extensionality of C). We obtain Tcont = {C-A1-C-A5, C-D}.

3.2 Dimension-dependent contact relations

The relationship between containment and dimension is simple: if y contains x, x must be of equal or lower dimension than y. We obtain Tldc-basic = Tld ∪Tcont∪ CD-A1.

(CD-A1) Cont(x,y)→x ≤ y

We use Tldc-basic to define three types of contact depending on the dimension of the entities and their common entity. We distinguish two types of strong contact and one type of weak contact. But first we define the useful notion of equidimensional parthood, i.e. containment between two entities of equal dimension. Parthood is a non-strict partial order (reflexive, antisymmetric, transitive) and implies contact.

(EP-D) P(x,y)↔Cont(x,y)∧x =dim y (parthood)

Equi-dimensional strong contact: Partial overlap

Partial overlap is the strongest of our contact relations, it holds when two regions share a part. Partial overlap is a reflexive and symmetric relation requiring equi-dimensionality, it is more commonly known as O in other spatial theories.

Non-equi-dimensional strong contact: Incidence

Entities of different dimensions can also be in strong contact. We generalize partial overlap to incidence by requiring that the common element is an equi-dimensional part of exactly one of them. Incidence is irreflexive, symmetric, and prevents equi-dimensionality. INC-T4 shows its dimension constraint.

(INC-T4) Inc(x,y)→x < y∨y < x

Weak contact: Superficial contact

In contrast to partial overlap and incidence, superficial contact SC is a weak contact in the following sense: shared entities must be of a lower dimension than both of the entities in contact (SC-T4). SC is provably irreflexive and symmetric. The equi-dimensional version of SC, external contact EC, is only definable for entities of maximal dimension, i.e. with equal dimension and codimension 0 (SC-E1).

(SC-D) SC(x,y) ↔ ∃z[Cont(z,x) ∧ Cont(z,y)] ∧ ∀z[Cont(z,x) ∧ Cont (z, y) → z < x ∧ z < y] (superficial contact) (SC-T4) SC(x,y)→∃z(z < x∧z < y∧Cont(z,x)∧Cont(z,y)) (SC requires a shared entity of a lower dimension) (SC-E1) SC(x,y)∧MaxDim(x)∧MaxDim(y)→EC(x,y) (EC)

Exhaustiveness and disjointness

It is now easily provable that the three defined relations are jointly exhaustive, pairwise disjoint (JEPD) subrelations of contact in Tldc = Tldc-basic∪ {EP-D,PO-D,INC-D,SC-D}:

Theorem 1. In a model M of Tldc, for all x,y ∈ dom(M), C(x,y) iff exactly one of PO(x,y), Inc(x,y), or SC(x,y).

4 Relationship to other mereotopologies

To show that our theory is a general multidimensional mereotopology, we extend T 0 ldc = Tldc∪ Z-A1 so that the models of the extension are models of (a) the INCH-calculus [Gotts, 1996] or (b) the RCC [Cohn et al., 1997] 4 . Essentially, T 0 ldc together with axioms of extensionality and Boolean closures is at least as expressive as those two mereotopologies.

4.1 INCHCalculus

The INCH calculus can be obtained by defining its sole primitive INCH(x, y) ('x includes a chunk (a part) of y') in terms of dimension and containment (I-D); all other relations are definable while the axioms I-PA3-I-PA7 of the INCH calculus are provable by Prover9.

Extensionality of INCH (I-PA1, I-PA2) and the Boolean operations sum and diff (I-PA9, I-PA10) are not provable and must be included as axioms. I-PA8 stating that 'x being a chunk (equidimensional part) of y' implies that 'x is a constituent of (contained in) y' must also be included to prevent entities of mixed dimensions, such as a disk with a spike [Gotts, 1996]. The complete set of axioms and definitions are available in [Hahmann & Gr¨uninger, 2011].

We then obtain the following relationship between Tinch and the INCH calculus denoted by the theory T ′ inch ={I-PA1I-PA10, I-D1-I-D9}, cf. [Hahmann &Gr¨uninger, 2011]:

Theorem 2. T ′ inch faithfully interprets Tinch.

While I-M1 becomes provable, I-M1R is not provable.

4 For these results, we use definable and faithful interpretations between theories T,T ′ with languages L,L ′ : T ′ definably interprets T iff every model M of T extends to a model M′ of T ′ . The interpretation is faithful iff valid sentences in M are valid in M′ .

(I-M1) Cont(x,y)∨ZEX(x)→CS(x,y) (mapping to constituent) (I-M1R) CS(x,y)∧¬ZEX(x)→Cont(x,y) (reverse mapping)

The converse of Thm. 2 must not only include I-M1R to eliminate models of the INCH calculus not extendible to a model of Tinch, but is generally weaker: some sentences consistent with the INCH calculus are inconsistent with Tinch.

Theorem 3. Tinch∪ I-M1R definably interprets T ′ inch .

4.2 Equi-dimensional mereotopology (RCC)

Somewhat counter-intuitively, we cannot restrict T 0 ldc to models of equi-dimensional mereotopology by prohibiting entities of lower dimensions; otherwise 'external contact' in the RCC, a special case of SC, has an empty extension by SC-T4. This reduces the mereotopology to a pure mereology with overlap as only contact relation. Instead, the mapping is based on the entities of maximum dimension together with the zero region - all guaranteed to exist in Tldc∪ D-E2 ∪ Z-A1. These regions are denoted by the set R with RP denoting the parthood relation P restricted to entities in R. We then take an indirect approach by constructing connected atomless Boolean contact algebras - which in turn represent RCC models [D¨untsch & Winter, 2005]. For this purpose axioms forcing Boolean closures (intersections, sums, a universal in R, and unique complements) together with region-extensionality of C are necessary so that each structure 〈R,RP〉 with RP as partial order is a Boolean lattice. It is then sufficient to ensure connectedness, that is SC(x,x′ ), and to rule out trivial models (which are then atomless [D¨untsch &Winter, 2005]). See [Hahmann & Gr¨uninger, 2011] for the full set of necessary axioms (R-A1-R-A7) and definitions (R-D1-R-D3). That results in the following relationship:

Theorem 4. For any model M of Tldc∪ D-E2 ∪ Z-A1 ∪ {R-D1-R-D3, R-A1-R-A7} there exists a model N of RCC such that N is definably interpreted in M.

5 Relationship to incidence structures

We now show that our theory Tldc is also a direct abstraction of (geometric) incidence structures and in particular incidence geometries. Incidence structures are weak theories dealing with entities of varying dimensions. By showing that Tldc is interpretable by a theory of incidence structures, we confirm that though Tldc abstracts classical geometry, its incidence relation still behaves as anticipated. In our terminology and definitions, we follow Ch. 3 of [Buekenhout, 1995].

Definition 1. An incidence structure 〈X, I,∗,t〉 is a set X equipped with a binary, symmetric, reflexive relation ∗ and a surjective function t : X →I into a set of types I.

We first show that a model of T ¬0 ldc = Tldc∪ NZ-A1can always be extended to a k-partite incidence structure in the following way: The incidence relation ∗ is defined by Inc while the number of equivalence classes of entities of identical dimension determines the k in the resulting incidence structure, that is, entities of identical dimension have identical type I.

Theorem 5. The axiomatization of the class of incidence structures faithfully interprets the theory T ¬0 ldc .

Proof. For amodel M of T ¬0 ldc choose X = dom(M) and define x ∗ y ⇔ (Inc(x, y)∨x = y in M) as the reflexive and symmetric relation. By D-D1 dim can be defined as a function so that dim(x) = dim(y) ⇔ (x =dim y in M). dim then maps each x ∈ X to a type in I. By only including types i ∈ I with dim(x) = i for some x ∈ X, dim becomes surjective. The so-defined structure 〈M, I,∗,dim〉 is then an incidence structure.

The number of distinct types in I corresponds to the dimensionality of the space: {x ∈ dom(M)|MinDim(x)} contains the entities (called flats in incidence structures) of dimension 0, {x ∈ dom(M)|∃y[MinDim(y)∧y ≺ x]} the flats of dimension 1, etc. Notice that members of dom(M) are not sets, so incidence x∗y must be read as: 'there exists an entity contained in x and y with the dimension of either x or y'.

5.1 Incidence geometries

Now we show how the line axiom together with some existential axioms can be used to reconstruct (finite) bipartite incidence geometries, in particular near-linear 5 spaces, linear spaces and affine spaces. For this purpose, we first define two classes of 'maximal' entities which we call points, Pt, and lines, L, and introduce the theory T ¬0 pl-e = T ¬0 ldc ∪ {PL-A1PL-A5,PL-D1,PL-E1} to axiomatize their relationship:

(PL-A1) Pt(x)∧Pt(y)→x =dim y (points are of uniform dim.) (PL-A2) L(x)∧L(y)→x =dim y (lines are of uniform dim.) (PL-A3) Pt(x)∧L(y)→x ≺ y (dim. of points lower than lines) (PL-D1) Max(x)↔∀z[P(x,z)→x = z] (maximal in a dim.) (PL-A4) Pt(x)→Max(x) (points are maximal in their dim.) (PL-A5) L(x)→Max(x) (lines are maximal in their dim.) (PL-E1) L(x)→∃y,z[Pt(y)∧Pt(z)∧Cont(y,x)∧Cont(z,x)∧y ̸=z] (a line contains at least two distinct points)

Points and lines are disjoint sets of dimensionally uniform spatial entities that are maximal in their respective dimension; lines being of greater dimension than points. In T ¬0 pl-e points and lines can be interpreted in the usual geometric sense but other interpretations are also feasible, e.g., as two-dimensional regions and four-dimensional space-time objects. Apart from points and lines, other entities of same or differing dimension can still exist, but are irrelevant for the construction of line spaces as defined in [Buekenhout, 1995]:

Definition 2. A line space is a structure 〈P,L〉 of a non-empty set of points P and a collection L of subsets of P, called lines, with each line containing at least two distinct points.

Theorem 6. The structure 〈Pt,L〉 of a model of T ¬0 pl-e is definably equivalent to a line space.

Proof. Use Pt as the set of points and L=B1 as the collection of lines with B1,y ∈ B1 ⇔ L(y) and x ∈ B1,y ⇔ Pt(x) ∧ Cont(x, y). By PL-E1 every set B1,y in the collection B1 must contain at least two distinct points.

We restrict T ¬0 pl-e further to obtain Tpl-nlin = T ¬0 pl-e∪ NL-A1, Tpl-lin = Tpl-nlin∪ L-A1, and Tpl-a f f = Tpl-lin∪ {A-A1,A-A2}. These respectively axiomatize near-linear, linear, and affine spaces - the (bipartite) line geometries of the geometries with the same name. Both linear and affine spaces assume the line axiom (NL-A1 and L-A1). The FOL axioms are direct translation of the following descriptions:

5 Also known as partial linear space or semi-linear space.

(NL-A1) Two distinct points are contained in some common line.

(L-A1) Two distinct points are contained in at most one line.

(A-A1) A point not contained in a line l is contained in a unique line disconnected from ('parallel to') l.

(A-A2) Three distinct non-collinear points, i.e. which are not contained in any single line, exist.

Theorem 7. Let M be a model of Tpl-nlin (Tpl-lin, Tpl-a f f ) and define x ∗ y ⇔ [(Pt (x)∨L(x))∧(Pt (y)∨L(y))∧Inc(x, y)∨ x = y in M]. Then the structure 〈Pt,L〉 with the incidence relation ∗ is a near-linear (linear, affine) space.

6 Betweenness

We have demonstrated that the theory of dimension and containment, Tldc, is a dimension-independent first-order axiomatization of mereotopology and a generalization of incidence geometry. We now return to our original motivation and propose an extension by 'betweenness' - a qualitative spatial relation of relative positions that (1) avoids using implied references as necessary for cardinal directions [Frank, 1996] or orientations [Freksa, 1992] and (2) avoids using absolute dimensions and thus fits into our general dimension-independent approach. E.g. a point can be in between two other points on a line; equally, a line can be in between two other lines within a region (or on a plane). Moreover, betweenness is commonly used in everyday descriptions of space, in particular when describing street networks in a city. Without betweenness, e.g., a model of a grid network of streets is invariant under permutations of parallel streets. Our example in the introduction contains several cases of betweenness: Btw6th Ave.(start, river bridge, Main St.) - read 'on 6th Ave., the bridge over the river is in between the starting point and the intersection with Main St.', Btw6th Ave.(river, Main St., hospital), and BtwMain St.(6th Ave., park, store). Other commonly used non-mereotopological spatial relations, in particular convexity (line segments, rays, half-planes) can be defined in terms of betweenness if both the betweenness relation and the incidence structure are sufficiently restricted.

Ternary betweenness relations have been studied as part of many geometries [Hilbert, 1971; Tarski & Givant, 1999; Veblen, 1904] and also as independent systems [Huntington & Kline, 1917]. We use a quaternary version of Huntington's set of independent postulates A,B,C,D,1,2 for strict betweenness on an undirected line, Btw(r,a,b,c) meaning 'among the entities contained in r, b is strictly in between a and c'. Its intended topological interpretation is borrowed from the Jordan-Curve-Theorem: Any continuous set (i.e. consisting of a single connected piece) containing both a and c must include some point of b. In other words, b divides r into two subsets - one containing a and the other containing c.

In higher-dimensional cases betweenness is not always a total order, e.g., intersecting lines in a plane cannot be ordered. Therefore Tbtw = {B-A1-B-A5} omits the orderability postulate B (cf. BMT-E1) from [Huntington & Kline, 1917].

(B-A1) Btw(r,a,b,c)→a ̸=b ̸= c ̸=a (strong ≡ irreflexive)

(B-A2) Btw(r,a,b,c)→Btw(r,c,b,a) (outer symmetry) (B-A3) Btw(r,a,b,c)→¬Btw(r,a,c,b) (strict ≡ acyclic) (B-A4) Btw(r,x,a,b)∧Btw(r,a,b,y)→Btw(r,x,a,y) (out. trans.) (B-A5) Btw(r,x,a,b)∧Btw(r,a,y,b)→Btw(r,x,a,y) (in. trans.)

Extending our mereotopology with betweenness results in the theory Tbmt = Tldc ∪Tbtw∪ BMT-A1. By using Huntington's postulates for linear orders, we rule out cyclic orders. As a consequence, all spatial entities in the theory Tbmt must be simple, that is, entities are not allowed to self-intersect or self-connect (loop), e.g., a line cannot be a circular, otherwise B-A3 is violated. A circular line can still be modelled as two segments on distinct lines that meet in two points. The modular design of our theories allows us to replace Tbtw in the future by a weaker theory of betweenness that generalizes partial linear orders and partial cyclic orders. Finding such an axiomatization still remains a challenge.

(BMT-A1) Btw(r,x,y,z) → x =dim y =dim z ≺ r ∧Cont(x,r) ∧ Cont(y, r)∧Cont(z, r) ('betweenness' only amongst equi-dim. ent. contained in a common ent. of next highest dimension) (BMT-D1) PBtw(r,x,y,z)↔x=dim y=dim z≺r∧∃a,b,c[P(a,x)∧ P(b,y) ∧ P(c,z) ∧ Cont(a,r) ∧ Cont(b,r) ∧ Cont(c,r)] ∧ ∀a, b, c[P(a, x) ∧ P(b, y) ∧ P(c, z) ∧ Cont (a, r) ∧ Cont (b, r) ∧ Cont (c, r) → Btw(x, a, b, c)] (betweenness amongst parts)

BMT-D1 defines a looser notion of betweenness as relationship amongst the parts contained in a higher-dimensional entity. E.g., lines not fully contained in a region r can still be ordered if all their parts (line segments) in r are orderable. Other definable notions (on a line) are: (i) points between line segments, (ii) line segments between other line segments, and (iii) betweenness amongst lines (or segments) connected to a common line or segment (such as streets being ordered by their intersections with a common street).

7 Relationship to ordered geometry

Tbmt generalizes the various geometries found in the literature that are based on incidence and betweenness, such as betweenness geometry [Hashimoto, 1958], ordered incidence geometry, ordered affine geometry, and the theory defined by Hilbert's axioms of order and incidence [Hilbert, 1971]. This is because those geometries include the axioms of Tbtw and BMT-A1 either as axioms or entail them as theorems, while Section 5 already established that even the weakest incidence geometries are extensions of T ¬0 pl-e and thus of Tldc. In fact, the theory of linear spaces, Tpl-lin, is still weaker than all geometries that combine incidence and betweenness. Total orderability, expressed dimension-independently as BMT-E1, is another assumption shared by those geometries. We obtain Tbgeom = Tbmt ∪Tpl-lin∪ BMT-E1 as weakest theory common to all the geometries that involve incidence and betweenness. For continuous geometries BMT-E2 must also be included. Depending on the particular geometry reconstructed, further axioms, e.g., the Pasch or Dedekind axiom, are necessary.

(BMT-E1) x =dim y =dim z ≺ r ∧ x ̸= y ̸= z ̸= x ∧Cont(x,r) ∧ Cont(y,r) ∧ Cont(z,r) → [Btw(r,x,y,z) ∨ Btw(r,x,z,y) ∨ Btw(r, y, x, z)] (three distinct equi-dim. entities contained in an entity of next highest dim. are totally orderable) (BMT-E2) Btw(r,x,y,z) → ∃s,t[s =dim t =dim x ∧ Cont(s,r) ∧ Cont(t,r)∧Btw(r,x,s,y)∧Btw(r,t,x,y)] (continuity axiom)

Tbgeom does not limit the number of distinct dimensions. Entities of dimension k > 2 can be captured by a unary predicate Lk with axioms analogous to PL-A1-PL-A5 and PL-E1 (entities in Lk must contain at least k distinct points). Similar to the proof of Thm. 6, we can define flats of dimension k as sets Bk = {Bk,y|Lk(y)} of maximal entities with each Bk,y ∈ Bk being represented as the set of the points it contains.

8 Summary and discussion

Based on primitives of relative dimension, spatial containment, and betweenness, we have developed 'betweenness mereotopology', Tbmt , as qualitative analogue of the geometries of incidence and betweenness without reference to absolute dimensions. Throughout the development, we aligned subtheories of Tbmt with other mereotopologies, incidence geometries and finally geometries that involve both incidence and betweenness. Altogether, it indicates that though the basic theory is fairly weak, it can be easily extended to the strength of existing qualitative spatial theories. Tbmt combines the simplicity of equi-dimensional mereotopology, the multidimensional approach of incidence structures, and the expressiveness of the betweenness primitive.

The theory Tbmt avoids the heavy mathematical apparatus usually necessary to define dimension as known from point-set topology or classical geometry. Unlike mathematics which necessitates rigorous definitions of dimension, when giving qualitative directions or answering queries such as 'what are the possible fire escape routes from a specific room in a building?', an undefined (and more vague) concept of relative dimension is often sufficient. The full strength of Tbmt is probably best evaluated with respect to specific subclasses of models such as 2D or 3D maps, e.g., of a city or of a building. Other feasible models include streets or hiking paths on a bounded map which are essentially curves arbitrarily placed in a plane (or any higher-dimensional space). In fact, the most immediate use of the theory are likely qualitative abstractions of maps for extracting human-like directions.

Finding a representation theorem for all models of Tbmt remains as a challenge which will first require to identify a suitable class of mathematical structures capable of capturing the models - currently at best vaguely described as 'spaces of dimension m containing spatial regions of uniform dimension n ≤ m composed of n-manifolds (closed or with boundaries)'.

9 Acknowledgement

We are grateful for the anonymous reviewers' apt questions and comments which helped preparing the final version.