From Three-Dimensional Topological Relations to
Contact Relations

Yohei Kurata
SFB/TR8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany

Abstract
Topological relations, which concern how two objects intersect, are one of
the most fundamental and well-studied spatial relations. However, in reality, two physical objects can take only disjoint relation if they are solid.
Thus, we propose an alternative of topological relations, called contact relations, which capture how two objects contact each other. Following theframework of the 9-intersection, this model distinguishes contact relations
based on the presence or absence of contacts between several surface elements of two objects. Consequently, the contact relations have a strong
correspondence to the 9-intersection-based topological relations. Making
use of this correspondence, we derive the contact relations between various
combinations of objects in a 3D Euclidean space (ℝଷ ). For this purpose,
we first review and analyze the topological relations in ℝଷ . Then, these topological relations are mapped to contact relations.

1 Introduction
Qualitative spatial relations are fundamentals for characterizing spatial arrangements of objects in a space, usually following how people conceptualize them. Spatial database communities have studied several types ofqualitative spatial relations, among which topological relations have attracted much attention due to its importance in human spatial cognition(Shariff, et al. 1998). Egenhofer (1989), for instance, distinguished eight2

Yohei Kurata

types of topological relations between two regions in a 2D Euclidean spaceℝଶ , called disjoint, meet, overlap, covers, coveredBy, contains, inside, andequal relations. The same set of eight relations holds between two bodies
in ℝଷ (Zlatanova 2000). Similarly, Randell et al. (1992) distinguishedeight types of topological relations without regard to the dimension of theunderlying space. Such topological relations, however, fail when they areapplied to physical objects—simply because they are usually solid and, accordingly, they do not intersect/connect with each other (note that the connection of two objects in Randell et al.’s sense is established by the presence of a common point, thereby different from the notion of contact).
Although the solid objects are always topologically disjoint (disconnected) in theory, people often care about whether they are totally separated or having a contact and, if they have a contact, in what way. For instance, we use the expressions like the bottom of A meets the top of B (orsimply A is on B, although this expression has more broad meanings (Feist
2000)) or A stands on the edge/corner of B (Billen and Kurata 2008).
These expressions concern which part of one object contacts which part ofanother object. Such information is critical when we characterize the spatial arrangement of two contacting objects. We, therefore, propose a newmodel of qualitative spatial relations that captures how two objects contact
each other, called contact relations.
Contact may occur only between the surfaces of two objects. In a 3D
space, for each region, we can distinguish its front and back sides. Similarly, we can distinguish several sides of bodies considering their shapes(cubes, pyramids, etc.). Thus, the model of contact relations should be able
to record the presence or absence of contacts between several surface elements of two objects in different granularities. Our model, therefore, follows the frameworks of the 9-intersection (Egenhofer and Herring 1991)
and the 9+-intersection (Kurata and Egenhofer 2007), which distinguishtopological relations based on the presence or absence of intersections between the topological parts of two objects. Naturally, contact relations in
our model have a strong correspondence with 9-intersection-based topological relations. Indeed, making use of this correspondence, we derive
contact relations between various combinations of objects (Section 5).
The remainder of this paper is organized as follows: Section 2 summarizes the concepts of the 9- and 9+-intersection. Based on these models,Section 3 develops a model of contact relations. Section 4 reviews topological relations in ℝଷ and discusses the property of these relations for later discussions. Section 5 derives six sets of contact relations in ℝଷ fromthe corresponding sets of topological relations discussed in Section 4. Finally, Section 6 concludes with a discussion of future problems.

From Three-Dimensional Topological Relations to Contact Relations

3

In this paper, solid objects refer to the objects that do not intersect. We
can consider that any sort of objects (points, lines, regions, and bodies)
may be solid or non-solid objects. Our target is limited to solid objects. In
addition, to simplify, we consider only simple objects (Schneider and Behr
2006). Simple objects consist of a single connected component. Simple
lines are non-branching lines without loops, and simple regions/bodies are
regions/bodies without holes, spikes, cuts, and disconnected interior.

2 The 9-Intrersection and The 9+-Intersection
Our model of contact relations follows the 9-intersection (Egenhofer andHerring 1991) and its refinement called the 9+-intersection (Kurata andEgenhofer 2007). Based on point-set topology (Alexandroff 1961), these
two models distinguish the interior, boundary, and exterior each object.
The interior of an object X, denoted ܺ°, is the union of all open sets contained in X, X’s boundary ߲ܺ is the difference between X’s closure (the intersection of all closed point sets that contain X) and ܺ°, and X’s exteriorܺ ି is the complement of X’s closure. By definition, the boundary of a linerefers to the set of its two endpoints, and a point does not have an interior.
In the 9-intersection, topological relations are characterized by the properties of the 3×3 intersections between the topological parts (interior, boundary, and exterior) of two objects. These 3×3 intersections are concisely
represented in the 9-intersection matrix in Eq. 1. In the most basic approach, topological relations are distinguished by the presence or absenceof these 3×3 intersections. Accordingly, topological relations are characterized by the pattern of bitmap-like icons (Mark and Egenhofer 1994),
whose 3×3 cells indicate the emptiness/non-emptiness of the 3×3 elementsin the 9-intersection matrix (Fig. 1).
‫ܣ‬° ∩ ‫ܤ‬° ‫ܣ‬° ∩ ߲‫ܤ‬Mሺ‫ܣ‬, ‫ܤ‬ሻ = ൭߲‫ܤ ∩ ܣ‬° ߲‫ܤ߲ ∩ ܣ‬‫ܤ ∩ ିܣ‬° ‫ܤ߲ ∩ ିܣ‬

BA∅Mሺ‫ܣ‬, ‫ܤ‬ሻ = ൭ ∅¬∅‫ܣ‬° ∩ ‫ିܤ‬߲‫ ିܤ ∩ ܣ‬൱‫ିܤ ∩ ିܣ‬

∅
¬∅
¬∅

¬∅
¬∅൱
¬∅

(1)



Fig. 1. Representations of a topological relation by the 9-intersection matrix/icon

The 9+-intersection extends the 9-intersection by considering the subdivision of topological parts. For instance, the boundary of a line can be sub-

4

Yohei Kurata

divided into two endpoints. To support such subdivision, the nested version of the 9-intersection matrix shown in Eq. 2, called the 9+-intersection
matrix, is used, where ‫ܣ‬°೔ , ∂௜ A, and ‫ିܣ‬೔ are the ith subpart of A’s interior,boundary, and exterior, while ‫ܤ‬°ೕ , ∂௝ B, and ‫ିܤ‬ೕ are the jth subpart of B’s
interior, boundary, and exterior, respectively. Just like the 9-intersection,
topological relations are distinguished by the presence or absence of all intersections listed in the 9+-intersection matrix. For instance, Fig. 2 shows
the 9+-intersection matrix and its iconic representation of a topological relation between a (directed) line and a region. To simplify, the bracket ofeach matrix element is omitted if it consists of a single sub-element.
ൣ‫ܣ‬°೔ ∩ ‫ ܤ‬°ೕ ൧

M ା ሺ‫ܣ‬, ‫ܤ‬ሻ = ൮ൣ∂௜ A ∩ ‫ ܤ‬°ೕ ൧
ൣ‫ܣ‬

B
A

ି೔

∩‫ ܤ‬൧
°ೕൣ‫ܣ‬°೔ ∩ ∂௝ B൧

ൣ∂௜ A ∩ ∂௝ B൧
ൣ‫ܣ‬

ି೔

∩ ∂௝ B൧M ା ሺ‫ܣ‬, ‫ܤ‬ሻ‫ܣ‬° ∩ ‫ܤ‬°‫ܣ‬° ∩ ߲‫ܤ‬߲ଵ ‫ܤ ∩ ܣ‬°߲ଵ ‫ܤ߲ ∩ ܣ‬
= ൮൤
൨ ൤
൨
߲ଶ ‫ܤ ∩ ܣ‬°߲ଶ ‫ܤ߲ ∩ ܣ‬ିି‫ܤ ∩ ܣ‬°‫ܤ߲ ∩ ܣ‬¬∅ ¬∅ ¬∅∅∅¬∅= ൮ቂ ቃ ቂ ቃ ቂ ቃ൲¬∅∅∅¬∅ ¬∅ ¬∅

ሾ‫ܣ‬°೔ ∩ ‫ି ܤ‬ೕ ሿሾ∂௜ A ∩ ‫ି ܤ‬ೕ ሿ൲ሾ‫ିܣ‬೔∩‫ ܤ‬ሿ

(2)ିೕ‫ܣ‬° ∩ ‫ି ܤ‬߲ ‫ିܤ ∩ ܣ‬൤ ଵ൨൲߲ଶ ‫ି ܤ ∩ ܣ‬ିି‫ܤ∩ ܣ‬



Fig. 2. Representations of a topological relation by the 9+-intersection matrix/icon

3 Modeling Contact Relations
Contact relations between two objects are distinguished basically based on
the presence or absence of contacts between their surface elements. Surface elements of an object are the parts of the object that is connected directly to the object’s exterior. For regions in ℝଷ , we can naturally distinguish three surface elements; the front side, the back side, and the edge.
The front and back sides correspond to the region’s topological interior,
while the edge corresponds to the region’s topological boundary. For bodies, we may distinguish different numbers of surface elements; for instance, we can distinguish six sides of a cubic body. To simplify, however,this paper does not distinguish the sides of bodies and considers that the
body has only one surface element, which corresponds to the body’s topological boundary. For lines, we consider that they have two surface ele-

From Three-Dimensional Topological Relations to Contact Relations

5

ments, a set of two endpoints and an intermediate segment, which correspond to the line’s topological boundary and interior, respectively.
In this way, surface elements of objects are distinguished in association
with the topological part of the objects. Making use of this association, we
use a 9+-intersection-like matrix, called the 9+-contact matrix (Eq. 3), forrepresenting contact relations. In this matrix, each Boolean functioncሺܺ, ܻሻ indicates whether X contacts Y or not. X and Y may refer to a surface element of an object, which we define as a subpart of the object’s interior or boundary. X and Y may also refer to the exterior of an object. By
recording the presence or absence of contact between A’s surface elements(say X) and B’s exterior ‫ ିܤ‬, we can tell from the matrix whether X contacts the surface of another object entirely, partly, or not at all—for instance, if X contacts only one of B’s surface element Y and not ‫ ିܤ‬, X entirely contacts Y. The most right-bottom element in the 9+-contact matrix isfixed, as it does not contribute to the distinction of contact relations. This
does not necessarily mean that we should interpret that the exteriors of two
objects contact each other.
ൣc൫‫ܣ‬°೔ , ‫ ܤ‬°ೕ ൯൧

C ା ሺ‫ܣ‬, ‫ܤ‬ሻ = ൮ൣc൫∂௜ ‫ܣ‬, ‫ ܤ‬°ೕ ൯൧ൣc൫‫ ܣ‬, ‫ ܤ‬൯൧ି°ೕሾcሺ‫ܣ‬°೔ , ‫ ି ܤ‬ሻሿൣc൫‫ܣ‬°೔ , ∂௝ B൯൧ሾcሺ∂௜ ‫ܣ‬, ‫ ି ܤ‬ሻሿ൲ൣc൫∂௜ ‫ܣ‬, ∂௝ B൯൧
ൣc൫‫ ܣ‬, ∂௝ B൯൧‫݁ݑݎݐ‬

ି(3)

Since all elements in the 9+-contact matrix are two-valued (true or
false), the patterns of the 9+-contact matrix are represented by bitmap-like
icons (Fig. 3) in which each black/white cell indicates the true/false valueof the corresponding element in the 9+-contact matrix. In the example ofFig. 3 the icon’s first column and first row are partitioned, since they correspond to the front and back sides of the regions.

AB

C ା ሺ‫ܣ‬, ‫ܤ‬ሻ =݂݈ܽ‫݁ݏ݈݂ܽ ݁ݏ‬൤൨݂݈ܽ‫݁ݏ݈݂ܽ ݁ݏ‬൮ሾ‫݁ݏ݈݂ܽ ݁ݑݎݐ‬ሿሾ‫݁ݑݎݐ ݁ݑݎݐ‬ሿ൤݂݈ܽ‫݁ݏ‬൨݂݈ܽ‫݁ݏ‬݂݈ܽ‫݁ݏ‬‫݁ݑݎݐ‬

ቂ‫݁ݑݎݐ‬
ቃ‫݁ݑݎݐ‬
൲‫݁ݑݎݐ‬‫݁ݑݎݐ‬Ao1



B o1 B o 2 ∂B

B−

Ao 2

∂A
A−

Fig. 3. Representations of a contact relation by the 9+-contact matrix/icon

An attention should be paid to the definition of the contact between theboundary (edge) of a region and the exterior of another object. We say thatthe boundary of a region A contacts the exterior of an object B if and only
if A’s boundary has an interval that does not contact B’s surface. Accordingly, in Fig. 4, we consider that A’s edge does not contact B’s exterior.

6

Yohei Kurata

A o1

A

A

B o1 Bo 2 ∂B

B−

o2

∂A

B

A−

Fig. 4. An example case where we consider that a region’s boundary does not contact a body’s exterior

Dimensional model by Billen et al. (2002) also considers the distinctionof surface elements (corner points, edges, and faces) for distinguishing dimensional relations, which are essentially a refinement of topological relations. Later Billen and Kurata (2008) reformulated the dimensional modelusing the framework of the 9+-intersection, giving a new name projective
9+-intersection. Our model is structurally similar to this projective 9+intersection, although our model targets the contacts while the projective
9+-intersection deals with the intersections. In addition, the front and backsides of regions are not distinguished in the projective 9+-intersection.

4 Three-Dimensional Topological Relations

This section reviews and analyzes topological relations in ℝଷ , which arelater used for deriving contact relations. The topological relations in ℝଷ
were studied by Zlatanova (2000). Later, Kurata (2008) systematically reidentified the sets of topological relations between various combinations ofobjects in ℝଵ , ℝଶ , and ℝଷ , making use of the universal constraints on the
9+-intersection. Table 1 shows the numbers of the identified relations.
Among these relation sets, this paper uses point-body relations (Fig. 5),
line-region relations (Fig. 6), line-body relations (Fig. 7), region-region relations (Fig. 8), region-body relations (Fig. 7), and body-body relations(Fig. 9), each of which contains the relations that hold only in ℝଷ .

Table 1. Numbers of topological relations between points, simple lines, simple regions, and simple bodies in ℝଵ , ℝଶ , and ℝଷ , distinguished by the emptiness/nonemptiness patterns of the 9-intersection (Kurata 2008)

Point-Point
Point-Line
Point-Region
Point-Body
Line-Line

ℝଵ
2
3
–
–
8

ℝଶ
2
3
3
–
33

ℝଷ
2
3
3
3
33

Line-Region
Line-Body
Region-Region
Region-Body
Body-Body

ℝଵ
–
–
–
–
–

ℝଶ
19
–
8
–
–

ℝଷ
31
19
44
19
8

From Three-Dimensional Topological Relations to Contact Relations

7

4.1 Correspondence between Topological Relation Sets
Comparison of the relation sets in Figs. 5-9 reveals several correspondences between the relation sets. The most remarkable correspondence isthat between the 19 line-body relations and the 19 region-body relations,which are represented by almost the same sets of icons (Fig. 7). The 19
line-body relations also correspond to the 19 of the 31 line-region relationsin Figs. 6a-s. Note that these 19 line-region relations are the relations that
may hold also in ℝଶ . Considering that both the boundary of a body andthat of a region forms a Jordan curve in ℝଷ and ℝଶ , respectively, the correspondence between the line-body relations in ℝଷ and the line-region relations in ℝଶ is reasonable. For the same reason, the 8 body-body relations(Fig. 9) correspond to the 8 of the 43 region-region relations in Figs. 8af1/2, which may hold also in ℝଶ .

Fig. 5. 3 topological point-body relations in ℝଷ
(A)

(B)

(C)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

(s)

(A)

(B)

(C)

(D)

(E)

Fig. 6. 31 topological line-region relations in ℝ

(K)

(L)

(F)

(G)

(H)

(I)

(J)

ଷ

8

Yohei Kurata

(A)

(B)

(C)

(D)

(E)

(H)

(I)

(J)

Fig. 7. 19 topological line-body and region-body relations in ℝ

(R)

(S)

(L)

(M)

(a)

(b)

(c)

(d)

(e1)

(e2)

(f1)

(f2)

(A)

(B)

(C)

(D)

(E)

(F)

(G)

(H)

(I)

(J)

(K)

(L1)

(L2)

(M1)

(M2)

(N1)

(N2)

(O1)

(O2)

(P1)

(P2)

(Q1)

(Q2)

(R1)

(R2)

Fig. 8. 43 topological region-region relations in ℝ

(V2)

(W1)

(W2)

(S2)

(T1)

(T2)

(O)

(G)

(K)

(S1)

(N)

(F)

(U1)

(P)

(U2)

(V1)
ଷ

(Q)
ଷ

From Three-Dimensional Topological Relations to Contact Relations

Fig. 9. 8 topological body-body relations in ℝ
(A)

(B)

(C)

(D)

(E1)
ଷ

(E2)

(F1)

9

(F2)

4.2 Topological Relations That Hold between Convex Objects
For each topological relation set, we identify the relations that hold evenwhen the objects are limited to convex ones. For instance, the line-region
relations in Figs. 8a-f1/2 hold between two convex regions, while the relation in Fig. 8A does not. The reason why we pay attention to such relations
between convex objects, since convex objects are prototypical—convex
lines are straight and convex regions are flat—and also many physical objects in the real world are convex.
The topological relations that cannot hold between two convex objects(say, A and B) are filtered out by the following constraints:• if A’s boundary intersects with B’s interior only or with B’s interior andboundary, but not B’s exterior, then A’s interior intersects with B’s interior only (and vice versa);• if A’s boundary intersects with B’s boundary only, then A’s interior intersects with B’s interior only or B’s boundary only (and vice versa);• A’s interior and B’s interior intersect if and only if A’s boundary intersects with B’s closure or B’s boundary intersects with A’s closure.
By sketching an instance manually it is confirmed that the remaining topological relations hold between two convex objects. In this way, we identified the following topological relations that hold even when the objects arelimited to convex ones:• all point-body relation (Figs. 5A-C);• 13 line-region relations in Figs. 6a-c,f,j,l-p,s,C,I;• 11 line-body relations in Figs. 7A-C,F,J,L-P,S;• 11 region-body relations in Figs. 7A-C,F,J,L-P,S;• 18 region-region relations in Figs. 8a-f1/2,,B,L1/2-O1/2; and• all body-body relations (Figs. 9A-F1/2).
4.3 Topological Relations with Piercing
We say that an object A pierces an object B when A’s interior intersects
continuously with B’s interior and its neighboring exterior on two different

10

Yohei Kurata

sides. In our framework, the pierced object B is limited to a region, since
the sides are defined only for regions (Section 3). We pay attention to suchpiercing because topological relations that require piercing cannot bemapped to contact relations (Sections 5.3-5.4). Piercing are found in thesample configurations of the relations in Fig. 6C, Figs. 7C-F,I,K,L,O-S,
and Figs. 8B,E,N1/2-O1/2. This does not mean that these relations requirepiecing. In fact, Fig. 10 shows that the line-region relation in Fig. 6C andthe region-region relations in Figs. 8B,E,N1/2-O1/2 do not require piercing(when two objects are limited to convex ones, however, these topologicalrelations require piercing). On the other hand, the region-body relations in
Figs. 7C-F,I,K,L,O-S always require piercing, because whenever the
body’s interior intersects with the region’s interior, the body’s interior alsointersects continuously with the region’s neighboring exterior on bothsides.

(6C)

(8B)

(8E)

(8N1)

(8N2)

(8O1)

(8O2)

Fig. 10. Alternative configurations of the line-region relation in Fig. 6C and theregion-region relations in Figs. 8B,E,O1/2-M1/2, which do not have piercing.

4.4 Topological Relations with Enclosed Spaces
In Figs. 8F-K,P1/2-W1/2, we can find a space (or spaces) enclosed by two
regions. Actually, any configuration of the region-region relations in
Figs. 8F-K,P1/2-W1/2 have enclosed space(s), because the closure of one region contains the boundary of another region, but not its interior. Similarly, any configuration of the region-body relations in Figs. 7D,G,H,Q haveenclosed space(s). The presence of such enclosed space imposes some restrictions on the corresponding contact relations (Section 5.4).

5 Deriving Contact Relations
Contact relations have a strong correspondence with topological relations,as we can imagine from the structural similarity between the 9+-contact
matrix and the 9-/9+-intersection matrix. Normally, contact relations can bederived from topological relations simply by replacing intersections with

From Three-Dimensional Topological Relations to Contact
Relations11

contacts (Figs. 11a-b). As for topological relations between a region and an
object X, each topological relation is potentially mapped to multiple contact relations, since the intersection between the region’s interior and X’sinterior/boundary is mapped to contacts between either or both faces of theregion and X’s interior/boundary (Fig. 11b). On the other hand, there aresome topological relations that cannot be mapped to contact relations ,such as those with piercing (Fig. 11c). In the following subsections, we derive the sets of contact relations between various combinations of objects
based on the mapping from the corresponding sets of topological relations.

(a)

(b)

(c)

Fig. 11. Sample mappings from topological relations to contact relations

5.1 Point-Body, Line-Body, and Body-Body Relations
The topological point-body relations in Fig. 5A,B are mapped to one contact relation, respectively, while the relation in Fig. 5C cannot be mapped
to contact relations because the point is inside the body. Consequently, twocontact relations between a point and a body in ℝଷ , represented by the 9+contact icons, are derived. In a similar way, seven contact relations

between a line and body in ℝଷ ,, are derived
from the topological line-body relations in Figs. 7A,B,G,H,J,M,N, and two
contact relations between two bodies in ℝଷ ,, are derived from the
topological body-body relations in Figs. 9A,B.
Among these contact relations, which hold when the objects are limited
to convex ones? Section 4.2 found that the topological point-body relationsin Fig. A,B, the topological line-body relations in Figs. 7A,B,J,M,N, andthe topological body-body relations in Figs. 9A,B hold in convex cases.
Naturally, the contact relations derived from these topological relations are
the relations that hold in convex cases; i.e.,• two contact relations,, hold between a point and a convex body;• five contact relations,, hold between a convex line
and convex body; and• two contact relations,, hold between two convex bodies.

12

Yohei Kurata

5.2 Region-Body Relations

Contact relations between a region and a body in ℝଷ are derived from the
19 topological region-body relations in Fig. 7. The relations in
Figs. 7A,G,M are mapped to one contact relation, respectively. Accordingly, 3×1 contact relations,, are derived from them. The relationsin Figs. 7B,H,J,N are mapped to three contact relations, respectively, because the body’s boundary contacts the region’s either or both sides. Thus,
4×3 contact relations,, arederived from them. Finally, the remaining relations, where the body’s interior intersects with the region’s closure, cannot be mapped to contact relations. In this way, in total 3×1+4×3 = 15 contact relations between a region
and a body in ℝଷ are derived.
Among these 15 contact relations, the relations that hold in convex cases
are limited to those derived from the topological region-body relations that
hold in convex cases—i.e., the relations in Figs. 7A,B,J,M,N (Section 4.2).
At this time the relations in Figs. 7B,J,N are mapped to not three, but two
contact relations, respectively, because the boundary of a convex bodymay contact either side of a convex region, but not both sides. Consequently, 2×1+3×2 = 8 contact relations,
between a convex region and a convex body in ℝଷ .

, hold

5.3 Line-Region Relations
The mapping from topological line-region relations to contact relations is a
bit complicated, because the line’s interior and boundary may contact theregion’s either or both sides, in some cases not independently. To simplify,
we start from the relations between a convex line and a convex region.
Section 4.2 found that there are 13 topological line-region relations that
hold in convex cases (Figs. 6a-c,f,j,l-p,s,C,I). Among these relations,• the five relations in Figs. 6a,b,j,m,n, where the region’s interior does notintersect with the line’s interior or boundary, are mapped to one contact
relation, respectively (and thus 5×1 contact relations
are derived);• the seven relations in Figs. 6c,f,l,o,p,s,I, where the region’s interior intersects with the line’s interior/boundary, are mapped to two contact relations in which the line’s interior/boundary contacts either side of theregion (and thus 7×2 contact relations
are derived); andFrom Three-Dimensional Topological Relations to Contact
Relations13• the relation in Fig. 6C cannot be mapped to a contact relation because it
requires piercing.
In this way, 5×1+7×2 = 19 contact relations between a convex line and aconvex body in ℝଷ are derived.
If the line and the body are not limited to convex ones, contact relations
are derived as follows:• the seven topological relations in Figs. 6a,b,g,h,j,m,n, where the region’s interior does not intersect with the line’s interior or boundary, aremapped to one contact relation (e.g.,), respectively;• the seven topological relations in Figs. 6c,i,k,o,B,C,H, where the region’s interior intersects with a part of the line’s interior and not theline’s boundary, are mapped to three contact relations (e.g.,)
in which the line’s interior contacts the region’s either or both sides, respectively;• the two topological relations in Figs. 6D,E, where the region’s interior
intersects with both of the line’s endpoints and not the line’s interior, aremapped to three contact relations (e.g.,) in which the line’s
two endpoints contact the region’s either or both sides, respectively;• the four topological relations in Figs. 6I-L, where the region’s interior
intersects with one of the line’s endpoints and not the line’s interior, aremapped to two contact relations (e.g.,) in which the line’s one
endpoint contacts the region’s either side, respectively;• the three topological relations in Figs. 6f,l,s, where the region’s interior
contains the line’s interior, are mapped to two contact relations (e.g.,) in which the line’s interior contacts either side of the region andthe line’s endpoint(s) follows it, respectively;• the two topological relations in Figs. 6d,A, where the region’s interior
intersects with both of the line’s endpoints and a part of the line’s interior, are mapped to 3×3 contact relations (e.g.,) in which the line’s interior and boundary contact either or bothsides of the region independently, respectively;• the four topological relations in Figs. 6p,q,F,G, where the region’s interior intersects with one of the line’s endpoints and a part of the line’s interior, are mapped to 3×2 contact relations (e.g.,)
in which the line’s interior contacts either or both sides of the region andthe line’s one endpoint contacts either side of the region independently,
respectively;

14

Yohei Kurata• the topological relation in Fig. 6e is mapped to five contact relations() where the line’s interior contact either or both sidesof the region and the line’s endpoints follow it; and• similarly, the topological relation in Fig. 6r is mapped to four contact relations ().
In this way, in total 7×1+7×3+4×3+2×2+3×2+2×9+4×6+5+4 = 99 contact
relations between a line and a region in ℝଷ are derived
5.4 Region-Region Relations
The mapping from topological region-region relations to contact relations
is more complicated than the previous case, because two sides and edge of
one region may contact either or both sides of another region, in many cases not independently. The dependency occurs in the mapping from the topological relations in Figs. 8F-K,P1/2-W1/2 and those in Figs. 8d-f1/2. In theformer relations, the configurations always have enclosed space(s) (Section 4.4). Consequently, the side of one object that entirely faces the enclosed space cannot contact the side of another object that does not facethe enclosed space. In the latter relations, one region X is contained byanother region Y. Consequently, in their corresponding contact relations, if
X’s either or both sides entirely contacts Y’s α-side, then X’s boundary also
contacts Y’s α-side. Considering these constraints, we derived 1051 contact
relations between two regions in ℝଷ from the 43 topological region-region
relations in ℝଷ (See Appendix for the detail).
When two regions are limited to convex ones, the mapping becomesmuch simpler. Section 4.2 found 18 topological region-region relations
that hold between two convex regions in ℝଷ (Figs. 8a-f1/2, B, E, and L1/2O1/2). These relations are mapped to contact relations as follows:• The two relations in Figs. 8a,b, which have no interior-related intersection, are mapped to one contact relation (e.g.,), respectively;• The six relations in Figs. 8c-f1/2, which have an interior-interior intersection, are mapped to 2×2 contact relations (e.g.,) in which
either side of one region contacts either side of another region, respectively;• The four relations in Figs. 8L1/2-M1/2, which have a boundary-interior intersection but no interior-interior intersection, are mapped to two contact
relation (e.g.,) in which the boundary of one region contacts either side of another region, respectively;

From Three-Dimensional Topological Relations to Contact
Relations15• The six relations in Figs. 8B, E, and N1/2-O1/2 cannot be mapped to contact relation because they require piercing (Section 4.3).
Consequently, in total 2×1+6×4+4×2 = 34 contact relations between two
convex regions in ℝଷ are derived. These 34 contact relations are illustrated
schematically in Fig. 12. This figure is actually a conceptual neighborhood
graph (Freksa 1992) of the 34 contact relations, whose links show pairs ofsimilar relations (in the sense that the configuration of one relation may
switch to another relation by a minimal change). We can see nice horizontal and vertical symmetries in this graph, which result from the fact thateach region has two sides.
back

back

back

back

back

back
↓

back
↓
back

back

back

back

Fig. 12. A conceptual neighborhood graph of the 34 contact relations between two
convex regions in ℝଷ

6 Conclusions and Future Work
This paper proposed a model of contact relations. The contact relations
work as an alternative of topological relations when the target objects are

16

Yohei Kurata

solid. Due to the models’ schematic similarity, contact relations have astrong correspondence with topological relations distinguished by the 9intersection. Making use this correspondence, the sets of contact relations
between various combinations of objects in ℝଷ are derived from the corresponding sets of topological relations. The numbers of the derived relations (2 for point-body relations, 7 for line-body relations, 2 for body-bodyrelations 15 for region-body relations, and 99 for line-region relations) areprobably cognitively and practically acceptable, but unfortunately that forregion-region relations (1051) is overwhelming. In general, if the objects
are limited to convex ones, the numbers of the contact relations becomemuch smaller (2 for point-body relations, 5 for line-body relations, 2 forbody-body relations, 8 for region-body relations, 19 for line-region relations, and 34 region-region relations). One remaining issue is to analyze
the completeness of the derived relations (i.e., to check the absence of additional relations).
This paper assumed that each body has only one surface element, but it
is often possible to distinguish multiple surface elements of the body considering its shape (a cube, a pyramid, etc.). The 9+-contact matrix allows
the distinction of surface elements in arbitrary granularity, thanks to its
nested structure. Of course, it is expected that the distinction of more surface elements yields rapid increase of the number of contact relations, but
the model itself is useful for describing how objects contact.
One interesting future topic is spatial reasoning based on contact relations. It is expected that the composition rules of contact relations are considerably different from those of topological relations. For instance, thecomposition rule of topological relations “if X includes whole Y and Y includes whole Z, then X includes whole Z” (Egenhofer 1994) cannot betransformed to the composition rule of contact relations, because if X contacts whole Y, then Y cannot contact Z.
Another interesting future topic is to identify and analyze contact relations in ℝଶ . In a 2D space we can distinguish left and right sides of lines.
2D contact relations can be used for characterizing the spatial arrangements of two streets and, accordingly, reasoning techniques on such 2D
contact relations will be useful for mobile robots to develop the knowledgeof street networks efficiently without exploring all streets.

From Three-Dimensional Topological Relations to Contact
Relations17

Acknowledgment
This work is supported by DFG (Deutsche Forschungsgemeinschaft)through the Collaborative Research Center SFB/TR 8 Spatial Cognition—
Strategic Project “Spatial Calculi for Heterogeneous Objects.”

References
Alexandroff, P.: Elementary Concepts of Topology. Dover Publications, Mineola,
NY, USA (1961)
Billen, R., Kurata, Y.: Refining Topological Relations between Regions Considering Their Shapes. In: Cova, T., Miller, H., Beard, K., Frank, A., Goodchild,M. (eds.): GIScience 2008, Lecture Notes in Computer Science, vol. 5266, pp.
20-37. Springer, Berlin/Heidelberg, Germany (2008)
Billen, R., Zlatanova, S., Mathonet, P., Boniver, F.: The Dimensional Model: A
Framework to Distinguish Spatial Relationships. In: Richardson, D., van Oosterom, P. (eds.): Advances in spatial data handling: 10th International Symposium on Spatial Data Handling, pp. 285-298. Springer, Berlin/Heidelberg,
Germany (2002)
Egenhofer, M.: A Formal Definition of Binary Topological Relationships. In: Litwin, W., Schek, H.-J. (eds.): 3rd International Conference on Foundations of
Data Organization and Algorithms, Lecture Notes in Computer Science, vol.
367, pp. 457-472. Springer, Berlin/Heidelberg, Germany (1989)
Egenhofer, M.: Deriving the Composition of Binary Topological Relations. Journal of Visual Languages and Computing 5(2), 133-149 (1994)
Egenhofer, M., Herring, J.: Categorizing Binary Topological Relationships between Regions, Lines and Points in Geographic Databases. In: Egenhofer, M.,
Herring, J., Smith, T., Park, K. (eds.): NCGIA Technical Reports 91-7. National Center for Geographic Information and Analysis, Santa Barbara, CA,
USA (1991)
Feist, M.: On In and On: An Investigation into the Linguistic Encoding of Spatial
Scenes. Ph.D. Thesis. Northwestern University (2000)
Freksa, C.: Temporal Reasoning Based on Semi-Intervals. Artificial Intelligence
54(1-2), 199-227 (1992)
Kurata, Y.: The 9+-Intersection: A Universal Framework for Modeling Topological Relations. In: Cova, T., Miller, H., Beard, K., Frank, A., Goodchild, M.
(eds.): GIScience 2008, Lecture Notes in Computer Science, vol. 5266, pp.
181-198. Springer, Berlin/Heidelberg, Germany (2008)
Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between
a Directed Line Segment and a Region. In: Gottfried, B. (ed.): 1st Workshop
on Behavioral Monitoring and Interpretation, TZI-Bericht, vol. 42, pp. 62-76.
Technogie-Zentrum Informatik, Universität Bremen, Germany (2007)

18

Yohei Kurata

Mark, D., Egenhofer, M.: Modeling Spatial Relations between Lines and Regions:
Combining Formal Mathematical Models and Human Subjects Testing. Cartography and Geographical Information Systems 21(3), 195-212 (1994)
Randell, D., Cui, Z., Cohn, A.: A Spatial Logic Based on Regions and Connection.
In: Nebel, B., Rich, C., Swarout, W. (eds.): 3rd International Conference on
Knowledge Representation and Reasoning, pp. 165-176. Morgan Kaufmann,
San Francisco, CA, USA (1992)
Schneider, M., Behr, T.: Topological Relationships between Complex Spatial Objects. ACM Transactions on Database Systems 31(1), 39-81 (2006)
Shariff, A., Egenhofer, M., Mark, D.: Natural-Language Spatial Relations between
Linear and Areal Objects: The Topology and Metric of English-Language
Terms. International Journal of Geographical Information Science 12(3), 215246 (1998)
Zlatanova, S.: On 3D Topological Relationships. In: Erwig, M., Schneider, M.,
Sellis, T. (eds.): International Workshop on Advanced Spatial Data Management, pp. 913-924. IEEE Computer Society (2000)

Appendix: Mapping from Topological Region-Region
Relations in ℝ૜ to Contact Relations• the topological relations in Figs. 8a,b,F are mapped to only one contact
relation, respectively, due to the lack of interior-related intersections;• the topological relations in Fig. 8c, Figs. 8A-B, Figs. 8C-D, Fig. 8E,
Figs. 8L1/2-M1/2, and Figs. 8N1/2-O1/2 are mapped to 15×3×3, 15, 3×3,
15×3×3, 3, and 15×3 contact relations, respectively, because in these
mappings we can consider edge-side contacts and side-side contacts independently; that is,- if the topological relations have a boundary-interior intersection, they
are mapped to 22−1 = 3 types of edge-side contacts (i.e., the boundaryof one region contacts either or both sides of another region); and- if the topological relations have an interior-interior intersection, thisintersection is mapped to 24−1 = 15 types of side-side contacts (i.e.,either or both sides one region contact either or both sides of anotherregion);• the topological relations in Fig. 8G is mapped to six contact relations—four are the contact relations where A’s one side contacts B’s one side(i.e.,) and two are the contact relations where A’s two
sides contact B’s different sides (i.e.,);

From Three-Dimensional Topological Relations to Contact
Relations19• the topological relation in Fig. 8H is mapped to four contact relations inwhich the boundary of each region contacts either side of another region(i.e.,);• the topological relation in Fig. 8I is mapped to one more contact relation
than the previous case, in which the boundary of each region contacts
both sides of another region (i.e.,
in addition to);• the topological relation in Fig. 8J is mapped to 24 contact relations, because once we assume that A’s x-side contacts B’s boundary and B’s yside contacts A’s boundary (four possibilities exist), there are six possible side-side contacts (since A’s x-side and B’s y-side may contact either
or both sides of another region, A’s non-x-side may contact B’s y-side,
and B’s non-y-side may contact A’s x-side);• the topological relation in Fig. 8K is mapped to 15 more contact relations than the previous case, in which the boundary of both regions contact the both sides of another region and both sides of each region may
contact either or both sides of another region;• the topological relations in Figs. 8T1/2 are mapped to two contact relations, in which the entire boundary of one region contacts either side ofanother region;• the topological relations in Figs. 8U1/2 are mapped to one more contact
relation than the previous case, in which one region clips another region(Fig. 13a) and, accordingly, the boundary of the clipping region contacts
both sides of the clipped region;• the topological relations in Figs. 8P1/2 are mapped to four contact relations, in which the boundary of each region contacts either side ofanother region;• the topological relations in Figs. 8Q1/2 are mapped to three more contact
relations than the previous case, in which one region clips another region and the boundary of the clipped region contacts either or both sidesof another region;• the topological relations in Figs. 8R1,V1 are mapped to 28 contact relations, because once we assume that A’s x-side and B’s y-side encloses a
space (four possibilities exist), there are seven possible side-side contacts (because A’s x-side may contact B’s side, while A’s non-x-side
may contact either or both sides of B), and similarly the topological relations in Figs. 8R2,V2 are mapped to 28 contact relations;• the topological relations in Figs. 8W1/2 are mapped to 15 more relations
than those in Figs. 8V1/2 are, in which either or both sides of the clipped
region contact either or both sides of another regions;20

Yohei Kurata• the topological relations in Figs. 8S1/2 are mapped to 45 more relations
than those in Figs. 8R1/2 are, in which the boundary and either or bothsides of the clipped region contact either or both sides of another region
independently;• the topological relation in Fig. 8d is mapped to four contact relations inwhich either side of one region contacts either side of another region;• the topological relation in Fig. 8f1 is mapped to 16 contact relations,among which four are the relations in which one entire side of A contacts either side of B (i.e.,) and twelve are the relation
where one side of A entirely contacts either side of B and A’s anotherside partly contacts either or both sides of B (i.e.,), and similarly the topological relation in Fig. 8f2 ismapped to 16 contact relations; and• the topological relation in Fig. 8e1 is mapped to eight more contact relations than that in Fig. 8f1, in which A is clipped by B plainly such that
B’s one side contacts both sides of A (Fig. 13b) and B’s another side
may contact either or both sides of A, and similarly, the topological relation in Fig. 8e2 is mapped to eight more contact relations than that inFig. 8f2.

A

B
(a)

A

B
(b)

Fig. 1. Configurations of two contact relations, derived from the topological region-region relations in (a) Fig. 8U1 and (b) Fig. 8e1, in which the region A isclipped by the region B