Three-Valued 9-Intersection for Deriving Possible
Topological Relations from Incomplete
Observations

Yohei Kurata
SFB/TR 8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany
ykurata@informatik.uni-bremen.de

Abstract
Topological relations, which concern how two objects intersect, are one of
the most fundamental and well-studied spatial relations. Typically, topological relations are distinguished by the presence or absence of pairwiseintersections between several parts of two objects. However, when an observation is not complete, it is often impossible to determine the presenceor absence of some intersections. In order to support such uncertain situations, this paper introduces three-valued 9-intersection matrix (3-9i matrix), which records the presence, absence, or indeterminate state of thenine types of intersections between the objects. We can use the 3-9i matrix
to describe the spatial arrangement of objects in various scenarios of incomplete observations. In addition, from the pattern of the 3-9i matrix we
can computationally determine a set of topological relations that may holdbetween the objects. We assess the degree of topological information derived from the 3-9i matrix for 14 sets of topological relations between
simple lines, regions, and bodies embedded in ℝ , ℝ , ℝ , 𝕊 , and 𝕊 .

1 Introduction
Topological relations are one class of spatial relations that concern how
two objects intersect with each other in a space. Topological relations have

2

Yohei Kurata

been studied extensively, as they have been considered fundamental for
people’s conceptualization of spatial configurations. In many studies, topological relations were distinguished based on the presence or absence of intersections between several parts of two objects (e.g., Egenhofer and Franzosa 1991; Egenhofer and Herring 1991; Clementini and Felice 1998;
Kurata 2008). However, when an observation is not complete, it is often
impossible to determine the presence or absence of some of the intersections. For instance, look at Fig. 1a, which shows an old Japanese paintingof a battle scene. In the center of this painting, we can see two troop units
facing with each other, but a trailing cloud hides their front lines (Fig. 1b).
So, we are tempted to imagine whether the battle already starts or not—or,geometrically speaking, the areas of the two units are disjoint or meeting.
We sometimes have such incomplete spatial data, such as torn historicalmaps, aerial images with clouds or shadows, and partly-masked maps due
to political reasons. Interestingly, even if the data is not complete, it is often possible to determine a small set of relations (Fig. 2a) or even a uniquerelation (Fig. 2b) that may hold between two objects. So, our interest is
how we can systematically derive such possible relations from incomplete
observations and how crisp they are.

(a)

(b)

Fig. 1. (a) An old Japanese painting of a battle scene, in which the spatial arrangement of two troop units is partly hidden by a cloud, as highlighted in (b)

Æ

(a)

Æ

(b)

Fig. 2. Mappings from partly-masked configurations of two regions to the possible
topological relations between these regions

Three-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
3

In order to characterize incompletely-observed arrangements of spatial
objects from a topological viewpoint, we introduce a three-valued approach to the 9-intersection (Egenhofer and Herring 1991). The 9intersection is a widely-used and well-studied model of topological relations. The three-valued 9-intersection matrix (3-9i matrix) records thepresence, absence, or indeterminate state of 3×3 types of intersections between two objects. We can use the 3-9i matrix to characterize uncertain
spatial arrangements under various scenarios of incomplete observations.
In addition, given a 3-9i matrix, we can computationally determine the setof topological relations that may hold between two objects. This technique
can be used not only for topological region-region relations, but also for avariety of topological relations distinguished by the 9-intersection.
As a simpler version of the 3-9i matrix, the three-valued 4-intersection
matrix (3-4i matrix) was already proposed by Winter (1999). His focus
was to deduce quickly the topological relation between two regions, captures by such a hierarchical partition as a quadtree, by calculating the conjunction of the 3-4i matrices that represent the partial topological relations
between two regions within spatial partitions. Later this approach was extended to vague regions (Winter and Bittner 1999). While their work uses
the 3-4i matrix for representing a partial knowledge of a spatial arrangement, our work uses the 3-9i matrix for representing the total (but incomplete) knowledge of the spatial arrangement. Naturally, we are interested
in the assessment of topological information that the 3-9i matrix can capture in various scenarios of incomplete observations, which are not yet
analyzed before. Also, our target is not only region-region relations in a
2D space, but 14 sets of relations between simple lines, regions, and bodies
in five types of spaces.
This research serves as a complement of qualitative spatial calculi (Ligozat and Renz 2004) on topological relations. Qualitative spatial calculi
are a computational framework of spatial reasoning, by which we can disambiguate the spatial arrangement of multiple objects with respect to a certain relation set. To conduct such reasoning, we need preliminary roughknowledge about possible relations between pairs of the objects. Such preliminary knowledge of topological relations can be derived from incomplete observations by the technique discussed in this paper.
The remainder of this paper is structured as follows: Section 2 reviews
the 9-intersection by which we distinguish topological relations. Section 3
reviews previous studies on topological relations under uncertainty. Section 4 defines the 3-9i matrix and relevant concepts. Section 5 applies the
3-9i matrix to characterize uncertain spatial arrangements under various
scenarios of incomplete observations. Section 6 assesses the degree of to-4

Yohei Kurata

pological information derived from the 3-9i matrices for various sets of topological relations. Finally, Section 7 concludes the discussion.

2 The 9-Intersection
The 9-intersection (Egenhofer and Herring 1991) is a model of topologicalrelations in which the relations are characterized by certain topologicallyinvariant properties of intersections between the topological parts (interior, boundary, and exterior) of two objects. Under point-set topology(Alexandroff 1961), the interior of a spatial object 𝑋, denoted 𝑋°, is defined as the union of all open sets contained in 𝑋, 𝑋’s boundary ∂𝑋 is defined as the difference between 𝑋’s closure (i.e., the intersection of all
closed point sets that contain 𝑋) and 𝑋°, and 𝑋’s exterior 𝑋 is defined as
the complement of 𝑋’s closure. The 9-intersection matrix in Eq. 1 concisely represents the 3×3 types of intersections between two spatial objects 𝐴
and 𝐵 . For simplification, each element in the 9-intersection matrix isrepresented also by 𝑚 (𝐴, 𝐵) where 𝑖, 𝑗 ∈ {1,2,3} . For instance,𝑚 (𝐴, 𝐵) = ∂𝐴 ∩ 𝐵°
𝐴° ∩ 𝐵° 𝐴° ∩ ∂𝐵 𝐴° ∩ 𝐵(1)
M(𝐴, 𝐵) = ∂𝐴 ∩ 𝐵° ∂𝐴 ∩ ∂𝐵 ∂𝐴 ∩ 𝐵
𝐴 ∩ 𝐵° 𝐴 ∩ ∂𝐵 𝐴 ∩ 𝐵
In the most basic approach, topological relations are distinguished simply by the presence and absence of the 3×3 types of intersections. Thus, weconsider a 3×3 matrix with two symbols ∅ and ¬∅, which shows the emptiness and non-emptiness of the 3×3 elements in the 9-intersection matrix.
This matrix is called the two-valued 9-intersection matrix (in short, the 29i matrix) in this paper and denoted M II (𝐴, 𝐵). By the patterns of the 2-9i
matrix, we can distinguish, for instance, eight topological relations between two simple regions in a 2D Euclidian space ℝ (Fig. 3) (Egenhofer
and Herring 1991). Table 1 shows the numbers of topological relations between simple lines, simple regions, and simple bodies in ℝ , ℝ , ℝ , 𝕊(1-sphere), and 𝕊 (2-sphere), distinguished by the patterns of the 2-9i matrix (Kurata 2008). Each topological relation set is denoted 𝓣𝓡𝐃 𝐃 ̵𝒮 ,where 𝐃 and 𝐃 are the domains of the objects 𝐴 and 𝐵 (𝐋:simple lines,
𝐑:simple regions, and 𝐁:simple bodies) and 𝒮 is the class of the space thatembeds 𝐴 and 𝐵. For instance, 𝓣𝓡𝐑𝐑˗ℝ is the set of topological relations
between two simple regions in ℝ .

Three-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
5

∅
∅
¬∅

∅
∅
¬∅

¬∅
¬∅
¬∅

∅
∅
¬∅

disjoint

¬∅
¬∅
¬∅

∅
¬∅
¬∅

∅
∅
¬∅

coveredBy

∅
¬∅
¬∅

¬∅
¬∅
¬∅

meet

¬∅
∅
∅

¬∅
∅
∅

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
∅
∅

overlap¬∅¬∅¬∅

contains

¬∅
¬∅
¬∅

∅
∅
¬∅

¬∅
¬∅
∅

¬∅
¬∅
¬∅

covers

∅
∅
¬∅

¬∅
∅
∅

inside

∅
¬∅
∅

∅
∅
¬∅

equal

Fig. 3. Eight topological relations between two simple regions in ℝ , distinguished by the patterns of the 2-9i matrix (Egenhofer and Herring 1991)
Table 1. Numbers of topological relations between simple lines, simple regions,and simple bodies in ℝ , ℝ , ℝ , 𝕊 , and 𝕊 , distinguished by the patterns of the
2-9i matrix (Kurata 2008)

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

ℝ
8
–
–
–
–
–

ℝ
33
19
–
8
–
–

ℝ
33
31
19
43
19
8

𝕊
11
–
–
–
–
–

𝕊
33
19
–
11
–
–

The 9-intersection has been studied extensively in GIS communities,
because the same framework can be used for modeling a variety of topological relations. However, the 9-intersection cannot capture some topological or metrical characteristics of spatial arrangements, such as thenumber of intersections, and the dimension/degree of intersections, the distinction of the line’s boundary subparts (i.e., start point and end point), andthe distinction of the inner and outer boundary/exterior of holed regions,which may be critical for some applications. Thus, several extensions oralternative approaches of the 9-intersection have been proposed (e.g.,
Egenhofer and Franzosa 1995; Kurata and Egenhofer 2007; Nedas, et al.
2007).

6

Yohei Kurata

3 Handling Topological Relations under Uncertainty
Uncertainty, which comprises such sub-concepts as inaccuracy (lack ofcorrelation with reality) and imprecision (lack of specificity), has been an
important topic in GIS studies, since geographic information is closely
linked with observations of the world (Worboys 2004). Inaccuracy is triggered by measurement errors or low resolution in observations, while theimprecision results from incomplete observations or vagueness. For modeling vague objects whose spatial extent is not clearly definable (e.g.,
mountains), three-valued logic and Fuzzy set theory (Zadeh 1965) havebeen often applied (e.g., Yee 1987; Clementini and Felice 1996; Cohn andGotts 1996; Erwig and Schneider 1997; Schneider 1999). On the other
hand, for handling inaccuracy, probabilistic and statistical approaches havebeen taken (e.g., Burrough 1996; Winter 2000; Tøssebro and Nygård
2002).
Qualitative spatial relations under uncertainty are one of the key topics
in the studies of uncertainty in GIS. The early studies on this topic favored
three-zone approaches, which consider the area that definitely belongs to a
spatial object, the area that may belong to the object, and the area that definitely does not belong to the object, respectively. Cohn and Gotts (1996)
distinguished 46 relations between two regions with such indeterminate
areas, namely egg-yolks, and they identified the mapping from egg-yolk
relations to five topological relations under RCC-5 (Randell, et al. 1992).
On the other hand, based on the 9-intersection (Egenhofer and Herring1991), Clementini and Felice (1996) distinguished 44 topological relations
between two regions with broad boundaries in which the true boundaries
physically or conceptually take place. This band-based approach was
adopted for topological line-line relations (Clementini 2005; Reis, et al.
2006), point-point relations (Lee and Flewelling 2004), and line-region relations (Tang, et al. 2006).
Recently many studies applied Fuzzy logic (Zadeh 1965) for handlingspatial relations between uncertain objects. Molenaar (Zadeh 1965) discussed the topological relations between Fuzzy regions. Each Fuzzy region
was represented by a set of points and their membership to an entity. Alternatively, Du et al. (2005) and Liu and Shi (2009) define Fuzzy interior,boundary, and exterior of spatial objects and described their topologicalrelations within the framework of the 9-intersection. Similarly, Tang et al.
(2006) adopted the framework of the 9-intersection based on the formal
distinction of the interior, boundary, and exterior of Fuzzy n-cells.
Winter (2000) analyzed the topological relations under inaccuracy, instead of vagueness. Given an observation of two regions and its resolution,

Three-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
7

his method enables us to calculate the probability that each topological relation holds between the regions.
In this way, previous studies featured the treatment of vagueness and inaccuracy in topological relations. On the other hand, it seems that topological relations under incomplete observations have not been attracted muchattention.

4 Three-Valued 9-Intersection Matrix
The two-valued 9-intersection records the presence or absence of the 3×3
types of intersections. In order to support the lack of knowledge about thepresence or absence of some of the intersections, we consider a 3×3 matrix
with three symbols {∅, ¬∅, ? }, which shows the emptiness, non-emptiness,or indeterminate state of the corresponding elements in the 9-intersection
matrix (Eq. 1). This matrix is called the three-valued 9-intersection matrix(3-9i matrix). The 3-9i matrix that corresponds to the 9-intersection matrix
M(𝐴, 𝐵) is denoted M III (𝐴, 𝐵). For instance, the configuration in Fig. 4a,
where the presence or absence of interior-interior, interior-boundary,boundary-interior, and boundary-boundary intersections cannot be determined, is characterized by the 3-9i matrix

?
?
¬∅

?
?
¬∅

¬∅
¬∅ . Figs. 4b-c show¬∅

two more examples of uncertain spatial configurations characterized by 39i matrices.

?
?
¬∅

?
?
¬∅
(a)

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
?
¬∅
(b)

¬∅
¬∅
¬∅

¬∅
?
?

¬∅
?
?
(c)

¬∅
¬∅
¬∅

Fig. 4. Three examples of partly-masked configurations of two regions, each characterized by a 3-9i matrix

Among the eight 2-9i matrices that represent the relations in 𝓣𝓡𝐑𝐑˗ℝ(Fig. 3),

∅
∅
¬∅

∅
∅
¬∅

¬∅
¬∅
¬∅

,

∅
∅
¬∅

∅
¬∅
¬∅

¬∅
¬∅
¬∅

, and

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

, which represent

disjoint, meet, or overlap relations, are consistent with the 3-9i matrix
?
?
¬∅

?
?
¬∅

¬∅
¬∅
¬∅

in Fig. 4a; that is,

∅
∅
¬∅

∅
∅
¬∅

¬∅
¬∅
¬∅

,

∅
∅
¬∅

∅
¬∅
¬∅

¬∅
¬∅
¬∅

, and

8

Yohei Kurata

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

correspond to

?
?
¬∅

?
?
¬∅

¬∅
¬∅
¬∅

if we regard each ‘?’ as a wild-card symbol (Winter 1999). This means the actual relation between thetwo regions in Fig. 4a is either disjoint, meet, or overlap (Fig. 5). Similarly, the actual relation between the two regions in Fig. 4b is uniquely de¬∅

¬∅
¬∅
¬∅

termined as overlap, because ¬∅consistent with

¬∅
¬∅
¬∅

¬∅
?
¬∅

¬∅
¬∅
¬∅

=

¬∅

¬∅
¬∅
¬∅

is the only 2-9i matrix that is¬∅¬∅ . Like these examples, given a 3-9i matrix¬∅

M III (𝐴, 𝐵) that characterizes the spatial configuration of two objects 𝐴 and
𝐵 in a space 𝒮, we can derive a set of relations in 𝓣𝓡𝐃 𝐃 ̵𝒮 that may holdbetween 𝐴 and 𝐵, called the candidate relation set, simply by checking theconsistency between M III (𝐴, 𝐵) and every 2-9i matrix that represents a relation in 𝓣𝓡𝐃 𝐃 ̵𝒮 . The operation to derive the candidate relation set iscalled candidate-listing and denoted CL𝓣𝓡𝐃 𝐃 ̵𝒮 . In the previous example,?
?
¬∅

CL𝓣𝓡𝐑𝐑˗ℝ

?
?
¬∅

?
?
¬∅

¬∅
¬∅
¬∅

?
?
¬∅

Æ

∅
∅
¬∅

∅
∅
¬∅

¬∅
∅
¬∅ , ∅
¬∅
¬∅

∅
¬∅
¬∅

¬∅
¬∅
¬∅ , ¬∅
¬∅
¬∅

∅
∅
¬∅

∅
∅
¬∅

¬∅
¬∅
¬∅

∅
∅
¬∅

∅
¬∅
¬∅

disjoint

meet

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

¬∅
¬∅
¬∅

.

¬∅
¬∅
¬∅

overlap

Fig. 5. A 3-9i matrix, which are mapped to three relations in 𝓣𝓡𝐑𝐑˗ℝ by the candidate-listing operation

4.1 Interpretable 3-9i Matrices
The 3-9i matrix may take 3 = 19683 patterns. However, not all patterns
have a candidate relation set. If a 3-9i matrix has a candidate relation set,the matrix is called interpretable.
Let us focus on

∅
∅
¬∅

∅
∅
¬∅

¬∅
¬∅
¬∅

which represents the disjoint relation in

𝓣𝓡𝐑𝐑˗ℝ (Fig. 3). By replacing arbitrary elements in this 2-9i matrix by‘?’, we can obtain 2 = 1024 interpretable 3-9i matrices. Similarly, foreach of the eight 2-9i matrices in Fig. 3, we can obtain 1024 interpretable
3-9i matrices. By integrating these eight sets of 1024 interpretable 3-9i matrices, we can obtain 2946 interpretable 3-9i matrices for 𝓣𝓡𝐑𝐑˗ℝ .

Three-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
9

In general, given a set of n topological relations represented by the 2-9i
matrix M II = 𝑚II
where 𝑘 ∈ {1, ⋯ , 𝑛} , the 3-9i matrix, ∈{ , , }M III = 𝑚III

, ∈{ , , }isinterpretable

if

and

only

if

∃𝑘 ∈ {1, ⋯ , 𝑛} ∀𝑖, 𝑗 ∈ {1,2,3} 𝑚III ∈ 𝑚II , ? .
4.2 Valid 3-9i Matrices
For some sets of topological relations, the 3-9i matrix may have the elements whose value is fixed. For instance, for 𝓣𝓡𝐑𝐑˗ℝ , 𝑚III is always¬∅, because the exteriors of two regions always intersect with each otherin ℝ . Such fixed elements in the 3-9i matrix for a topological relation set
𝓣𝓡 are found simply by comparing the 2-9i matrices that represents therelations in 𝓣𝓡 . Table 2 shows the position and value of the fixed elements in the 3-9i matrix for 14 sets of topological relations.
Obviously, any 3-9i matrix that has ‘?’ at the position of a fixed element
is nonsense, as its value is predetermined as ∅ or ¬∅. Therefore, in the remainder of this paper we consider only valid 3-9i matrices that are interpretable and do not have ‘?’ at the position of any fixed element. For instance, there are 1473 valid 3-9i matrices for 𝓣𝓡𝐑𝐑˗ℝ . Table 2 also shows
the number of valid 3-9i matrices for 14 sets of topological relations. We
can see that a relation set 𝓣𝓡 has a larger number of valid 3-9i matrices
as (i) the 3-9i matrices have fewer fixed elements and (ii) 𝓣𝓡 has a larger
number of relations.
Table 2. The number of relations, the position and value of fixed matrix elements,
and the number of valid 3-9i matrices for 14 sets of topological relations.
Relation set

𝓣𝓡𝐋𝐋˗ℝ
𝓣𝓡𝐑𝐑˗ℝ
𝓣𝓡𝐁𝐁˗ℝ

𝓣𝓡𝐋𝐋˗𝕊
𝓣𝓡𝐑𝐑˗𝕊

𝓣𝓡𝐋𝐑˗ℝ
𝓣𝓡𝐋𝐑˗𝕊
𝓣𝓡𝐋𝐁˗ℝ
𝓣𝓡𝐑𝐁˗ℝ

𝓣𝓡𝐋𝐑˗ℝ

𝓣𝓡𝐋𝐋˗ℝ
𝓣𝓡𝐋𝐋˗ℝ
𝓣𝓡𝐋𝐋˗𝕊

𝓣𝓡𝐑𝐑˗ℝ

Number of
relations

8

11

19

31

33

43

¬∅ ¬∅ ¬∅¬∅ ¬∅ ¬∅

463

562

Fixed
elements in
3-9i matrices
Number ofvalid 3-9i
matrices

¬∅
1473

–

3953

¬∅
2836

¬∅
3016

10

Yohei Kurata

4.3 Hierarchy of 3-9i Matrix Classes
For each topological relation set, the valid 3-9i matrices are categorized into equivalent classes with respect to the candidate-listing operation. For
instance, under 𝓣𝓡𝐑𝐑˗ℝ ,

?
?
¬∅

?
¬∅
¬∅

?
?
? , ?
¬∅
¬∅

?
¬∅
?

categorized into the same class, because
CL𝓣𝓡𝐑𝐑˗ℝ

?
?
¬∅

?
¬∅
?

?
?
¬∅

= CL𝓣𝓡𝐑𝐑˗ℝ

? ?
? ¬∅
? ¬∅

?
?
¬∅

?
? ?
?
? , and ? ¬∅ ? are¬∅? ¬∅ ¬∅?
?
?
=
CL𝓣𝓡𝐑𝐑˗ℝ? ¬∅ ?
¬∅ ¬∅ ¬∅

= {𝑚𝑒𝑒𝑡, 𝑜𝑣𝑒𝑟𝑙𝑎𝑝, 𝑐𝑜𝑣𝑒𝑟𝑒𝑑𝐵𝑦}.

These equivalence classes of 3-9i matrices are called topologicallyequivalent 3-9i matrix classes. For instance, there are 43 topologicallyequivalent 3-9i matrix classes for 𝓣𝓡𝐑𝐑˗ℝ . These classes are jointlyexhaustive and pairwise disjoint. Each class consists of 1 to 177 matrices.
Each topologically-equivalent 3-9i matrix class can be represented by
the corresponding candidate relation set or, alternatively, a representative
3-9i matrix in the class with the fewest ‘?’ elements. For instance, the pre?
?
?
¬∅ ? , and ?
? ¬∅
?
?
?
?
represented by {𝑚𝑒𝑒𝑡, 𝑜𝑣𝑒𝑟𝑙𝑎𝑝, 𝑐𝑜𝑣𝑒𝑟𝑒𝑑𝐵𝑦} or ? ¬∅ ? .
¬∅ ¬∅ ¬∅

vious class that consists of

?
?
¬∅

?
¬∅
¬∅

?
?
? , ?
¬∅
¬∅

?
¬∅
¬∅

?
?
¬∅

is

For each relation set, we can determine partial orders among topologically-equivalent 3-9i matrix classes based on their crispness. For instance,
the class that consists of

?
?
¬∅

∅
¬∅
¬∅

?
?
¬∅

,

?
?
¬∅

∅
¬∅
?

?
?
¬∅

, and

? ∅
? ¬∅
? ¬∅

?
?
¬∅

,

which is represented by {𝑚𝑒𝑒𝑡, 𝑐𝑜𝑣𝑒𝑟𝑒𝑑𝐵𝑦}, is crisper than the previous{𝑚𝑒𝑒𝑡, 𝑜𝑣𝑒𝑟𝑙𝑎𝑝, 𝑐𝑜𝑣𝑒𝑟𝑒𝑑𝐵𝑦} class, because the possibility of overlap relation is excluded. Based on such crispness-based partial orders, we candetermine a hierarchy of the topologically-equivalent 3-9i matrix classes.
For instance, Fig. 6 shows the hierarchy of the topologically-equivalent 39i matrix classes for 𝓣𝓡𝐑𝐑˗ℝ . Each class is represented by both its corresponding candidate relation set (icon) and its representative 3-9i matrix.
We arranged these classes in eight levels, depending on the number of ‘?’elements in their representative 3-9i matrix. This diagram shows:• there are ‘converse’ pairs of topologically-equivalent 3-9i classes, which
are derived from each other by transposing their representative 3-9i matrices (or mirroring their icons);• the converse pairs are located symmetrically across the vertical center;• the converse pairs consist of the same number of 3-9i matrices; andThree-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
11• as the topologically-equivalent 3-9i matrix class becomes crisper, thenumber of ‘?’ elements in the representative 3-9i matrix decreases monotonically.
We can make similar hierarchical graphs for other sets of topological relations, even though the graphs become more complicated. A similar graphis seen in Cohn and Gotts (1996), which shows the hierarchy of 13 clustersof 46 egg-yolk relations. The egg-yolk relations in each cluster correspondto the same subset of five topological relations under RCC-5 (Randell, etal. 1992). These clusters, therefore, correspond to our topologicallyequivalent 3-9i matrix classes. Schilder (1997) also shows a similar hierarchical graph for 82 convex relations on interval relations.

1disjoint
meet
overlap
coverscontains⎛? ? ? ⎞⎜⎟⎜? ? ? ⎟⎜⎟⎝ ? ? ¬⎠

coveredBy
insideequal⎛? φ ? ⎞⎟⎜⎜? ? ? ⎟⎜ ? ? ¬⎟⎠⎝⎛¬ ? ? ⎞⎟⎜⎜? ? ?⎟⎜ ? ? ¬⎟⎠⎝

1

1⎛? ? ?⎞⎟⎜⎜? ? ?⎟⎜ ¬ ¬ ¬⎟
⎠
⎝

3

1

3

11

3

φ⎞
⎟
φ⎟

13

3

⎛¬ ? ? ⎞⎟⎜⎜? ¬ ?⎟⎜ ? ? ¬⎟⎠⎝

1⎛? φ ?⎞⎟⎜⎜? φ ?⎟⎟⎜⎝ ¬ ¬ ¬⎠⎛¬ φ φ ⎞⎜⎟⎜¬ ¬ φ ⎟⎜ ¬ ¬ ¬⎟
⎝
⎠

119

3

7

3

113

⎛ φ φ ¬⎞⎜⎟
⎜ φ φ ¬⎟⎜ ¬ ¬ ¬⎟
⎝
⎠

103

11

⎛ ¬ ¬ ¬⎞⎜⎟
⎜ ? ¬ ¬⎟⎜⎟
⎝ ? ? ¬⎠⎛¬ ? ? ⎞⎜⎟⎜φ ¬ ? ⎟⎜⎟⎝ φ φ ¬⎠

11

95

177

⎛ ¬ ¬ ¬⎞⎟⎜
⎜ ? ? ¬⎟⎟⎜
⎝ ? ? ¬⎠⎛¬ ? ? ⎞⎟⎜⎜φ ? ? ⎟⎟⎜⎝ φ φ ¬⎠

13⎛ ¬ ¬ ¬⎞⎜⎟⎜ ¬ ¬ ¬⎟⎜ ¬ ¬ ¬⎟⎝⎠

⎛ ? ? ¬⎞⎜⎟
⎜ ? ? ¬⎟⎜⎟
⎝ ? ? ¬⎠

⎛ ? ? ¬⎞⎜⎟
⎜ ? ¬ ¬⎟
⎜ ? ? ¬⎟⎝⎠

13

⎛ φ φ ¬⎞⎜⎟
⎜ φ ? ¬⎟⎜⎟⎝ ¬ ¬ ¬⎠

⎛ φ φ ¬⎞⎜⎟⎜ φ ¬ ¬⎟⎜ ¬ ¬ ¬⎟⎝⎠

3

⎛ ? ? ¬⎞⎟⎜⎜φ ¬ ¬⎟⎟⎜⎝ ? ? ¬⎠

3

9

103

? ?⎞
⎟
¬ ?⎟
? ¬ ⎠⎟⎛ ? ? ¬⎞⎟⎜
⎜φ ? ¬⎟⎟⎜⎝ ? ? ¬⎠

⎛ ? ? ¬⎞⎟⎜
⎜ φ φ ¬⎟⎟⎜
⎝ ? ? ¬⎠

9

⎛?
⎜
⎜φ
⎜
⎝?

⎛ ? ? ¬⎞⎟⎜
⎜ ? ¬ ¬⎟⎜ ¬ ¬ ¬⎟⎠⎝⎛¬ φ φ ⎞⎜⎟⎜¬ ? φ ⎟⎜⎟⎝ ¬ ¬ ¬⎠⎛¬ φ φ ⎞⎜⎟⎜¬ φ φ ⎟⎜ ¬ ¬ ¬⎟
⎝
⎠

1

φ ?⎞
⎟
¬ ?⎟
? ¬ ⎠⎟

⎛?
⎜
⎜φ
⎜
⎝?

13

95

⎛¬ ? ? ⎞⎟⎜⎜? φ ?⎟⎜ ? ? ¬⎟⎠⎝

1⎛¬ φ φ ⎞⎜⎟⎜? ¬ φ⎟⎜⎟⎝ ? ? ¬⎠

11

1

⎛ ? ? ¬⎞⎟⎜
⎜ ? ? ¬⎟⎟⎜⎝ ¬ ¬ ¬⎠

7⎛? ? ?⎞⎟⎜⎜φ ? ? ⎟⎜ ? ? ¬⎟⎠⎝

1

1⎛? φ ?⎞⎟⎜⎜? ? ?⎟⎟⎜⎝ ¬ ¬ ¬⎠⎛? φ ?⎞⎟⎜⎜? ¬ ?⎟⎟⎜⎝ ¬ ¬ ¬⎠¬ ⎠⎟⎛¬ ? ? ⎞⎜⎟⎜¬ ¬ ? ⎟⎜⎟⎝ ¬ ¬ ¬⎠

95

1⎛? ? ?⎞⎟⎜⎜? ¬ ?⎟⎟⎜⎝ ¬ ¬ ¬⎠

⎛¬ φ
⎜
⎜? ?
⎜
⎝? ?

⎛¬ ? ? ⎞⎟⎜⎜¬ ? ? ⎟⎟⎜⎝ ¬ ¬ ¬⎠

1⎛? φ ? ⎞⎟⎜⎜φ ? ? ⎟⎜ ? ? ¬⎟⎠⎝⎛? φ ? ⎞⎜⎟⎜? ¬ ? ⎟⎜ ? ? ¬⎟⎝⎠⎛? ? ? ⎞⎟⎜⎜? φ ? ⎟⎜ ? ? ¬⎟⎠⎝⎛? ? ? ⎞⎟⎜⎜? ¬ ? ⎟⎜ ? ? ¬⎟⎠⎝

194⎛¬ φ φ ⎞⎜⎟⎜φ ¬ φ ⎟⎜ φ φ ¬⎟⎝⎠

119⎛ ¬ ¬ ¬⎞⎜⎟
⎜ φ φ ¬⎟
⎜ φ φ ¬⎟⎝⎠⎛ ¬ ¬ ¬⎞⎜⎟
⎜ φ ? ¬⎟⎜⎟
⎝ φ φ ¬⎠

95

⎛ ¬ ¬ ¬⎞⎜⎟⎜ φ ¬ ¬⎟
⎜ φ φ ¬⎟⎝⎠

Fig. 6. The hierarchy of 43 topologically-equivalent 3-9i matrix classes for
𝓣𝓡𝐑𝐑˗ℝ , together with the numbers of 3-9i matrices that form these classes

12

Yohei Kurata

5 Expressing Uncertain Spatial Arrangements with ThreeValued 9-Intersection Matrix
This section demonstrates how the 3-9i matrix is applied to the characterization of spatial arrangements of two objects under several scenarios of incomplete observations. We then assess the degree of topological information derived from the 3-9i matrix in each scenario. Let 𝐴 and 𝐵 refer to thetwo spatial objects whose topological relation is of interest.
Scenario 1: Neutral incomplete observation

In this scenario, any of the 3×3 type of intersections between 𝐴 and 𝐵 has
the risk that its presence or absence cannot be determined. This case may
happen when obstacles (e.g., clouds) hide a part or whole of the interior,boundary, and exterior of each object. In this case, the 3-9i matrix may
take the pattern in Eq. 2. Naturally, all valid 3-9i matrices are the target of
this scenario.
{∅, ¬∅, ? } {∅, ¬∅, ? }M III = {∅, ¬∅, ? } {∅, ¬∅, ? }{∅, ¬∅, ? } {∅, ¬∅, ? }{∅, ¬∅, ? }{∅, ¬∅, ? }{∅, ¬∅, ? }(2)Scenarios 2-3: Observation on the boundary/boundaries

Suppose the observation is conducted only on 𝐴’s boundary, because theobserver’s access is not allowed except 𝐴’s boundary (imagine, for instance, the edge of a volcanic crater or the surface of a planet). By this observation, we can detect the presence or absence of ∂𝐴 ∩ 𝐵∘ , ∂𝐴 ∩ ∂𝐵, and∂𝐴 ∩ 𝐵 , but not others. Accordingly, the 3-9i matrix may take the pattern
in Eq. 3.
?
?
?
(3)
M III = {∅, ¬∅} {∅, ¬∅} {∅, ¬∅}?
?
?
Similarly, if the observation is conducted only on the boundaries of bothobjects, the 3-9i matrix may take the pattern in Eq. 4.
M

III

?
= {∅, ¬∅}?

{∅, ¬∅}{∅, ¬∅}{∅, ¬∅}?
{∅, ¬∅}?

(4)

Three-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
13
Scenarios 4-5: Observation from the boundary/boundaries

Even if the observer’s access is not allowed except 𝐴’s boundary, it issometime possible to observe the neighbor of 𝐴’s boundary (i.e., a part of
𝐴’s interior and that of 𝐴’s exterior) thanks to visibility or the sensor’s effective range. If this is the case, it may be possible to detect the presence of𝐴∘ ∩ 𝐵 ∘ , 𝐴∘ ∩ ∂𝐵, 𝐴∘ ∩ 𝐵 , 𝐴 ∩ 𝐵 ∘ , 𝐴 ∩ ∂𝐵, and 𝐴 ∩ 𝐵 , but not theirabsence because not all part of 𝐴’s interior/exterior can be observed. Accordingly, the 3-9i matrix may take the pattern in Eq. 5.
MIII{¬∅, ? }= {∅, ¬∅}{¬∅, ? }{¬∅, ? }{∅, ¬∅}{¬∅, ? }{¬∅, ? }{∅, ¬∅}{¬∅, ? }(5)

Similarly, if the observation is conducted from the boundaries of bothobjects, the 3-9i matrix may take the pattern in Eq. 6.
MIII{¬∅, ? }{= ∅, ¬∅}{¬∅, ? }{∅, ¬∅}{∅, ¬∅}{∅, ¬∅}{¬∅, ? }{∅, ¬∅}{¬∅, ? }(6)

Scenario 6: Observation from the outside

Suppose 𝐴 and 𝐵 have the same dimension with the space (e.g., two bodies
in ℝ ) and their arrangement is observed from the outside (i.e., somewherein 𝐴 ∩ 𝐵 ). In this case, we can always detect the presence or absence of∂𝐴 ∩ 𝐵 and 𝐴 ∩ ∂𝐵. In addition, it is possible to detect the presence orabsence of ∂𝐴 ∩ ∂𝐵 when 𝐴 is not a part of 𝐵 and vice versa. Consequently, the 3-9i matrix may take the pattern in Eq. 7. Note 𝐴 ∩ 𝐵 , in which
the observer is located, must be non-empty.
?
M III = ?
?

?
?
{∅, ¬∅, ? } {∅, ¬∅}{∅, ¬∅}¬∅(7)

Scenarios 7-8: Position uncertainty of the boundary/boundaries

In this scenario, we cannot precisely determine the spatial position of 𝐴’s
boundary due to blurring, low resolution, inherit vagueness, and so on. As
a consequence, we cannot detect the presence or absence of the intersections related to 𝐴’s boundary. In addition, we cannot determine the ab-14

Yohei Kurata

sence of the intersections related to 𝐴’s interior and exterior. Thus, the 3-9i
matrix may take the pattern in Eq. 8.
M III ={¬∅, ? }?
{¬∅, ? }{¬∅, ? }?
{¬∅, ? }{¬∅, ? }?
{¬∅, ? }(8)

Similarly, if we cannot precisely determine the spatial positions of two
objects’ boundaries, the 3-9i matrix may take the pattern in Eq. 9.
MIII{¬∅, ? }=?
{¬∅, ? }? {¬∅, ? }?
?
? {¬∅, ? }(9)5.1 Modification of Equations
As stated in Section 4.2, the 3-9i matrix may have fixed elements. Accordingly, the 3-9i matrices in Eqs. 2-9 should be modified to accommodate
the fixed elements if they exist. For instance, for 𝓣𝓡𝐑𝐑˗ℝ , 𝑚III is fixedas ¬∅ and, accordingly, the 3-9i matrix in Eq. 2 is modified into Eq. 2'.
MIII{∅, ¬∅, ? }= {∅, ¬∅, ? }{∅, ¬∅, ? }{∅, ¬∅, ? }{∅, ¬∅, ? }{∅, ¬∅, ? }{∅, ¬∅, ? }{∅, ¬∅, ? }
¬∅

(2')

5.2 Assessment of Topological Information Derived in Eight
Observation Scenarios
We have seen eight scenarios of incomplete observations where the 3-9i
matrix can be used for charactering uncertain spatial arrangements of theobjects. An interesting question is how much topological information we
can expect to derive from these incomplete observations. Thus, we conducted the following assessment featuring 𝓣𝓡𝐑𝐑˗ℝ . First, we identified
the sets of 3-9i matrices effective under Scenarios 1-8 (i.e., all valid 3-9i
matrices that satisfy the respective patterns in Eqs. 2-9 except 𝑚III ).
Then, we calculated the average number of relations in a candidate relation
set (i.e., the average number of relations to which the 3-9i matrices are
mapped by the candidate-listing operation) for each scenario. Table 3
shows the result. In Scenarios 7-8 the average numbers of relations in a
candidate relation set is much larger than those in other scenarios. This indicates that the knowledge about the presence or absence of boundary-Three-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
15

related intersections is critical for deriving a crisper set of possible relations. In Scenarios 1-6, on average one candidate relation set contains 1 to
1.45 relations. Considering that 𝓣𝓡𝐑𝐑˗ℝ consists of 8 relations, incomplete observations in Scenarios 1-6 are highly useful for deducing a small
number of possible relations. Especially, the result of Scenario 3 indicatesthat only from the observations on their boundaries of two regions we canuniquely determine their topological relation.
Table 3. Statistics on the mapping from 3-9i matrices to topological relations in
𝓣𝓡𝐑𝐑˗ℝ under eight scenarios of incomplete observations
Scenario
Number of corresponding 39i matrices
Average number of relations
in a candidate relation set

1

2

3

4

5

6

7

8

1473

6

8

78

34

11

32

8

1.39

1.33

1

1.05

1

1.45

2.56

4.25

6 Assessment of Topological Information Derived underDifferent Topological Relation Sets
Section 5.2 assessed the topological information derived from incomplete
observations featuring 𝓣𝓡𝐑𝐑˗ℝ . In this section we extend the target to the
14 sets of topological relations between simple lines, simple regions, andsimple bodies in ℝ , ℝ , ℝ , 𝕊 , and 𝕊 (Table 1). For simplification, here
we focus only on Scenario 1 (neutral incomplete observations), where all
valid 3-9i matrices are relevant to the analysis.
First, for each relation set 𝓣𝓡 , we calculated the average number ofrelations in a candidate relation set, 𝑎𝑣𝑒 . For comparison, we calculated
its standardized index 1 − 𝑎𝑣𝑒 /|𝓣𝓡 |, namely the crispness of mapping,on the analogy of the crispness of compositions in Egenhofer (2005). We
also counted valid 3-9i matrices that are mapped to a unique relation in
𝓣𝓡 , as well as its ratio. The result shown in Table 4 indicates that thecrispness of mapping is very high in any relation set, while the ratios of
uniquely-mapped 3-9i matrices under 𝓣𝓡𝐋𝐑˗ℝ , 𝓣𝓡𝐋𝐑˗𝕊 , 𝓣𝓡𝐋𝐁˗ℝ ,𝓣𝓡𝐑𝐁˗ℝ , 𝓣𝓡𝐋𝐑˗ℝ , 𝓣𝓡𝐋𝐋˗ℝ , 𝓣𝓡𝐋𝐋˗ℝ , 𝓣𝓡𝐋𝐋˗𝕊 , and 𝓣𝓡𝐑𝐑˗ℝ are significantly lower than the others. These nine relation sets have a common
feature: one or both objects are lower-dimensional than the space. Assume
that 𝐴’s dimension is equal to the dimension of the space. In this case, 𝐴’s
boundary forms a Jordan curve and, accordingly, if 𝐵’s topological part 𝑝intersects with 𝐴’s interior and exterior, then 𝑝 also intersects with both
𝐴’s boundary as well. This serves as a constraint on the value of ∂𝐴 ∩ 𝑝 .

16

Yohei Kurata

Conversely, if 𝐴 is lower-dimensional than the space, the value of ∂𝐴 ∩ 𝑝
has more freedom. As a result, 3-9i matrices become more rarely mapped
to a unique relation.
We also counted the valid 3-9i matrices that are mapped to all relations?

in 𝓣𝓡 . The result was always one matrix, ?
?

?
?
?

?
? , for any relation set.
?

Next, we counted the topologically-equivalent 3-9i matrix classes for
𝓣𝓡 . For comparison, the number was standardized by the number of
elements in 𝓣𝓡 ’s power-set (i.e., 2|𝓣𝓡 | ), because each 3-9i matrix classis represented as a subset of 𝓣𝓡 . For instance, there are 43 topologicallyequivalent 3-9i matrix classes for 𝓣𝓡𝐑𝐑˗ℝ , which are only 16.8% of
𝓣𝓡𝐑𝐑˗ℝ ’s power-set. The percentage decreases rapidly as 𝓣𝓡 contains
more relations. This indicates that only slight portion of uncertain states
may occur in actual incomplete observations, especially when the base relation set is large.
Table 4. Statistics on the mapping from 3-9i matrices to topological relations in
14 sets of topological relations
Relation set

𝓣𝓡𝐋𝐋˗ℝ

𝓣𝓡𝐑𝐑˗ℝ
𝓣𝓡𝐁𝐁˗ℝ

𝓣𝓡𝐋𝐋˗𝕊

𝓣𝓡𝐑𝐑˗𝕊

𝓣𝓡𝐋𝐑˗ℝ
𝓣𝓡𝐋𝐑˗𝕊
𝓣𝓡𝐋𝐁˗ℝ

𝓣𝓡𝐑𝐁˗ℝ

𝓣𝓡𝐋𝐑˗ℝ

𝓣𝓡𝐋𝐋˗ℝ
𝓣𝓡𝐋𝐋˗ℝ
𝓣𝓡𝐋𝐋˗𝕊

𝓣𝓡𝐑𝐑˗ℝ# of relations

8

8

11

11

19

19

31

33

43

# of valid
3-9i matrices

1473

1473

3953

3953

463

463

562

2836

3016

Average # ofrelations in a
candidate set

1.39

1.39

1.42

1.42

2.63

2.63

3.53

2.98

3.65

Crispness of
mapping

.826

.826

.870

.870

.862

.862

.886

.910

.915

# of uniquelymapped
3-9i matrices

1016

1016

2694

2694

170

170

134

978

838

% of uniquely-mapped
3-9i matrices

69.0%

69.0%

68.2%

68.2%

36.7%

36.7%

23.8%

34.5%

27.8%

# of 3-9i
matrix classes

116

43

113

113

144

144

552

424

558

% of 3-9i
matrix classes

45.3%

16.8%

5.52%

5.52%

0.03%

0.03%

2.6×
10-5%

4.9×
10-6%

6.3×
10-9%

Note in Table 4 the columns of 𝓣𝓡𝐑𝐑˗ℝ and 𝓣𝓡𝐁𝐁˗ℝ are integrated,because these two relation sets are equivalent with respect to the 9intersection; that is, they consist of the same number of topological relations, which are represented by the same patterns of 2-9i matrices. For thesame reason, the columns of 𝓣𝓡𝐋𝐑˗ℝ , 𝓣𝓡𝐋𝐑˗𝕊 , and 𝓣𝓡𝐋𝐁˗ℝ , and thoseThree-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
17of 𝓣𝓡𝐋𝐋˗ℝ , 𝓣𝓡𝐋𝐋˗ℝ , and 𝓣𝓡𝐋𝐋˗𝕊 are integrated. Surprisingly, the resultof 𝓣𝓡𝐋𝐋˗ℝ and that of 𝓣𝓡𝐑𝐑˗ℝ /𝓣𝓡𝐁𝐁˗ℝ become identical, even though
they are represented by different sets of 2-9i matrices. Similarly, the resultsof 𝓣𝓡𝐋𝐋˗𝕊 and 𝓣𝓡𝐑𝐑˗𝕊 , and those of 𝓣𝓡𝐋𝐑˗ℝ /𝓣𝓡𝐋𝐑˗𝕊 /𝓣𝓡𝐋𝐁˗ℝ and𝓣𝓡𝐑𝐁˗ℝ become identical.
Finally, we investigated the relation between the number of ‘?’ elementsin the 3-9i matrix and the average number of relations in a candidate relation set for 14 sets of topological relations. Interestingly, for every set of
topological relations, the result shows very similar pattern (Fig. 7); that is,
the average number of possible relations increases exponentially as the 39i matrix has more ‘?’ elements. This supports our intuition that the number of ‘?’ elements in the 3-9i matrix serves as a measure of topologicalambiguity.
11
10
9
8
7
6
5
4
3
2 1
1
0

8.00

8
7
6
5

4.00

4
3
2

2.29
1

1.05 1.10 1.18 1.31

0

1

1.60

1
0
2

3

4

5

6

7

8

0

9

11.00

5.50
3.00
1.47
1.04 1.09 1.15 1.25

1𝓣𝓡𝐋𝐋˗ℝ , 𝓣𝓡𝐑𝐑˗ℝ , 𝓣𝓡𝐁𝐁˗ℝ

3

4

5

6

7

8

9

7

8

9

𝓣𝓡𝐋𝐋˗𝕊 , 𝓣𝓡𝐑𝐑˗𝕊

19.00

18

2

1.93

31.00

30

16

25

14
12
10

20

9.50

15.50

15

8
4.91

6
4
2 1

1.33 1.86

7.88

10

2.84

5

0

1

1.51 2.45

0

1

4.25

0
0

1

2

3

4

5

6

7

8

9

2

𝓣𝓡𝐋𝐑˗ℝ , 𝓣𝓡𝐋𝐑˗𝕊 , 𝓣𝓡𝐋𝐁˗ℝ , 𝓣𝓡𝐑𝐁˗ℝ

3

4

5

6

𝓣𝓡𝐋𝐑˗ℝ

33.00

43.00
40

30

35

25

30

20

25

16.50

15

8.72

10
5

21.50

20

15

1

3.26
1.25 1.62 2.23

0

1

11.36

10

5.10

5 1

0

4.15
1.36 1.90 2.75

6.62

0
2

3

4

5

6

7

8

𝓣𝓡𝐋𝐋˗ℝ , 𝓣𝓡𝐋𝐋˗ℝ , 𝓣𝓡𝐋𝐋˗𝕊

9

0

1

2

3

4

5

6

7

8

9

𝓣𝓡𝐑𝐑˗ℝ

Fig. 7. Relations between the number of ‘?’ elements in the 3-9i matrix (x-axis)
and the average number of relations in a candidate relation set (y-axis) for 14 setsof topological relations

18

Yohei Kurata

7 Conclusions
This paper studied the three-valued 9-intersection matrix by which we caneasily represent the spatial arrangement of objects in various scenarios ofincomplete observations, and also we can computationally a set of possible
topological relations that may hold between the objects. We demonstrated
that this candidate set is considerably precise, especially when the 3-9i matrix has fewer ‘?’ elements, for any set of topological relations. This technique for deriving possible topological relations from incomplete observations serves as a complement of qualitative spatial calculi based on the 9intersection, since rough knowledge about possible relations between objects is prerequisite for conducting qualitative spatial inference. In addition, our assessment shows that only slight portion of uncertain states may
occur in actual incomplete observations. This finding is used in qualitative
spatial calculi for reducing the search space considerably, as the calculi
normally consider the power-set of spatial relations as the representation of
all uncertain states of spatial configurations.
The three-valued approach on 4- or 9-intersection can be used also on
various extensions of the 9-intersection, such as the 9+-intersection (Kurata
and Egenhofer 2007; Kurata 2008). The 9+-intersection can capture a larger variety of topological relations, including those related to directed lines,
holed regions, and complex objects. With the three-valued 9+-intersection
matrix, we will be able to process, for instance, uncertain spatial arrangement of motion paths and landmarks or those of temporal intervals underincomplete observations. Thus, the analysis of the three-valued 9+intersection matrix will be also fruitful for practical applications of qualitative spatial reasoning.

References
Alexandroff, P.: Elementary Concepts of Topology. Dover Publications, Mineola,
NY, USA (1961)
Burrough, P.: Natural Objects with Indeterminate Boundaries. In: Bur-rough, P.,
Frank, A. (eds.): Geographic Objects with Indeterminate Boundaries. Taylor& Francis, London, UK, pp. 3-28 (1996)
Clementini, E.: A Model for Uncertain Lines. Journal of Visual Language andComputing 16(4), 271-288 (2005)
Clementini, E., Felice, P.: An Algebraic Model for Spatial Objects with Indeterminate Boundaries. In: Burrough, P., Frank, A. (eds.): Geographic Objects
with Indeterminate Boundaries. Taylor & Francis, London, UK, pp. 155-170(1996)

Three-Valued 9-Intersection for Deriving Possible Topological Relations from
Incomplete Observations
19
Clementini, E., Felice, P.: Topological Invariants for Lines. IEEE Transactions on
Knowledge and Data Engineering 10(1), 38-54 (1998)
Cohn, A., Gotts, N.: The ‘Egg-Yolk’ Representations of Regions with Indeterminate Boundaries. In: Burrough, P., Frank, A. (eds.): Geographic Objects with
Indeterminate Boundaries. Taylor & Francis, London, UK, pp. 171-188(1996)Du, S., Qin, Q., Wang, Q., Li, B.: Fuzzy Description of Topological Relations I: A
Unified Fuzzy 9-Intersection Model. In: Wang, L., Chen, K., Ong, Y. (eds.):
ICNC 2005, Lecture Notes in Computer Science, vol. 3612, pp. 1261-1273.
Springer, Berlin/Heidelberg, Germany (2005)
Egenhofer, M.: Spherical Topological Relations. Journal on Data Semantics III,
25-49 (2005)
Egenhofer, M., Franzosa, R.: Point-Set Topological Spatial Relations. International Journal of Geographical Information Systems 5(2), 161-174 (1991)
Egenhofer, M., Franzosa, R.: On the Equivalence of Topological Relations. International Journal of Geographical Information Systems 9(2), 133-152 (1995)
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)
Erwig, M., Schneider, M.: Vague Regions. In: Scholl, M., Voisard, A. (eds.): 5thInternational Symposium on Advances in Spatial Databases, Lecture Notes in
Computer Science, vol. 1262, pp. 298-320. Springer, Berlin/Heidelberg, Germany (1997)
Kurata, Y.: The 9+-Intersection: A Universal Framework for Modeling Topological Relations. In: Cova, T., Miller, H., Beard, K., Frank, A., Goodchild, M.
(eds.): GIScience 2008, Lecture Notes in Computer Science, vol. 5266, pp.
181-198. Springer, Berlin/Heidelberg, Germany (2008)
Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between
a Directed Line Segment and a Region. In: Gottfried, B. (ed.): First International Workshop on Behavioral Monitoring and Interpretation, TZI-Bericht,
vol. 42, pp. 62-76. Technogie-Zentrum Informatik, Universität Bremen, Germany (2007)
Lee, B., Flewelling, D.: Spatial Organicism: Relations between a Region and a
Spatially Extended Point. In: Egenhofer, M., Freksa, C., Miller, H. (eds.):
GIScience 2004, Extended Abstracts and Poster Summaries, pp. 144-147(2004)
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)
Liu, K., Shi, W.: Quantitative Fuzzy Topological Relations of Spatial Objects by
Induced Fuzzy Topology. International Journal of Applied Earth Observation
and Geoinformation 11(1), 38-45 (2009)20

Yohei Kurata

Molenaar, M.: Fuzzy Spatial Objects. In: Molenaar, M. (ed.): An Introduction to
the Theory of Spatial Object Modelling for GIS. Taylor & Francis, London,
UK, pp. 193-224 (1998)
Nedas, K., Egenhofer, M., Wilmsen, D.: Metric Details of Topological Line-Line
Relations. International Journal of Geographical Information Science 21(1),21-48 (2007)
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)
Reis, R., Egenhofer, M., Matos, J.: Topological Relations Using Two Models ofUncertainty for Lines. In: Caetano, M., Painho, M. (eds.): 7th International
Symposium on Spatial Accuracy Assessment in Natural Resources and Environmental Sciences, pp. 286-295 (2006)
Schilder, F.: A Hierarchy for Convex Relations. In: 4th International Workshop on
Temporal Representation and Reasoning, pp. 86-93. IEEE Computer Society(1997)
Schneider, M.: Uncertainty Management for Spatial Data in Databases: Fuzzy
Spatial Data Types. In: Güting, R.H., Papadias, D., Lochovsky, F. (eds.): 6thInternational Symposium on Advances in Spatial Databases, Lecture Notes in
Computer Science, vol. 1651, pp. 330-351. Springer, Berlin/Heidelberg, Germany (1999)
Tang, X., Fang, Y., Kainz, W.: Fuzzy Topological Relations between Fuzzy Spatial Objects. In: Wang, L., Jiao, L., Shi, G., Li, X., Liu, J. (eds.): 3rd International Conference on Fuzzy Systems and Knowledge Discovery, Lecture
Notes in Computer Science, vol. 4223, pp. 324-333. Springer, Berlin/Heidelberg, Germany (2006)
Tøssebro, E., Nygård, M.: An Advanced Discrete Model for Uncertain Spatial Data. In: Meng, X., Su, J., Wang, Y. (eds.): 3rd International Conference on
Web-Age Information Management, Lecture Notes in Computer Science, vol.
2419, pp. 37-51. Springer, Berlin/Heidelberg, Germany (2002)
Winter, S.: Topological Relations in Hierarchical Partitions. In: Freksa, C., Mark,D. (eds.): COSIT'99, Lecture Notes in Computer Science, vol. 1661, pp. 141155. Springer, Berlin/Heidelberg, Germany (1999)
Winter, S.: Uncertain Topological Relations between Imprecise Regions. International Journal of Geographical Information Science 14(5), 411-430 (2000)
Winter, S., Bittner, T.: Hierarchical Topological Reasoning with Vague Regions.
In: Shi, W., Goodchild, M., Fisher, P. (eds.): International Symposium on
Spatial Data Quality '99, pp. 555-565. Hong Kong Polytechnic University,
Hong Kong, China (1999)
Worboys, M.: Spatial Reasoning and Uncertainty. In: Worboys, M., Duckham, M.
(eds.): GIS: A Computing Perspective. CRC Press, Boca Raton, FL, USA, pp.
323-358 (2004)
Yee, L.: On the Imprecision of Boundaries. Geographical Analysis 19(2), 125-151(1987)
Zadeh, L.: Fuzzy Sets. Information and Control 8, 338-353 (1965)