The 9+-Intersection: A Universal Framework for
Modeling Topological Relations
Yohei Kurata
SFB/TR8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany
ykurata@informatik.uni-bremen.de

Abstract. The 9+-intersection is an extension of the 9-intersection, which
distinguishes the topological relations between various spatial objects by thepattern of a nested matrix. This paper develops a small set of constraints on thismatrix, which is applicable to arbitrary pairs of spatial objects in various spaces.
Based on this set of universal constraints, the sets of matrix patterns, each
representing a candidate for topological relations, are derived for every possible
pair of basic objects (points, directed/non-directed line segments, regions, andbodies) embedded in R1, R2, R3, S1, and S2. The derived sets of candidates are
consistent with the sets of topological relations ever identified, as well as yield
the identification of some missing sets of topological relations. Finally, thetopological relations between a region and a region with a hole in R2 and S2 are
identified to demonstrate the applicability of our approach to deriving
topological relations between more complicated objects.

1.

Introduction

Topological relations between two spatial objects, which concern how the objects
intersect with each other, have been studied extensively in the geographic databasecommunity, motivated by the necessity of a formal and cognitively-adequate basis ofspatial query language. Previous studies have identified sets of all possible
topological relations between various pairs of objects in R2 [1-7], as well as in R1 [8],R3 [9], S1 [10], S2 [11], and Z2 [12]. Rn is an n-dimensional Euclidean space, S1 is a
circle (1-sphere), and S2 is an ordinary sphere (2-sphere), and Z2 is a discrete rasterspace. Each identified set of topological relations has a specific practical value. For
instance, topological line-region relations in R2 are useful for modeling spatial
predicates related to motions, such as enter and go across [13], and topological lineline relations in R1 or S1 are useful for modeling temporal relations [8, 10].
As a formal model of topological relations, many studies have adopted the 4intersection [1], the 9-intersection [2], or their extension [5, 6, 10, 14]. In thesemodels, topological relations between two objects A and B are represented by thepatterns of a matrix, whose elements represent the intersections between point sets
associated with A and those associated with B. Usually, candidates for possible
topological relations between A and B are derived computationally as the set of matrix
patterns that satisfy certain constraints. The set of candidates, each with at least one

2

Yohei Kurata

geometric realization, is approved as the set of all possible topological relations
between A and B. Previous studies developed such a constraint set on the matrix foreach pair of objects in each space [1, 2, 4-7, 9-12]. Although there are certain overlaps
between such constraint sets [2, 9], it is a hard step to develop a constraint set in orderto study a new set of topological relations. As a solution to this problem, this paper
develops a set of universal constraints, which is applicable to arbitrary pairs ofobjects embedded in various spaces.
Our universal constraints are applied to the matrix of the 9+-intersection [6]. The+
9 -intersection is an extension of the 9-intersection, which supports the subdivision of
objects’ interior, boundary, and exterior. For instance, the exterior of a region with ahole is subdivided into outer and inner exterior subsets. Thanks to the support of suchsubdivisions, the 9+-intersection is able to capture the topological relations between
various spatial objects, including complicated ones. Accordingly, making use of the
9+-intersection together with the set of universal constraints, we can easily derive thecandidates for the topological relations between various pair of objects embedded invarious spaces. Indeed, this paper derives the sets of such candidates for every
possible pair of basic objects (points, directed/non-directed lines, regions, and bodies)embedded in R1, R2, R3, S1, and S2. In this paper, lines and regions normally refer tosimple lines and simple regions [4, 15], respectively. Simple lines are lines with noself-intersection and no branch, derived by a one-to-one mapping from [0,1] to thespace. If their two endpoints are ordered, lines are called DLines (directed lines).
Simple regions are two-dimensional point sets with a connected interior, no hole, andno spike, as well as no fin in R3. Finally, bodies refer to simple bodies, which arethree-dimensional counterparts of simple regions.
The remainder of this paper is structured as follows: Section 2 introduces the 9+intersection and its matrix-based representation. Section 3 develops a set of universal
constraints on the matrix of the 9+-intersection. Based on this set of constraints,
Section 4 derives the candidates for topological relations between every pair of basic
objects and analyzes the candidates in comparison with the topological relations
identified in the previous studies. Section 5 derives further candidates of basic
topological relations by converting the matrix patterns derived in Section 4 andanalyzes these new candidates. Section 6 demonstrates the applicability of ourapproach to the derivation of topological relations between more complicated objects.
Finally, Section 7 concludes with the discussion of a future problem.

2.

The 9+-Intersection

The 9-intersection [2] is a model of topological relations between two spatial objects.
Based on point-set topology [16], this model distinguishes the interior, boundary, andexterior of each object, which are also called the object’s topological parts. Let X be a
spatial object and X be X’s closure (the intersection of all closed point sets that
contain X). Uppercase letters are used because spatial objects are considered sets ofpoints. X’s interior X ° is the union of all open sets contained in X, X’sboundary ∂X is the difference between X and X ° , and X’s exterior X − is X ’s
complement. Accordingly, the boundary of a region refers to its looped edge, theThe 9+-Intersection: A Universal Framework for Modeling Topological Relations

3boundary of a line refers to its two endpoints, and the boundary of a point refers to thepoint itself.
The 9-intersection captures the topological relation between two spatial objects A
and B based on the intersections of A’s three topological parts and B’s three
topological parts. These 3 × 3 = 9 types of intersections are concisely represented by
the 9-intersection matrix in Eqn. 1. Normally, topological relations are distinguishedby the presence or absence of these nine types of intersections. The use of some
additional properties of the intersections are also proposed for more detailed
distinction of topological relations [14, 17].
⎛ A° ∩ B° A° ∩ ∂B A° ∩ B − ⎞⎜⎟M ( A, B ) = ⎜ ∂A ∩ B° ∂A ∩ ∂B ∂A ∩ B − ⎟
⎜ −
−
−
−⎟
⎝ A ∩ B° A ∩ ∂B A ∩ B ⎠(1)Each topological part of a spatial object may be subdivided into multiple subparts
based on their disconnection or qualitative difference (e.g., dimensions [18]). For
instance, the boundary of a DLine is subdivided into two subparts; start-point andend-point [5]. In order to support such subdivision of objects’ topological parts, the9+-intersection [6] extends the 9-intersection, considering the intersections between
the subparts of A’s three topological parts and those of B’s three topological parts. In
this model, the topological relations between A and B are characterized by the 9+intersection matrix in Eqn. 2, whose nine bracketed elements are matrices bythemselves, each representing the intersections between the subparts of A’s one
topological part and those of B’s one topological part. Ao , ∂ i A , and A− are the ithiisubpart of A’s interior, boundary, and exterior, while B o , ∂ j B , and B − are the jth
subpart of B’s interior, boundary, and exterior, respectively. If a topological part is not
subdivided, we consider that this topological part consists of a single subpart. As seenfrom the comparison of the matrices in Eqns. 1-2, the 9+-intersection matrix keeps theframework of the 9-intersection matrix; that is, the nine inner matrices in the 9+intersection matrix uniquely correspond to the nine elements in the 9-intersection
matrix. Just like the 9-intersection, topological relations between A and B are
distinguished by the presence or absence of all intersections listed in the matrix.
j

[
[
[

⎛ Ao i ∩ B o j⎜o
M + ( A, B ) = ⎜ ∂ i A ∩ B j⎜⎜ A −i ∩ B o j⎝j] [A ∩ ∂ B] [A ∩ B ] ⎞⎟] [∂ A ∩ ∂ B] [∂ A ∩ B ]⎟⎟] [A ∩ ∂ B] [A ∩ B ] ⎟⎠
oi

oi

−j

j

−j

i

j

−i

i

−i

(2)

−j

j

As an example, Eqn. 3 shows the 9+-intersection matrix for the topological relation
between a DLine D and a region R. In this matrix, ∂1 D and ∂ 2 D represent D’s
start-point and end-point, respectively. For simplification, if a topological partconsists of a single subpart, the subscript assigned to this subpart is omitted. In
addition, brackets of inner matrices are omitted if they have only one element.
Originally, the 9+-intersection matrix was introduced to capture such topological
DLine-region relations in [6], where 26 relations are identified using the specific4

Yohei Kurata

constraints on the patterns of the 9+-intersection matrix in Eqn. 3, instead of theuniversal constraints proposed in this paper.
⎛ D° ∩ R°
D° ∩ ∂R
D° ∩ R − ⎞⎟⎜−⎜ ⎡∂1D ∩ R° ⎤ ⎡∂1D ∩ ∂R ⎤ ⎡∂1D ∩ R ⎤ ⎟M + ( D, R ) = ⎜ ⎢
⎥
⎢
⎥
⎢
⎥
∂ D ∩ R°⎦ ⎣∂ 2 D ∩ ∂R ⎦ ⎣⎢∂ 2 D ∩ R − ⎦⎥ ⎟⎜⎣ 2 −⎟⎜ D ∩ R°D − ∩ ∂RD − ∩ R − ⎟⎠⎝(3)

For visualization, the patterns of the 9-/9+-intersection matrix are represented bybitmap-like icons [6, 19]. Each icon is partitioned into nine blocks, which correspondto the nine elements of the 9-intersection matrix or the nine element sets of the 9+intersection matrix (Figs. 1a-b). In the icon of the 9+-intersection matrix, each blockof the icon is further partitioned if the corresponding element set has multiple
elements (Fig. 1b). Each block or sub-block is marked out if the corresponding
intersection is non-empty. Accordingly, topological relations are distinguished by theicons’ marking patterns.
⎛ L° ∩ R °⎜⎜ ∂L ∩ R°⎜ L− ∩ R°⎝

L° ∩ ∂R L° ∩ R − ⎞ ⎛ ¬φ⎟ ⎜∂L ∩ ∂R ∂L ∩ R − ⎟ = ⎜ ¬φ−−−⎟L ∩ ∂R L ∩ R ⎠ ⎜⎝ ¬φ

φ
¬φ
¬φ

φ ⎞
⎟
φ ⎟
¬φ ⎟⎠

Æ

(a)
⎛ D ° ∩ R°
D° ∩ ∂R
D° ∩ R − ⎞ ⎛ ¬φφ
⎟ ⎜⎜⎜ ⎡∂1 D ∩ R° ⎤ ⎡∂1 D ∩ ∂R ⎤ ⎡∂1 D ∩ R − ⎤ ⎟ ⎜ ⎡¬φ ⎤ ⎡ φ ⎤
=
⎢
⎥
⎜⎢
⎥ ⎢
⎥
− ⎟
⎜⎢ ⎥ ⎢ ⎥⎜ ⎣∂ 2 D ∩ R°⎦ ⎣∂ 2 D ∩ ∂R ⎦ ⎣⎢∂ 2 D ∩ R ⎦⎥ ⎟ ⎜ ⎣ φ ⎦ ⎣¬φ ⎦
−
−
− ⎟
¬φ
⎜ D − ∩ R°
D ∩ ∂RD ∩ R ⎠ ⎝ ¬φ⎝φ ⎞⎟⎡φ ⎤ ⎟⎢φ ⎥ ⎟
⎣ ⎦
¬φ ⎟⎠

Æ

(b)

Fig. 1. Iconic representations of (a) the pattern of the 9-intersection matrix and (b) that of the
9+-intersection matrix.

3.

Universal Constraints on the 9+-Intersection Matrix

The primitives of a spatial object X are defined as the subparts of X’s interior,boundary, or exterior that are each self-connected and mutually disjoint. For instance,
the interior, boundary, and exterior of a DLine in R1 consist of one, two, and two
primitives, respectively, as its boundary consists of two distinctive points (i.e., startpoint and end-point) and its exterior consists of two distinctive half-lines (i.e., front
and back exterior subparts). Primitives of spatial objects are classified by theirdimension and spatial extent (Table 1). For instance, the primitives that form theinterior, boundary, and exterior of the DLine in R1 are classified into B-1D (bounded,
non-looped one-dimensional primitive), 0D (zero-dimensional primitive), and U-1D
(unbounded one-dimensional primitive), respectively.
By illustrating the class of all primitives that form the interior, boundary, andexterior of a spatial object X, as well as the adjacency among these primitives, X’s
topological structure is represented as a graph. For instance, Fig. 2 illustrates theThe 9+-Intersection: A Universal Framework for Modeling Topological Relations

5

topological structures of points, DLines, and regions embedded in R1, R2, R3, S1, andS2. These topological structures have the following features:• Every primitive has at least one adjacent primitive; and• Every pair of adjacent primitives has different dimensions and belongs to different
topological parts.
Table 1. Classes of basic primitives.

Class
0D
B-1D
L-1D
U-1D

Dim.
0D
1D
1D
1D

interior
boundary
exterior

0D

0D

U-1D U-1D U-1D U-1D

U-2D

0D

interior

exterior

0D

DLine in R1

0D 0D

B-1D

B-1D

Point in S1

DLine in S1

0D

0D

U-2D

Point in R2 DLine in R2

B-1D
0D

Class
B-2D
L-2D
U-2D
B-3D
U-3D
B-1D

B-1D

Point in R1

boundary

Spatial extent–
bounded, non-looped
circularly looped
unbounded

B-1D
0D
B-2D

0D

0D

B-2D

Dim.
2D
2D
2D
3D
3D

B-1D

B-2D
L-1D

0D

U-2D

U-3D

Region in R2

Spatial extent
bounded, non-looped
spherically looped
unboundedbounded non-looped
unbounded

0D

0D

U-3D

B-2D
L-1D
U-3D

Point in R3 DLine in R3 Region in R3

B-3D
L-1D
U-3D
Body in R3

B-2D
L-1D
B-2D

Point in S2 DLine in S2 Region in S2

Fig. 2. Topological structures of points, DLines, and regions embedded in R1, R2, R3, S1, andS2, based on the class and adjacency of their primitives.

Assume that two spatial objects A and B are embedded in the space S. Then, A’sprimitives and B’s primitives must satisfy the following nine conditions (seeAppendix for their proofs):• Condition 1: Each of A’s primitives intersects with at least one of B’s primitives,and vice versa.
• Condition 2: If A has a zero-dimensional primitive (0D), then it intersects with
only one of B’s primitives, and vice versa.
• Condition 3: If A’s primitive Pi intersects with more than one of B’s primitives,then these primitives jointly form a connected point set, and vice versa.
• Condition 4: A’s bounded primitives, either looped or non-looped, cannot contain a
B’s unbounded primitives, and vice versa.

6

Yohei Kurata• Condition 5: A’s non-looped primitives cannot contain a B’s looped primitive of
the same dimension, and vice versa.
• Condition 6: If A’s primitive Pi intersects with B’s primitive Qj, then all of Pi’s
adjacent higher-dimensional primitives intersect with Qj or at least one of Qj’s
adjacent higher-dimensional primitives, and vice versa (Fig. 3a).
• Condition 7: If A’s primitive Pi is contained by B’s primitive Qj and they belong to
the same primitive class, then at least one of Pi’s adjacent lower-dimensional
primitives intersects with Qj, and vice versa (Fig. 3b).
• Condition 8: If A’s primitive Pi intersects with B’s primitive Qj that is lower
dimensional than Pi, then Pi intersects with at least one of Qj’s adjacent higherdimensional primitives (Fig. 3c) or at least two of them including one of Qj’s
adjacent primitives that are bounded, non-looped, and one-dimensionally higher
than Qj (Fig. 3d), and vice versa.
• Condition 9: If A has only one unbounded primitive whose dimension is the samewith S, then this primitive intersects with all of B’s unbounded primitives, and viceversa.
Qj

Qj

Q j ’s adjacent higherdimensional primitivePi

Pi

P i ’s adjacent
lower-dimensional
primitives

P’s adjacent higherdimensional primitives

(a)

Pi

(b)

Pi
Qj

Qj
Q j ’s adjacenthigher-dimensional
primitive(c)

Q j ’s adjacent primitives thatare non-looped and onedimensionally higher than Q j

Q j ’s otheradjacent
primitive(d)Fig. 3. Intersection of two primitives Pi and Qj determines the presence of intersections of Pi’s
certain adjacent primitives and Qj or Qj’s adjacent primitives

When the 9+-intersection illustrates the intersections of A’s primitives and B’s
primitives, Conditions 1-9 serve as the constraints on the patterns of the 9+intersection matrix. For instance, the 9+-intersection matrix in Eqn. 3 illustrates theintersections of the primitives of a DLine D ( D° , ∂1D , ∂ 2 D and D − ) and theprimitives of a region R ( R° , ∂R and R − ). This matrix may distinguish 4096 patterns,
as it has 4×3 two-valued elements, but only 26 patterns among the 4096 patterns
satisfy Conditions 1-9. Consequently, we can conclude that these 26 patterns of the
9+-intersection matrix represent the candidates for the topological relations between a
DLine D and a region R.

The 9+-Intersection: A Universal Framework for Modeling Topological Relations

4.

7

Deriving Topological Relations between Basic Objects

For every possible pair of basic objects (points, DLines, regions, and bodies)embedded in R1, R2, R3, S1, and S2, we derived the patterns of the 9+-intersection
matrix that satisfy Conditions 1-9, making use of their structural information
illustrated in Fig. 2. Table 2 shows the number of the derived matrix patterns. Since
each matrix pattern represents a candidate for topological relations, the number of all
possible topological relations between each pair of objects in each space is equal or
possibly less than the number in Table 2.
Table 2. Numbers of the derived patterns of the 9+-intersection matrix for every possible pair ofbasic objects embedded in R1, R2, R3, S1, and S2.

Point-Point
Point-DLine
Point-Region
Point-Body
DLine-DLine
DLine-Region
DLine-Body
Region-Region
Region-Body
Body-Body

R1
6
10
–
–
26
–
–
–
–
–

R2
2
4
3
–
80
26
–
8
–
–

R3
2
4
3
3
80
45
26
43
19
8

S1
2
4
–
–
28
–
–
–
–
–

S2
2
4
3
–
80
26
–
11
–
–

For point-point relations in R2, R3, S1, and S2, the same two patterns of the 9+intersection matrix are derived. These two matrix patterns correspond to the two
scenarios—two points coincide or not. Meanwhile, point-point relations in R1 yieldeda larger number of matrix patterns, because in R1 the exterior of each point is
subdivided into two primitives (i.e., front and back exterior subparts) and their orderinfluences the distinction of topological relations. Similarly, the same four matrix
patterns are derived for point-DLine relations in R2, R3, S1, and S2, but not for thosein R1. These four matrix patterns correspond to the four scenarios where the point islocated at the DLine’s interior, exterior, start-point, or end-point. For point-region
relations in R2, R3, and S2 and point-body relations in R3, we derived the same threematrix patterns, which correspond to the three scenarios where the point is located at
the interior, exterior, or boundary of the region/body.
For DLine-DLine relations in R1, we derived 26 patterns of the 9+-intersection
matrix. These 26 patterns correspond to the 26 relations between two directedintervals in R1 [20], because directed intervals are essentially DLines.
For DLine-DLine relations in R2, 80 patterns of the 9+-intersection matrix arederived. Kurata and Egenhofer [5] identified only 68 DLine-DLine relations in R2, as
they used an extension of the 4-intersection. They also speculated that additional 12
relations appear if they distinguish the collapsed configurations (i.e., theconfigurations where one DLine contains another DLine). Our 80 patterns of the 9+-

8

Yohei Kurata

intersection matrix successfully distinguish these 68 + 12 = 80 DLine-DLine
relations.
For DLine-region relations in R2, we derived 26 patterns of the 9+-intersection
matrix. This successfully corresponds to the result in [6], which identified 26 DLineregion relations based on the 9+-intersection.
DLine-DLine relations in R2, R3, and S2 yielded the same 80 matrix patterns. This
result indicates that the set of 80 DLine-DLine relations in R2 are also seen in R3 andS2. Similarly, from the result that DLine-region relations in R2, DLine-region
relations in S2, and DLine-body relations in R3 has yielded the same 26 matrix
patterns, it is concluded that the set of 26 DLine-region relations in R2 are also seen in
S2, and have a one-to-one correspondence with DLine-body relations in R3. This
correspondence stems from the structural similarity between a region in R2 and abody in R3 (Fig. 2).
For DLine-Region relations in R3, we derived 45 patterns of the 9+-intersection
matrix, among which 26 patterns are identical to the 26 matrix patterns derived forDLine-Region relations in R2. We confirmed that each of the remaining 19 patterns
has at least one geometrical realization in R3 (Fig. 4). Consequently, we identified
that topological DLine-Region relations in R3 consist of 19 relations peculiar to R3(Fig. 4) and 26 relations common to R2, R3, and S2 (see [6] for the list). Such DLineRegion relations in R3 are useful for categorizing the movement patterns inassociation with region-like landmarks—for instance, how a bird moves around apond. The newly identified 19 relations capture the bird’s movement patterns thatrealize only in a three-dimensional space.

Fig. 4. 19 topological DLine-region relations, which are peculiar to R3.

For region-region relations in R2, eight patterns of the 9+-intersection matrix arederived. In this case, the matrix is essentially the 9-intersection matrix, because no
topological part of a region is subdivided into multiple primitives. These eight matrix
patterns are exactly the same as those derived in [2]. Similarly, the following
correspondences to the findings of the previous studies are observed:

The 9+-Intersection: A Universal Framework for Modeling Topological Relations

9• the eleven matrix patterns derived for region-region relations in S2 are the same as
those derived in [11];• the nineteen matrix patterns derived for region-body in R3 are the same as thosederived in [9]; and• the eight matrix patterns derived for body-body relations in R3 are the same as
those derived in [9].
Meanwhile, for region-region relations in R3, we derived 43 patterns of the 9intersection matrix, while only 38 patterns are reported in [9]. Through thecomparison the matrix patterns, we identified five missing relations (Fig. 5). In [21],43 region-region relations in R3 are derived based on another spatial model, called
Dimensional Model [18]. The 43 region-region relations in the Dimensional Modelare equivalent to the region-region relations characterized by our 43 patterns of the 9intersection matrix.

(and its converse)

Fig. 5. Five topological region-region relations in R3 that should be added to the list in [9].

5.

Topological Relations Derived by Matrix Conversion

A unique feature of the 9+-intersection is that the 9+-intersection matrix can beconverted to the 9-intersection matrix, simply by integrating the elements of its nineelement sets by union operation (Fig. 6). If the original 9+-intersection matrix captures
the topological relation between a DLine and another object X, the 9-intersection
matrix derived by the conversion captures the topological line-X relations, as thedistinction of the DLine’s start-point and end-point is lost. Similarly, for the relations
in R1, the distinction of objects’ front and back exterior subparts is lost by the matrix
conversion (Fig. 6b). Making use of this matrix conversion, the sets of candidates for
topological line-X relations and the modified candidate sets for topological relations
in R1 are derived from the matrix patterns derived in Section 4. Table 3 shows thenumber of the derived patterns of the 9-intersection matrix.

10

Yohei Kurata
D2 ° ∂ s D2 ∂ e D 2 ° D2
⎛
⎜
⎜ ¬φ
⎜
⎜
∂ s D1 ⎜ ⎡ φ ⎤∂ e D1 ° ⎜ ⎢⎣¬φ ⎥⎦
⎜
⎜
⎜
−s
D1
⎜⎡ φ ⎤⎜ ⎢¬φ ⎥
−e
⎝⎣ ⎦
D
D1 °

1

D1
D2

−s

∂ s D1−s∂ s D2

[φ

φ]

D1 °

D2 °

−e

φ] ⎟

⎟
⎟
⎡φ φ ⎤ ⎟⎢φ φ ⎥ ⎟
⎣
⎦ ⎟
⎟
⎟
¬
φ
φ
⎤⎟
⎡
⎢ φ ¬φ ⎥ ⎟
⎦⎠
⎣

φ ⎤
¬φ ⎥⎦
∂ e D1

D2

⎞
⎟

[φ

⎡¬φ φ ⎤
⎢ φ φ⎥
⎣
⎦
⎡φ
⎢φ
⎣

−s

D1

−

conversion

L 2 ° ∂L 2 L 2
L1 ° ⎛ ¬φ φ
φ ⎞⎜⎟∂L1 ⎜ ¬φ ¬φ φ ⎟−L1 ⎜⎝ ¬φ ¬φ ¬φ ⎟⎠

∂L1

−e

L1

−

L1 °
D

∂e D2 2

L2 °

−e

∂L2

L2

−

Fig. 6. Conversion from the 9+-intersection matrix to the 9-intersection matrix. In the left
figure, DLines D1 and D2 are represented by two arrows.

Table 3. Numbers of the patterns of the 9-intersection matrix derived by matrix conversion.

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

R1
2
3
8
–
–

R2
–
–
33
19
–

R3
–
–
33
31
19

S1
–
–
11
–
–

S2
–
–
33
19
–

For line-line relations in R1, eight patterns of the 9-intersection matrix are derived.
These eight patterns correspond to the eight line-line relations in R1, identified in[22]. In addition, these eight matrix patterns are the same as the matrix patterns forregion-region relations in R2. This indicates a one-to-one correspondence between theeight line-line relations in R1 and the eight region-region relations in R2. Similarly,
we found a one-to-one correspondence between the eleven line-line relations in S1
and the eleven region-region relations in S2.
For line-line and line-region relations in R2, we derived 33 and 19 patterns of the
9-intersection matrix. These two sets of matrix patterns are the same as those in [2].
Similarly, for line-line, line-region, and line-body relations in R3, we derived 33, 31,
and 19 patterns of the 9-intersection matrix, which are the same as those in [9].
The 9+-intersection matrix allows another type of matrix conversion when bothobjects have topological parts that can be subdivided into multiple primitives. This
conversion removes the subdivision of topological parts with respect to only one of
the two objects (Fig. 7). Accordingly, the matrix derived by the conversion is still the
9+-intersection matrix. Making use of this matrix conversion, we derived additional
sets of patterns of the 9+-intersection matrix from those of the 9+-intersection matrix
in Section 4. Table 4 shows the numbers of the derived matrix patterns.

The 9+-Intersection: A Universal Framework for Modeling Topological Relations−s

D2 ° ∂ s D2 ∂ e D2 ° D2
⎛
⎜
⎜ ¬φ
⎜
⎜
∂ s D1 ⎜ ⎡ φ ⎤∂ e D1 ° ⎜ ⎢⎣¬φ ⎥⎦
⎜
⎜
⎜
−s
D1
⎜⎡ φ ⎤⎜ ⎢¬φ ⎥
−e
D
⎝⎣ ⎦
D1 °

1

D1
D2

−s

∂ s D1−s∂ s D2

[φ

φ]

[φ

D1 °

φ ⎤
¬φ ⎥⎦
∂ e D1

D2 °

−e

L2 °

⎞
⎟

⎛
⎜
⎜ ¬φ
⎜
⎜
∂ s D1 ⎜ ⎡ φ ⎤∂ e D1 ° ⎜ ⎢⎣¬φ ⎥⎦
⎜
⎜
⎜
−s
D1
⎜⎡ φ ⎤⎜ ⎢¬φ ⎥
−e
⎝⎣ ⎦
D

D1

Æ

D1
D

∂e D2 2

L2

φ

φ ⎟

−s

∂ s D1

D1 °

⎞
⎟

⎟
⎟
⎡φ ⎤ ⎟⎢φ ⎥ ⎟
⎣ ⎦ ⎟
⎟
⎟
¬
φ
⎡ ⎤⎟
⎢¬φ ⎥ ⎟
⎣ ⎦⎠

⎡¬φ ⎤
⎢φ ⎥
⎣ ⎦
⎡φ ⎤
⎢¬φ ⎥
⎣ ⎦

1

−e

−

∂L2 °

D1 °

φ] ⎟

⎟
⎟
⎡φ φ ⎤ ⎟⎢φ φ ⎥ ⎟
⎣
⎦ ⎟
⎟
⎟
φ
φ
¬
⎡
⎤⎟
⎢ φ ¬φ ⎥ ⎟⎣⎦⎠⎡¬φ φ ⎤
⎢ φ φ⎥
⎣
⎦
⎡φ
⎢φ
⎣

D2

11

∂ e D1

D1

−e

L2 °

−e

∂L2

L2

−

Fig. 7. Conversion of the 9+-intersection matrix that removes the subdivision of the second
object’s topological parts.

Table 4. Numbers of the patterns of the 9+-intersection matrix that are newly derived by thematrix conversion in Fig. 7.

Point-Point
Point-Line
DLine-Line

R1
3
5
13

R2
–
–
49

R3
–
–
49

S1
–
–
16

S2
–
–
49

For point-point relations in R1, three patterns of the 9+-intersection matrix arederived. These three matrix patterns correspond to the three scenarios where one point
precedes, coincides, or succeeds another point on the same axis. In the previous step,
we derived only two patterns for the same relations , because the 9-intersection matrix
does not distinguish whether one point precedes or succeeds another point. For thesame reason, the number of the patterns of the 9+-intersection matrix derived forpoint-line relation in R1 is larger than that of the 9-intersection matrix.
For DLine-line relations in R1, 13 patterns of the 9+-intersection matrix arederived. Interestingly, these 13 matrix patterns correspond to the 13 interval relations
in Allen’s interval algebra [8], because DLine-Line relations in R1 essentially
illustrate how one line (interval) extends with respect to another line (interval) on thesame axis with the distinction of front and back. Similarly, for DLine-Line relations in
S1, we derived 16 matrix patterns, which correspond to the 16 interval relations in acyclic temporal frame identified in [10].
For DLine-line relations in R2, R3, and S2, the same 49 patterns of the 9+intersection matrix are derived. We confirmed that each of these 49 matrix patterns
has at least one geometric realization (Fig. 8). Thus, it is concluded that these 49
matrix patterns represent the set of all possible DLine-line relations in R2, R3, and S2
under the 9+-intersection. Such DLine-line relations are useful for categorizing the
movement patterns associated with a linear landmark, such as a wall or a trench.

12

Yohei Kurata

Fig. 8. 49 topological DLine-line relations, common to R2, R3, and S2, each with an example ofgeometric realizations.

Finally, through the comparison of Tables 2-4, we found the following features:• The number of matrix patterns for line-line/DLine-line/DLine-DLine relations in
S1 are larger than that for the counterparts in R1, because S1 allows the relation
where one line/DLine includes the entire exterior of another line/DLine, but R1
does not.
• The number of topological relations between two spatial objects is invariant to theembedding space, as long as these two objects are lower dimensional than theThe 9+-Intersection: A Universal Framework for Modeling Topological Relations

13

space. One exception is point-point relations in R1 distinguished by the 9+intersection (Table 2), because the distinction of the points’ front and backexteriors increases the number of point-point relations.

6.

Deriving Topological Relations related to Complicated Objects

The combination of the 9+-intersection and the universal constraints are effective also
for deriving the possible topological relations between a basic object and a more
complicated object, or even the relations between two complicated objects (here,
complicated objects mean the objects that are derived by a set operation on multiple
basic objects). As a demonstration, this section derives all possible topologicalrelations between a simple region (so far we have called this a region) and a simple
region with a hole. For simplification, these relations are called topological regionregion+1H relations. In [7], 23 topological region-region+1H relations in R2 are alreadyidentified, but those in S2 are not yet.
A simple region with a hole X is defined as the difference between two simple
regions X* and XH, where X* contains XH entirely. X* is called X’s generalized
region, while XH is called X’s hole [23]. A simple region with a hole in S2 may
represent a ring-like object on a sphere (Fig. 9a) or a belt-like object that surrounds
the sphere (Fig. 9b) Accordingly, region-region+1H relations in S2 can be used formodeling, for instance, the spatial arrangement of an island and a typhoon, that of theiris and the covered surface of a human eye, or that of the Earth’s surface receiving
sunlight and a certain latitude zone.

(a)

(b)

Fig. 9. Examples of simple regions with a hole embedded in S2.

The topological relation between a simple region A and a simple region with a hole
B are characterized by the 9+-intersection matrix in Eqn. 4, where ∂1 B , ∂ 2 B , B − ,and B − are B’s outer boundary, hole-side boundary, outer exterior, and hole-side
exterior, respectively. In S2, the outer exterior and the hole-side exterior have nogeometric difference (Fig. 9b) and, accordingly, their distinction depends on theobserver’s view.
1

2⎛ A° ∩ B°⎜
M ( A, B ) = ⎜ ∂A ∩ B°⎜ −⎝ A ∩ B°+[A° ∩ ∂1B A° ∩ ∂ 2 B] [A° ∩ B −[∂A ∩ ∂1B ∂A ∩ ∂ 2 B] [∂A ∩ B −[A ∩ ∂ B A ∩ ∂ B] [A ∩ B
−

−

1

−

2

1

1

−1

]
]
]

A° ∩ B − 2 ⎞⎟∂A ∩ B − 2 ⎟⎟A− ∩ B − 2 ⎠

(4)

14

Yohei Kurata

Instead of the 9+-intersection matrix in Eqn. 4, the same topological regionregion+1H relation is characterized by a pair of the 9-intersection matrices, which
represent the topological region-region relation between A and B’s generalized region
B* and that between A and B’s hole BH, respectively [7, 23]. The patterns of these two
9-intersection matrices are determined uniquely from the pattern of the corresponding
9+-intersection matrix (Fig. 10).
union

union
⎛ A° ∩ B°⎜
M + ( A, B ) = ⎜ ∂A ∩ B°⎜ −⎝ A ∩ B°[A° ∩ B[∂A ∩ B
] [A ∩ B[A° ∩ ∂1B[∂A ∩ ∂1B

A° ∩ ∂ 2 B ]∂A ∩ ∂ 2 B ]A − ∩ ∂1 B A − ∩ ∂ 2 B[⎛ A° ∩ B * ° A° ∩ ∂B * A° ∩ B *− ⎞⎜⎟M ( A, B *) = ⎜ ∂A ∩ B * ° ∂A ∩ ∂B * ∂A ∩ B *− ⎟⎜ A − ∩ B * ° A − ∩ ∂B * A − ∩ B * − ⎟
⎝
⎠

−

−1
−1
−1

]
]
]

A° ∩ B ⎞⎟∂A ∩ B −2 ⎟−2 ⎟−A ∩B ⎠−2⎛ A° ∩ BH ° A° ∩ ∂BH⎜
M ( A, BH ) = ⎜ ∂A ∩ BH ° ∂A ∩ ∂BH⎜⎜ −−⎝ A ∩ B H ° A ∩ ∂B H−
A° ∩ BH ⎞⎟−∂A ∩ B H ⎟−⎟A − ∩ BH ⎟⎠Fig. 10. Conversion from the 9+-intersection matrix for a topological region-region+1H relation
to a pair of the 9-intersection matrices. This figure shows the conversion of the elements in thematrix’s first row. The elements in the second and third rows are converted in the same way.

Fig. 11 shows the topological structures of simple regions and simple regions witha hole embedded in R2 and S2. Based on this structural information and Conditions 19 (i.e., universal constraints), we computationally derived 23 and 37 matrix patterns
for topological region-region+1H relations in R2 and S2, respectively. It is confirmed by
the matrix conversion in Fig. 10 that the former 23 matrix patterns perfectly
correspond to the 23 region-region+1H relations in R2 identified in [7]. Among thelatter 37 matrix patterns, 23 patterns are the same as those for region-region+1H
relations in R2. Meanwhile, we confirmed that each of the remaining 14 matrix
patterns has at least one geometric realization in S2 (Fig. 12). Thus, it is confirmedthat topological region-region+1H relations in S2 consist of 14 relations peculiar to S2(Fig. 12) and 23 relations that are also seen in R2 (see [7] for the list).
interior

B-2D

B-2D

B-2D

B-2D

boundary

L-1D

L-1D L-1D

L-1D

L-1D L-1D

exterior

U-2D

U-2D B-2D

B-2D

B-2D B-2D

Simple Region
in S2

Simple Region
with a Hole in S2

Simple Region Simple Region
in R2
with a Hole in R2

Fig. 11. Topological structures of simple regions and simple regions with a hole, embedded in
R2 and S2.

The 9+-Intersection: A Universal Framework for Modeling Topological Relations15

attachesdisjoint

entwineddisjoint

entwinedmeet

entwinedoverlap

entwinedcovers

entwinedcontains

embracesdisjoint

embracesmeet

embracesoverlap

embracescovers

embracescontains

embracesattaches

embracesentwined

embracesembraces

Fig. 12. 14 topological relations between a region A and a region with a hole B, which are
peculiar to S2, together with an example configuration and its cross section. The name given toeach relation combines the name of the topological relation between A and B’s generalized
region and that between A and B’s hole, following the notation of [7].

In the same way, it is possible to derive the candidates for topological relations
between a basic object and a complicated object (e.g., DLine-region+1H relations), as
well as the relations between two complicated objects (e.g., region+1H-region+1H
relations).

7.

Conclusions

Topological relations, which concern how two objects intersect with each other, havebeen studied for decades in pursuit of cognitively adequate models of the objects’spatial arrangement. The 9+-intersection captures such topological relations in asystematic way using a nested matrix, called the 9+-intersection matrix. This paper
developed a set of universal constraints on the patterns of the 9+-intersection matrix.
These constraints allow us to derive the candidates for the topological relations
between a given pair of objects, regardless of their geometric types. The combinationof the 9+-intersection and the universal constraints is, therefore, highly useful when
we study new sets of topological relations. Indeed, we newly identified DLine-Region
relations in R3, DLine-Line relations in R2, R3, and S2, and region-region+1H relations

16

Yohei Kurata

in S2, as well as found that many sets of topological relations in S1 and S2 areequivalent to those in R1 and R2.
A remaining issue is to answer whether our universal constraints are always
sufficient, in the sense that every pattern of the 9+-intersection matrix, determined by
the universal constraints, always has at least one geometric realization. The
constraints’ sufficiency is empirically confirmed with respect to the relation between
every possible pair of basic objects embedded in R1, R2, R3, S1, and S2. For the
relations between complicated objects, however, it becomes hard to check the validityof all derived matrix patterns due to its large number. Thus, a mathematicalexamination of the constraints’ sufficiency is left for future work.
Acknowledgements
Yohei Kurata’s work is supported by DFG (Deutsche Forschungsgemeinschaft)through the Collaborative Research Center SFB/TR 8 Spatial Cognition. The author
appreciates Dr. Max J. Egenhofer, Dr. Roland Billen, and Dr. Tetsushi Ito for theirhelpful advice and information.

References
1. Egenhofer, M., Franzosa, R.: Point-Set Topological Spatial Relations. International Journalof Geographical Information Systems 5, 161-174 (1991)
2. 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)
3. 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 (1992)
4. Schneider, M., Behr, T.: Topological Relationships between Complex Spatial Objects. ACM
Transactions on Database Systems 31, 39-81 (2006)
5. Kurata, Y., Egenhofer, M.: The Head-Body-Tail Intersection for Spatial Relations between
Directed Line Segments. In: Raubal, M., Miller, H., Frank, A., Goodchild, M. (eds.):
GIScience'06, LNCS, vol. 4197, pp. 269-286. Springer (2006)
6. Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between a
Directed Line Segment and a Region. In: Gottfried, B. (ed.): 1st International Symposiumfor Behavioral Monitoring and Interpretation, pp. 62-76 (2007)
7. Egenhofer, M., Vasardani, M.: Spatial Reasoning with a Hole. In: Winter, S., Duckham, M.,
Kulik, L., Kuijpers, B. (eds.): COSIT'07, LNCS, vol. 4736, pp. 303-320. Springer (2007)
8. Allen, J.: An Interval-Based Representation of Temporal Knowledge. In: Hayes, P. (ed.): 7thInternational Joint Conference on Artificial Intelligence, pp. 221-226 (1981)
9. Zlatanova, S.: On 3D Topological Relationships. In: 11th International Workshop on
Database and Expert Systems Applications, pp. 913-924. IEEE Computer Society (2000)
10.Hornsby, K., Egenhofer, M., Hayes, P.: Modeling Cyclic Change. In: Chen, P., Embley, D.,
Kouloumdjian, J., Liddle, S., Roddick, J. (eds.): Advances in Conceptual Modeling, LNCS,
vol. 1227, pp. 98-109. Springer (1999)
11.Egenhofer, M.: Spherical Topological Relations. Journal on Data Semantics III 25-49 (2005)

The 9+-Intersection: A Universal Framework for Modeling Topological Relations

17

12.Egenhofer, M., Sharma, J.: Topological Relations between Regions in R2 and Z2. In: Abel,D., Ooi, B.C. (eds.): Advances in Spatial Databases: 3rd International Symposium on Large
Spatial Databases, LNCS, vol. 692, pp. 316-336. Springer (1993)
13.Mark, D.: Calibrating the Meanings of Spatial Predicates from Natural Language: LineRegion Relations. In: Waugh, T., Healey, R. (eds.): 6th International Symposium on Spatial
Data Handling, pp. 538-553. Taylor Francis (1994)
14.Nedas, K., Egenhofer, M., Wilmsen, D.: Metric Details of Topological Line-Line Relations.
International Journal of Geographical Information Science 21, 21-48 (2007)
15.Clementini, E., Di Felice, P.: A Model for Representing Topological Relationships between
Complex Geometric Features in Spatial Databases. Information Science 90, 121-136 (1996)
16.Alexandroff, P.: Elementary Concepts of Topology. Dover Publications, Mineola, NY(1961)
17.Egenhofer, M., Franzosa, R.: On the Equivalence of Topological Relations International
Journal of Geographical Information Systems 9, 133-152 (1995)
18.Billen, R., Zlatanova, S., Mathonet, P., Boniver, F.: The Dimensional Model: A Framework
to Distinguish Spatial Relationships. In: Richardson, D., van Oosterom, P. (eds.): 10th
International Symposium on Spatial Data Handling, pp. 285-298. Springer (2002)
19.Mark, D., Egenhofer, M.: Modeling Spatial Relations between Lines and Regions:
Combining Formal Mathematical Models and Human Subjects Testing. Cartography andGeographical Information Systems 21, 195-212 (1994)
20.Renz, J.: A Spatial Odyssey of the Interval Algebra: 1. Directed Intervals. In: Nebel, B.
(ed.): 7th International Joint Conference on Artificial Intelligence, pp. 51-56. Morgan
Kaufmann (2001)
21.Billen, R.: Nouvelle Perception De La Spatialité Des Objets Et De Leurs Relations.
Développment D'une Modélisation Tridimensionnelle De L'information Spatiale.
Department of Geography, Ph.D. Thesis. University of Liège, Liège, Belgium (2002)
22.Pullar, D., Egenhofer, M.: Towards Formal Definitions of Topological Relations among
Spatial Objects. In: Marble, D. (ed.): 3rd International Symposium on Spatial Data
Handling, pp. 225-241 (1988)
23.Egenhofer, M., Clementini, E., Di Felice, P.: Topological Relations between Regions with
Holes. International Journal of Geographical Information Science 8, 129-142 (1994)

Appendix: Proofs of Conditions 1-9 in Section 3
Conditions 1-3:
These three conditions are satisfied because the primitives of a spatial object are
jointly exhaustive, mutually exclusive, and self-connected, respectively.
Conditions 4-5:
These two conditions are basic properties of topology.
Condition 6:
Let Pk be a Pi’s adjacent higher-dimensional primitive. Pk is adjacent to Pi ∩ Qj as
well. On the other hand, Pi ∩ Qj is surrounded entirely by the set of all Qj’s adjacenthigher-dimensional primitives and Q j \ Pi . Accordingly, Pk intersects with at least
one of Qj’s adjacent higher-dimensional primitives or Qj.

18

Yohei Kurata

Condition 7:
Let us consider a subspace of S, called S', which embeds Qj and whose dimension is
the same with Qj. Since Qj contains Pi, S' also embeds Pi. Pi’s adjacent primitives inS', which are always lower-dimensional than Pi, is identical with the set of Pi’s
adjacent lower-dimensional primitives in S. Since Qj contains Pi in S', Qj intersectwith at least one of Pi’s adjacent primitives in S'. Accordingly, Qj intersect with atleast one of Pi’s adjacent lower-dimensional primitives in S.
Condition 8:
Let Q be the set of all of Qj’s adjacent higher-dimensional primitives. Pi ∩ Qj issurrounded entirely by Q and Q j \ Pi . Accordingly, Pi, which contains Pi ∩ Qj andhigher dimensional than Q j \ Pi , intersects with at least one of primitives in Q. Let us
assume that Qj has an adjacent primitive that is bounded, non-looped, and onedimensionally higher than Qj, called Qk. Qk is an element of Q. Let S' be a sub-spaceof S, which embeds Pi and whose dimension is the same with Pi. Since Qj cannot split
the Qk, Qj must be located at the end of Qk. Accordingly, Pi ∩ Qj is not surrounded
entirely by Qk in S', but by the combination of Qk,, some other elements in Q, andQ j \ Pi in S'. On the other hand, Pi ∩ Qj is surrounded entirely by Pi \ Q j and Q j \ Pi
in S'. Consequently, if Qk exists, Pi intersects with not only Qk, but also anotherelement in Q.
Condition 9:
Let Pi be A’s only one unbounded primitive whose dimension is the same with S.
Since Pi’s complement Pi is bounded, each of B’s unbounded primitive is not entirely
included in Pi . Consequently, Pi intersects with B’s unbounded primitives. Note Pi
refers to the exterior of a spatial object in Rn (n ≥ 2).