9+-Intersection Calculi for Spatial Reasoning on the
Topological Relations between Heterogeneous Objects
Yohei Kurata
Tokyo Metropolitan University
1-1 Minami-Osawa, Hachioji
Tokyo 192-0397, Japan+81-42-677-1111

ykurata@tmu.ac.jp

ABSTRACTThis paper develops a series of qualitative spatial calculi thatfeature topological relations based on the 9+-intersection. Whilemost qualitative spatial calculi have targeted spatial relations
between single-type objects, our calculi support spatial relations
between heterogeneous pairs of objects. We generalize the rules
for deriving compositions of topological relations. As a result, avariety of composition tables can be generated systematically as afoundation of our new calculi. By integrating all relevant sets of
topological relations, composition tables, and lists of converse
relations, the algebraic framework of ordinary qualitative spatial
calculi is successfully reused in our calculi for conducting spatial
reasoning. We demonstrate that our 9+-intersection calculi realize
finer reasoning than the former 9-intersection calculi.

Categories and Subject Descriptors
H.2.8 [Database Management]: Database Applications – spatial
database and GIS

General Terms
TheoryKeywords

topological relations, heterogeneous objects, 9+-intersection,
qualitative spatial reasoning, qualitative spatial calculi

1. INTRODUCTION
Topological relations, which essentially concern how two objects
connect or overlap, are one of the most studied sorts of spatial
relations in GIS communities. This paper develops a series ofqualitative spatial calculi (QSC) that target the topologicalrelations. QSC are the frameworks of qualitative spatial reasoning,with which we can detect inconsistency in the information about
possible relations between a set of objects and, if inconsistency is
not detected, we can further refine these possible relations. The
remarkable feature of our QSC is the ability to conduct spatial
reasoning even when the objects are heterogeneous (i.e., a mixtureof points, lines, and regions). Usually QSC target spatial relations
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. To copy
otherwise, or republish, to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.
ACM GIS '10, November 2-5, 2010. San Jose, CA, USA(c) 2010 ACM ISBN 978-1-4503-0428-3/10/11...$10.00

between single-type objects. For instance, Allen’s interval algebra[1], Region Connection Calculus [2], Cardinal Direction Calculus[3], and Double Cross Calculus [4] target the relations between
two intervals, two regions, two points, and three points,
respectively. Such calculi nicely fit into an algebraic frameworkand thus, spatial reasoning is achieved by algebraic computation(Section 3). In geographic contexts, however, we often deal withthe relations between geographic features of different geometric
types. Naturally, a question arises as to how we can disambiguatespatial arrangements of such heterogeneous objects. We answer
this question with regard to topological relations.
In GIS communities, both the 9-intersection [5] and Region
Connection Calculus [2] have been frequently used as models of
topological relations. This work targets the topological relations
distinguished by the 9+-intersection [6, 7], which is a refinementof the 9-intersection. Under the 9+-intersection, we can semiautomatically identify sets of topological relations, as well as theirconceptual neighborhood graphs, for arbitrary pairs of objects [7,8]. This paper shows that the 9+-intersection also allows us togeneralize the rules for deriving the compositions of topologicalrelations and accordingly, the composition tables, used as a basisof qualitative spatial reasoning, can be derived systematically.
This is a great advantage of the 9+-intersection, because under the
9-intersection the composition tables have been developed foreach pair of relation sets in an ad-hoc way. Another advantage isthat we can represent and reason on spatial arrangements ofobjects more precisely than the 9-intersection.
The remainder of this article is structured as follows: Sections 2-3
introduce the 9+-intersection and basic concepts of QSC,
respectively. Section 4 develops the 9+-intersection calculi.
Section 5 demonstrates the use of our new calculi for qualitative
spatial reasoning. Finally, Section 6 concludes the discussion. In
this article, lines and regions refer to simple lines and simple
regions [9], respectively. We distinguish two terminal points ofeach line, which we tentatively call the start point and end point,
but this does not mean that the line should have directionality.

2. 9+-INTERSECTION

Both the 9-intersection [5] and the 9+-intersection [6, 7] presume
the distinction of topological parts (interior, exterior, andboundary) of each object. In this paper, the interior, exterior, andboundary of a n-dimensional spatial object X embedded in a space, and ∂ , are defined as the union of all n, denoted °,dimensional open sets contained in X, the union of all open setsthat do not intersect with X, and the difference between theand °, respectively. By this definition, thecomplement ofboundary of a region and that of a line always refer to the region’sbounding edge and the line’s two endpoints, respectively,
regardless of the dimension of .
Given two objects A and B embedded in , the 9-intersection
characterizes the topological relation between A and B based on
the topological properties of the 33 set intersections between the
topological parts of A and those of B. These 33 set intersections
are concisely represented in the 9-intersection matrix (Equation 1).
Usually, topological relations are distinguished simply by the
emptiness/non-emptiness of these 33 set intersections, which wecall the 9-intersection pattern.
M

°∩ °
∂ ∩ °
∩ °

,

°∩∂
∂ ∩∂
∩∂

°∩
∂ ∩
∩

(1)

In the 9-intersection, the distinction of the line’s two terminal
points is lost. This motivated the extension of the 9-intersection
by considering the set intersections between the topologicalprimitives [6], which are self-connected and mutually-separated
subparts of the objects’ topological parts. For instance, theboundary of a simple line L consists of two primitives (the startpoint ∂ and the end point ∂ ), while the interior and exterior ofL, and the interior, exterior, and boundary of a simple region R,
consist of one primitive each. Hence, the topological relation
between L and R is characterized by a refined 9-intersection
matrix in Equation 2, and the topological relations are
distinguished by the emptiness/non-emptiness of the set
intersections in this matrix, called the 9+-intersection pattern.

3. QUALITATIVE SPATIAL CALCULIQSC have been studied extensively in AI communities [10]. EachQSC features a specific JEPD (jointly-exhaustive and pairwise
disjoint) set of qualitative spatial relations. A binary QSC, whichfeatures the relations between two objects, normally supports
converse and weak/strong composition operations, in addition to
ordinary set-theoretic operations. Let r and s be the spatial relation
between A and B and that between B and C. The converse of ,denoted ˘, gives the spatial relation between B and A (usuallyuniquely determined). The weak composition of and , denoted⋄ , gives the set of all spatial relations that may hold between A
and C. The weak composition ⋄ is an upper approximation of
the strong composition ∘ defined in Equation 3.
∘

,

∈

|∃ ∈

,

∈ ∧

,

M

,

°∩∂
∂ ∩∂
∂ ∩∂
∩∂

°∩
∂ ∩
∂ ∩
∩

(2)

Given two object domains DA and DB and a space , the sets of
topological relations that may hold between an object in DA andan object in DB, distinguished by the 9- and 9+-intersection
patterns, are denoted̵ and̵ , respectively. For
is the set of topological line-region relations ininstance,̵
distinguished by the 9+-intersection patterns. Note that P, L, R,
and B represent the domains of points, lines, regions, and bodies.
Table 1 lists the numbers of topological relations between all pairsof objects distinguished by the 9- and 9+-intersection patterns [7].
Table 1: Numbers of topological relations distinguished by the9-/9+-intersection patterns [7] ( : n-dimensional Euclidian
space, :n-sphere, P:point, L:line, R:region, B:body)
RelationType
P-P
P-L/L-P
P-R/R-P
P-B/B-P
L-L
L-R/R-L
L-B/B-L
R-R
R-B/B-R
B-B

9+-intersection

9-intersection
2
3
–
–
8
–
–
–
–
–

2
3
3
–
33
19
–
8
–
–

2
3
3
3
33
31
19
43
19
8

2
3
–
–
11
–
–
–
–
–

2
3
3
–
33
19
–
11
–
–

6
10
–
–
26
–
–
–
–
–

2
4
3
–
80
26
–
8
–
–

2
4
3
3
80
45
26
43
19
8

2
4
–
–
28
–
–
–
–
–

(3)

The relations that each QSC features are called base relations anddenoted as a set. Many QSC also consider the general relations,each referring to a subset of . By introducing such generalrelations, every state of knowledge about the possible spatial
relations between two objects is represented by a single generalrelation. For instance, if we know that A is north or northeast of B,
this state is represented by a general relation {north, northeast}.
The set of all general relations for (i.e., the power set of ) isdenoted. The converse and composition operations on
aredefined based on those on
as Equations 4-5. Naturally, theconverse and composition on is closed under .
∀

∈

˘

˘

(4)

∈

°∩ °
∂ ∩ °
∂ ∩ °
∩ °

∈

∀ ,

∈

;

⋄
∈

∈

(5)

The set , together with its converse and composition operations,gives rise to an algebra. Normally, a binary QSC forms a nonassociative algebra or its stronger form. Such an algebraic
framework allows us to conduct spatial reasoning by computation.
Spatial relations that cannot hold between objects are removed ina stepwise manner by enforcing the constraint of algebraic
closure [10]. There are already some tools for conducting suchspatial reasoning on user-defined QSC (e.g., SparQ [11]).

4. 9+-INTERSECTION CALCULI
Following the framework of QSC sketched in the previous section,
we formulate a series of qualitative spatial calculi that target the
9+-intersection-based topological relations. As a foundation, we
first develop converse and composition operations on the 9+intersection-based topological relations.

4.1 Converse
2
4
3
–
80
26
–
11
–
–

By converse, a topological relation in̵ is mapped to a
topological relation in̵ . The converse list CL ̵shows the mapping from̵ to
̵ by converse
operation. The converse lists of the 9+-intersection-based
topological relations are derived very easily, because for any
relation inand ˘ are represented by a pair of̵ ,transposed 9+-intersection patterns.

4.2 Composition
By composition operation, a pair of a topological relation in̵ and that in̵ is mapped to a subset of̵ .
The composition table CT ̵
̵ shows the mapping fromby composition̵̵ to the power-set ofoperation. The composition table is derived as follows: first, foreach pair of∈∈, we prepare all
̵ and
,
,
∈
.
Then,
we removewheretuples of̵the tuples that do not satisfy some geometric constraints. Afterin each remaining tuple becomes athis filtering process,candidate for an element of the composition ofand. Eachcandidate is approved if we can find an instance of thecomposition by sketching. By repeating this process for every pairofand, we can obtain the composition tableCT ̵̵ .
For the filtering process, we use the following four geometricconstraints. Suppose that three objects A, B, and C (AD1,
BD2,CD3) are embedded in the space . Let X, Y, and Z be
arbitrary sets of topological primitives of A, B, and C (in arbitraryorder). Then, we have the following two constraints:
Constraint 1: If X contains Y and Y intersects with Z, then X andZ intersect.
(Proof) Let ∈ ∩ . Naturally, ∈ and∈ . Thus, ∈ ∩ , which indicates that

∈ . Since
∩
∅.

⊆ ,

Constraint 2: If X contains Y and X does not intersect with Z, thenY and Z do not intersect.
(Proof) Let ∈ . Since ⊆ , ∈ . Meanwhile, since∩∅, ∈ implies ∉ . Therefore, ∩∅.
Similarly, let x, y, and z be arbitrary topological primitives of A, B,
and C (in arbitrary order). Then, we have the following two
constraints:
Constraint 3: If x contains both y and z, x and y are of the same
dimensionality, and z partially overlaps with y, then z alsointersects with at least one of the adjacent lower-dimensional
primitives of y (Figure 1a).
(Proof) Since x contains both y and z, x can be regarded as a subspace of that embeds y and z. If ⊂ , y is bounded on thespace x by the adjacent lower-dimensional primitive(s) of y, sincex and y are of the same dimension. Thus, if z overlaps y, z must
intersect with the bound of y formed by the adjacent lowerdimensional primitive(s) of y. On the other hand, yis notpossible, since z cannot overlap with y.
Constraint 4: If x contains y, y contains z, and the adjacent lowerdimensional primitives of y and those of z do not intersect, thenthe adjacent lower-dimensional primitives of x and those of z also
do not intersect (Figure 1b)(Proof) Let
be the set of adjacent lower-dimensional⊂
primitives of a primitive p. In general, ⊆ implies∪. In this case,∩∅. Thus,⊂ y.
Since ⊆ ,⊂ x. Since ∩∅,∩∅.

4.3 9+-Intersection Calculi

9+-intersection calculus for a space , denoted 9 , is a QSC thattargets the 9+-intersection-based topological relations between
is built on:
arbitrary simple objects embedded in . Hence, 9

d+1 object domains
, and
;



(d+1)2 sets of topological relations

(d+1)2 converse lists CL ̵(d+1)3 composition tables CT ̵

,

;
; and
.

where , , ∈ 0, … , . These elements are adapted to theframework of ordinary QSC using a technique proposed in [12].
First, we introduce a generalized object domain D* and a set ofgeneralized base relations * as follows:


∗



∗

⋃ ∈ ,…,⋃ ∈ ,…,∪∗*

refers to all topological relations between two arbitrary objects
in D*. * also contains a global identity relation eq*. The presenceof an identity relation is a requirement of the algebraic framework(non-associative algebra) of QSC. At the same time, we decided
to keep domain-level identity relations (,, …), because
the reasoning power is reduced if they are replaced by the global
identity relation. For instance, the composition of any point-point
relation and any line-line relation is impossible and accordingly,;∅ whereis an arbitrary line-line relation. Thisknowledge is lost if
is replaced by eq*, since ∗ ;.
Theoretically speaking, the relations in * must be pairwise∗. To hold this property, eq* must be virtual,disjoint over ∗in the sense that it satisfies ∗ ;; ∗, but has nogeometric interpretation; in other words, we always use domainlevel identity elements for representing equality of two objects.
Next, the converse list and composition table for * are prepared.
The converse list CL ̵
is derived simply by∗ ∗̵
concatenating all relevant converse lists CL ̵
and
̵∗
adding an item that indicates ∗ ˘(See [12]). Similarly, thecomposition table CT ̵
is derived simply by adjoining∗ ∗ ∗̵
all relevant composition tables CT ̵
and adding a̵∗⋄and a column that indicates
row that indicates
for any relation r in
[12].
⋄ ∗
∗ ∗̵
Now we have a set of base relations * and converse andcomposition operations on *. These elements satisfy theframework of ordinary qualitative spatial calculi. Consequently,
constraint-based spatial reasoning on topological relations
between any simple objects can be conducted by algebraic
computation.

5. DEMONSTRATION(a)(b)
Figure 1. Example configurations for Constraints 3-4

,

where

,…,

This section demonstrates how the 9+-intersection calculi work in
spatial problem solving. We consider the highway network in the
Boston metropolitan area (Figure 2a). Imagine that we drive threeof the four highways in this area and infer the connection between
the remaining highway and Boston’s two districts. For instance,
when we have driven I-90E, I-95S, and I-495S and obtained theknowledge illustrated in Figure 2b, we can expect that I-93S goes
through the two districts. To solve the problems, we use 9,
since we have to deal with highway-highway, highway-district,and highway-junction connections, which are represented by
topological line-line, line-region, and line-point relations in,
respectively. We also use the information about district-district
relations (Boston urban district covers Boston municipal district),
district-junction relations (which are observable from highways),and junction-junction relation (disjoint). For computation, we firstregister the data of 9
to SparQ [11]. Then, for each drive
scenario, we input all topological relations in Figure 12a, except
the relations between the unvisited highway we have assumed andthe two districts, and compute all consistent scenarios in SparQ.
The derived consistent scenarios show the candidates for the pairof topological relations between the unvisited highway and thetwo districts. These candidates successfully contained the actual
pair of relations. For instance, when we assumed the drive on I90E, I-95S, and I-495S (Figure 2b), we obtained only one correct
solution in which I-93S goes through the two districts. Table 2
shows the numbers of the derived candidates, in comparison withthose derived by the corresponding 9-intersection calculus (which
we call 9 ) [12]. When we assumed the drive except I-93S, 9
gave a unique result, while 9 did not. As pointed out in [12], the9-intersection omits the information that each line has exactly two
endpoints and accordingly, 9 derives invalid candidates which
presume that the line has more than two endpoints. This problem
is successfully avoided under 9, thanks to the clear distinctionof the line’s two endpoints. In the other three drive scenarios, thenumbers of the candidates derived by 9
and 9 are the same.
This indicates that the results of 9
are actually more
informative, since they capture directional characteristics of
highway-district relations (e.g., entering or leaving).

that target heterogeneous objects, such as topological line-region
relations [6] and generalized cardinal direction relations [13].
How to equip such models with the capability of spatial reasoning
has been left as a research challenge. In this paper, one of suchmodels, the 9+-intersection, was built into the existing frameworkof QSC. The resulting 9+-intersection calculi enable us todisambiguate spatial arrangements of heterogeneous objects froma topological viewpoint. The 9+-intersection calculi realize finerreasoning than the 9-intersection calculi [12] when the target
includes lines, or potentially any object whose interior, boundary,or exterior consists of multiple subparts.

REFERENCES[1] Allen, J. Maintaining knowledge about temporal intervals.
Communications of the ACM, 26, 11 (1983), 832-843.
[2] Randell, D., Cui, Z. and Cohn, A. A spatial logic based onregions and connection. In Intl. Conf. on Knowledge
Representation and Reasoning (San Mateo, CA, USA, 1992).
Morgan Kaufmann, San Francisco, CA, USA.
[3] Frank, A. Qualitative Spatial Reasoning about Cardinal
Directions. In AutoCarto 10 (Baltimore, MD, USA, 1991).
ACSM/ASPRS.
[4] Zimmermann, K. and Freksa, C. Qualitative Spatial
Reasoning Using Orientation, Distance, and Path Knowledge.
Applied Intelligence, 6, 1 (1996), 49-58.
[5] Egenhofer, M. and Herring, J. Categorizing binary
topological relationships between regions, lines and points in
geographic databases. NCGIA Technical Reports 91-7.
[6] Kurata, Y. and Egenhofer, M. The 9+-intersection for
topological relations between a directed line segment and aregion. In Workshop on Behaviour Monitoring andInterpretation (Osnabrück, Germany, 2007). TZI-Bericht 42.
TZI, Universität Bremen, Germany.
[7] Kurata, Y. The 9+-Intersection: A Universal Framework for
Modeling Topological Relations. In GIScience 2008 (Park
City, Utah, USA, 2008). LNCS 5266. Springer.
[8] Kurata, Y. Semi-automated Derivation of Conceptual
Neighborhood Graphs of Topological Relations. In COSIT
2009 (Abe Wrac'h, France, 2009). LNCS 5756. Springer.

(a)(b)
Figure 2. (a) Spatial arrangement of highways, junctions, andtwo districts in Boston metropolitan area and (b) information
obtained by the drive on I-90E, I-95S, and I-495S
Table 8. Number of candidates for the topological relations
between the unvisited highway and two districts
I-90E

Unvisited Highway
I-93S
I-95S

I-495S

9

1

1

3

6

9

1

6

3

6

6. Conclusions
In geographic contexts, we sometimes deal with heterogeneous
objects whose spatial arrangement is of concern. Naturally, GIS
communities have developed a number of spatial relation models[9] Schneider, M. and Behr, T. Topological Relationships
Between Complex Spatial Objects. ACM Transactions on
Database Systems, 31, 1 (2006), 39-81.
[10] Ligozat, G. and Renz, J. What is a Qualitative Calculus? A
General Framework. In PRICAI 2004 (Auckland, New
Zealand, 2004). LNAI 3157. Springer.
[11] Wallgrün, J. O., Frommberger, L., Wolter, D., Dylla, F. andFreksa, C. Qualitative Spatial Representation and Reasoning
in the SparQ-Toolbox. In Spatial Cognition V (Bremen,
Germany, 2006). LNAI 4387. Springer.
[12] Kurata, Y. 9-Intersection Calculi for Spatial Reasoning on
the Topological Relations between Multi-Domain Objects. In
IJCAI Workshop on Spatial and Temporal Reasoning(Pasadena, CA, USA, 2009). AAAI Press.
[13] Goyal, R. and Egenhofer, M. Consistent Queries overCardinal Directions across Different Levels of Detail. In Intl.
Workshop on Database and Expert Systems Applications(Greenwich, UK, 2000).