Discrete Mereotopology

Abstract

Whereas mereology, in the strict sense, is concerned solely with the part–whole relation, mereotopology extends mereology by including also the notion of connection, enabling one to distinguish, for example, between internal and peripheral parts, and between contact and separation. Mereotopology has been developed particularly within the Qualitative Spatial Reasoning research community, where it has been applied to, amongst other areas, geographical information science and image analysis. Most research in mereotopology has assumed that the entities being studied may be subdivided without limit, but a number of researchers have investigated mereotopological structures based on discrete spaces in which entities are built up from atomic elements that are not themselves subdivisible. This chapter presents an introductory treatment of mereotopology and its discrete variant, and provides references for readers interested in pursuing this subject in further detail.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 From Mereology to Mereotopology

Mereology, as the theory of parts and wholes, leads to a set of five jointly exhaustive and pairwise disjoint (JEPD) relations that may hold between any pair of entities X and Y that come under its purview, namely

$$\displaystyle\begin{array}{rcl} & & \text{X is a proper part of Y}\qquad \quad \mathsf{PP(x,y)} {}\\ & & \text{X coincides with Y}\qquad \quad \ \ \ \ \ \mathsf{EQ(x,y)} {}\\ & & \text{X partially overlaps Y}\qquad \quad \ \mathsf{PO(x,y)} {}\\ & & \text{X contains Y as a proper part}\ \ \mathsf{PPI(x,y)} {}\\ & & \text{X is disjoint from Y}\qquad \qquad \mathsf{DR(x,y)} {}\\ \end{array}$$

For the logical development, we first stipulate that the primitive relation of parthood (P) is reflexive and transitive¹:

$$\displaystyle{ \mathsf{P(x,x)\;,} }$$

(A1)

$$\displaystyle{ \mathsf{P(x,y) \wedge P(y,z) \rightarrow P(x,z)\;.} }$$

(A2)

We then define overlap as possession of a common part:

$$\displaystyle\begin{array}{rcl} \mathsf{O(x,y) = _{\mathrm{def}}\exists z(P(z,x) \wedge P(z,y))}& &{}\end{array}$$

(D1)

and go on to define the five relations listed above as follows:

$$\displaystyle\begin{array}{rcl} \mathsf{PP(x,y) = _{\mathrm{def}}P(x,y) \wedge \neg P(y,x)\;,}& &{}\end{array}$$

(D2)

$$\displaystyle\begin{array}{rcl} \mathsf{EQ(x,y) = _{\mathrm{def}}P(x,y) \wedge P(y,x)\;,}& &{}\end{array}$$

(D3)

$$\displaystyle\begin{array}{rcl} \mathsf{PO(x,y) = _{\mathrm{def}}O(x,y) \wedge \neg P(x,y) \wedge \neg P(y,x)\;,}& &{}\end{array}$$

(D4)

$$\displaystyle\begin{array}{rcl} \mathsf{PPI(x,y) = _{\mathrm{def}}PP(y,x)\;,}& &{}\end{array}$$

(D5)

$$\displaystyle\begin{array}{rcl} \mathsf{DR(x,y) = _{\mathrm{def}}\neg O(x,y)\;.}& &{}\end{array}$$

(D6)

This system of relations is known in the Qualitative Spatial Reasoning (QSR) community as RCC5, the five-element Region Connection Calculus.²

If the terms of the formal language are interpreted as referring to spatial entities, which we here call regions, it is generally felt that mereology alone does not provide sufficient expressive power to be useful for QSR. In addition to parthood and the relations derived from it, we need also to be able to distinguish between, on the one hand, internal and peripheral parts, and on the other, between contact and separation. To express these, a primitive relation C (for contact, or connection) is introduced, and stipulated to be reflexive and symmetric:

$$\displaystyle\begin{array}{rcl} \mathsf{C(x,x)\;,}& &{}\end{array}$$

(A3)

$$\displaystyle\begin{array}{rcl} \mathsf{C(x,y) \rightarrow C(y,x)\;.}& &{}\end{array}$$

(A4)

The minimal relationship between P and C is that anything connected to an entity is automatically connected to anything that entity is part of:

$$\displaystyle{ \mathsf{P(x,y) \rightarrow \forall z(C(z,x) \rightarrow C(z,y))\;.} }$$

(A5)

Using P and C as primitives, we can now define a number of important additional relations as follows:

• X is disconnected from Y:

  $$\displaystyle{ \mathsf{DC(x,y) = _{\mathrm{def}}\neg C(x,y)\;.} }$$

  (D7)

• X is externally connected to Y:

  $$\displaystyle{ \mathsf{EC(x,y) = _{\mathrm{def}}C(x,y) \wedge \neg O(x,y)\;.} }$$

  (D8)

• X is a tangential part of Y:

  $$\displaystyle{ \mathsf{TP(x,y) = _{\mathrm{def}}P(x,y) \wedge \exists z(C(x,z) \wedge \neg O(z,y))\;.} }$$

  (D9)

  (i.e., X is a part of Y that is connected to something disjoint from Y).

• X is a non-tangential part of Y:

  $$\displaystyle{ \mathsf{NTP(x,y) = _{\mathrm{def}}P(x,y) \wedge \forall z(C(x,z) \rightarrow O(z,y))\;.} }$$

  (D10)

  (i.e., X is a part of Y that is only connected to things that overlap Y).

Note that any part of a region must be either a tangential part or a non-tangential part of it, but not both. In particular, a region is a non-tangential part of itself if and only if it is not connected to any region disjoint from it and is therefore a union of one or more connected components of the whole space.

The system of eight JEPD relations known as RCC8 comprises DC, EC, PO, EQ, TPP (defined as the conjunction of PP and TP), NTPP (the conjunction of PP and NTP), and the inverses of TPP and NTPP.

The logical language here is denoted $\mathcal{L}_{\mathsf{P,C}}$, and comprises all first-order formulae in which the non-logical language is restricted to the two binary predicates P and C—all formulae containing the other RCC8 relations being reducible to formulae containing just P and C, via the definitions given above. Systems of this kind, which combine the mereological notion of parthood with the topological notion of connection, are called mereotopologies.

Mereotopologies are normally interpreted as referring to regions which can be indefinitely subdivided. This is expressed by positing the formula

$$\displaystyle{ \mathsf{\exists yPP(y,x)} }$$

(N1)

as an axiom. The domain of such an interpretation is usually taken to be some collection of non-empty subsets of $\mathbb{R}^{n}$ for some positive integer n (typically either 2 or 3). In order to ensure infinite subdivisibility, only infinite subsets should be considered as possible domain elements, but this still leaves open many different possible such collections, for example

• All infinite subsets of $\mathbb{R}^{n}$

• All non-empty open subsets of $\mathbb{R}^{n}$

• All non-empty regular open³ subsets of $\mathbb{R}^{n}$

• All non-empty regular closed subsets of $\mathbb{R}^{n}$ (Gotts, 1996)

• All open polygonal (polyhedral, etc.) subsets of $\mathbb{R}^{n}$ (Pratt and Lemon, 1997; Pratt and Schoop, 1997; Pratt-Hartmann and Schoop, 2002)

In these interpretations, it is usual to interpret the predicates P and C as standing for the following relations:

• X is part of Y if and only if X ⊆ Y.

• X is connected to Y if and only if $\overline{X} \cap \overline{Y }\neq \varnothing$, i.e., the topological closures of X and Y have at least one point in common.

The interpretation of parthood in terms of the subset relation explains why the domain has to be restricted to non-empty sets: if the empty set were allowed, then any pair of regions would overlap, since they would have the empty set as a common part.

It should be noted that under any of these interpretations, parthood is necessarily antisymmetric, satisfying the formula

$$\displaystyle{ \mathsf{P(x,y) \wedge P(y,x) \rightarrow x = y\;,} }$$

(A6)

and thus extensional, meaning that two distinct entities cannot have exactly the same parts:

$$\displaystyle{ \mathsf{\forall z(P(z,x) \leftrightarrow P(z,y)) \rightarrow x = y\;.} }$$

(T1)

From now on we shall assume that P denotes an antisymmetric relation; a consequence of this is that EQ(x,y) becomes equivalent to x = y, meaning that the symbol EQ can be dropped.

Connection, on the other hand, need not be extensional: that is, it does not necessarily follow that two entities are identical if they are connected to exactly the same things. In the first two models above, connection is not extensional; for example, if the domain of discourse consists of all infinite subsets of $\mathbb{R}^{n}$, an open set and its closure are connected to exactly the same sets, yet they are not identical. In the last three models listed above, connection is extensional, that is, they satisfy

$$\displaystyle{ \mathsf{\forall z(C(x,z) \leftrightarrow C(y,z)) \rightarrow x = y\;.} }$$

(N2)

In such models, if X is connected to everything Y is connected to, then X is part of Y, which means that the converse of (A5) holds. In this case, parthood can be characterised exactly in terms of connection, as follows:

$$\displaystyle{ \mathsf{P(x,y) \leftrightarrow \forall z(C(x,z) \rightarrow C(y,z))\;.} }$$

(N3)

It is easy to see that (N2) and (N3) together imply (A6) and hence (T1). If we have (N3), we can use it to defineP, leaving just the one primitive predicate C. In this case the logical language can be reduced to $\mathcal{L}_{C}$.

It should be noted that although individual terms in $\mathcal{L}_{\mathsf{P,C}}$ refer to regions, by interpreting them as denoting subsets of $\mathbb{R}^{n}$ we are implicitly postulating a universe of points, even though these cannot be referred to in the language. To avoid this unsatisfactory situation, Stell (2000a) showed that the terms of RCC could be interpreted as referring to elements of structures called Boolean Connection Algebras (BCAs), which do not presuppose that regions are collections of points. This notion was generalised by Li and Ying (2004) to Generalized Boolean Connection Algebras, which as well as subsuming Stell’s BCAs can provide models for the discrete versions of RCC which we turn to next.

2 Discrete Mereotopology and Adjacency Spaces

If we wish to interpret the mereotopological predicates over discrete domains, in which entities are not indefinitely subdivisible, it is no longer possible to define parthood in terms of connection. In a discrete domain, every entity decomposes into atoms, which have no proper parts. We define

$$\displaystyle{ \mathsf{Atom(x) = _{\mathrm{def}}\neg \exists yPP(y,x)} }$$

(D11)

Then it can be seen that (N1) is equivalent to $\mathsf{\neg \exists xAtom(x)}$.

If A is an atom which is connected to its complement A^c, then anything connected to A must either be A itself or overlap A^c, and hence in either case must be connected to A^c; but on the other hand A is obviously not part of its complement,⁴ so we have

$$\displaystyle{\forall z(\mathsf{C(a,z) \rightarrow C(b,z)) \wedge \neg P(a,b)}}$$

(where a and b denote A and A^c respectively), contradicting (N3).

For discrete mereotopology, then, both P and C are needed as primitive predicates in the logical language. How should they be interpreted? The subsets of $\mathbb{R}^{n}$ listed above are no longer appropriate, and an obvious substitute here would be to use subsets of $\mathbb{Z}^{n}$, i.e., sets of points with integer coordinates. How should C be interpreted in this case? Since overlap is a form of connection,⁵ we need only concern ourselves with the interpretation of non-overlapping connection, i.e., EC.

Fig. 11.1

External connection in discrete space

An example is illustrated in Fig. 11.1, where the atomic regions are shown as unit squares, which can be mapped in the obvious way to elements of $\mathbb{Z}^{2}$. The external connection between the two differently shaded regions depends on the fact that the squares labelled ‘a’ and ‘b’, one from each region, are adjacent to each other, and it is this notion of adjacency which forms the basis for a general way of interpreting the connection predicate in discrete mereotopologies. We do not confine ourselves to subsets of $\mathbb{Z}^{n}$ but rather to regions defined over a more general class which we define as follows:

Definition.

An adjacency space is a non-empty set U of entities called cells together with a reflexive, symmetric relation $\sim \subseteq U \times U$, called adjacency.

An adjacency space can be regarded as a graph; but this does not mean that the theory of adjacency spaces is identical to graph theory. An important difference emerges when we consider substructures. A graph is specified by a set V of vertices and a set E of edges, where each edge joins an element of V to an element of V. A subgraph is specified by a subset $V ^{\prime} \subseteq V$ of the vertices and a subset $E^{\prime} \subseteq E$ of the edges, with the proviso that each edge in E′ joins an element of V ′ to an element of V ′. There is no requirement that an edge in E which happens to join an element of V ′ to an element of V ′ must be in E′. Thus there can be many different subgraphs of (V, E) all of which have the vertex-set V ′. In adjacency spaces, the adjacency or otherwise of two cells is fixed by the space and is automatically inherited by the substructures. Thus a substructure of an adjacency space can be specified by giving its cells alone, without reference to adjacency.

These substructures, which may be thought of as aggregates of cells, are called regions, and it is these entities that discrete mereotopology is primarily concerned with, not the cells themselves. A cell might, indeed, be considered to be the aggregate which is composed of precisely that cell and nothing else; but for theoretical purposes it is convenient to specify a region in terms of the (non-empty) set of cells which make it up, and in that case a one-cell region is conceptually distinct from its only cell, the former being, in fact, the singleton set of the latter. Therefore an interpretation I of the logical language $\mathcal{L}_{\mathsf{P,C}}$ over an adjacency space (U, ∼ ) is specified as follows:

• Each individual term t of the logical language denotes a non-empty subset $t^{I} \subseteq U$.

• A formula P(t₁, t₂) is interpreted to mean that $t_{1}^{I} \subseteq t_{2}^{I}$.

• A formula C(t₁, t₂) is interpreted to mean that there are cells x ∈ t₁^I and y ∈ t₂^I such that x ∼ y.

Thus two regions are regarded as connected so long as some cell in one is adjacent to some cell in the other.⁶

The theory of Discrete Mereotopology (DM), as we shall understand it in this paper, comprises all and only those formulae of the language $\mathcal{L}_{\mathsf{P,C}}$ which are satisfied by every adjacency space under the scheme of interpretation just specified. It is easy to see that DM includes all the formulae thus far introduced with labels beginning with either A or T: the formulae (A1), (A2), (A6), and (T1) characterising parthood, (A3) and (A4) characterising connection, and (A5) relating parthood and connection. ^7, 8

DM does not include the converse of (A5), meaning that the definitional reduction of P to C given by (N3) is not available here. The other important non-theorem is (N1), which expresses the infinite subdivisibility of regions that is characteristic of non-discrete (dense or continuous) models; instead, DM includes the formula

$$\displaystyle{ \mathsf{\forall x\exists y(P(y,x) \wedge Atom(y))\;,} }$$

(A7)

which says that every region has an atomic region as part. The predicate Atom is clearly satisfied by just the singleton subsets of the universe U; and every subset of U has at least one singleton subset; under the interpretation, these two sets count as a region and an atomic part of that region.

It will be convenient to introduce a predicate AP to say that one region is an atomic part of another; this is straightforwardly defined as follows:

$$\displaystyle{ \mathsf{AP(x,y) = _{\mathrm{def}}Atom(x) \wedge P(x,y)\;,} }$$

(D12)

enabling us to rewrite (A7) as ∀x∃yAP(y,x).

The mereotopological relations of atoms are much simpler than those of general regions. In particular, if A overlaps B, where A is an atom, then the common part of A and B cannot be a proper part of A and must therefore be A itself. We thus have

$$\displaystyle{ \mathsf{Atom(x) \rightarrow (O(x,y) \rightarrow P(x,y)).} }$$

(T2)

An important mereological principle, which forms part of General Extensional Mereology, is the Strong Supplementation Principle (Simons, 1987, p. 29), which states that any region that is not part of a given region must have a part that does not overlap that region:

$$\displaystyle{ \mathsf{\neg P(y,x) \rightarrow \exists z(P(z,y) \wedge \neg O(z,x))} }$$

(A8)

In combination with (A7), this leads to a powerful extensionality principle for DM, namely

$$\displaystyle{ \mathsf{\forall z(AP(z,x) \leftrightarrow AP(z,y))) \rightarrow x = y.} }$$

(T3)

Whereas, in order to show that two regions are the same, (T1) requires us check that they agree in all their parts, with (T3) it suffices to check that they agree in just their atomic parts.

To see how this follows from (A8), suppose we have

$$\displaystyle{ \mathsf{\forall z(AP(z,x) \leftrightarrow AP(z,y)).} }$$

(*)

We must show that x = y. Suppose not; then by (A6), either $\mathsf{\neg P(x,y)}$ or $\mathsf{\neg P(y,x)}$. Without loss of generality we may assume the former. By (A8), this means there is a region u such that

$$\displaystyle{ \mathsf{P(u,x) \wedge \neg O(u,y)\;.} }$$

(**)

By (A7), there is a region v such that AP(v,u), and by transitivity therefore AP(v,x). By (∗) this means that AP(v,y). We now have $\mathsf{P(v,u)} \wedge \mathsf{P(v,y)}$, so O(u,y), which contradicts ( ∗∗).

It is clear that the Strong Supplementation Principle is satisfied when regions are interpreted as subsets of an adjacency space, so both (A8) and (T3) belong to DM. The upshot of this is that we can define a region uniquely by characterising its atomic parts. We will use this in the following fashion: if a predicate ϕ is defined by a rule of the form

$$\displaystyle{\phi \mathsf{(x) = _{\mathrm{def}}\forall z(Atom(z) \rightarrow (P(z,x) \leftrightarrow }\psi \mathsf{(z,x)))}}$$

then it follows that any two regions with the property ϕ are identical.

The formulae (A1), (A2), (A6), and (A8) together constitute the axiomatic basis for the system designated EM (for Extensional Mereology) in Varzi (1996). The addition of (A7) yields Atomic Extensional Mereology AEM.

The study of discrete mereotopology can be pursued on two levels, which we may loosely characterise as “set-theoretical” and “logical”. At the set-theoretical level, the class of adjacency spaces are treated as mathematical objects in their own right, independently of any particular logical language chosen for describing them. At the logical level, on the other hand, one focusses on the particular first-order language $\mathcal{L}_{\mathsf{P,C}}$, which is the common language in which to express mereotopological theses, regardless of whether discrete or continuous spaces are intended. The set-theoretical level provides a metalanguage within which one can specify interpretations of the logical level. While much of what is said at one level can be transposed easily to the other, it is important to maintain a clear conceptual distinction between them. This is supported here by a typographical distinction: formulae at the logical level are always printed in a sanserif font.

Moving back and forth between the levels we can investigate what formulae of $\mathcal{L}_{\mathsf{P,C}}$ are satisfied in adjacency spaces (these formulae constituting the theory of DM), and conversely which properties of adjacency spaces can be expressed in the language. We can then ask whether the theory of adjacency spaces, insofar as it can be expressed in $\mathcal{L}_{\mathsf{P,C}}$, is axiomatisable, i.e., whether there is a finitely specifiable set of $\mathcal{L}_{\mathsf{P,C}}$ formulae from which all and only the true theorems of DM follow as logical consequences.

In the remainder of this paper we present a few of the most important features of DM, briefly discuss its relation to some other approaches, and describe an area in which it is being applied.

3 Examples of Adjacency Spaces

The adjacency space in Fig. 11.1 is underdetermined, in that we did not specify how the relation ∼ was to be defined. It was assumed that the reader would naturally understand that the cells labelled ‘a’ and ‘b’ were to count as adjacent. In fact there are (at least) two different, and equally natural, ways of understanding adjacency in $\mathbb{Z}^{2}$. Under orthogonal adjacency, only cells which share an edge count as adjacent; thus each cell is adjacent to four cells other than itself. We denote this relation ∼ ₄. Orthodiagonal adjacency is where cells count as adjacent so long as they share at least one boundary point—either along an edge or at a corner; each cell is adjacent to eight others, and hence we denote this relation ∼ ₈. These two adjacency relations are defined as follows:

• (x, y) ∼ ₄(x′, y′) iff | x − x′ | + | y − y′ | ≤ 1.

• (x, y) ∼ ₈(x′, y′) iff | x − x′ | ≤ 1 and | y − y′ | ≤ 1.

Both of these spaces are homogeneous in the sense that all cells “look the same”; more formally, for any x, y ∈ U there is a bijective adjacency-preserving function from U to U which maps x onto y.

The adjacency spaces $(\mathbb{Z}^{2},\sim _{4})$ and $(\mathbb{Z}^{2},\sim _{8})$ have played a prominent part in work on discrete spaces, mainly because they are the most natural spaces within which to model digital pictures, as seen, for example, on a computer screen in which the display is produced by assigning colour values to each element in a rectangular array of pixels (see, e.g., Rosenfeld, 1979; Kong and Rosenfeld, 1989).

Other homogeneous adjacency spaces correspond to tessellations of triangles or hexagons. In the triangular case, there are two possible adjacency relations: X ∼ ₃Y if triangles X and Y share an edge, and X ∼ ₁₂Y if they share at least one boundary point. With the hexagonal lattice there is only one natural adjacency relation, ∼ ₆, which holds between hexagons that share an edge. All these cases are illustrated in Fig. 11.2.

Fig. 11.2

Adjacency relations in regular planar tessellations

Homogeneous adjacency spaces do not need to be infinite. Familiar examples of finite spaces are provided by the five platonic solids. The faces of a dodecahedron, for example, can be thought of as a 12-element adjacency space, where adjacency is interpreted as edge-sharing between the pentagonal faces.

Beyond these examples, adjacency spaces do not have to be homogeneous. Non-homogeneous tessellations include the triangulated irregular networks (TIN) used in Geographical Information Science. An example is shown in Fig. 11.3a. As with the homogeneous tessellation of squares, two kinds of adjacency can be defined on a TIN: either adjacency along edges only, or adjacency at edges and vertices. The advantage of a hexagonal tessellation is that this ambiguity does not arise, and for this reason we will use such tessellations for our illustrative examples in what follows—though for practical convenience, the hexagonal tessellation will be represented in the form of an isomorphic “staggered squares” grid, as shown in Fig. 11.3b.

Fig. 11.3

(a) A triangular irregular network (TIN). (b) A grid of staggered squares, isomorphic to the regular hexagonal tessellation

4 Mereotopological Relations on Adjacency Spaces

Given the interpretation of the relations P and C over an adjacency space, the interpretations of all the relations defined in terms of P and C, such as the RCC8 relations, become fixed. Following the standard convention in model theory, we write $(U,\sim )\models R[X,Y ]$ to mean that the relation denoted by a predicate R (defined in $\mathcal{L}_{\mathsf{P,C}}$) holds between the elements X, Y ∈ U. Thus for example we have, for regions X, Y:

• $(U,\sim )\models \mathsf{DC}[X,Y ]$ iff there are no cells x ∈ X and y ∈ Y such that x ∼ y.

• $(U,\sim )\models \mathsf{EC}[X,Y ]$ iff $X \cap Y = \varnothing$ and there are cells x ∈ X and y ∈ Y such that x ∼ y.

• $(U,\sim )\models \mathsf{TP}[X,Y ]$ iff $X \subseteq Y$ and there are cells x ∈ X and y∉Y such that x ∼ y.

• $(U,\sim )\models \mathsf{NTP}[X,Y ]$ iff for all cells x ∈ X, if x ∼ y then y ∈ Y.

• $(U,\sim )\models \mathsf{EQ}[X,Y ]$ iff X = Y.

Examples of all the RCC8 relations are illustrated in Fig. 11.4, using regions defined on the “staggered squares” grid.

Fig. 11.4

RCC8 relations in an adjacency space

It should be noted that every region is a non-tangential part of U since the consequent of the defining condition, y ∈ Y, is always true when Y = U.

The set of subsets of U forms a Boolean algebra under the usual set-theoretic operations of union, intersection, and complement, with U itself acting as the top element (generally notated 1 or ⊤) and ∅ as the bottom element (notated 0 or ⊥ ). Since ∅ is not a region, the regions just fall short of being a Boolean algebra: they form a quasi-Boolean algebra. In mereotopology, therefore, the Boolean operations are appropriately restricted so that neither their range nor their domain contains the empty set, as we show below.

The universe U can be characterised in $\mathcal{L}_{\mathsf{P,C}}$ as the region which every other region is part of. This can be expressed by the predicate U, defined by

$$\displaystyle{ \mathsf{U(x) = _{\mathrm{def}}\forall yP(y,x)} }$$

(D13)

That such a region exists is stated by the formula

$$\displaystyle{ \mathsf{\exists xU(x),} }$$

(A9)

which is generally accepted as an axiom in RCC, whether in a discrete or continuous setting. By antisymmetry of P, it straightforwardly follows from this that there can be at most one universal region; in terms of adjacency structures we have

$$\displaystyle{(U,\sim )\models \mathsf{U}[X]\mbox{ if and only if }X = U.}$$

We can therefore introduce a constant symbol U to denote the unique universal region, defined contextually as follows:

$$ \phi \mathbf{(U)} = {{}_{{\mathrm{def}}}\forall x({\rm U}(x)} \rightarrow \phi \mathsf{(x))\;,} $$

(D14)

where ϕ stands for any open formula with one free variable.

Since not all pairs of regions have a Boolean product (intersection), we cannot represent it by a function symbol in $\mathcal{L}_{\mathsf{P,C}}$; instead we define a relational predicate Prod, the intended meaning of Prod(x,y,z) being that z is the intersection of x and y, defined as follows:

$$\displaystyle{ \mathsf{Prod(x,y,z) = _{\mathrm{def}}\forall v(P(v,z) \leftrightarrow P(v,x) \wedge P(v,y))\;.} }$$

(D15)

Similarly, the Boolean sum (union) is defined by

$$\displaystyle{ \mathsf{Sum(x,y,z) = _{\mathrm{def}}\forall v(O(v,z) \leftrightarrow O(v,x) \vee O(v,y))\;,} }$$

(D16)

and the Boolean difference by

$$\displaystyle{ \mathsf{Diff(x,y,z) = _{\mathrm{def}}\forall v(P(v,z) \leftrightarrow P(v,x) \wedge \neg O(v,y))\;.} }$$

(D17)

The existence of regions playing the role of z in these formulae is stated by the following formulae, which also specify the conditions on x and y for such a z to exist:

$$\displaystyle{ \mathsf{O(x,y) \rightarrow \exists zProd(x,y,z)\;,} }$$

(A10)

$$\displaystyle{ \mathsf{\exists zSum(x,y,z)\;,} }$$

(A11)

$$\displaystyle{ \mathsf{\neg P(x,y) \rightarrow \exists zDiff(x,y,z)\;.} }$$

(A12)

As with (D13), it follows from (D15), (D16), and (D17) that products, sums, and differences, where they exist, are unique. Note that (A12), in conjunction with (A1), logically implies (A8), meaning that the latter could be relegated to the status of a theorem (with a ‘T’ label) rather than an axiom; however, we shall retain the designation (A8) to avoid confusion.

The complement of a non-universal region can be defined as its difference from U, i.e.,

$$\displaystyle{\mathsf{Compl(x,y) = _{\mathrm{def}}Diff(U,x,y)\;.}}$$

Since we always have P(v,U), this may be expanded as

$$\displaystyle{ \mathsf{Compl(x,y) = _{\mathrm{def}}\forall v(P(v,y) \leftrightarrow \neg O(v,x))\;.} }$$

(D18)

It is easy to show that, for non-empty sets X, Y ⊆ U, $(U,\sim )\models \mathsf{Compl}[X,Y ]$ if and only if X = Y^c, thus ensuring that the $\mathcal{L}_{\mathsf{P,C}}$-definable predicate Compl captures the set-theoretic relation of complementation insofar as it applies to regions in adjacency spaces. It does not immediately follow from this, of course, that Compl behaves like complementation in arbitrary models of DM, but that this is so is shown by the following theorem:

$$\displaystyle{ \mathsf{Compl(x,y) \leftrightarrow \neg O(x,y) \wedge Sum(x,y,U)\;,} }$$

(T4)

which says that one region is the complement of another if and only if they are disjoint regions whose sum is the universe. A corollary of this is that complementarity is mutual:

$$\displaystyle{ \mathsf{Compl(x,y) \rightarrow Compl(y,x)} }$$

(T5)

The proofs of these theorems are given in Appendix 1.

With the addition of (A9), (A10), (A11), and (A12) to EM we obtain the system of Closed Extensional Mereology designated CEM by Varzi (1996). Li and Ying (2004) show that every model of CEM is isomorphic to a complete quasi-Boolean algebra, and therefore that ACEM, the atomic variant of CEM with the additional axiom (A7) is isomorphic to an atomic complete quasi-Boolean algebra,

In standard mereotopology, where there are no atomic regions, and parthood is defined in terms of connection, the definition of these Boolean operations in $\mathcal{L}_{\mathsf{P,C}}$ has proved somewhat problematic, it being difficult to demonstrate that the required interrelationships hold when connection is taken into account. In particular, (D18) does not suffice to captured the desired behaviour and needs to be supplemented by an additional axiom, represented here by the formula

$$\displaystyle{ \mathsf{Compl(x,y) \rightarrow \forall z(C(z,y) \leftrightarrow \neg NTP(z,x))} }$$

(T6)

In DM, however, it can be proved that (T6) follows from (D18) and the existing axioms, as demonstrated in Appendix 2.

5 Quasi-topological Operators

The relation NTP picks out those subregions of a given region which are disconnected from the complement of the region: the neighbours of each cell in the subregion are all in the region itself. The union of all the non-tangential parts of a region thus consists of all the cells in the region whose neighbours are also all in the region:

$$\displaystyle{\bigcup \{X\ \vert \ (U,\sim )\models \mathsf{NTP}[X,R]\} =\{ x \in U\ \vert \ \forall y(x \sim y \rightarrow y \in R)\}}$$

This set is called the (discrete) interior of region R and is denoted int_D(R). So long as it is non-empty, it is of course a region itself.

While int_D, considered as an operator on sets of cells, is a total function, when considered as an operator on regions it is only a partial function, since if int_D(R) is empty, R does not have an interior region. In the language $\mathcal{L}_{\mathsf{P,C}}$, therefore, the notion of interior is expressed by means of a relational predicate Int(x,y), meaning that y is an interior of x, defined by:

$$\displaystyle{ \mathsf{Int(x,y) = _{\mathrm{def}}\forall z(P(z,y) \leftrightarrow NTP(z,x))} }$$

(D19)

Thus a region is an interior of R if and only if its parts are all and only the non-tangential parts of R. As discussed earlier, it suffices, in fact, to consider just atomic parts, so we have

$$\displaystyle{ \mathsf{Int(x,y) \leftrightarrow \forall z(Atom(z) \rightarrow (P(z,y) \leftrightarrow NTP(z,x))).} }$$

(D19')

It now follows that a region cannot have two distinct interiors, since if $\mathsf{Int(x,y_{1}) \wedge Int(x,y_{2})}$ then from (D19) we have $\mathsf{\forall z(P(z,y_{1}) \leftrightarrow P(z,y_{2}))}$ so in particular P(y₂,y₁) and P(y₁,y₂), whence y₁= y₂ by antisymmetry of P (A6). The appropriateness of (D19) follows from the easily demonstrated fact that, if $Y \neq \varnothing$, $(U,\sim )\models \mathsf{Int}[X,Y ]$ if and only if Y = int_D(X). Thus Int does capture in $\mathcal{L}_{\mathsf{P,C}}$ the relationship between a region and its discrete interior, so long as the latter is non-empty.

Any connected component of U, and any union of such connected components (including U itself), is its own interior, since it is a non-tangential part of itself. If a region has no non-tangential parts, and hence no interior, we describe it as “thin”. In Fig. 11.5a, the left-hand region has its interior shaded a darker grey; the right-hand region is thin, since all of its cells have at least one neighbour outside the region. Note that U. and any of its connected components, cannot be thin since it is its own interior; in particular, therefore, a single cell is a thin region so long as it is connected to at least one other cell, but if it is a connected component of U (and thus an isolated cell, disconnected from the rest of the space), it is not thin.

Fig. 11.5

Discrete interiors and closures. In (a), a two-part region (all shading) and its discrete interior (dark grey); in (b), a region (mid-grey) and its discrete closure (all shading)

We refer to the discrete interior in order to distinguish int_D from the topological interior operator int, which does not apply to adjacency spaces since they are not defined as topologies. The two operators share a number of common features, notably:

• int_(D)(U) = U , 

• $\forall X(\mathit{int}_{(D)}(X) \subseteq X)\;,$

• $\forall X\forall Y (X \subseteq Y \rightarrow \mathit{int}_{(D)}(X) \subseteq \mathit{int}_{(D)}(Y ))\;.$

The most important difference between the discrete and topological interior operators is that whereas the latter is idempotent, i.e.,

• $\forall X(\mathit{int}(\mathit{int}(X)) = \mathit{int}(X))\;,$

this is not, in general true for the former, since, in an adjacency space, the only regions for which int_D(X) = X are unions of connected components of the space. In view of both the similarities and the differences, we call int_D a quasi-topological operator.

In topology, the closure of a set is defined as the complement of the interior of its complement: cl(X) = (int(X^c))^c. The analogous operation in adjacency spaces gives us another quasi-topological operator, the discrete closure,

$$\displaystyle{\mathit{cl}_{D}(R)=(\mathit{int}_{D}(R^{c}))^{c}\,=\,\{x\ \vert \ \exists y(x \sim y \wedge y \in R)\}\,=\,\bigcap \{X\ \vert \ (U,\sim )\models \mathsf{NTP}[X,R]\}.}$$

Thus the discrete closure of a region R consists of all those cells which are adjacent to an element of R; it is the intersection of all regions which R is a non-tangential part of.

As with the interiors, the discrete closure shares some properties with the topological closure, namely

• $\mathit{cl}_{(D)}(\varnothing ) = \varnothing \;,$

• $\forall X(X \subseteq \mathit{cl}_{(D)}(X))\;,$

• $\forall X\forall Y (X \subseteq Y \rightarrow \mathit{cl}_{(D)}(X) \subseteq \mathit{cl}_{(D)}(Y ))\;,$

but not:

• $\forall X(\mathit{cl}(\mathit{cl}(X)) = \mathit{cl}(X))\;.$

As with interiors, the only regions in adjacency space for which cl_D(X) = X are the unions of connected components of the space.

Analogously to discrete interior, we can define the discrete closure relation in $\mathcal{L}_{\mathsf{P,C}}$ by

$$\displaystyle{ \mathsf{Cl(x,y) = _{\mathrm{def}}\forall z(P(y,z) \leftrightarrow NTP(x,z))\;,} }$$

(D20)

which says that y is the closure of x if and only if x is a non-tangential part of all and only those regions y is part of.

Our decision to develop mereology with a universal element but no null element leads to a certain asymmetry. In set-theoretical interpretations the asymmetry shows up as the fact that the universal set is recognised as determining a region but the empty set is not. A consequence of this is that, unlike the discrete interior, discrete closure is a total function on regions: not every region has a discrete interior, but every region has a discrete closure. This means that we can also define the closure functioncl by

$$\displaystyle{ \phi \mathsf{(cl(x)) = _{\mathrm{def}}\forall y(Cl(x,y) \rightarrow }\phi \mathsf{(y)),} }$$

(D21)

where ϕ stands for any open formula with one free variable. Figure 11.5b shows a region (dark grey cells) and its discrete closure (the region plus the lighter grey cells).

Within $\mathcal{L}_{\mathsf{P,C}}$, in order to characterise the relationship between discrete closure and interior, we need to use the predicate Compl already defined in (D18). The relationship between discrete interior and discrete closure is then expressed in $\mathcal{L}_{\mathsf{P,C}}$ by the formula

$$\displaystyle{ \mathsf{Compl(x,y) \wedge Int(y,z) \wedge Compl(z,w) \rightarrow Cl(x,w),} }$$

(T7)

a proof of which is given in Appendix 3.

From now on, we shall use the words ‘closure’ and ‘interior’ on their own to mean the discrete closure and interior; if we need to refer to the topological operators, we shall do so explicitly. A useful way of characterising the closure and interior in an adjacency space is to use the idea of the neighbourhood of a cell, defined as follows:

$$\displaystyle{N(x) =\{ y \in U\ \vert \ x \sim y\}}$$

Thus neighbourhoods are in fact the closures of atoms, and the closure of any region $R \subseteq U$ is the union of the neighbourhoods of its constituent cells:

$$\displaystyle{\mathit{cl}_{D}(R) =\bigcup \{ N(x)\ \vert \ x \in R\}.}$$

The interior comprises those cells whose neighbourhoods are parts of the region:

$$\displaystyle{\mathit{int}_{D}(R) =\{ x \in U\ \vert \ N(x) \subseteq R\}\;.}$$

Useful operations result from combining closure and interior, in either order. If a set X includes some thin spikelike parts, these will disappear when the interior is taken, and will not be restored if closure is then applied. Thus $\mathit{cl}_{D}(\mathit{int}_{D}(X))$ is essentially like X but with any thin parts removed (Fig. 11.6, left). On the other hand, if the region has any thin holes or fissures, these will be filled in by the closure operation and not be opened out again when interior is applied. Thus int_D(cl_D(X)) is like X but with any thin holes or fissures filled in (Fig. 11.6, right). Regions which lack spikes or fissures, i.e., for which $X = \mathit{cl}_{D}(\mathit{int}_{D}(X)) = \mathit{int}_{D}(\mathit{cl}_{D}(X))$, may be called regular.

Fig. 11.6

Left: A region (mid grey) with its interior (dark grey) and the closure of the interior (heavy outline). Right: The same region, with its closure (all shading) and the interior of the closure (heavy outline)

Referring back to the earlier discussion of the distinction between adjacency spaces and graphs, it should be noted that Stell (2000b) has reformulated these quasi-topological operators in terms of two kinds of complementation definable on graphs. Recall that a subgraph is specified by giving both its vertices and its edges. The negation$\neg G$ of a subgraph G consists of all the vertices of U that are not in G, and all the edges of U joining vertices in $\neg G$. The supplement ∼ G consists of all the edges of U that are not in G, and all the vertices of V that are incident with an edge in $\neg G$. Then the subgraphs $\neg \sim G$ and $\sim \neg G$ correspond to int_D(G) and cl_D(G) respectively. It is worth noting that Stell defines a region in a graph to be subgraph G such that $\neg \neg G = G$; thus a region, in this sense, includes all the edges of U that join vertices of G to a vertices of G; it can therefore can be specified just by giving its vertices, and thus corresponds to a region in adjacency space.

6 Measures of Size and Distance

From now on we assume that the universe is connected, meaning that every region (other than the universe itself) is connected to its complement:

$$\displaystyle{\forall X \subset U((U,\sim )\models \mathsf{C}[X,X^{c}])\;.}$$

This means that the universe consists of a single connected component, itself, and is therefore the only region which is its own closure and interior (the empty set also has this property, but it is not a region).⁹

We have already characterised a thin region as one with empty interior. More generally we can define the thickness of a region as the number of successive interior operations required to reduce the region to nothing. For a region R of thickness n we have the sequence

$$\displaystyle{R,\mathit{int}_{D}(R),\mathit{int}_{D}(\mathit{int}_{D}(R)),\ldots,\mathit{int}_{D}^{n}(R) = \varnothing \;.}$$

Thus for $X \subseteq U$ we define

$$\displaystyle{\mathit{Thickness}(X) = _{\mathrm{def}}\left \{\begin{array}{ll} 0 &(\mbox{ if $X = \varnothing $}) \\ n + 1&(\mbox{ if $X\neq \varnothing $ and $\mathit{Thickness}(\mathit{int}_{D}(X)) = n$}) \\ \infty &(\mbox{ Otherwise}) \end{array} \right.}$$

The thin regions are then those with thickness 1. The universe, U, since it is its own interior, can never be reduced to nothing in this way, so its thickness is infinite—even if it is finite in the sense of containing only finitely many cells.¹⁰ Regions other than the universe can only have infinite thickness if the universe is infinite. Thickness provides a measure of how ‘substantial’ a region is.

A region of thickness n is the union of a sequence of n − 1 shells surrounding a central core of thickness 1. If Thickness(R) = n, then the shells of region R are

$$\displaystyle{R\setminus \mathit{int}_{D}(R),\mathit{int}_{D}(R)\setminus \mathit{int}_{D}(\mathit{int}_{D}(R)),\ldots,\mathit{int}_{D}^{n-2}(R)\setminus \mathit{int}_{ D}^{n-1}(R),\mathit{int}_{ D}^{n-1}(R)\;,}$$

where the final term in the sequence is the core, whose interior is empty.

We can perform an analogous construction, starting from a region R and repeatedly forming the closure, thus building up a sequence of regions:

$$\displaystyle{R,\mathit{cl}_{D}(R),\mathit{cl}_{D}(\mathit{cl}_{D}(R)),\mathit{cl}_{D}(\mathit{cl}_{D}(\mathit{cl}_{D}(R))),\ldots \;.}$$

If the universe is infinite, this process may go on for ever, depending on the starting point R, otherwise, given that the universe is connected, we will reach a point where cl_Dⁿ(R) = U. Give the complementarity of closure and interior, this occurs when Thickness(R^c) = n. We can think of the sequence of closures being built up by the successive addition of outer shells,

$$\displaystyle{\mathit{cl}_{D}(R)\setminus R,\mathit{cl}_{D}(\mathit{cl}_{D}(R))\setminus \mathit{cl}_{D}(R),\ldots,\mathit{cl}_{D}^{n}(R)\setminus \mathit{cl}_{ D}^{n-1}(R),\ldots \;.}$$

The notion of distance is usually defined in terms of shortest paths; but as we shall see, in adjacency spaces it can also be defined in terms of closures.

A path of length n from cell x to cell y is a sequence x₀, x₁, …, x_n such that x₀ = x, x_n = y, and for i = 1, …, n, x_i−1 ∼ x_i. We can prove that there is a path of length n from x to y if and only if y ∈ cl_Dⁿ({x}). We use induction on n:

• Base case (n = 0). A path of length 0 from x to y consists of a single point x₀ which must be equal to both x and y. Clearly this exists if and only if x = y. Since cl_D⁰({x}) = { x} this means that y ∈ cl_D⁰({x}) as required.

• Induction step (from n − 1 to n). Assume the result holds for n − 1. If x₀, x₁, …, x_n is a path of length n from x to y, then x₀, x₂, …, x_n−1 is a path of length n − 1 from x to x_n−1. By hypothesis such a path exists if and only if x_n−1 ∈ cl_Dⁿ⁻¹({x}). Since x_n−1 ∼ x_n = y, this means that $y \in \mathit{cl}_{D}(\mathit{cl}_{D}^{n-1}(\{x\})) = \mathit{cl}_{D}^{n}(\{x\})$, as required.

This gives us a natural measure of the distance between two cells:

$$\displaystyle{d(x,y) =\min _{n\in \mathbb{N}}(y \in \mathit{cl}_{D}^{n}(\{x\}))\;.}$$

From the above, this is the length of a shortest path from x to y, and it is easy to see that it is a true metric, i.e.,

• d(x, y) = 0 if and only if x = y,

• d(x, y) = d(y, x)

• d(x, z) ≤ d(x, y) + d(y, z) (triangle inequality).

Note that there will not, in general, be a unique shortest path between two cells. A familiar example is the adjacency space $(\mathbb{Z}^{2},\sim _{4})$. The points (m, n) and (m + 1, n + 1) are linked by two minimal paths, of length 2, one going via (m, n + 1) and the other via (m + 1, n); in general, between the points (m, n) and (m + h, n + k) there are^h+kC_h minimal paths, of length h + k. This is the “Manhattan” or “city-block” distance.

An obvious generalisation of distance to regions gives us the proximal distance between two regions, defined as the smallest number of closure operations that can be applied to X to produce a region that overlaps Y; as before, this is equivalent to the more familiar definition as the shortest distance between a cell in one region and a cell in the other:

$$\displaystyle{\mathit{pd}(X,Y ) =\min _{n\in \mathbb{N}}(\mathit{cl}_{D}^{n}(X)\cap Y \neq \varnothing ) =\min _{\begin{array}{c} x \in X \\ y \in Y \end{array} }d(x,y).}$$

Unfortunately proximal distance is not a true metric since (1) the proximal distance between distinct but overlapping regions is zero, and (2) the triangle inequality does not hold, i.e., we can have regions X, Y, Z such that pd(X, Z) > pd(X, Y ) +pd(Y, Z).

A more satisfactory measure of distance for regions is the Hausdorff distance, defined as the greatest distance between any point in one of the regions and the nearest point in the other:

$$\displaystyle{\mathit{hd}(X,Y ) =\max \left (\max _{x\in X}\min _{y\in Y }d(x,y),\max _{y\in Y }\min _{x\in X}d(x,y)\right ).}$$

If $\max _{x\in X}\min _{y\in Y }d(x,y) = n$, then for any x ∈ X, y ∈ Y we have $y \in \mathit{cl}_{D}^{n}(\{x\}) \subseteq \mathit{cl}_{D}^{n}(X)$, so $Y \subseteq \mathit{cl}_{D}^{n}(X)$, and likewise with X and Y reversed. Thus an equivalent formulation in terms of closures is

$$\displaystyle{\mathit{hd}(X,Y ) =\min \left \{n \in \mathbb{N}\ \vert \ X \subseteq \mathit{cl}_{D}^{n}(Y ) \wedge Y \subseteq \mathit{cl}_{ D}^{n}(X)\right \}.}$$

The Hausdorff distance between two regions in adjacency space is thus the smallest n such that each region is within the nth closure of the other. Unlike proximal distance, Hausdorff distance is a true metric.

It should be noticed that while the Hausdorff distance between a region and its closure is always 1, i.e., hd(X, cl_D(X)) = 1, this is not necessarily the case for a region and its interior. In fact

$$\displaystyle{\mathit{hd}(X,\mathit{int}_{D}(X)) = 1\mbox{ if and only if }\mathit{cl}_{D}(\mathit{int}_{D}(X)) = X.}$$

Such an X is called a regular closure set in Smyth and Webster (2007).

7 Relation to Mathematical Morphology

Mathematical Morphology (MM) comprises a set of mathematical tools for manipulating images. Readers familiar with MM will recognise a clear similarity between our discrete interior and closure operations and the erosion and dilation operators of that theory. Here we make this relationship explicit. While the theory of MM may be developed both for continuous and discrete images, for our purposes we will consider only the discrete case: in this case we are working with $\mathbb{Z}^{2}$. An image is any subset of this set.

In Mathematical Morphology, there is no pre-defined adjacency relation. Instead, erosion and dilation may be performed with respect to an arbitrary structuring element which in effect determines which points are to count as adjacent. A structuring element is itself an image, typically small. Given an image X and a structuring element B, we define

• The dilation of X by B is the image

  $$\displaystyle{X \oplus B =\{ x + b\ \vert \ x \in X,b \in B\}.}$$

• The erosion of X by B is the image

  $$\displaystyle{X \ominus B =\{ y \in \mathbb{Z}^{2}\ \vert \ \forall b \in B(y + b \in X)\}.}$$

Addition here is coordinate-wise, i.e., treating points as vectors. The dilation of a region by B expands B by replacing each of its points by a copy of B; the location of the copy depends on where B itself is with respect to the origin. It is usual to assume that the origin is one of the points of B, otherwise dilation will result in a displacement of the image as well as an expansion. If the structuring element is taken to be a 3 × 3 square centered on the origin, then the dilation of any image will be exactly its closure with respect to the adjacency relation ∼ ₈. If instead we take a cross-shaped structuring element consisting of the origin and the four points orthogonally adjacent to it (like the leftmost image in Fig. 11.2), dilation then gives closure with respect to the relation ∼ ₄.

Erosion removes the outer part of the image, retaining a point only if a copy of the structuring element anchored on that point would lie entirely within the image. So long as the structuring element has central symmetry (i.e., B = −B), erosion and dilation are related exactly as interior and closure. More generally we have

$$\displaystyle{X \oplus B = (X^{c} \ominus (-B))^{c}\;,}$$

where − B = { −x  |  x ∈ B}.

MM makes much use of operations called opening and closing, defined as follows:

• Opening: $X \circ B = (X \ominus B) \oplus B$,

• Closing: $X\bullet B = (X \oplus B) \ominus B$.

These correspond to the DM operations cl_D(int_D(X)) and int_D(cl_D(X)) illustrated in Fig. 11.6.

Mathematical Morphology may appear to be in some ways more general, and in other ways less so, than Discrete Mereotopology, but both these appearances are misleading.

The sense in which MM may appear to be more general than DM is that it allows arbitrary structuring elements; but this generality could be recovered in DM by defining a different adjacency relation on $\mathbb{Z}^{2}$ for each possible structuring element. For example, if the structuring element consists of just the points {(0, 0), (1, 0), (0, 1)}, then the corresponding adjacency relation would relate any point (x, y) to (x, y), (x + 1, y), (x, y + 1) and nothing else.

On the other hand, as usually presented in terms of structuring elements, MM would appear to presuppose spaces which are homogeneous in the sense that they allow a copy of the same structuring element to be located at each point in the space. As we have seen, however, DM is equally happy in non-homogeneous spaces where such arbitrary translation of structuring elements does not make sense; the discrete closure and interior operations of DM work just as well in this setting as with homogeneous spaces, but the most familiar forms of MM gain no purchase in this context.

This is not, however, the full story, since a number of researchers have investigated forms of MM which allow variable structuring elements—see for example Roerdink and Heijmans (1988) and Verly and Delanoy (1993). And it is certainly true more generally that the study of MM is a much more mature research area than that of DM, and as a result has been developed to a considerably greater degree of mathematical sophistication and generality—see for example Bloch et al. (2007).

8 Relation to Digital Topology

Adjacency spaces are examples of a general class of mathematical structures called closure spaces (Čech, 1966). A closure space is a pair (U, cl), where U is any set, and cl is a function mapping each set $X \subseteq U$ to a set $\mathit{cl}(X) \subseteq U$ such that

• 1. $\mathit{cl}(\varnothing ) = \varnothing$,

• 2. $X \subseteq \mathit{cl}(X)$,

• 3. $\mathit{cl}(X \cup Y ) = \mathit{cl}(X) \cup \mathit{cl}(Y )$.

This notion generalises topological closure, which in addition to satisfying conditions 1–3 also satisfies the idempotency rule

• 4. $\mathit{cl}(\mathit{cl}(X)) = \mathit{cl}(X)$,

which as we have noted is not, in general, satisfied by sets in an adjacency space.

Although the discrete closure operation in an adjacency space is not a topological closure (since it is not idempotent), one can define topological spaces associated with any adjacency space. A trivial way of doing this is to specify the discrete topology on U, that is, the topology under which cl(X) = X for every X ⊆ U. Much more interesting is to extend U by including in the universe not just the original elements of U (conceived of as atomic regions) but also boundary elements where these atomic regions adjoin one another, and boundaries of those, etc, depending on the dimensionality one wishes to confer on the space. This is illustrated in Fig. 11.7, where, on the left is shown part of an adjacency space in the form of a regular hexagonal lattice, and on the right is shown a space which includes, in addition to the hexagons of the original lattice, a set of line segments representing the boundaries of the hexagons and a set of points representing the ends of the line segments. This space can be made into a topology by specifying that the closure of any set consists of the elements of that set together with all their bounding elements. Thus the closure of one hexagonal tile consists of the hexagon together with its six bounding lines and its six bounding points, and the closure of a line element is the line together with its two bounding points. It is easy to see that this closure operation satisfies the conditions (1)–(4) above, and therefore defines a topological space. Such topological spaces, if finite, are called cellular complexes, and these are investigated in the context of applications to image analysis in Kovalevsky (1989).

Fig. 11.7

An adjacency space in the form of a hexagonal grid (left), and the topological space obtained by the addition of bounding lines and points (right)

The topological spaces obtained in this way from rectangular grids of the form $\mathbb{Z}^{n}$ are called Khalimsky spaces (Khalimsky et al., 1990; Kong et al., 1991). See also Kong and Rosenfeld (1991) for a discussion of the relationship between these topological approaches and graph-based approaches such as DM.

9 An Application

Discrete Mereotopology has been applied to the analysis of histological images (Randell and Landini, 2008; Randell et al., 2013). Real-world images invariably have imperfections which means that when standard segmentation algorithms are applied to them in order to extract information about the entities pictured, the resulting structures are not always in conformity with theoretical models—e.g., one might find cell nuclei overlapping the boundaries of their cytoplasm, or distinct tissue types wrongly labelled. DM can be used to identify maximally parsimonious ways of repairing such ill-formed images, using “conceptual neighbourhood diagrams” (Freksa, 1992) to identify sequences of operations that can transform an existing inappropriate structure to one that is in conformity with expectation. This method works at the level of individual image pixels, and can therefore harness the power of mathematical morphology alongside DM; but by considering a coarser segmentation of the image one can exploit the ability of DM to allow reasoning about arbitrary adjacency spaces.

To illustrate, Fig. 11.8a shows a Haemotoxylin and Eosin stained section of an odontogenic keratocyst lining. Image-processing techniques are used to extract theoretical cell boundaries from this image, defining “virtual cells” or “v-cells” in the epithelial compartment separating the background free space at the top of the image from the connective tissue at the bottom. The segmentation into v-cells is shown in Fig. 11.8b. Individual v-cells, as well as the whole block of connective tissue and the background space, can be regarded as atomic regions of an adjacency space. The v-cells adjacent to the connective tissue form what is called the basal layer. If V is the region in the image consisting of the v-cells, and C is the region corresponding to the connective tissue, then the basal layer B can be identified as $V \cap \mathit{cl}_{D}(C)$. By taking successive closures of the basal layer we can segment the epithelium into layers as shown in Fig. 11.8c. This operation allows one to derive a more meaningful measure of tissue thickness, for example, than crude measures involving pixel counts or Euclidean distance. Such measures can provide important diagnostic criteria for histopathology. By taking a single target cell within the segmented image, one can similarly use the closure operation to generate nested rings of v-cells, as shown in Fig. 11.8d, which can again provide useful information, at the cellular level, on local tissue architecture.

Fig. 11.8

Application of discrete closure operation to a histological image (Images courtesy of Prof. Gabriel Landini and Dr D. Randell). (a) Stained epithelium section. (b) Segmentation into “virtual cells” (v-cells). (c) Layering of epithelial v-cells. (d) Nested shells of v-cells around a target cell

Appendix 1: Proof of (T4) and (T5)

The first theorem to be proved is

$$\displaystyle{ \mathsf{\forall x\forall y(Compl(x,y) \leftrightarrow \neg O(x,y) \wedge Sum(x,y,U))} }$$

(T4)

First, suppose Compl(x,y), so since P(y,y) we have $\mathsf{\neg O(y,x)}$ by (D18) and therefore

$$\displaystyle{ \mathsf{\neg O(x,y).} }$$

(1)

Let v be any region; if $\mathsf{\neg O(v,x)}$, then P(v,y) (since Comp(x,y)), so O(v,y). Hence $\mathsf{O(v,x) \vee O(v,y)}$. Since v is arbitrary, we always have O(v,U), and hence we have $\mathsf{O(v,U) \leftrightarrow O(v,x) \vee O(v,y)}$, i.e.,

$$\displaystyle{ \mathsf{Sum(x,y,U)} }$$

(2)

Conversely, suppose we have $\mathsf{\neg O(x,y) \wedge Sum(x,y,U)}$.

Let P(u,y), so that whenever P(w,u) we have also P(w,y). Therefore from $\mathsf{\neg O(x,y)}$, i.e. $\mathsf{\neg \exists w(P(w,y) \wedge P(w,x))}$, we infer $\mathsf{\neg \exists w(P(w,u) \wedge P(w,x))}$, i.e., $\mathsf{\neg O(u,x)}$. Hence we have shown $\mathsf{\forall u(P(u,y) \rightarrow \neg O(u,x))}$.

Now suppose $\mathsf{\neg O(u,x)}$. We must show P(u,y). Suppose not; then from $\mathsf{\neg P(u,y)}$, by (A8), there is a region w such that $\mathsf{P(w,u) \wedge \neg O(w,y)}$. From $\mathsf{\neg O(w,y)}$, since Sum(x,y,U) we have O(w,x) (since O(w,U) in any case). From P(w,u) and O(w,x) it is an easy deduction that O(u,x), contradicting our assumption. Hence we have shown $\mathsf{\forall u(\neg O(u,x) \rightarrow P(u,y))}$.

We now have $\mathsf{\forall u(P(u,y) \leftrightarrow \neg O(u,x))}$, i.e., Compl(x,y). □ 

The proof of (T5) is now straightforward:

$$\displaystyle\begin{array}{rcl} \mathsf{Compl(x,y)}& \mathsf{\Leftrightarrow }& \mathsf{\neg O(x,y) \wedge Sum(x,y,U) \Leftrightarrow \neg O(y,x) \wedge Sum(y,x,U)} {}\\ & \mathsf{\Leftrightarrow }& \mathsf{Compl(y,x).} {}\\ \end{array}$$

Appendix 2: Proof of (T6)

The theorem to be proved is

$$\displaystyle{ \mathsf{\forall x\forall y(Compl(x,y) \rightarrow \forall z(C(z,y) \leftrightarrow \neg NTP(z,x)))} }$$

(T6)

Assuming

$$\displaystyle{ \mathsf{Compl(a,b),} }$$

(1)

suppose, first, that C(c,b). From (1), since P(b,b), we have $\mathsf{\neg O(b,a)}$, hence we have $\mathsf{C(c,b) \wedge \neg O(b,a)}$ and therefore $\mathsf{\neg NTP(c,a)}$ by (D10). Hence we have $\mathsf{\forall z(C(z,b) \rightarrow \neg NTP(z,a))}$.

Next, suppose we have $\mathsf{\neg NTP(c,a)}$. Then from (D10), either we have

$$\displaystyle{ \mathsf{\neg P(c,a)} }$$

(2a)

or there is a region d such that

$$\displaystyle{ \mathsf{C(c,d) \wedge \neg O(d,a).} }$$

(2b)

In the former case, from (1) and (T5) we have Compl(b,a), so (2a) implies O(c,b), which implies C(c,b). In the latter case (2b), from (1) and ¬O(d,a) we have P(d,b). Then from C(c,d) and P(d,b) we have C(c,b) by (A5). Thus in either case we have C(c,b) and we have proved $\mathsf{\forall z(\neg NTP(z,a) \rightarrow C(z,b))}$.

Combining the results and generalising give us (T6). □ 

Appendix 3: Proof of (T7): Relationship of Discrete Interior and Closure

The theorem to be proved is

$$\displaystyle{ \mathsf{Compl(x,y) \wedge Int(y,z) \wedge Compl(z,w) \rightarrow Cl(x,w)} }$$

(T7)

Using the definitions (D19, D20, D18), this means that from

$$\displaystyle\begin{array}{rcl} \mathsf{\forall x(P(x,b)}& \leftrightarrow & \mathsf{\neg O(x,a))}{}\end{array}$$

(1)

$$\displaystyle\begin{array}{rcl} \mathsf{\forall x(P(x,c)}& \leftrightarrow & \mathsf{NTP(x,b))}{}\end{array}$$

(2)

$$\displaystyle\begin{array}{rcl} \mathsf{\forall x(P(x,d)}& \leftrightarrow & \mathsf{\neg O(x,c)))}{}\end{array}$$

(3)

we must derive

$$\displaystyle{ \mathsf{\forall x(P(d,x) \leftrightarrow NTP(a,x))} }$$

(4)

From (T5) we can rewrite (1) and (3) as

$$\displaystyle\begin{array}{rcl} \mathsf{\forall x(P(x,a)}& \leftrightarrow & \mathsf{\neg O(x,b))}{}\end{array}$$

(5)

$$\displaystyle\begin{array}{rcl} \mathsf{\forall x(P(x,c)}& \leftrightarrow & \mathsf{\neg O(x,d))}{}\end{array}$$

(6)

so from (2) and (6) we have

$$\displaystyle{ \mathsf{\forall x(\neg O(x,d) \leftrightarrow NTP(x,b))} }$$

(7)

Then from (1) and (7) (since NTP(x,b) implies P(x,b)) we have

$$\displaystyle{ \mathsf{\forall x(\neg O(x,d) \rightarrow \neg O(x,a))} }$$

(8)

Suppose $\mathsf{\neg P(a,d)}$. Then by (A8) there must be a region e such that $\mathsf{P(e,a) \wedge \neg O(e,d)}$. By (8) this would imply $\mathsf{P(e,a) \wedge \neg O(e,a)}$, a contradiction. Therefore we have P(a,d), and therefore

$$\displaystyle{ \mathsf{\forall x(P(d,x) \rightarrow P(a,x))} }$$

(9)

Suppose P(d,g). and let f be any region connected to a, i.e., C(a,f). Suppose $\mathsf{\neg O(f,d)}$. Then by (6) we have P(f,c) and so by (2), NTP(f,b). Therefore any region connected to f must overlap b. Since we have C(a,f) this means that O(a,b). But from (1) we know that $\mathsf{\neg O(a,b)}$ and we have a contradiction. Therefore O(f,d), and therefore, since P(d,g), we have O(f,g).

Thus we have

$$\displaystyle{ \mathsf{\forall x(P(d,x) \rightarrow \forall y(C(a,y) \rightarrow O(y,x)))} }$$

(10)

Combining (9) and (10) (and using (D10)) we get

$$\displaystyle{ \mathsf{\forall x(P(d,x) \rightarrow NTP(a,x))} }$$

(11)

which is one half of (4).

For the converse, let NTP(a,e); we must show that P(d,e). Assume on the contrary that

$$\displaystyle{ \mathsf{\neg P(d,e)} }$$

(12)

By (A8), there is a region f such that P(f,d) and $\mathsf{\neg O(f,e)}$.

From P(f,d) we have, by (3), $\mathsf{\neg O(f,c)}$, and therefore

$$\displaystyle{ \mathsf{\neg P(f,c)} }$$

(13)

From $\mathsf{\neg O(f,e)}$, we have, since NTP(a,e),

$$\displaystyle{ \mathsf{\neg C(a,f)} }$$

(14)

Also from $\mathsf{\neg O(f,e)}$, given NTP(a,e), and therefore P(a,e), we have $\mathsf{\neg O(f,a)}$, and therefore, by (1), P(f,b).

We will show that in fact NTP(f,b).

To this end we must show that anything connected to f overlaps b. Suppose $\mathsf{\neg O(z,b)}$. By (5) this implies P(z,a), and therefore, from (14), (A4) and (A5) $\mathsf{\neg C(z,f)}$. Hence if C(z,f) it follows that O(z,b). Thus we have NTP(f,b).

By (2) this gives P(f,c), contradicting (13). Hence assumption (12) is false, and we conclude, as required, that P(d,e).

We have now shown that $\mathsf{\forall x(NTP(a,x) \rightarrow P(d,x))}$, which, in combination with (11), gives us (4). □