ArticleslgStudy

mathematics

Region connection calculus

Region connection calculus is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Region connection calculus rather than just read about it. In short: The region connection calculus (RCC) is intended to serve for qualitative spatial representation and reasoning. RCC abstractly describes regions (in Euclidean space, or in a topological space) by their possible relations to each other.

Region connection calculus — main illustration
Region connection calculus — illustration

Key takeaways

  • Region connection calculus belongs to mathematics; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Region connection calculus to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Region connection calculus from memory before moving on to harder problems.

Reference excerpt

The region connection calculus (RCC) is intended to serve for qualitative spatial representation and reasoning. RCC abstractly describes regions (in Euclidean space, or in a topological space) by their possible relations to each other. RCC8 consists of 8 basic relations that are possible between two 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.

Axioms RCC is governed by two axioms.

for any region x, x connects with itself for any region x, y, if x connects with y, y connects with x

Remark on the axioms The two axioms describe two features of the connection relation, but not the characteristic feature of the connect relation. For example, we can say that an object is less than 10 meters away from itself and that if object A is less than 10 meters away from object B, object B will be less than 10 meters away from object A. So, the relation 'less-than-10-meters' also satisfies the above two axioms, but does not talk about the connection relation in the intended sense of RCC.

Composition table The composition table of RCC8 are as follows:

"*" denotes the universal relation, no relation can be discarded. Usage example: if a TPP b and b EC c, (row 4, column 2) of the table says that a DC c or a EC c.

Examples The RCC8 calculus is intended 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 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 (PO) property2, or is a tangential proper part of it. But, if the road is a tangential proper part of property2, then the road can only be externally connected (EC) to property1. That is, road PO property1 is not possible when road TPP property2. This fact is not obvious, but can be deduced once we examine the consistent "singleton-labelings" of the constraint network. The following paragraph briefly describes singleton-labelings. First, we note that the path-consistency algorithm will also reduce the possible properties between house2 and property1 from { DC, EC } to just DC. So, the path-consistency algorithm leaves multiple possible constraints on 5 of the edges in the constraint network. Since each of the multiple constraints involves 2 constraints, we can reduce the network to 32 (25) possible unique constraint networks, each containing only single labels on each edge ("singleton labelings"). However, of the 32 possible singleton labelings, only 9 are consistent. (See qualreas for details.) Only one of the consistent singleton labelings has the edge road TPP property2 and the same labeling includes road EC property1. 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).

RCC8 use in GeoSPARQL RCC8 has been partially implemented in GeoSPARQL as described below:

Implementations GQR is a reasoner for RCC-5, RCC-8, and RCC-23 (as well as other calculi for spatial and temporal reasoning) qualreas is a Python framework for qualitative reasoning over networks of relation algebras, such as RCC-8, Allen's interval algebra and more.

See also Spatial relation DE-9IM

References

Bibliography Randell, D.A.; Cui, Z; Cohn, A.G. (1992). "A spatial logic based on regions and connection". 3rd Int. Conf. on Knowledge Representation and Reasoning. Morgan Kaufmann. pp. 165–176. Anthony G. Cohn; Brandon Bennett; John Gooday; Micholas Mark Gotts (1997). "Qualitative Spatial Representation and Reasoning with the Region Connection Calculus". GeoInformatica. 1 (3): 275–316. Bibcode:1997GInfo...1..275C. doi:10.1023/A:1009712514511. S2CID 14841370.. Renz, J. (2002). Qualitative Spatial Reasoning with Topological Information. Lecture Notes in Computer Science. Vol. 2293. Springer Verlag. doi:10.1007/3-540-70736-0. ISBN 978-3-540-43346-0. S2CID 8236425. Dong, Tiansi (2008). "A Comment on RCC: From RCC to RCC⁺⁺". Journal of Philosophical Logic. 34 (2): 319–352. doi:10.1007/s10992-007-9074-y. JSTOR 41217909. S2CID 6243376..

Illustrations

Region connection calculus: The eight basic relations of the RCC8 calculus.
The eight basic relations of the RCC8 calculus.
Region connection calculus: A graphical representation of Region Connection Calculus (RCC: Randell, Cui and Cohn, 1992) and the links to the equivalent naming by the Open Geospatial Consortium (OGC) with their equivalent URIs.
A graphical representation of Region Connection Calculus (RCC: Randell, Cui and Cohn, 1992) and the links to the equivalent naming by the Open Geospatial Consortium (OGC) with their equivalent URIs.

Worked examples

Example 1 — a first encounter with Region connection calculus

Start with the simplest possible case. Write down what Region connection calculus claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Region connection calculus before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Region connection calculus ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Region connection calculus

In research
Region connection calculus appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Region connection calculus in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Region connection calculus is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computational topology, Constraint programming, Knowledge representation, so understanding it makes those chapters shorter.
In everyday life
Look for Region connection calculus outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Region connection calculus in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Region connection calculus means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Region connection calculus out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Region connection calculus in simple terms?

The region connection calculus (RCC) is intended to serve for qualitative spatial representation and reasoning. RCC abstractly describes regions (in Euclidean space, or in a topological space) by their possible relations to each other.

Why does Region connection calculus matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Region connection calculus?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Region connection calculus.

Tags

  • Computational topology
  • Constraint programming
  • Knowledge representation
  • Logical calculi
  • Reasoning

Keep exploring