Region Connection Calculus

Syntax

Symbols

We define an infinite set P whose members are called regions (P is used for Part or Place), and the set R = {DC, EC, PO, EQ, TPP, TPPi, NTTP, NTTPi} disjoint from P whose members are called spatial relations.

Symbols of RCC₈

The symbols of RCC₈ are Sym_RCC8 = P ⋃ R.

As with propositions in propositional logic, we will write distinct regions with distinct sequences of latin characters like so: AuvergneRhôneAlpes, CoursFauriel, etc.

Each spatial relation has a name that helps understanding its meaning. The table below informally explains the symbols:

Spatial relations

Symbol	Name	Note
DC	disconnected	the two regions are completely disconnected (there are no common pieces)
EC	externally connected	the boundaries of the regions touch, but their interiors are disjoint
PO	partially overlapping	the two regions partially overlap (there are disjoint sub parts, and some part of one is included in some part of the other
EQ	equal	two regions have the same spatial extent
TTP	tangential proper part	the first region is entirely inside the second region and their boundaries touch each other from the inside
TTPi	tangential proper part inverse	the first region entirely contains the second region and their boundaries touch each other from the inside
NTTP	non-tangential proper part	the first region is entirely inside the second region and their boundaries do not touch
NTTPi	non-tangential proper part inverse	the first region entirely contains the second region and their boundaries do not touch

Formulas

formulas of RCC₈

The set For_RCC8 of RCC₈ formulas is defined as follows: for all regions p₁, p₂ ∈ P, and all a spatial relation r ∈ R, p₁ r p₂.

Note that we use a light shading on formulas in order to clearly distinguish them from other syntactic constructs.

France TPPi AuvergneRhôneAlpes

EspaceFauriel NTPP SaintÉtienne

Semantics

Interpretations

Interpretations in RCC₈

An interpretation in RCC₈ is a pair (Δ, 𝓘) such that:

• Δ is a n-dimensional Euclidean space, for some natural number n > 1;
• 𝓘 : P ⟶ 2^Δ that maps regions to compact sets of Δ with a non-empty interior.

Note that the terms compact and interior are used in the sense of mathematical topology. In many applications, regions are understood as 2-dimensional areas that can be represented on a flat map (subsets of ℝ²), but the formalism can also be used for 3D objects. Higher dimensions can also be covered but are less practically useful.

Satisfaction relation

Before introducing the satisfaction relation, we need to introduce a few additional notations. Given an Euclidean space Δ and a compact set S ∈ Δ, we denote by In(S) the interior of S and by Bd(S) the boundary of S.

Satisfaction relation in RCC₈

For p₁, p₂ ∈ P, an interpretation (Δ, 𝓘) in RCC₈ satisfies:

• p₁ DC e₂ if and only if 𝓘(p₁) ⋂ 𝓘(p₂) = ∅;
• p₁ EC e₂ if and only if In(𝓘(p₁)) ⋂ In(𝓘(p₂)) = ∅ and Bd(𝓘(p₁)) ⋂ Bd(𝓘(p₂)) ≠ ∅;
• p₁ PO e₂ if and only if In(𝓘(p₁)) ⋂ In(𝓘(p₂)) ≠ ∅ and there exists x ∈ In(𝓘(p₁)) (respectively, x ∈ In(𝓘(p₂))) such that x ∉ In(𝓘(p₂)) (x ∉ In(𝓘(p₁)), respectively);
• p₁ EQ e₂ if and only if 𝓘(p₁) = 𝓘(p₂);
• p₁ TPP e₂ if and only if 𝓘(p₁) ⊊ 𝓘(p₂) and Bd(𝓘(p₁)) ⋂ Bd(𝓘(p₂)) ≠ ∅;
• p₁ TPPi e₂ if and only if 𝓘(p₂) ⊊ 𝓘(p₁) and Bd(𝓘(p₁)) ⋂ Bd(𝓘(p₂)) ≠ ∅;
• p₁ NTPP e₂ if and only if 𝓘(p₁) ⊊ 𝓘(p₂) and Bd(𝓘(p₁)) ⋂ Bd(𝓘(p₂)) = ∅;
• p₂ NTPPi e₁ if and only if 𝓘(p₁) ⊊ 𝓘(p₂) and Bd(𝓘(p₁)) ⋂ Bd(𝓘(p₂)) = ∅.

Table 2 presents a graphical view of the relations between regions, presented as discs on a 2-dimensional Euclidean space.

RCC₈ spatial relations depicted geometrically as relations between discs

Relation	Inverse relation	Graphical representation
X DC Y	Y DC X
X EC Y	Y EC X
X PO Y	Y PO X
X EQ Y	Y EQ X
X TPP Y	Y TPPi X
X NTPP Y	Y NTTPi X

Extensions to sets of relations

Instead of defining spatial relations as a single possible relation (strictly defining how the boundaries and interiors of the regions relate relative to the other), we can extend RCC₈ to express a set of alternative spatial relations between pairs of regions. We define the extension RCC⁺₈ = (Sym_RCC⁺8, For_RCC⁺8, Int_RCC⁺8, ⊨_RCC⁺8) as follows:

• Sym_RCC⁺8 = Sym_RCC8 ⋃ {‘{’, ‘}’, ‘,’};
• for p₁, p₂ ∈ P and a tuple (r₁, …, r_n) ∈ Rⁿ, p₁ {r₁, …, r_n} p₂ ∈ For_RCC⁺8;
• Int_RCC⁺8 = Int_RCC8;
• for 𝓘 ∈ Int_RCC⁺8 and φ = p₁ {r₁, …, r_n} p₂ ∈ For_RCC⁺8, 𝓘 ⊨_RCC⁺8 φ if and only if 𝓘 ⊨_RCC8 p₁ r_i p₂ for some i ∈ {1, …, n}.

Properties of RCC

TODO