The Head-Body-Tail Intersection for
Spatial Relations Between Directed Line Segments
Yohei Kurata and Max J. Egenhofer
National Center for Geographic Information and Analysis
andDepartment of Spatial Information Science and Engineering
University of Maine
Boardman Hall, Orono, ME 04469-5711, USA{yohei, max}@spatial.maine.edu

Abstract. Directed line segments are fundamental geometric elements used tomodel through their spatial relations such concepts as divergence, confluence,and interference. A new model is developed that captures spatial relations
between pairs of directed line segments through the intersections of thesegments’ heads, bodies, and tails. This head-body-tail intersection identifies
68 classes of topological relations between two directed line segments
highlighting two equal-sized subsets of corresponding relations that differ onlyby their empty and non-empty body-body intersections. The relations’ conceptual neighborhood graph takes the shape of a torus inside a torus, one foreach subset. Another 12 classes of topological relation classes are distinguished
if the segments’ exteriors are considered as well, lining up such that theirconceptual neighborhood graph forms another torus that contains the other two
tori. These conceptual neighborhoods as well as the relations’ composition tableenable spatial inferences and similarity assessments in a consistent andreasoned manner.

1 Introduction
Directed line segments (called DL segments) are fundamental geometric elements
used in geographic databases to represent directed linear entities, such as one-way
roads and watercourses. People also often employ arrow symbols, an expressive formof DL segments, to display dynamic phenomena, for instance, movement, interaction,
causality, and change (Kurata and Egenhofer 2005b), and their spatial relations
illustrate such scenarios as divergence, confluence, and interference (Kurata andEgenhofer 2006). Geographic databases have a tradition of processing spatial queries
over line segments (Hoel and Samet 1991) and spatio-temporal database systems havebeen increasingly adding corresponding relations into query languages to enable theretrieval and analysis of spatio-temporal configurations at a high level of abstraction(Erwig and Schneider 1999). To further advance spatial query languages for directed
linear element, and to supply a basis for the interpretation of the semantics of route
M. Raubal et al. (Eds.): GIScience 2006, LNCS 4197, pp. 269 – 286, 2006.
© Springer-Verlag Berlin Heidelberg 2006

270

Y. Kurata and M.J. Egenhofer

graphs (Krieg-Brückner and Shi, 2005) to communicate route descriptions in ameaningful way, formal models of spatial relations between DL segments andcomprehensive reasoning mechanisms about those relations are needed. In comparison to the well-established methods for topological relations for regions, however,models of relations among DL segments have attracted only little attention. Since
DL segments are 1-dimensional objects embedded in a 2-dimensional space, they
have more degrees of freedom than regions in the same space, which is a property of
DL segments that makes reasoning with them more intricate. This paper’s scope is on
those spatial relations that are invariant under topological transformations of theembedding space. Metric properties can be used subsequently to provide refinementsof the resulting relations in analogy to the way line-line relations have been enhanced
metrically (Nedas et al. in press).
Throughout the rest of this paper DL segments are illustrated as arrow symbols,
which are essentially DL segments that are constrained such that they typically refer
to (i.e., originate from, traverse, and point to) other elements in a diagram, thereby
establishing the semantics of these related elements (Kurata and Egenhofer 2005a),whereas generic DL segments are often used independently. We focus on the direct
relations between DL segments, which are formed by their mutual intersections, anddo not consider indirect relations, which are materialized by other elements. EachDL segment is further assumed to be embedded in a 2-dimensional space and not tointersect with itself.
The remainder of this paper is structured as follows: Section 2 reviews models forline-line relations. Section 3 classifies the topological relations between two
DL segments based on the intersections between the lines’ heads, bodies, and tails(called the hbt-intersection), yielding 68 classes of DL relations. Section 4 schematizes these 68 classes by their conceptual neighborhood graph, thereby arranging
the relations according to their similarities. Section 5 develops the relations’composition table, forming a formal foundation for qualitative reasoning about DL
segments. Section 6 analyzes the effect of considering—in addition to the DL
segments’ heads, bodies, and tails—also their exteriors, rendering a DL relation
model that identifies another twelve classes. Section 7 concludes with a discussion of
future work items.

2 Models of Line-Line Relations
Binary relations between line segments in IR 2 (and their lower-dimensional relatives,
temporal intervals in IR 1 ) have been studied extensively in artificial intelligence andspatio-temporal databases. Allen (1983) identified thirteen order relations between
two temporal intervals embedded in IR 1 . The 4-intersection (Egenhofer and Franzosa1991) captures the topological relations between two objects based on theexistence/non-existence of geometric intersections between the objects’ interiors andboundaries. For non-directed line segments in IR 1 , it identifies eight topologicalrelations (Pullar and Egenhofer 1988), essentially the same as for two regions in IR 2 ,The Head-Body-Tail Intersection for Spatial Relations Between DL Segments

271

and distinguishes sixteen binary relations between two lines in IR 2 , without capturing
an equivalence relation (Hadzilacos and Tryfona 1992). The dimension-extended
method of the 4-intersection (Clementini et al. 1993) finds eighteen line-line relations.
The 9-intersection (Egenhofer and Herring 1991) extends the 4-intersection byconsidering also the intersections with respect to the objects’ exteriors, which
gives rise to distinguishing formally 33 topological relations between two nondirected line segments in IR 2 (Egenhofer 1994). Another variation of the 4intersection distinguishes explicitly the two boundaries (i.e., endpoints) of a line
segment, identifying sixteen relations between two intervals in a temporal cycle,
which are equivalent to topological relations between uni-directed line segments
embedded in a cyclic 1-dimensional space (Hornsby et al. 1999). Models for detailed
topological relations, capturing for non-empty intersections such properties as
sequences of crossing types, intersection dimensions, and orientations of common
segments, have been developed for region-region relations (Egenhofer and Franzosa1995) and line-line relations (Clementini and di Felice, 1998), yielding a set of
topological invariants. Such additional invariants of component intersections havebeen known to be germane to distinguishing even basic line-line relations, such as
touching from crossing (Herring 1991). Nedas et al. (in press) provided metricrefinements for detailed topological relations between line segments by incorporating
two metric measures, splitting ratios and closeness measures, into the 9-intersection
matrix and the topological invariants.
Conceptual neighborhood graphs, which establish links among relations to capture
similarities among them, have been developed for a series of spatial and temporal
relations (Egenhofer and Al-Taha 1992, Freska 1992a, Egenhofer and Mark 1995,
Papadias et al. 1995, Schlieder 1995, Hornsby et al. 1999, Egenhofer 2005) to support
qualitative analyses of change and to provide the foundations for computational
similarity models over spatial relations (Egenhofer 1997) as well as a rationale formodeling the semantics of natural-language spatial predicates (Mark and Egenhofer
1994, Shariff et al. 1998). Several increments towards the identification of aconceptual neighborhood graph of line-line relations have been made, starting with
Freksa’s (1992a) neighborhood graphs of Allen’s thirteen interval relations. A
fragment of a conceptual neighborhood graph for line-line relations in IR 2 (Egenhofer
et al. 1993) was recently incremented (Reis et al. 2005), but lacks the comprehensive
treatment found for other relations. Apparently the degree of freedom for lines in ahigher-dimensional space leads to an increased complexity for identifying those pairsof relations for which atomic transformations in the spirit of the conceptual
neighborhood similarity are feasible.
In addition to topological relations, spatial relations of line segments have been
categorized based on order and direction. The double-cross (Freksa 1992b) introduces
left/right and front/back dichotomies to capture qualitative directions, yielding 15
direction relations from an observer’s point to a target. Another approach, based on
Allen’s interval relations, identifies 63 order relations (essentially directional
relations) between two straight DL segments in IR 2 (Schlieder 1995). The dipole
calculus (Moratz et al. 2000) is based on 24 directional relations between two straight
DL segments in IR 2 , which fulfill the constraints of a relation algebra. Likewise, 26272

Y. Kurata and M.J. Egenhofer

order relations between two directed intervals in IR 1 form the directed interval
algebra (Rentz 2001). The Direction-Relation Matrix provides an overall frameworkfor describing direction relations between any pair of extended objects in IR 2 ,including arbitrarily shaped lines (Goyal and Egenhofer 2000).

3 Classes of Topological Relation Between DL Segments
A DL segment consists of two distinct points, a non-self-intersecting, continuous linethat connects the two points, and an orientation imposed on the line, which
categorizes the two points as start and end points. Following principles from algebraic
topology (Alexandroff 1961), the two points form the boundary of a DL segment,
whereas the connection between the points forms the interior. Due to the geometricsimilarity of DL segments and arrow symbols, the binary topological relations
between DL segments are captured like the topological relations between two arrowsymbols (Kurata and Egenhofer 2006), that is, based on the intersections between
their interiors (the body X ° ) and the two ordered boundaries (head ∂ head X andtail ∂ tail X ). These nine intersections yield the DL segments’ head-body-tailintersection (hbt-intersection), which is concisely represented by a 3×3 matrix, called
the hbt-matrix for DL segment relations (Eqn. 1).
⎛ ∂ tail A ∩ ∂ tail B ∂ tail A° ∩ B° ∂ tail A ∩ ∂ head B ⎞⎜⎟M I ( A, B ) = ⎜ A° ∩ ∂ tail B
A° ∩ B°A° ∩ ∂ head B ⎟⎜ ∂ A ∩ ∂ B ∂ A ∩ B° ∂ A ∩ ∂ B ⎟
tail
head
head
head ⎠⎝ head(1 )Like for line-line relations, each intersection could be analyzed for various
topological invariants, such as its dimension, the number of intersections, and the typeof intersection, but we choose the most fundamental property, that is, whether eachintersection is empty ( φ ) or non-empty ( ¬φ ). The empty/non-empty entries of thehbt-matrix are constrained among each other since the first and third column, as wellas the first and third row, have at most one non-empty entry, because the head or tailof a DL segment is a point, which cannot intersect with more than one part of anotherDL segment. Among the 29 = 512 configurations of a 3×3 matrix with empty or nonempty entries, only 68 cases satisfy this constraint (Tables 1 and 2). Each of these 68
configurations corresponds to a different set of topological relations (Fig. 1), while
the remaining 444 configurations have no valid geometric interpretations. In this way,

Æ

⎛φ
⎜
⎜φ
⎜φ
⎝

¬φ φ ⎞⎟φ φ⎟¬ φ φ ⎟⎠

Fig. 1. Five different topological relations between two DL segments with the same hbt-matrix,
which implies that the hbt-intersection groups this set of DL relations into the same TR-classThe Head-Body-Tail Intersection for Spatial Relations Between DL Segments273

the hbt-intersection classifies topological relations between two DL segments into 68
topological relation classes (TR-classes). Among the 68 TR-classes, 34 classes(Table 1) are TR-classes without body-body intersections ( A° ∩ B° = φ ), whereas theother half (Table 2) has body-body intersections ( A° ∩ B° = ¬φ ).
Each TR-class is given a name, based on the name primitives split (sp), diverge(dv), precede (pr), divergedBy (dvB), cross/touch (ct), mergedBy (mgB), follow (fl),merge (mg), and meet (mt) that are assigned to the nine types of intersections (Eqn. 2).
split ( sp )diverge ( dv )preceed ( pr ) ⎞⎛⎟⎜divergedBy(
dvB)
cross/touch(ct)
mergedBy(mgB ) ⎟⎜⎟⎜follow ( fl )merge (mg )meet (mt )
⎠
⎝

(2 )

The names of each TR-class are then described as a set of these name primitives, likesplit-cross/touch-meet, thereby indicating the intersections that establish each TRclass. The sequence in such a compound name, however, does not reflect thesequence of the intersection types that one might observe by following one segment
form head to tail, but follows a standardized naming convention (row-order acrossEquation 2, i.e., sp-dv-pr-dvB-ct-mgB-fl-mg-mt). To more concisely refer to TRclasses, we also give each TR-class a numeric label. Tables 1 and 2 show themappings from names to numeric labels.
Properties of the hbt-matrices reflect certain algebraic properties of thecorresponding relations. For example, if an hbt-matrix N can be obtained bytransposing another hbt-matrix M along its main diagonal (i.e., N = MT), then the twocorresponding TR-classes form a pair of converse relations. Likewise, if M = MT, thenthe corresponding relation is symmetric. In total, there are twenty symmetric TRclasses, and each of the remaining 48 TR-classes has a converse TR-class within these48 TR-classes, forming 24 pairs of converse TR-classes.
The TR-class whose matrix has non-empty entries along the main diagonal, but
empty entries otherwise (i.e., #44: split-cross/touch-meet), deserves special attention,
as it includes the situation in which two DL segments completely coincide, which
would correspond to the equality of two DL segments and imply this class’s transitive
property (Fig. 2a). This coincidence is, however, not the only configuration thatmatches the hbt-matrix specification, because other topological configurations thanequal (Fig. 2b) are also covered by the same hbt-matrix of non-empty values for thethree intersections of the head-head, body-body, and tail-tail pairs. As a consequence,
this TR-class is not a transitive relation (Fig. 2c). This issue is revisited in Section 6.

C
B
A

(a)

(b)

(c)

Fig. 2. Two configurations (a) and (b) covered by TR-class #44, and (c) an example that thisTR-class is not transitive274

Y. Kurata and M.J. Egenhofer

Table 1. The 34 TR-classes without body-body intersections (#1 through #34) with examples
of geometric prototypes
symmetric
TR-classes#10

disjoint⎛φ φ φ ⎞⎜⎟⎜φ φ φ ⎟⎜φ φ φ ⎟
⎝
⎠

#2

1

split

⎛φ φ
⎜
⎜φ φ
⎜φ φ
⎝

#3

#5

#10

meet
φ ⎞
⎟
φ ⎟
¬φ ⎟⎠

split-meet⎛ ¬φ φ
⎜
⎜ φ φ
⎜ φ φ
⎝

number of intersections

#11

φ ⎞
⎟
φ ⎟
¬φ ⎟⎠

precede-follow

⎛ φ φ
⎜
⎜ φ φ
⎜ ¬φ φ
⎝

¬φ ⎞
⎟
φ ⎟
φ ⎟⎠

precede#6

diverge

#8

¬φ ⎞
⎟
φ ⎟
φ ⎟⎠

⎛φ
⎜
⎜φ
⎜φ
⎝

¬φ φ ⎞⎟φ φ⎟
φ φ ⎟⎠

⎛φ φ
⎜
⎜φ φ
⎜φ φ
⎝

↑↓
follow#7↑↓
divergedBy

#9

↑↓
merge
φ φ⎞
⎟
φ φ⎟
¬φ φ ⎟⎠

⎛φ
⎜
⎜φ
⎜φ
⎝

#14

diverge-merge

#18

#22

diverge-follow

⎛φ
⎜
⎜φ
⎜φ
⎝

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

⎛ φ
⎜
⎜ φ
⎜ ¬φ
⎝

¬φ φ ⎞⎟φ φ⎟
φ φ ⎟⎠#15↑↓
divergedBy-mergedBy#19↑↓
split-merge#23↑↓
precede-divergedBy

⎛ ¬φ
⎜
⎜ φ
⎜ φ
⎝

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

#20

divergedBy-meet

#24

⎛ φ φ
⎜
⎜ ¬φ φ
⎜ φ φ
⎝

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

diverge-divergedBy#16¬φ φ ⎞⎟φ φ⎟
φ φ ⎟⎠

⎛φ
⎜
⎜φ
⎜φ
⎝

#13

mergedBy-merge#17↑↓
divergedBy-merge

#21

⎛ φ
⎜
⎜ ¬φ
⎜
⎝ φ

φ φ⎞
⎟
φ φ⎟
¬φ φ ⎠⎟

⎛φ
⎜
⎜φ
⎜
⎝φ

diverge-mergedBy
¬φ

φ
φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

split-mergedBy-merge#28

precede-divergedBymerge

#30

⎛ ¬φ
⎜
⎜ φ
⎜ φ
⎝

φ
φ ⎞
⎟
φ ¬φ ⎟¬φ φ ⎟⎠

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

φ ¬φ ⎞⎟φφ ⎟¬φ φ ⎟⎠

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

#27

diverge-divergedBymeet

#29

⎛ φ
⎜
⎜ ¬φ
⎜
⎝ φ

#34
⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

¬φ

φ
φ

φ ⎞
⎟
φ ⎟
¬φ ⎠⎟

diverge-divergedBymergedBy-merge
¬φ

φ ⎞
⎟
φ ¬φ ⎟¬φ φ ⎟⎠

⎛ φ
⎜
⎜ φ
⎜
⎝ ¬φ

↑↓
diverge-mergedByfollow
¬φ

φ
φ

φ

⎞
⎟
¬φ ⎟
φ ⎠⎟

split-mergedBy⎛ φ φ⎜⎜ ¬φ φ
⎜ φ φ
⎝

#26

3

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

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

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

φ
φ ⎞
⎟
φ ¬φ ⎟¬φ φ ⎟⎠

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

#12

⎛φ
⎜
⎜φ
⎜
⎝φ

4

#4

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

⎛φ φ
⎜
⎜φ φ
⎜φ φ
⎝

2

converse pairs of asymmetric TR-classes

#31
⎛ φ
⎜
⎜ ¬φ
⎜
⎝ φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

φ ⎞
⎟
φ ⎟
¬φ ⎟⎠

↑↓
diverge-meet
¬φ

φ
φ

φ ⎞
⎟
φ ⎟
¬φ ⎠⎟

diverge-divergedBymergedBy
¬φ

φ
φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

↑↓
diverge-divergedBymerge¬φ φ ⎞⎟φ φ⎟¬φ φ ⎠⎟

⎛φ
⎜
⎜φ
⎜φ
⎝

#25

¬φ ⎞
⎟
φ ⎟
φ ⎟⎠

precede-merge
φ ¬φ ⎞⎟φφ ⎟¬φ φ ⎟⎠↑↓
mergedBy-follow

⎛ φ φ
⎜
⎜ φ φ
⎜
⎝ ¬φ φ

φ ⎞
⎟
¬φ ⎟
φ ⎠⎟

#32

divergedBy-mergedBymerge

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

φ
φ ⎞
⎟
φ ¬φ ⎟¬φ φ ⎟⎠

#33
⎛φ
⎜
⎜φ
⎜
⎝φ

↑↓
diverge-mergedBymerge
¬φ

φ ⎞
⎟
φ ¬φ ⎟¬φ φ ⎟⎠

The Head-Body-Tail Intersection for Spatial Relations Between DL Segments

275

Table 2. The 34 TR-classes with body-body intersections (#35 through #68) with examples ofgeometric prototypes
symmetric
TR-classes
1

2

cross/touch

⎛φ
⎜
⎜φ
⎜φ
⎝

⎞
⎟
¬φ φ ⎟
φ φ ⎟⎠#36

split-cross/touch

#38

⎛ ¬φ
⎜
⎜ φ
⎜ φ
⎝

φ φ⎞
⎟
¬φ φ ⎟
φ φ ⎟⎠

⎛φ
⎜
⎜φ
⎜φ
⎝

#37

cross/touch-meet#39

number of intersections

⎛φ
⎜
⎜φ
⎜φ
⎝

φ

φ
¬φ

φ

φ

φ ⎞
⎟
φ ⎟
¬φ ⎟⎠

precede-cross/touch#40

diverge-cross/touch

#42

⎛φ
⎜
⎜φ
⎜φ
⎝

¬φ φ ⎞⎟¬φ φ ⎟
φ φ ⎟⎠

⎛φ
⎜
⎜φ
⎜φ
⎝

↑↓
cross/touch-follow#41↑↓
divergedBy-cross/touch#43↑↓
cross/touch-merge

⎛ φ
⎜
⎜ φ
⎜ ¬φ
⎝

φ φ⎞
⎟
¬φ φ ⎟
φ φ ⎟⎠

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

φ φ⎞
⎟
¬φ φ ⎟
φ φ ⎟⎠

⎛φ
⎜
⎜φ
⎜φ
⎝

φ φ⎞
⎟
¬φ φ ⎟¬φ φ ⎟⎠#56

diverge-cross/touchfollow

⎛ φ
⎜
⎜ φ
⎜
⎝ ¬φ

¬φ φ ⎞⎟¬φ φ ⎟
φ φ ⎠⎟φ ¬φ ⎞⎟¬φ φ ⎟φφ ⎟⎠cross/touch-mergedByφφ ⎞⎟¬φ ¬φ ⎟
φ
φ ⎟⎠

#44

split-cross/touch-meet#48

diverge-cross/touchmerge#52

split-cross/touchmergedBy

⎛ ¬φ
⎜
⎜ φ
⎜
⎝ φ

φ
¬φ

⎛φ
⎜
⎜φ
⎜
⎝φ

¬φ φ ⎞⎟¬φ φ ⎟¬φ φ ⎠⎟

⎛ ¬φ
⎜
⎜ φ
⎜
⎝ φ

¬φ

#53

split-cross/touch-merge

#57

⎛ ¬φ
⎜
⎜ φ
⎜ φ
⎝

φ φ⎞
⎟
¬φ φ ⎟¬φ φ ⎟⎠

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

¬φ

#54

divergedBycross/touch-meet#58

precede-cross/touchmerge

⎛ φ
⎜
⎜ ¬φ
⎜
⎝ φ

¬φ

φ

φ ⎞
⎟
φ ⎟
¬φ ⎠⎟

#45

precede-cross/touchfollow

⎛ φ
⎜
⎜ φ
⎜ ¬φ
⎝

¬φ

φ

#49

¬φ

#46

diverge-divergedBycross/touch#50

diverge-cross/touchmergedBy

⎛ φ
⎜
⎜ ¬φ
⎜
⎝ φ

¬φ φ ⎞⎟¬φ φ ⎟
φ φ ⎠⎟

⎛φ
⎜
⎜φ
⎜
⎝φ

φ

cross/touch-mergedBymerge

#47
⎛φ
⎜
⎜φ
⎜φ
⎝

#60
⎛ ¬φ
⎜
⎜ φ
⎜ φ
⎝

4
#61
⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

#68
⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

¬φ ⎞
⎟
φ ⎟
φ ⎟⎠

↑↓
divergedBycross/touch-mergedBy

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

3

5

converse pairs of asymmetric TR-classes

#35

φ
¬φ
¬φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

split-cross/touchmergedBy-merge
φ
¬φ
¬φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

diverge-divergedBycross/touch-meet
¬φ
¬φ

φ

φ ⎞
⎟
φ ⎟
¬φ ⎟⎠

diverge-divergedBycross/touchmergedBy-merge
¬φ
¬φ
¬φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

#51

φ
φ

¬φ
¬φ

φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

φ

⎞
⎟
¬φ ⎟
φ ⎠⎟

↑↓
divergedBycross/touch-merge

⎛φ
⎜
⎜φ
⎜φ
⎝

#62

precede-divergedBycross/touch-merge

#64

#63
⎛ φ
⎜
⎜ φ
⎜ ¬φ
⎝

φ

¬φ ⎞
⎟
φ ⎟
φ ⎟⎠

↑↓
diverge-cross/touchmergedBy-follow
¬φ
¬φ

φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

φ
φ

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

#65
⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

φ ⎞
⎟
φ ⎟
¬φ ⎠⎟

↑↓
diverge-cross/touchmeet

#55

φ φ⎞
⎟
¬φ φ ⎟¬φ φ ⎟⎠

¬φ
¬φ

φ

φ ⎞
⎟
¬φ ⎟
φ ⎠⎟

↑↓

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

φ

¬φ
¬φ

φ

φ ⎞
⎟
φ ⎟
¬φ ⎟⎠

diverge-divergedBycross/touch-mergedBy
¬φ
¬φ

φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

↑↓
diverge-divergedBycross/touch-merge¬φ φ ⎞⎟¬φ φ ⎟¬φ φ ⎟⎠

⎛φ
⎜
⎜φ
⎜
⎝φ

#59

↑↓
precede-divergedBycross/touch
φ
φ

φ
¬φ
¬φ

¬φ ⎞
⎟
φ ⎟
φ ⎟⎠

¬φ ⎞
⎟
φ ⎟
φ ⎠⎟

↑↓
cross/touch-mergedByfollow

⎛ φ
⎜
⎜ φ
⎜ ¬φ
⎝

¬φ

#66

divergedBy-cross/touch-mergedBy-merge

⎛ φ
⎜
⎜ ¬φ
⎜ φ
⎝

#67
⎛φ
⎜
⎜φ
⎜φ
⎝

φ
φ

φ
¬φ
¬φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

↑↓
diverge-cross/touchmergedBy-merge
¬φ
¬φ
¬φ

φ ⎞
⎟
¬φ ⎟
φ ⎟⎠

276

Y. Kurata and M.J. Egenhofer

4 Conceptual Neighborhoods of the 68 TR-Classes
If a continuous transformation can be performed between two spatial relations without
having to go through a third relation, then this establishes a direct transition. These
two relations have been called conceptual neighbors (Freksa 1992a). For example, thetwo TR-classes split (#2) and split-mergedBy (#18) are conceptual neighbors, because
moving the head of the first DL segment from the other segment’s exterior to its body
is a direct transition. On the other hand, TR-classes spilt (#2) and meet (#3) are notneighbors, because disconnecting the head-tail intersection of split and establishing
the head-head intersection of meet would need to go through either split-meet (#10) or
disjoint (#1). We focus here on the equivalents of type-A neighbors for 1-dimensional
intervals (Freksa 1992a), that is, those pairs of relations that can be transformed into
each other by changing in their hbt-matrices one intersection from empty to nonempty, or vice-versa, but not several of them simultaneously. Equivalents of Type-B
neighbors would require an entire DL segment to move—establishing, for instance, alink between disjoint (#1) and diverge-cross/touch-mergedBy (#50)—whereas theequivalents of Type-C neighbors are such that both boundary points of a DL segment
would need to be moved—for example, turning disjoint (#1) and diverge-merge (#14)
into neighbors.
The conceptual neighborhood graph of the 68 TR-classes is derived computationally from the relations’ hbt-matrices, counting the number of differences incorresponding matrix cells with regards to empty/non-empty values (Egenhofer and
Al-Taha 1992). Pairs of TR-classes with no differences in corresponding matrix cells
would mean that the two TR-classes are identical, whereas pairs of TR-classes with asingle difference across their hbt-matrices reflect an atomic change, dissolving either
an intersection of two boundary elements, or an intersection between a boundary
element and a body, or an intersection between two bodies. Pairs of TR-classes with adifference of 1 are called conceptual 1-neighbors.
The 1-neighbors among TR-classes #1 through #34 (as well among TR-classes #35
through #68) have the following countable properties: One TR-class has eight 1neighbors; four TR-classes have six 1-neighbors and another four TR-classes have
five 1-neighbors; eleven TR-classes have four 1-neighbors; twelve TR-classes havethree 1-neighbors; and two TR-classes have two 1-neigbors. Across the two groups of
TR-classes, each TR-class has exactly one 1-neighbor such that #n and #(n+34) areneighbors (1≤n≤34). This means each TR-class has, in addition to the 1-neighbors
within its group, another 1-neighbor that extends to the other group, increasing theneighbor count by one.
In the conceptual neighborhood graph, each TR-class has a node and each 1neighbor of two TR-classes maps onto an edge that links the TR-classes’ two nodes;
therefore, the number of 1-neighbors of a TR-class corresponds to the node’s degree
within the neighborhood graph. These properties bring forth a conceptual
neighborhood graph of one layer for TR-classes #1 through #34 (Fig. 3), and anotherone for TR-classes #35 through #68.

The Head-Body-Tail Intersection for Spatial Relations Between DL Segments
#11
pr-fl

#10
sp-mt
#33
dv-mgB-mg#34
dv-dvB-mgB-mg#26
sp-mgB-mg#15
dvB-mgB

#8
mgB

#29
dv-mgB-fl#34
dv-dvB-mgB-mg#33
dv-mgB-mg

#4
pr

#22
dv-fl
#14
dv-mg

#32
dvB-mgB-mg#23
pr-dvB
#7
dvB

#1
dj

#15
dvB-mgB#3
mt#20
dvB-mt#6
dv#12
dv-dvB#30
dv-dvB-mgB

#21
dv-mt

#27
dv-dvB-mt

#5
fl

#16
dv-mgB#28
pr-dvB-mg#17
dvB-mg

#9
mg
#2
sp

#25
mgB-fl#30
dv-dvB-mgB

#24
pr-mg

#19
sp-mg

#18
sp-mgB#31#34
dv-dvB-mg dv-dvB-mgB-mg

#14
dv-mg

#13
mgB-mg#32
dvB-mgB-mg

277

#31
#34
dv-dvB-mg dv-dvB-mgB-mg

Fig. 3. The flattened conceptual neighborhood graph of the TR-classes #1 through #34. It
displays more than 34 nodes in order to highlight some of the regularities of the neighborhoodsby repeating the nodes in the front and back row as well as in the left and right column

The graph highlights the special status of the TR-classes split-meet (#10) andprecede-follow (#11) as the only TR-classes with two conceptual neighbors among
their 34 companions without body-body intersections. A visual inspection mightsuggest that this graph misses some links (e.g., along the diagonal from #5 to #16 orfrom #29 to #34), but their hbt-matrices confirm that such pairs cannot qualify as 1neighbors, because any transition among them would require moving through anotherTR-class (e.g., through #6 or #8 to get from #5 to #16).
This graph of 1-neighbors also keeps its role as a reference framework when otherkinds of neighbors would be considered (e.g., 2-neighbors whose matrix difference
would be 2). In such a case, shortcuts along this graph would be introduced (e.g.,
another eight links among the eight TR-classes #2 thought #9 with exactly one nonempty intersection). Subsequently, only the graph derived from the 1-neighbors isanalyzed. The conceptual neighborhood graphs of TR-classes #1 through #34, as wellas TR-classes #35 through #68, have the following characteristics:• TR-classes with fewer intersections are located closer to the center. This property
is, however, one of choice, because different elements than TR-class #1 could havebeen selected as the central reference point.
• TR-classes located along the diagonal from top-left to bottom-right are symmetric(Fig. 4a).
• Pairs of TR-classes that are located symmetrically across the diagonal from top-leftto bottom-right are converse, that is, the same matrices are obtained by transposing
the matrices along their main diagonals (Fig. 4a).
• The conceptual neighborhood graph can be decomposed into four subgraphs with ahorizontal and vertical mirror axis such that the same matrices are obtained byreversing the direction of one DL segment (Fig. 4b).

278

Y. Kurata and M.J. Egenhofer

#7

n
co

#2

#4

rse
ve

#6

#5

#3

symmetric relation

(a)

(b)

Fig. 4. Characteristics of the flattened conceptual neighborhood graph of TR-classes #1 through#34: (a) symmetric and converse TR-classes and (b) the four subgraphs that are obtained byreversing the direction of a DL segment when mirroring the TR-class along the graph’s
horizontal or vertical axis, as highlighted by TR-classes #2-#5

Gluing the flattened graph’s front and back rows, and then the leftmost andrightmost columns, yields a non-redundant configuration in which the graph extends
over the surface of a torus (Fig. 5b). TR-classes #10 and #11, which placed irregularly
above the flattened graph (Fig. 3), are now outside the torus (Fig. 5b), highlighting
through their irregular locations again the two nodes’ unique properties of degree 2.
identical

identical

(a)

(b)

Fig. 5. The transition from (a) the flattened conceptual neighborhood graph of TR-classes #1
through #34 with repeated columns and rows to (b) a graph displayed on the surface of a torus,
which is obtained by gluing together the repeated rows and columns along the fringes of theflattened graph.

The integrated conceptual neighborhood graph of TR-classes #1 through #68 has a
two-layered structure, where each layer contains a homeomorphic conceptual
neighborhood graph of #1 through #34 or #35 through #68, and each node in one ofthese layers is linked to one node in another layer, thereby representing the neighbor
relation between #n and #(n+34). Consequently, the conceptual neighborhood graphof the TR-classes #1 through #68 is represented in a 3-dimensional space where nodes
are aligned on two parallel planes (Fig. 6a). When the flattened structure is connected

The Head-Body-Tail Intersection for Spatial Relations Between DL Segments

279

through the redundant nodes at its fringes, the graph forms a shape that extends overthe surfaces of two tori, one inside the other, with links across the two tori to establish
the neighborhoods of #n and #(n+34) with 1≤n≤34 (Fig. 6b).
#35-#68#35-#68#1-#34#1-#34(a)(b)

Fig. 6. Two structures of the conceptual neighborhood graph of TR-classes #1 through #68,
where nodes are aligned on (a) two parallel planes and (b) the surfaces of two nested tori

5 Inferences About the 68 TR-Classes
The 68 DL segment relations allow us to capture the topological relations between
these segments in a simple, consistent, and qualitative way that is suitable forprocessing queries about their relations recorded in a database. Queries may, howeveralso refer to relations that have not been recorded explicitly so that it may benecessary to deduce result candidates from a logical combination of available
information about several relations. In support of such queries involving implied
relations, this section develops the composition table of the 68 TR-classes. Given
three DL segments, A, B, and C, whose TR-classes are denoted by RAB, RBC, and RAC,
the composition of RAB and RBC, denoted by RAB ; RBC, is the set of all possible TRclasses between A and C. The actual value of RAC is always included in RAB ; RBC.
5.1 Constraints on the Hbt-Matrix for Composed TR-Classes

Let the TR-classes RAB, RBC, and RAC correspond to the respective hbt-matrices MAB,
MBC, and MAC (Eqn. 3).
tt⎛ I AB⎜ bt
M AB = ⎜ I AB
⎜ I ht
⎝ AB

tb
I AB
bb
I AB
hb
I AB

th
tt
⎞
⎛ I BC
I AB
⎟
⎜
bh
bt
I AB
⎟ M BC = ⎜ I BC
⎜
hh ⎟
ht
I AB ⎠⎝ I BC

tb
I BC
bb
I BC
hb
I BC

th
tt
⎞
⎛ I AC
I BC
⎟
⎜
bh
bt
I BC
⎟ M AC = ⎜ I AC
⎜
hh ⎟
ht
I BC ⎠⎝ I AC

tb
I AC
bb
I AC
hb
I AC

th
⎞
I AC
⎟
bh
I AC ⎟
hh ⎟
I AC
⎠

(3)

Symbols pA, pB, pC denote arbitrary parts of A, B, and C (i.e., either tail or body orhead). If B’s tail intersects with both pA and pC, then pA and pC must intersect, since
B’s tail is a point on which both pA and pC are partly or wholly located. Similarly, if
B’s head intersects with both pA and pC, then pA and pC must intersect as well. These
geometric constraints lead to the constraint on MAC that pA and pC intersect if B’s tailor head intersects with both pA and pC (Eqn. 4).

280

Y. Kurata and M.J. Egenhofer

For p A , pC ∈ {t , b, h}

(I

p At
AB

= ¬φ

∧

tpC
I BC
= ¬φ

) ∨ (I

p Ah
AB

= ¬φ

∧

hpC
I BC
= ¬φ

) → I

p A pC
AC

= ¬φ

(4)

The intersection between A’s tail and pB, if it exists, is totally included in pB, since
A’s tail is a point. Thus, if pB intersects with A’s tail, but not pC, A’s tail and pC do notintersect. Similarly,• A’s head and pC do not intersect if pB intersects with A’s head but not pC,• C’s tail and pA do not intersect if pB intersects with C’s tail but not pA, and• C’s head and pA do not intersect if pB intersects with C’s head but not pA.

These four conditions imply another constraint on MAC (Eqn. 5).
For p A , pB , pC ∈ {t , b, h}
tp B
I AB
= ¬φ

∧

p B pC
I BC
=φ

→

tp C
I AC
=φ

hp B
I AB
= ¬φ
pA pB
I AB
=φ

∧
∧

p B pCI BC=φpB t
I BC = ¬φ

hp C→ I AC=φp At→ I AC
=φ

pA pB
I AB
=φ

∧

pBh
I BC
= ¬φ

p Ah
→ I AC=φ(5)

Among the 68 configurations of the hbt-intersection (Tables 1 and 2), theconfigurations that satisfy the two constraints (Eqs. 4 and 5) are the candidates for
MAC and, therefore, the TR-classes that correspond to these candidates of MAC
configurations are the compositions of TR-classes RAB and RBC.
5.2 Composition Table for TR-Classes of DL Segment Relations

The compositions of the TR-classes were determined from the hbt-matrices (Tables 1
and 2) and the constraints on the hbt-matrix of the composition (Eqs. 4 and 5). The
resulting composition table for the TR-classes between DL segments contains 68×68= 4,624 composition elements, of which Table 3 shows a small subset for TR-classes#7, #9, #10, #19, and #44.
The validity of the composition table is demonstrated, although not proved
formally, by the following observations:• Any composition is connected in the conceptual neighborhood graph.
• Any composition satisfies the following constraint:∀X

R AA = sp-ct-mt ∈ R AX ; R XA

(6)

Eqs. 4 and 5 do not contain the constraint on the non-existence of a body-bodyintersection. Accordingly, if a composition contains a TR-class without a body-bodyintersection (say R-), then the composition also contains the TR-class that adds abody-body intersection to R-. This means that if a TR-class in the lower layer is in acomposition, then the vertical neighbor of this TR-class (located in the upper layer) is
also in that composition (Table 3). For example, the composition split-merge; splitmeet, contains split and split’s vertical neighbor, that is, split-cross/touch.

The Head-Body-Tail Intersection for Spatial Relations Between DL Segments

281

Table 3. A 5×5 subset of the composition table of the 68 TR-classes between DL segments#9 mg#10 sp-mt#19 sp-mg#44 sp-ct-mt#44 sp-ct-mt#19 sp-mg#10 sp-mt#9 mg#7 dvB#7 dvB

5.3

A Reasoning Example

To demonstrate the use of the composition table, consider a snow mountain with fourskiing trails, A, B, C, and D (Fig. 7). A skier went down on B and found that:• Trail A shares the same start point with B, takes a different course, and eventuallyends at a B’s midpoint.
• Trail C starts at a B’s midpoint and does not intersect with B after that point.

282

Y. Kurata and M.J. Egenhofer

The inference scenario is to determine symbolically (i.e., in a non-graphical way)
what are the possible relations between trails A and C.

A
C
D

B

Fig. 7. A snow mountain with four skiing trails

The TR-class between A and B is split-merge (#19) and the TR-class between B
and C is divergedBy (#7). According to Table 2, the composition of split-merge anddivergedBy is disjoint (#1), follow (#5), mergedBy (#8), mergedBy-follow (#25),
cross/touch (#35), cross/touch-follow (#39), cross/touch-mergedBy (#42), andcross/touch-mergedBy-follow (#59). Thus, these eight TR-classes are the candidatesof the relation between A and C.
When the skier went down on trail D, she found that:• Trail A ends at D’s midpoint and does not intersect before that point.
• Trail C shares the same start point with trail D, takes a different course, andeventually ends at the same destination with trail D.

This additional information further influences the inference about the possible
relations between trails A and C. The TR-class between A and D is merge (#9) and the
TR-class between D and C is split-meet (#10). According to Table 2, the compositionof merge and split-merge is disjoint (#1), diverge (#6), cross/touch (#35), anddiverge-cross/touch (#40). These four TR-classes are also the candidates of therelation between A and C. By integrating this result with the previous result, thepossible TR-classes between A and C are narrowed down to disjoint and cross/touch.
This indicates that the richer knowledge about the network reduces the ambiguity of
its unrecorded relations.

6 The HBT+-Intersection
Although the hbt-intersection features nine types of intersections, it resembles the 4intersection (Egenhofer and Franzosa 1991) more than the 9-intersection (Egenhofer
and Herring 1991), because both the hbt-intersection and the 4-interesection assess
the intersections between the interiors and boundaries, but not the intersections withexteriors. Since the 4-intersection cannot distinguish some topological relations
between line segments that the 9-intersection can distinguish (Egenhofer 1994), it
could be expected that the hbt-intersection cannot distinguish some topologicalrelations between DL segments as well. The observation about TR-class splitcross/touch-meet (#44) already gave evidence for an hbt-intersection that captures atleast two significantly different topological relations (Figs. 2a-b). By adding to the
hbt-intersection the intersections with the DL-segments’ exteriors, however, theThe Head-Body-Tail Intersection for Spatial Relations Between DL Segments283

difference between these two configurations could be captured: Fig. 2a’s bodies have
empty intersections with the opposite DL-segment’s exteriors, whereas Fig. 2b’s
bodies have non-empty intersections with the opposite DL-segments’ exteriors. The
extension by considering the exteriors of DL segments in addition to their heads,
bodies, and tails requires a total of 16 types of intersections, which are represented by
the hbt+-matrix, a 4×4 matrix whose top-left 3×3 submatrix is identical to theconfiguration’s hbt-matrix.
Among the 216 = 65,536 configurations with empty and non-empty values for the
hbt+-matrix, only 80 configurations have geometric interpretations. This number
includes the 68 configurations obtained with the hbt-intersection plus another twelve
configurations, each of which is a more constrained version of an hbt-intersection.
These twelve configurations are shown in Table 4. The TR-classes that are capturedby the hbt+-matrix include a specification of the equivalence relations for DL
segments as a refinement of TR-class #44, constraining the two bodies to coincide,and none of the two bodies to extend through the other DL-segment’s exterior.
The addition of these twelve TR-classes also has an impact on the conceptual
neighborhood graph. Since twelve TR-classes in the hbt-intersection are subdivided
into 24 TR-classes in the hbt+-intersection, the layer containing these twelve TRclasses (i.e., the upper layer in Fig. 6a) is split into two layers: one for the twelve
collapsed TR-classes and another for 34 non-collapsed TR-classes with body-bodyintersections. Consequently, the conceptual neighborhood graph’s structural
framework consists of three parallel planes stacked on top of each other in the
flattened version (Fig. 8a), or three tori nested transitively into each other (Fig. 8b).
Table 4. Collapsed topological relations and non-collapsed topological relations that can be
distinguish by the hbt+-intersection, but not by the hbt-intersection
Collapsed
#44

#48

#52

#54

#56

#58

Non-collapsed

§ I
¨
¨ I
¨ I
¨
¨ I
©

I
I
I ·
¸
I ¸
I I
I I I ¸¸II I ¸¹

§ I
¨
¨ I
¨ I
¨
¨ I
©

I
I
I ·
¸
I I I ¸
I I I ¸¸I I I ¸¹

§ I
¨
¨ I
¨ I
¨
¨ I
©

I
I
I
I

§ I
¨
¨ I
¨ I
¨
¨ I
©

I
I
I
I

I
I ·
¸
I
I ¸
I
I ¸
¸
I I ¸¹I
I ·¸I I ¸II ¸¸I I ¸¹I
I ·§ I I¨¸¨ I I I  I ¸¨ III I ¸¨¸¨ III I ¸¹©

I
I ·§ I I¨¸¨ I I I I ¸
¨ II
I I ¸¨¸¨ I I I I ¸©
¹

II I ·§ I¨¸¨ I I I I ¸
¨ I
I I I ¸¨¸¨ III I ¸¹©

I
I I ·§ I¨¸¨ I I I I ¸
¨ I
I I I ¸¨¸¨ I I I I ¸©
¹

I ·§ I I I¨¸I ¸¨ I I I¨ I III ¸¨¸¨ I I I I ¸©
¹

I ·§ I I I¨¸¨ I I I I ¸
¨ I III ¸¨¸¨ I I I I ¸©
¹

I I I ·
§ I
¨
¸
I ¸
¨ I I I¨ I I I
I ¸
¨
¸
¨
¸
© I I I I ¹

I I I ·§ I¨¸¨ I  I I I ¸
¨ I I I
I ¸
¨
¸
¨
¸
© I I I I ¹

Collapsed
#45

#49

#53

#55

#57

#59

§ I
¨
¨ I
¨ I
¨
¨ I
©
§ I
¨
¨ I
¨ I
¨
¨ I
©

Non-collapsed

I I I ·
¸
I ¸
I I
I
I
I ¸
¸
I
I I ¸¹

§ I
¨
¨ I
¨ I
¨
¨ I
©
§ I
¨
¨ I
¨ I
¨
¨ I
©

I

I

I

I

I
I

I
I

I ·
¸
I ¸
I ¸
¸
I ¸¹

I

I

I

I
I
I

I
I
I

I

I

I

I
I

I
I

I

·
¸
I ¸
I ¸
¸
I ¸¹
I ·
¸
I ¸
I ¸
¸
I ¸¹

I
I ·
§ I I¨¸I ¸¨ I I I¨ I I I
I ¸¨¸¨ I I I I ¸
©
¹

I
I ·
§ I I¨¸¨ I  I I I ¸
¨ I I I
I ¸¨¸¨ I I I I ¸©
¹

I ·§ I I I¨¸I ¸¨ I I I¨ I
I I I ¸¨¸¨ I I I I ¸©
¹

I ·§ I I I¨¸¨ I I I I ¸
¨ I
I I I ¸¨¸¨ I I I I ¸©
¹

I I I ·§ I¨¸¨ I I I I ¸
¨ II
I I ¸¨¸¨ III I ¸¹©

I I I ·§ I¨¸¨ I I I I ¸
¨ II
I I ¸¨¸¨ I I I I ¸©
¹

II I ·§ I¨¸¨ I I I I ¸
¨ I I
I
I ¸
¨
¸
¨
I
I I ¹¸© I

I
I I ·§ I¨¸¨ I I I I ¸
¨ I I
I
I ¸
¨
¸
¨
¸
© I I I I ¹

284

Y. Kurata and M.J. Egenhofer

collapsed
TR-classes

non-collapsed
TR-classes
with body-bodyintersections
TR-classes
without
body-bodyintersections

(a)

(b)

Fig. 8. Structures of the conceptual neighborhood graph of the 80 TR-classes obtained by the
hbt+-intersection, where nodes are aligned on (a) three parallel planes or (b) the surfaces ofthree tori nested transitively in each other.

7

Conclusions

This paper classified the topological relations between two directed line segments into
80 classes, 68 of them were identified by the head-body-tail intersection, whereasintersections with the line segments’ exteriors were needed to distinguish theremaining 12 cases. The 80 relations’ conceptual neighborhood graph revealed astructure of three parallel planes or three nested tori. For the first time, such acomprehensive account of a conceptual neighborhood graph involving DL segment
relations in a 2-dimensional space has been determined.
Future work about directed line relations will address the expressive power of thematrices’ empty and non-empty intersections. If the hbt-matrix and hbt+-matrix
continue to record the existence/non-existence of the intersections, then thecorresponding intersection models cannot distinguish some critical topologicalrelations (Fig. 9). The development of more detailed model of the topologicalrelations between DL segments will contribute to an improvement of the reasoning
power about directed line segments.

Æ

⎛ φ
⎜
⎜ φ
⎜ φ
⎜
⎜ ¬φ
⎝

φ

φ
φ
φ
φ
¬φ ¬ φ
¬φ

¬φ ⎞
⎟
¬φ ⎟
¬φ ⎟
⎟
¬φ ⎟⎠

Fig. 9. Sets of DL segments, whose topological relations cannot be distinguished by the hbtintersections or hbt+-intersections

Acknowledgments
This work was partially supported by the National Geospatial-Intelligence Agency
under grant number NMA201-01-1-2003 and NMA401-02-1-2009.

The Head-Body-Tail Intersection for Spatial Relations Between DL Segments

285

References
Alexandroff, P. (1961) Elementary Concepts of Topology. Dover: Mineola, NY.
Allen, J. (1983) Maintaining Knowledge About Temporal Intervals. Communications of theACM. 26(11):832-843.
Clementini, E. and di Felice, P. (1998) Topological Invariants for Lines. IEEE Transactions on
Knowledge and Data Engineering. 10(1):38-54.
Clementini, E., di Felice, P., and van Oosterom, P. (1993) A Small Set of Formal Topological
Relationships Suitable for End-User Interaction. in: Abel, D. and Ooi, B.-C. (eds.) Advancesin Spatial Databases, Third International Symposium, SSD'93, Singapore, Lecture Notes in
Computer Science, 692, 277-295.
Egenhofer, M. (1994) Definitions of Line-Line Relations for Geographic Databases. IEEE Data
Engineering Bulletin. 16(3):40-45.
Egenhofer, M. (1997) Query Processing in Spatial-Query-by-Sketch. Journal of Visual
Languages and Computing. 8(4):403-424.
Egenhofer, M. (2005) Spherical Topological Relations. Journal on Data Semantics III.25-49.
Egenhofer, M. and Al-Taha, K. (1992) Reasoning About Gradual Changes of Topological
Relationships. in: Frank, A., Campari, I. and Formentini, U. (eds.) Theories and Methods ofSpatio-temporal Reasoning in Geographic Space, Pisa, Italy, Lecture Notes in Computer
Science, 639, 196-219.
Egenhofer, M. and Franzosa, R. (1991) Point-Set Topological Spatial Relations. International
Journal of Geographical Information Systems. 5(2):161-174.
Egenhofer, M. and R. Franzosa, R. (1995) On the Equivalence of Topological Relations.
International Journal of Geographical Information Systems. 9(2): 133-152, 1995.
Egenhofer, M. and Herring, J. (1991) Categorizing Binary Topological Relationships between
Regions, Lines and Points in Geographic Databases. in: Egenhofer, M., Herring, J., Smith,
T. and Park, K. (eds.) A Framework for the Definitions of Topological Relationships and an
Algebraic Approach to Spatial Reasoning within This Framework, NCGIA Technical
Reports 91-7. National Center for Geographic Information and Analysis: Santa Barbara, CA.
Egenhofer, M. and Mark, D. (1995) Modeling Conceptual Neighborhoods of Topological LineRegion Relations. International Journal of Geographical Information Systems. 9(5):555565.
Egenhofer, M., Sharma, J. and Mark D. (1993) A Critical Comparison of the 4-Intersection andthe 9-Intersection Models for Spatial Relations: Formal Analysis. in: McMaster, R. andArmstrong, M. (eds.) Autocarto 11, Minneapolis, MD, 63-71.
Erwig, M. and Schneider, M. (1999) Developments in Spatio-Temporal Query Languages. in:10th International Workshop on Database & Expert Systems Application, Florence, Italy,
IEEE Computer Society, 441-449.
Freksa, C. (1992a) Temporal Reasoning Based on Semi-Intervals. Artificial Intelligence.
54:199-227.
Freksa, C. (1992b) Using Orientation Information for Qualitative Spatial Reasoning. in: Frank,
A., Campari, I. and Formentini, U. (eds.) The International Conference GIS—From Space toTerritory: Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, New
York, NY, Lecture Notes in Computer Science, 639, 162-178.
Goyal, R. and Egenhofer, M. (2000) Consistent Queries over Cardinal Directions across Different
Levels of Detail. in: Tjoa, A.M., Wagner, R., and Al-Zobaidie, A. (eds.), 11th International
Workshop on Database and Expert Systems Applications, Greenwich, U.K. 876-880.
Hadzilacos, T. and Tryfona, N. (1992) Model for Expressing Topological Integrity Constraints
in Geographic Databases. in: Frank, A., Campari, I. and Formentini, U. (eds.) The
International Conference GIS—From Space to Territory: Theories and Methods of SpatioTemporal Reasoning in Geographic Space, New York, NY, Lecture Notes in Computer
Science, 639, 252-268.

286

Y. Kurata and M.J. Egenhofer

Herring, J. (1991) The Mathematical Modeling of Spatial and Non-Spatial Information in
Geographic Information Systems. in: Mark, D. and Frank A. (eds.) Cognitive and Linguistic
Aspects of Geographic Space, Kluwer: Dordrecht, Netherlands, 313-350.
Hoel, E. and Samet, H. (1991) Efficient Processing of Spatial Queries in Line Segment
Databases. in: Gunther, O. and Schek, H.-J. (eds.) Advances in Spatial Databases—2nd
Symposium, SSD'91, New York, NY, Lecture Notes in Computer Science, 525, 237-256.
Hornsby, K., Egenhofer, M. and Hayes, P. (1999) Modeling Cyclic Change. in: Chen, P.,
Embley, D., Kouloumdjian, J., Liddle, S. and Roddick, J. (eds.) Advances in Conceptual
Modeling, Paris, France, Lecture Notes in Computer Science, 1227, 98-109.
Krieg-Brückner, B. and Shi, H. (2005) Orientation Calculi + Route Graphs: Towards Semantic
Representations of Route Descriptions. Dagstuhl Seminar on Spatial Cognition:
Specialization and Integration, http://www.dagstuhl.de/files/Materials/05/05491/ 05491.
KriegBruecknerBernd.Slides.pdf
Kurata, Y. and Egenhofer, M. (2005a) Semantics of Simple Arrow Diagrams. in: Barkowsky,
T., Freksa, C., Hegarty, M. and Lowe, R. (eds.) AAAI Spring Symposium on Reasoning with
Mental and External Diagram: Computational Modeling and Spatial Assistance, Stanford,
CA, 101-104.
Kurata, Y. and Egenhofer, M. (2005b) Structure and Semantics of Arrow Diagrams. in: Cohn,
A. and Mark, D. (eds.) COSIT '05, Ellicottville, NY, Lecture Notes in Computer Science,
3693, 232-250.
Kurata, Y. and Egenhofer, M. (2006) Topological Relations of Arrow Symbols in Complex
Diagrams. in: D. Barker-Plummer, R. Cox, and N. Swoboda (eds.), Diagrams 2006: FourthInternational Conference on the Theory and Application of Diagrams, Stanford, CA,
Lecture Notes in Artificial Intelligence, 4045, 112-126.
Mark, D. and Egenhofer, M. (1994) Modeling Spatial Relations between Lines and Regions:
Combining Formal Methods and Human Subjects Testing, Cartography and Geographic
Information Systems. 21(4):195-212.
Moratz, R., Renz, J. and Wolter, D. (2000) Qualitative Spatial Reasoning About Line
Segments. in: Horn, W. (ed.) 14th European Conference on Artificial Intelligence, Berlin,
Germany, 234-238.
Nedas, K., Egenhofer, M. and Wilmsen, D. (in press) Metric Details of Topological Line-Line
Relations. International Journal of Geographical Information Science.
Papadias, D., Theodoridis, Y., Sellis, T., and Egenhofer, M. (1995) Topological Relations in theWorld of Minimum Bounding Rectangles: A Study with R-Trees. In: Carey, M. andSchneider, D. (eds.) SIGMOD RECORD 24 (2): 92-103.
Pullar, D. and Egenhofer, M. (1988) Towards Formal Definitions of Topological Relations
among Spatial Objects. Third International Symposium on Spatial Data Handling, Sydney,
Australia, 225-241.
Renz, J. (2001) A Spatial Odyssey of the Interval Algebra: 1. Directed Intervals. in: Nebel, B.
(ed.) International Joint Conference on Artificial Intelligence 2001, Seattle, WA, 51-56.
Reis, R., Egenhofer, M., and Mattos, J. (2005) Grafos de Vinzihanças Conceptuais para
Relações Topológicas entre Linhas em R2. Fourth National Conference for Cartography
and Geodesy, Lisbon, Portugal, http://www.igeo.pt/Igeo/portugues/Novidades_eventos/
eventos/Lisboa/ivcncg_reis.pdf.
Schlieder, C. (1995) Reasoning About Ordering. in: Frank, A. and Kuhn, W. (eds.) COSIT '95,
Lecture Notes in Computer Science, 988, 341-349.
Shariff, A., Egenhofer, M. and Mark, D. (1998) Natural-Language Spatial Relations between
Linear and Areal Objects: The Topology and Metric of English-Language Terms.
International Journal of Geographical Information Science. 12(3):215-246.