8 Using Qualitative Information in Query Proc. over Multiresolution Maps
171
Table 8.1. Definition of the reference set of topological relationships
name
definition
object type
disjoint (d)
f 1 ∩ f 2 = ∅
all
touch (t)
( f
◦
1 ∩ f
◦
2 = ∅) ∧ ( f 1 ∩ f 2 ) ∅
R/R, R/L, R/P, L/L, L/P
in (i)
( f 1 ∩ f 2 = f 1 ) ∧ ( f
◦
1 ∩ f
◦
2 ) ∅
R/R, L/L, L/R, P/R, P/L
contain (c)
( f 1 ∩ f 2 = f 2 ) ∧ ( f
◦
1 ∩ f
◦
2 ) ∅
R/R, R/L, R/P, L/L, L/P
equal (e)
f 1 = f 2
R/R, L/L, P/P
cross (r)
dim( f
◦
1 ∩ f
◦
2 ) =
L/R
(max(dim( f
◦
1 ), dim( f
◦
2 )) − 1) ∧
( f 1 ∩ f 2 ) f 1 ∧ ( f 1 ∩ f 2 ) f 2
L/L
overlap (o)
dim( f
◦
1 ) = dim( f
◦
2 ) = dim( f
◦
1 ∩ f
◦
2 ) ∧ R/R
( f 1 ∩ f 2 ) f 1 ∧ ( f 1 ∩ f 2 ) f 2
L/L
cover (v)
( f 2 ∩ f 1 ) = f 2 ∧ ( f
◦
2 ∩ f
◦
1 ) ∅ ∧
R/R, R/L, L/L
( f 1 − f
◦
1 ) ∩ ( f 2 − f
◦
2 ) ∅
coveredby (vb)
( f 1 ∩ f 2 = f 1 ) ∧ ( f
◦
1 ∩ f
◦
2 ) ∅ ∧
R/R, L/L, L/R
( f 1 − f
◦
1 ) ∩ ( f 2 − f
◦
2 ) ∅
In defining the distance between two 9-intersection matrices ψ 1 and ψ 2 (denoted
by d 9 (ψ 1 , ψ 2 )), we adopt the approach proposed in [7] and we define it as the fraction
between the number of different cells in the two matrices and the total number of cells
(9). Two cells are considered different if one corresponds to a non-empty intersection
(whatever is its dimension) and the other to an empty intersection.
3
Based on this distance, given two relationships ψ 1 and ψ 2 in T REL, their distance
can now be computed as the minimum distance between any 9-intersection matrix
defining ψ 1 and any 9-intersection matrix defining ψ 2 . We have chosen the minimum
and not the average or other functions as we are interested in maximizing similarity
among topological relations after dimension changes.
Definition 8.1 (Topology Distance). Let θ 1 ∈ T REL(d 1 , d 2 ) and θ 2 ∈ T REL(d 3 , d 4 ).
The topology distance between θ 1 and θ 2 is defined as follows:
d t (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )) =
min{d 9 (ψ 1 , ψ 2 )|ψ 1 ∈ I 9 (θ 1 , d 1 , d 2 ), ψ 2 ∈ I 9 (θ 2 , d 3 , d 4 )}.
Example 8.1. Suppose we want to compute d t (Contain, (R, L), In, (L, R)). Based on
Table 8.1 and on the results presented in [2], it is possible to show that Contain over
(R, L) corresponds to the following two 9-intersection matrices:
Contain 1 =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
¬∅ ¬∅ ¬∅
∅ ∅ ¬∅
∅ ∅ ¬∅
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Contain 2 =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
¬∅ ¬∅ ¬∅
¬∅ ∅ ¬∅
∅ ∅ ¬∅
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
3 Note that the dimension of the intersection is not taken into account when computing the
distance.