9-Intersection Calculi for Spatial Reasoning on the Topological
Relations between Multi-Domain Objects
Yohei Kurata
SFB/TR8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany
ykurata@informatik.uni-bremen.de

Abstract
Most spatial calculi target spatial relations between singletype objects, whereas there are also a number of spatialmodels that distinguish spatial relations between objects indifferent domains. How to equip such cross-domain spatialmodels with reasoning capability is left as a research question. As a first step, this paper develops a series of qualitative spatial calculi based on the 9-intersection. The 9intersection distinguishes topological relations between various objects (points, lines, regions, bodies, etc.). We formulate two sorts of calculi: homogeneous 9-intersection calculi
target the topological relations between single-type objects,
while heterogeneous 9-intersection calculi can deal withmultiple sets of topological relations between various combinations of objects. As the foundation of these calculi,
composition tables and lists of converse relations are developed for various sets of topological relations inand .
For heterogeneous 9-intersection calculi, the sets of base relations, composition tables, and list of converse relations areintegrated, such that the algebraic framework of ordinary
single-domain spatial calculi can be reused. Finally, the useof the new calculi is demonstrated.
Keywords: qualitative spatial calculi, topological relations,cross-domain spatial models, 9-intersection, composition
tables

1. Introduction
Qualitative spatial calculi provide reasoning capability forthe models of spatial relations. With these calculi, for instance, incompletely-observed spatial arrangements of objects can be disambiguated with regard to a specific set of
spatial relations. Interestingly, most of existing qualitative
spatial calculi target spatial relations between single-sort
objects. For instance, Allen’s interval algebra [1], Region
Connection Calculus [2], Cardinal Direction Calculus [3],and Double Cross Calculus [4] feature a set of relations between two intervals, two regions, two points, and threepoints, respectively. Such single-domain spatial calculi fit
nicely into an algebraic framework (relation algebra or its
family), since their operations are closed under the single
set of spatial relations. On the other hand, spatial databasecommunities have developed a number of spatial models
that distinguish spatial relations between objects in differ-

ent domains. For instance, the 9-intersection [5] can distinguish the topological relations between a line and a region,in addition to the relations between two regions or thosebetween two lines. In [6], the target of cardinal direction
relations is extended to arbitrary combination of objects(points, lines, and regions). In [7], spatial arrangements ofa path and a landmark are modeled as relations between a
directed line and a region using a Double-Cross-like frameof spatial reference. How to equip such cross-domain spatial models with reasoning capability is left as a researchquestion. For instance, imagine a space where point-likeobjects, line-like objects, and region-like objects coexist.
Given partial knowledge about their arrangement, can we
disambiguate it? If this is possible by computation, the applicability of qualitative spatial calculi will be expanded
considerably.
As a first step, this paper develops a series of qualitative
spatial calculi based on the 9-intersection [5]. These 9intersection calculi consist of homogeneous 9-intersection
calculi, which target a set of topological relations between
single-type objects (e.g., line-line relations), and heterogeneous 9-intersection calculi, which can deal with multiple
sets of topological relations between various combinationsof objects (e.g., mixture of line-line, line-region, and region-region relations). We show that the algebraic framework of ordinary single-domain spatial calculi can bereused for the heterogeneous 9-intersection calculi and,
consequently, we can use existing reasoning tools of spatial calculi, such as SparQ [8] and GQR [9], to conduct
reasoning in the heterogeneous 9-intersection calculi. We
expect that a similar approach achieves reasoning capability in other cross-domain spatial models as well.
A secondary but important challenge of this paper is todevelop composition tables for various combinations of topological relations. The composition table of two topological region-region relations in
is reported in [10], but thetables for other combinations are not fully developed yet.
We therefore develop these composition tables i systematically with a small number of composition rules.
The remainder of this paper is organized as follow: Sections 2 and 3 summarize major concepts of qualitative spatial calculi and the 9-intersection, respectively. Section 4

develops the lists of converse relations and composition
tables for various topological relations. Section 5 develops
the 9-intersection calculi based on these lists and composition tables. Section 6 demonstrates the use of these calculi
for qualitative spatial reasoning. Finally, Section 7 concludes with a discussion of future problems.

2. Qualitative Spatial Calculi
Qualitative spatial calculi (and their lower dimensionalcounterparts, qualitative temporal calculi) have been studied extensively in AI communities [11, 12]. In a broad
sense, qualitative spatial calculi are the calculi formed by aset of spatial relations and operations on these relations.
Typically, binary spatial calculi are equipped with two operations, conversion (converse) and composition, in addition to set-theoretic operations. By conversion we can derive the relation between and from the relation between and , while composition enable us to derive
possible relations between and from the relation between and and that between and . Ternary spatial
calculi also have counterparts of these operations [13].
This paper focuses on binary spatial calculi, since topological relations are binary relations.
Normally each binary spatial calculus targets a jointly
exclusive and pairwise disjoint set of spatial relations that
may hold between two arbitrary objects in a spatial object
domain (points, regions, etc.), including an identity relation. These spatial relations are called base relations and asa set they are denoted .
In order to process incomplete knowledge about spatial
relations, the set of all base relations that may hold between a pair of objects is treated as a unit of computation,
called (general) relation. For instance, if the topologicalrelations between two regions and are known to beandisdisjointRR or meetRR, the relation between
represented as {disjointRR, meetRR}. If nothing is known
about the possible spatial relations between and , therelation between and is represented by the set of allbase relations in , which is called the universal relationand denoted U.
The set of all relations (essentially ’s power-set ) isdenoted . The converse ∪ and the composition ; on are
defined based on those on as equations 1-2. The set ,together with its converse and composition operations
closed under , gives rise to an algebra. Normally, a binary spatial calculus forms a non-associative algebra (oreven its stronger version, a relation algebra or a semiassociative algebra, depending on its associativity [12]).
Actually, from an algebraic point of view, Ligozat andRenz [12] defined a qualitative binary spatial calculus as atuple of a non-associative algebra and its weak representation.
∪

∪

(1)

,

;

;

,

(2)

The merit of such an algebraic treatment is that we cancomputationally disambiguate the relations between many
objects by algebraic computation without paying attention
to actual geometry of the objects. This problem corresponds to a constraint satisfaction problem (CSP). The
CSP’s key question is consistency checking, i.e., to identify the presence or absence of the variables that satisfy thegiven constraints. In spatial calculi, the variables and constraints correspond to spatial objects and their relations, respectively. Through checking algebraic closeness of every
scenario, we can detect invalid combinations of spatial relations that cannot hold between the objects (or the absenceof such combinations). By filtering them out, we can derive the candidates for the possible combinations of spatial
relations between the objects (although at this level wecannot guarantee that all of these candidates are geometrically realizable). There are already some effective tools to
support such constraint-based reasoning on user-defined
spatial/temporal (e.g., SparQ [8] and GQR [9]).

3. The 9-Intersection
The 9-intersection [5] is a model of binary topological relations based on point-set topology [14]. This model has
been studied extensively in spatial database communities,
primarily because it applies to various combinations of objects systematically. In this model, the relations between
two objects are distinguished by certain properties of intersections between their topological parts (interior, boundary, and exterior). The interior, boundary, and exterior ofa spatial object , denoted °, ∂ , and , are defined as
the union of all open sets contained in , the difference between ’s closure (i.e., the intersection of all closed pointsets that contain ) and °, and the complement of ’s
closure, respectively. The 9-intersection matrix in equation
3 concisely represents the 3×3 parts’ intersections between
two objects and .
M

,

∂

°

°
°

∂

°

∂
∂
∂

∂

°
(3)

In the most basic approach, topological relations are distinguished by the presence or absence of these 3×3 intersections. Thus, we consider two-valued 9-intersection matrix whose element are either empty ( ) or non-empty( ). By the patterns of the two-valued 9-intersection matrix, for instance, we can distinguish two point-point relations, three point-line relations, and eight line-line relations(figure 1). Note that by definiin a 1D Euclidian spacetion a point does not have an interior and the line’s boundary refers to the set of its two endpoints.
The set of topological relations distinguished by the pat,terns of two-valued 9-intersection is denotedwhereandare the domains of two objects ( :points, :simple lines, :simple regions, and :simple borefers to thedies) and is the space. For instance,˗(figure 1d). Taset of topological line-line relations inble 1 summarizes the numbers of topological relations distinguished by the patterns of the two-valued 9-intersection
matrix.

equalPPdisjointPP(a)disjointPL

meetPL(b)

insidePL

4. Conversion and Composition
Conversion and composition are fundamental operations ofqualitative spatial calculi. This section develops these two
operations for a variety of topological relations.
is a relation in
The converse of a relation in. For instance, the converse of containsRP in(region-point relations) is insidePR in(point-region relations). We can derive the converse of a
relationinsimply by transposing ’s 9intersection matrix and finding the same pattern from thetwo-valued 9-intersection matrices that represent the rela. By repeating this process for every relations intion in, we can obtain the converse list of,, which shows the mapping fromdenoted CL
toby conversion (e.g., table 2).
Table 2. Converse list of topological point-line relations in).
(∪

disjointLP

meetLP(c)disjointPL
disjointLP

meetPL
meetLP

insidePL
cotainsLP

containsLP

equalLL

overlapLL

disjointLL

meetLL

coversLL

coveredByLL(d)containsLL

insideLL

Figure 1. Topological relations between points, lines, and their
distinguished by the patterns of the twocombinations invalued 9-intersection.
Table 1. Numbers of topological relations distinguished by thepatterns of the two-valued 9-intersection matrix [15].
Point-Point

2

2

2

2

2

Point-Line / Line-Point

3

3

3

3

3

Point-Region / Region-Point

–

3

3

–

3

Point-Body / Body-Point

–

–

3

–

–

Line-Line

8

33

33

11

33

Line-Region / Region-Line

–

19

31

–

19

Line-Body / Body-Line

–

–

19

–

–

Region-Region

–

8

43

–

11

Region-Body / Body-Region

–

–

19

–

–

Body-Body

–

–

8

–

–

and a relaThe composition of a relation intion inis a subset of. The composition
table of two topological relation sets
and,denoted CT, shows the mapping fromto(the power-set of) by composition. In this study, we develop composition tables for the
combination of topological relations between simple ob(i.e., CT
, CT
, CT
, …,
jects in) and for those in(i.e., CT
, …,
CT
CT
).
Given three objects , , and (,,), the following set-theoretic constraints, originally in, always hold for
troduced in [16] for deriving CT
the composition of the topological relation between andand that between and :and ’s topological partdo• ’s topological partnot intersect if has a topological partthat includes
but does not intersect withor that includes
butdoes not intersect with ; andandintersect if has a topological partthat in•and is included inor that intersects
tersects with
withand is included in .
By filtering all relations inwith these constraints,
we obtain the candidates for the composition of the topological relation between and and that between and. Each candidate is examined if they have geometric interpretations. Then, the set of valid candidates are approved as the composition of the topological relation between and and that between and . By repeating this, weprocess for every relation pair inand
can develop the composition table of

(i.e., CT). For instance, table 3 shows the composition table of line-line relations and line-point relations(i.e., CT) derived by this method.
in
Table 3. Composition table of topological line-line relations and().
topological line-point relations in
disjointLP

meetLP

containsLP

equalLL

disjointLP

meetLP

containsLP

disjointLL

ULP

disjointLP

disjointLP

meetLL

ULP

disjointLP / meetLP

disjointLP

overlapsLL

ULP

ULP

ULP

coversLL

disjointLP

disjointLP / meetLP

ULP

coveredByLL

ULP

meetLP / containsLP

containsLP

containsLL

disjointLP

disjointLP

ULP

• If
,
and the relation between and is
LLneither equalLL, disjointLL, meetLL, overlapsLL, coversLL,; andcontainsLL, nor insideLL, then °
,
and
the
relation
betweenand• If
LL
is neither equalLL, disjointLL, meetLL, overlapsLL, co.
versLL, nor containsLL, then °By adding these four constraints, we can successfully derive the composition candidates that have geometric interpretations and, accordingly, we can develop the composition table accordingly, we can develop the composition ta.
ble CT
C
B

C

C

B

B

B
C

According to our investigation, the previous two constraints are sufficient when developing the most composi, …, CT
and CT, …,
tion tables ( CTCT), but not CT—in this case, the derived
composition candidates may have no geometric interpretation. For instance, imagine that there are three simple lines, , and , where contains and crosses (figure 2). Obviously, cannot contain . The constraints inequation 4, however, do not exclude the composition candidate where contains .
C

A

B

B

Figure 2. The arrangements of three lines A, B, and C, fromwhich we can conclude that A cannot contain C.

In general, when contains/covers , cannot contains/covers if:•
directly links ’s interior and exterior (figure 3);•
directly links ’s interior and exterior; or•covers and is inside of (figure 4).
We can tell from the given relations that the first two situations occur whenever the relation between and belong
to the topological line-line relations not realizable in(i.e., the line-line relations other than equalLL, disjointLL,
meetLL, overlapsLL, coversLL, containsLL, and insideLL).
Thus, the previous condition is simplified as follows:• If,
and the relation between and is
LLneither equalLL, disjointLL, meetLL, overlapsLL, coversLL,°
containsLL, nor insideLL, then;,and the relation between and is• If
LLneither equalLL, disjointLL, meetLL, overlapsLL, coversLL,°;
nor containsLL, then
Similarly, the following two constraints hold:

Figure 3. Examples of arrangements where a line C directly connects the interior and exterior of a line B.

ABCFigure 4. If a line A covers a line B and B is inside of a line C,then A cannot contain/covers C.

5. 9-Intersection Calculi
First, to conduct reasoning on topological relations between single-type objects, we introduce homogeneous 9intersection calculi. These calculi are defined for each object domain and each space. The homogeneous 9intersection calculus for the object domain and the space, denoted Homo9IC , is formulated based on the following elements:;• a set of base relations; and• a converse list CL.
• a composition table CT
These elements satisfy the requirements of ordinary qualitative spatial calculi (non-associative algebra); that is,
is jointly exclusive, pairwise disjoint, and contains•
an identity element;
is closed under• the converse operation on∪); and(i.e.,
is closed under• the composition operation on(i.e.,,;).
Consequently, spatial reasoning can be conducted in an algebraic framework.
Next, to conduct reasoning on topological relations between various combinations of objects, heterogeneous 9intersection calculi are introduced. These calculi are developed for each space. The heterogeneous 9-intersectioncalculus for the space , denoted Het9IC , have the ability
to deal with all sorts of simple objects (points, simple lines,
simple regions, and simple bodies) that can contain. Naturally, if is a d-dimension space, Het9IC covers:;,…,• d+1 object domains2• (d+1) sets of topological relations;,• (d+1)2 converse lists3CL• (d+1) composition tables

,

; and

,…,

CT

For instance, Het9IC covers:• two object domains: and ;• four sets of topological relations:
;
and
, CL
• four converse lists: CLCL; and• eight composition tables:
CT
CT
, CT
, …, CT

,…,

, ,

,…,

,

,
CL

,
,

CT

,
, and
,

.

These elements are integrated as follows. First, the geneand the generalized base relations
ralized object domain
are defined as follows:
•
,…,
•

,

,…,

Basicallyrefers to the relations between two arbitrary
objects in, but it also contains an identity relation(). The presence of an identity relation is a requirement of the calculi’s algebraic framework (non-associative
algebra). This identity element is different from domain. In Het9IC , for inlevel identity elements
stance,contains,, and. We did
not integrate these identity elements to prevent senseless;must becompositions. For instance,
empty since the composition of a point-point relation and aline-line
relationis
impossible.
However,;by definition and, acby
cordingly, it is not appropriate to substitute. Thus,is considered a purely abstract relation
with no geometric interpretation (i.e.,,,a jointly exhaustive and). Then, we can consider
pairwise disjoint set of base relations, which is also a requirement of the calculi’s algebraic framework.
Next, we integrate the relevant converse lists and composition tables. The integrated converse list CL
isderived by concatenating the relevant converse lists∪
CLand adding an item “.” For, which is derived frominstance, table 4 shows CL, …, CL. Similarly, the integrated compoCL
sition table CT
is derived by adjoining the relevant composition tables
CTand adding one
row and one column about-related composition. For

instance, table 5 shows CT, …, CT.
from CT, which is derived

Table 4. Integrated converse list
part corresponds to(the highlighted
in Table 2).

∪

∪

equal

equal

equalLL

equalLL

equalPPequalPPdisjointLL

disjointLL

disjointPP

disjointPP

meetLL

meetLLdisjointPL

disjointLP

overlapsLL

overlapsLL

meetPL

meetLP

coversLL

coveredByLL

insidePL

containsLP

coveredByLL

coversLL

disjointLP

disjointPL

containsLL

insideLL

meetLP

meetPL

insideLLcontainsLL

containsLP

insidePL

Now we have:• an integrated set of base relations , which is jointly
exclusive, pairwise disjoint, and contains an identity relation;• an integrated converse listCL, which is
closed under ; and• an integrated composition table CT, which is
closed under .
Consequently, it is expected that spatial reasoning on the
topological relations between arbitrary objects incan beconducted in an algebraic framework, just like we can doin ordinary single-domain spatial calculi. This will bedemonstrated in Section 6.

Simple Assessment of 9-Intersection Calculi
Based on the converse lists and composition tables developed in Section 4, we developed seven basic calculi:
Homo9IC, Homo9IC, Homo9IC,, Homo9IC, Het9IC , and Het9IC .
Homo9IC
We conducted simple assessment of these calculi.
First, for the composition table of each calculus, we calculated the crispness and the ratio of unique compositions(table 5). These two measures are used in spatial databasestudies for assessing the effectiveness of composition
tables [17, 18]. We found that Het9IC and Het9IC
marked high crispness, but this result is not so meaningful
because the integration of composition tables yields the increase of relations not contained in each composition andincreases the crispness. We also found that Homo9IC ’s
ratio of unique compositions was very low. This is because
in many compositions the presence or absence of intersection between two lines’ interiors cannot be determined.
Het9IC ’s ratio of unique compositions was also low, because its composition table has many empty cells that correspond to impossible compositions.

Table 5. Integrated composition table(the highlighted part corresponds toin Table 3;
eq: equal, dj: disjoint, mt: meet, ov: overlap, cv: covers, cB: coveredBy, ct: contains, and in:inside).
eq

eqPP

djPP

djPL

mtPL

inPL

djLP

mtLP

ctLP

eqLL

djLL

mtLL

ovLL

cvLL

cBLL

ctLL

inLL

djLP

mtLP

ctLP

eqLL

djLL

mtLL

ovLL

cvLL

cBLL

ctLL

inLL

UPL
djPL
mtPL
djPL

UPL

djPL
djPL
mtPL
UPL

UPL
mtPL
inPL
inPL

djPL

UPL

djPL

inPL

UPL

inPL

mtLL
djLL
mtLL
ovLL
cBLL
inLL
eqLL
djLL
mtLL
ovLL
cvLL
cBLL
djLL
mtLL
ovLL
cvLL
ctLL

ovLL
djLL
mtLL
ovLL
cBLL
inLL

cvLL

cBLL
djLL
mtLL
ovLL
cBLL
inLL

ctLL

inLL
djLL
mtLL
ovLL
cBLL
inLL

eq

eq

eqPP

djPP

djPL

mtPL

inPL

eqPP

eqPP

eqPP

djPP

djPL

mtPL

inPL

djPP

djPP

djPP

djPP

UPL

UPL

UPL

djPL

djPL

UPP

djPP

djPP

djPL

UPL

mtPL

mtPL

djPP

UPP

djPP

mtPL

djPL

inPL

inPL

djPP

djPP

UPP

inPL

djPL

djLP

mtLP

djLP

mtLP

djLP

mtLP

UPL

UPL

ULL

djLL
mtLL
ovLL
cBLL
inLL
djLL
mtLL
ovLL
cBLL
inLL

ovLL
cvLL
ctLL

ovLL
cBLL
inLL
ovLL
cvLL
cBLL
ctLL
inLL

ctLP

eqLL

eqLL

djLP

mtLP

ctLP

eqLL

djLL

djLL

djLL

ULP

djLP

djLP

djLL

ULL

ULP

djLP
mtLP

mtLL

djLL
mtLL
ovLL
cvLL
ctLL

ovLL

cvLL

cBLL

ctLL

inLL

mtLL

ovLL

cvLL

cBLL

ctLL

inLL

UPL

djLL
mtLL
ovLL
cBLL
inLL

ctLP

mtLL

ctLP

UPL

djLL
mtLL
ovLL
cBLL
inLL
eqLL
mtLL
ovLL
cvLL
cBLL

UPL

ULP

ULP

ULP

mtLP
ctLP

djLP

ULP

djLP

djLP
mtLP

ctLP

djLP

djLP

ULP

ctLP

ULP

ctLP

ULP

ovLL

cvLL

djLL
mtLL
ovLL
cvLL
ctLL
djLL
mtLL
ovLL
cvLL
ctLL

djLL

djLL
mtLL
ovLL
cBLL
inLL

djLL
mtLL

mtLL
ovLL
cBLL
inLL

djLL

ovLL
cBLL
inLL

ULL

djLL
mtLL
ovLL
cvLL
ctLL

ovLL
cBLL
inLL

djLL
mtLL
ovLL
cvLL
ctLL

ovLL
cBLL
inLL

mtLL
ovLL
cvLL
ctLL

ovLL
cvLL
ctLL

cvLL
ctLL

eqLL
ovLL
cvLL
cBLL

ctLL

ovLL
cBLL
inLL

djLL
mtLL
ovLL
cBLL
inLL

eqLL
djLL
mtLL
ovLL
cvLL
cBLL

cBLL
inLL

djLL
mtLL
ovLL
cvLL
ctLL

inLL

ctLL

eqLL
ovLL
cvLL
cBLL
ctLL
inLL

ULL

inLL

cBLL

djLL

djLL
mtLL

ctLL

djLL
mtLL
ovLL
cvLL
ctLL

ovLL
cvLL
ctLL

ovLL
cvLL
ctLL

ctLL

ovLL
cvLL
ctLL

djLL

djLL
mtLL
ovLL
cBLL
inLL

djLL
mtLL
ovLL
cBLL
inLL

inLL

inLL

djLL

djLL

Next, we examined the associativity of the compositions
in each calculus (i.e., whether A; B ; C A; B; C holds
or not) (table 6). We found that Homo9IC
is not associative, and accordingly Het9IC as well. Alternatively,
the compositions in these two calculi satisfy semiassociativity (i.e., A; ;A; ;holds). On theother hand, other five calculi are all associative. One example of non-associativity in Homo9IC
is that(equations 4LL ;
LL ;
LL
LL
6), but
LL ;
LL ;
LL
LL (equations 7-10). This conflict arises from the ambiguity of the. In equation 4, this pattern is inter-patternpreted as diverge&cross&divergedByLL relation (see B and
D in figure 5a), whereas in equation 6 this pattern is interpreted as overlapLL relation (see B and D in figure 5b). Unfortunately, the ambiguity of this pattern is an intrinsic
problem of the 9-intersection.
LL ;6. Examples
This section demonstrates the application of the proposed
9-intersection calculi for qualitative spatial reasoning. We
start from Homo9IC
as the representative of homogeneous 9-intersection calculi.
In the Boston metropolitan area, there are four interstate
highways; I-90, I-93, I-95, and I-495. Their actual network
is like figure 6a, but here we consider a simplified networkin figure 6b. Table 7 lists the topological relations between
the highways in the simplified network. Imagine that wedrive two of these four highways and observe their connections to other highways. For instance, figure 7a/b illustrates
the knowledge obtained from the drive on I-90 and I-95/I93. Based on such knowledge, what can we say about therelations between the remaining two highways? With
Homo9IC, we can derive possible relations between
unvisited highways from partial knowledge about the
highway network.

(4)

LL
LL

LL ;
LL ;

LL ;

LL ;

LL ;

LL

LL ;

LL ;

LL ;

LL ;

LL
LL

LL ;

LL

(7)

LL

LL ;

LL

LL

LL ;

LL

LL

Table 7. Topological relations between pairs of highways in the
network of figure 6b.
crossLL

divergesLL

I-93

divergedByLL–

diverges&crossLL

divergesLL

2

8

2

33

8

17

94

I-95

crossLL

divergedBy&crossLL–

meet-atboth-endsLL

.375

.623

.375

.645

.623

.869

.910

I-495

divergedByLL

divergedByLL

meet-atboth-endsLL

–

.750

.422

.750

.080

.422

.553

.167

√

√

√

√

√

√

√

√

√

√

I-495

divergesLL

Het9IC–

Het9IC ,I-495

Homo9IC

I-95

Homo9IC

I-93

Homo9IC

I-90
Homo9IC.

Homo9IC

and

(a)
(b)
Figure 6. (a) Network of four interstate highways in the Boston
metropolitan area and (b) its simplified version for experiment.

I-90

D

A

I-90

I-95

√

I-495

I-495

√

B
C

(8)
(9)
(10)

LL

I-93

B

(6)

LL

LL
LL

I-90

I-90

Table 6. Properties of 9-intersection calculi for

Number of
relations
Crispness ofcompositions
Ratio ofuniquecomposition
Associativity
SemiAssociativity

(5)

LL
LL

I-90
I-95

D

(a)
(b)
Figure 5. Illustrations of (a) equation 5 and (b) equation 6.

(a)(b)
Figure 7. Partial knowledge about the highway network, obtained
through the drive on (a) I-90 and I-95 and (b)I-90 and I-93.

In addition, we also use the following optional information
to obtain finer solutions:• topological point-region relations between the highway
junctions and the two areas; and• topological line-point relations between the visited
highways and the highway junctions.

Table 8. Possible relations between pairs of unvisited highways
derived as algebraically-consistent scenarios.
Unknown
relation

Derived solution(dv: diverges, dB: divergedBy)(I95, I495)

All but equalLL, coversLL, coveredByLL, containsLL, insideLL(I93, I495)

disjointLL, crossLL, divergesLL, diverges&crossLL
disjointLL, crossLL, divergesLL, diverges&crossLL(I90, I495)

disjointLL, crossLL, divergesLL, diverges&crossLL(I90, I95)

disjointLL, crossLL, divergesLL, diverges&crossLL(I90, I93)

disjointLL, coversLL, coveredByLL, crossLL, meet LL,
meet&crossLL, divergesLL, dv&crossLL, divergedByLL,
dB&crossLL, dv&meetLL, dv&cross&meetLL, dB&meetLL,
dB&cross&meetLL, dv&dBLL, dv&cross&dBLL,
dv&dB&meetLL, dv&cross&dB&meetLL

P5

Urban Area
P3

Next, we enrich the previous map by adding two areas—
Boston city and the urban area (covering the Boston city).
Their spatial arrangement is illustrated in figure 8. Imagine
that we have driven three of the four highways and obtained the knowledge about how the three highways connect to other highways and two areas. Based on suchknowledge, what can we say about the relation between theremaining highway and two districts? For instance, in figure 9a/b, how I-95/I-93 goes with regard to two districts?
To solve this problem, we use Het9IC , since it concerns
the following heterogeneous sets of topological relations:• topological line-line relations between the visited highways;• topological line-region between the visited highways
and the two areas; and• topological region-region relations between the twoareas—
,
.
RR

I-90

P8

Boston City

P7
P4

Figure 8. Spatial arrangement of highways and two districts in
the Boston metropolitan area.
P2

For the scenario in figure 7a, we obtained four possible
relations between I-93 and I-495—disjointLL, crossLL, divergesLL, and diverges&crossLL. This solution look reasonable, since we can say from the given knowledge that (i)both endpoints of I-495 do not intersect with I-93 and (ii)
one endpoint of I-93 do not intersect with I-495. On theother hand, for the scenario in figure 7b, we obtained as
many as 28 possible relations between I-95 and I-495, because from the given knowledge we can only say that I-95
is neither contained nor covered by I-495 and vice versa.

P6

I-90

P6

P7
P4

P8

P1

P2
P5

P5

I-95

P3

P1

P3

P6

I-90

I-93

(I93, I95)

P1

P2

I-95

For actual computation, we put the data of Homo9IC(, CL, and CT) into SparQ [8] and calculate all consistent scenarios under the constraint networkthat follows table 7 but replaces the relations between unvisited highways by ULL. The computation result is shownin table 8. For each pair of unvisited highways we obtained
4 to 28 possible relations. Each solution successfully contained the actual relation in the network of figure 6b.

P8

P7
P4

(a)
(b)
Figure 9. Partial knowledge about the highway network, obtained
through the drive on highways except (a) I-95 and (b) I-93.

For actual computation, we put the data of Het9IC into SparQ and calculated all consistent scenarios under theconstraints described above. We obtained 1 to 16 possible
relations for each scenario (table 9). Each solution successfully contains the actual relations in the highway-districtarrangement of figure 7a.
For the scenario in figure 9a, we obtained a solution inwhich I-95 goes through the urban area, and either goes
through, touches, or avoids the Boston city. This solution
looks reasonable, as we know that (i) both endpoints of I95 are out of the two districts and (ii) I-95 passes throughthe urban area. The solutions for I-90 and I-495 also lookreasonable. The solution for I-93, however, looks strange.
Even though both endpoints of I-93 are located out of theurban area (figure 9b), the derived solution does not filterout such unrealizable relations as
LR I 93, Urban .
This is because the current reasoning process does not use
the commonsense knowledge that the line’s boundary consists of two endpoints, but regard it simply as a point set1
1

On the other hand, in figure 9a, the possibility of
LR I 95, Urban is successfully excluded, because the data already tells that I-95’s boundary is completely contained in I495’s interior.

This indicates that we can still improve the reasoning making use of the structural information of spatial objects.
Table 9. Possible relations between an unvisited highway and two
districts, derived as algebraically-consistent scenarios.
Unknown
relations[(I-495, Urban),(I-495, Boston)]

Derived solution (gTLR: goThroughLR,
gIBELR: goIntoThenBackToEdgeLR)[gTLR, gTLR], [gTLR, touchLR], [gTLR, disjointLR],[touchLR, touchLR], [touchLR, disjointLR],[disjointLR, disjointLR][(I-95, Urban),(I-95, Boston)][gTLR, gTLR], [gTLR, touchLR], [gTLR, disjointLR][(I-93, Urban),(I-93, Boston)][gTLR, gTLR], [goIntoLR, goIntoLR],[goIntoLR, gTLR], [goIntoLR, gIBELR][gIBELR, gTLR], [gIBELR, gIBELR][(I-90, Urban),(I-90, Boston)][goInto, goInto]

7. Conclusions
This paper developed a series of qualitative spatial calculi
based on the 9-intersection [5]. These calculi can be used
for qualitative spatial reasoning on topological relations
between various combinations of objects. Unlike manyother calculi, the heterogeneous 9-intersection calculi areconcerned with situations where multiple sorts of objects
coexist in the same space. However, by integrating sets ofbase relations, composition tables, and converse lists, such
heterogeneity is no longer an obstacle to conduct spatial
reasoning in an algebraic framework.
In this work, we featured the 9-intersection because of
its popularity in spatial database studies. However, the recent extension of the 9-intersection, called the 9+intersection [15, 19], serves as a more flexible framework
for modeling topological relations. For instance, the 9+intersection can distinguish the topological relations between two directed lines in , which can be mapped totemporal relations between two intervals [15]. Thus, if we
extend the 9+-intersection into qualitative spatial calculi,
the resulting 9+-intersection calculi will cover temporalcalculi as well (e.g., Allen’s interval calculus [1]). In addition, the 9+-intersection calculi will support topological relations between a directed line and a point/line/region in
and, accordingly, it will be useful for integrating knowledge about path-landmark arrangements collected by mobile agents. We are planning to develop such 9+intersection calculi and provide a library of both the 9- and9+-intersection calculi on SparQ [8] and CASL [20] forpublic use.
Another interesting future topic is to develop qualitative
spatial calculi that feature non-topological relations (say,cardinal direction relations, relative orientations, distance
relations, etc.) between multi-domain objects. We expectthat we can use similar integration techniques for the development of such heterogeneous spatial calculi.

Acknowledgments
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
1. Allen, J.: Maintaining Knowledge about Temporal Intervals.
Communications of the ACM 26(11), 832-843 (1983)
2. 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)
3. Frank, A.: Qualitative Spatial Reasoning about Cardinal Directions. In: Mark, D., White, D. (eds.): AutoCarto 10.
ACSM/ASPRS (1991)
4. Freksa, C.: Using Orientation Information for Qualitative Spatial Reasoning. In: Frank, A., Campari, I., Formentini, U.
(eds.): International Conference GIS - From Space to Territory:
Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, Lecture Notes in Computer Science, vol. 639,
pp. 162-178. Springer, Berlin/Heidelberg, Germany (1992)
5. 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)
6. Goyal, R., Egenhofer, M.: Consistent Queries over Cardinal
Directions across Different Levels of Detail. In: Tjoa, A.M.,
Wagner, R., Al-Zobaidie, A. (eds.): 11th International Workshop on Database and Expert Systems Applications, pp. 876880 (2000)
7. Kurata, Y., Shi, H.: RfDL: Models for Capturing Directional
and Topological Characteristics of Route-Landmark Arrangements. In: Van de Weghe, N., Billen, R., Kuijpers, B., Bogaert,
P. (eds.): International Workshop on Moving Object (2008)
8. Wallgrün, J.O., Frommberger, L., Wolter, D., Dylla, F., Freksa, C.: Qualitative Spatial Representation and Reasoning in the
SparQ-Toolbox. In: Barkowsky, T., Knauff, M., Ligozat, G.,
Montello, D. (eds.): Spatial Cognition V, Lecture Notes in
Computer Science, vol. 4387, pp. 39-58. Springer, Berlin/Heidelberg, Germany (2006)
9. Gantner, Z., Westphal, M., Wölfl, S.: GQR - a Fast Reasoner
for Binary Qualitative Constraint Calculi. In: AAAI'08 Workshop on Spatial and Temporal Reasoning. AAAI Press (2008)
10. Egenhofer, M., Sharma, J.: Assessing the Consistency ofComplete and Incomplete Topological Information. Geographical Systems 1(1), 47-68 (1993)
11. Cohn, A., Hazarika, S.: Qualitative Spatial Representation
and Reasoning: An Overview. Fundamenta Informaticae 46(12), 1-29 (2001)
12. Ligozat, G., Renz, J.: What Is a Qualitative Calculus? A
General Framework. In: Zhang, C., Guesgen, H., Yeap, W.
(eds.): PRICAI 2004, Lecture Notes in Artificial Intelligence,

vol. 3157, pp. 53-64. Springer, Berlin/Heidelberg, Germany(2004)
13. Zimmermann, K., Freksa, C.: Qualitative Spatial Reasoning
Using Orientation, Distance, and Path Knowledge. Applied Intelligence 6(1), 49-58 (1996)
14. Alexandroff, P.: Elementary Concepts of Topology. Dover
Publications, Mineola, NY, USA (1961)
15. 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)
16. Egenhofer, M.: Deriving the Composition of Binary Topological Relations. Journal of Visual Languages and Computing
5(2), 133-149 (1994)
17. Egenhofer, M.: Spherical Topological Relations. Journal on
Data Semantics III, Lecture Notes in Computer Science, vol.
3534, pp. 25-49, Springer, Berlin/Heidelberg, Germany (2005)
18. Vasardani, M., Egenhofer, M.: Single-Holed Regions: Their
Relations and Inferences. In: Cova, T., Miller, H., Beard, K.,
Frank, A., Goodchild, M. (eds.): GIScience 2008, Lecture
Notes in Computer Science, vol. 5266, pp. 337-353. Springer,
Berlin/Heidelberg, Germany (2008)
19. Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between a Directed Line Segment and a Region.
In: Gottfried, B. (ed.): First International Workshop on Behavioral Monitoring and Interpretation, TZI-Bericht, vol. 42, pp.
62-76. Technogie-Zentrum Informatik, Universität Bremen,
Germany (2007)
20. Astesiano, E., Bidoit, M., Kirchner, H., Krieg-Brückner, B.,
Mosses, P., Sannella, D., Tarlecki, A.: CASL: The Common
Algebraic Specification Language. Theoretical Computer
Science 286(2), 153-196 (2002)