RCC8

From QUAIL

Contents 1 Description of the Calculus 2 Example 3 Base Relations 4 Converse Table 5 Composition Table 6 Fact Sheet 7 Calculus description in files (optional) 8 Miscellaneous 9 References

Description of the Calculus

RCC8 is a model of Region Connection Calculus (RCC) which serves for qualitative spatial representation and reasoning. RCC abstractly describes regions (in Euclidian space, or in a topological space) by their possible relations to each other.

Example

The RCC8 calculus can be used for reasoning about spatial configurations. Consider the following example: two houses are connected via a road. Each house is located on an own property. The first house possibly touches the boundary of the property; the second one surely does not. What can we infer about the relation of the second property to the road?

The spatial configuration can be formalized in RCC8 as the following constraint network:

house1 DC house2
house1 {TPP, NTPP} property1
house1 {DC EC} property2
house1 EC road
house2 { DC, EC } property1
house2 NTPP property2
house2 EC road
property1 { DC, EC } property2
road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property1
road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property2

Using the RCC8 weak composition table and the path-consistency algorithm, we can refine the network in the following way:

road { PO, EC } property1
road { PO, TPP } property2

That is, the road either overlaps with the second property, or is even (tangential) part of it.

Other versions of the region connection calculus include RCC5 (with only five basic relations - the distinction whether two regions touch each other are ignored) and RCC23 (which allows reasoning about convexity)..

Base Relations

RCC8 consists of 8 basic relations that are possible between to regions:

• disconnected (DC)
• externally connected (EC)
• equal (EQ)
• partially overlapping (PO)
• tangential proper part (TPP)
• tangential proper part inverse (TPPi)
• non-tangential proper part (NTPP)
• non-tangential proper part inverse (NTPPi)

From these basic relations, combinations can be built. For example, proper part (PP) is the union of TPP and NTPP.

Converse Table

Relation	Converse Relation
DC	DC
EC	EC
PO	PO
TPP	TPPi
NTPP	NTPPi
TPPi	TPP
NTPPi	NTPP
EQ	EQ

Composition Table

RCC8 has Weak Composition. The weak composition table of RCC8 is as follows:

o	DC	EC	PO	TPP	NTPP	TPPi	NTPPi	EQ
DC	*	DC,EC,PO,TPP,NTPP	DC,EC,PO,TPP,NTPP	DC,EC,PO,TPP,NTPP	DC,EC,PO,TPP,NTPP	DC	DC	DC
EC	DC,EC,PO,TPPI,NTPPI	DC,EC,PO,TPP,TPPi,EQ	DC,EC,PO,TPP,NTPP	PO,TPP,NTPP	PO,TPP,NTPP	DC,EC	DC	EC
PO	DC,EC,PO,TPPi,NTPPi	DC,EC,PO,TPPi,NTPPi	*	PO,TPP,NTPP	PO,TPP,NTPP	DC,EC,PO,TPPi,NTPPi	DC,EC,PO,TPPi,NTPPi	PO
TPP	DC	DC,EC	DC,EC,PO,TPP,NTPP	TPP,NTPP	NTPP	DC,EC,PO,TPP,TPPi,EQ	DC,EC,PO,TPPi,NTPPi	TPP
NTPP	DC	DC	DC,EC,PO,TPP,NTPP	NTPP	NTPP	DC,EC,PO,TPP,NTPP	*	NTPP
TPPi	DC,EC,PO,TPPi,NTPPi	EC,PO,TPPi,NTPPi	PO,TPPi,NTPPi	PO,TPP,TPPi,EQ	PO,TPP,NTPP	TPPi,NTPPi	NTPPi	TPPi
NTPPi	DC,EC,PO,TPPi,NTPPi	PO,TPPi,NTPPi	PO,TPPi,NTPPi	PO,TPPi,NTPPi	PO,TPP,NTPP,TPPi,NTPPi,EQ	NTPPi	NTPPi	NTPPi
EQ	DC	EC	PO	TPP	NTPP	TPPi	NTPPi	EQ

• "*" denotes the universal relation.

Fact Sheet

• Name: RCC8
• Arity of base relations: binary
• Number of base relations: 8
• Arity of composition: binary
• Domain(s): 2-d open regions
• Permutations of base relations are base relations: yes
• Composition table has been verified with a theorem prover: yes
• Calculus is:
  • Relation Algebra: yes
  • semi associative Algebra: yes
  • weakly associative Algebra: yes
  • Non-associative Algebra: yes
• Complexity of determining consistency for:
  • Arbitrary networks:
  • Atomic networks:
• Algebraic closure decides consistency in atomic networks: yes
• Strong composition / Extensional: no
• Tractable subsets:

Calculus description in files (optional)

e.g. GQR or SparQ format. (To be added)

Miscellaneous

Other things...

References

• Randell, D. A., Cui, Z. and Cohn, A. G.: A spatial logic based on regions and connection, Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, pp. 165–176, 1992.
• Anthony G. Cohn, Brandon Bennett, John Gooday, Micholas Mark Gotts: Qualitative Spatial Representation and Reasoning with the Region Connection Calculus. GeoInformatica, 1, 275–316, 1997.
• J. Renz: Qualitative Spatial Reasoning with Topological Information. Lecture Notes in Computer Science 2293, Springer Verlag, 2002.