Region Connection Calculus

Origin. Randell, Cui, Cohn (1992). Qualitative spatial reasoning. Mereotopology. RCC-8. Foundation of spatial AI.

Models. Spatial regions. Connection relation. Eight topological relations. Constraint networks. Qualitative space.

Formalism.

Primitive: C(x, y): x connects with y. Reflexive: C(x, x). Symmetric: C(x, y) → C(y, x). Regions share point or boundary.

Defined relations: DC(x,y): ¬C(x,y). Disconnected. P(x,y): ∀z[C(z,x) → C(z,y)]. Part of. PP(x,y): P(x,y) ∧ ¬P(y,x). Proper part. EQ(x,y): P(x,y) ∧ P(y,x). Equal. O(x,y): ∃z[P(z,x) ∧ P(z,y)]. Overlap. DR(x,y): ¬O(x,y). Discrete.

RCC-8 relations: DC: disconnected. EC: externally connected (touch). PO: partial overlap. EQ: equal. TPP: tangential proper part. NTPP: non-tangential proper part. TPPi: tangential proper part inverse. NTPPi: non-tangential proper part inverse.

JEPD: Eight relations jointly exhaustive. Pairwise disjoint. Exactly one holds for any pair.

Composition table: 8 × 8 entries. Each entry: disjunction of possible results. Constraint propagation.

Conceptual neighborhoods: Adjacent relations in space of possibilities. Continuous motion. Transition graph.

Modal interpretation: Spatial modality. Interior, closure operators. S4 connection.

Symbols.

Symbol	Unicode	Meaning
C	—	connection
DC, EC, PO, ...	—	RCC-8 relations
P	—	part-of
TPP, NTPP	—	proper part relations

Metatheory. Mereotopology. Relation algebra. Composition. Conceptual neighborhoods.

Applies to. GIS. Spatial reasoning. Robotics. Qualitative physics.

Limitations. Topological only. No metric. Tractability issues. 2D focus traditionally.