Information Technology Reference
In-Depth Information
An important concept in shape-spaces that is used for the definition of affinity (cf.
section 4) is that of complementarity. It can be defined for binary strings in a natural
way but can be adopted for arbitrary shape-spaces. The complement of an element
i
is
denoted as
compl
(
i
). Often the complement is defined with respect to a third element
c
and will be denoted by
compl
c
(
i
,
c
) or
i
c
for short. If we assume that the distance
function is the only structure that is defined on the carrier set of the shape-space
(nothing has been said about any other structure) then the complement must be
defined by means of the distance function alone. All elements of the space that have
the distance
d
(
i
,
c
) from
c
lie on the surface of an
n
-dimensional ball with center
c
and
radius
d
(
i
,
c
). There is a point on this surface that has the distance 2
d
(
i
,
c
) (the
diameter of the ball) from
i
. This point will be taken as the desired element
i
c
. But is
this point uniquely determined? It depends on the distance function
d
.
For instance for the function we get
d
(
i
,
c
) =
d
(
i
c
,
c
) =
d
(
i
,
i
c
) = 1, thus a
complementary element cannot be uniquely determined. We want to exclude distance
functions of this type and this can be done by an additional condition on distance
functions, the so called
triangle inequation
(cf. [10]): For an arbitrary element
z
(iv)
d
(
x
,
y
)
≤
d
(
x
,
z
) +
d
(
z
,
y
)
Notice that with this additional condition the distance function becomes a metric and
the shape-space a metric space. Now for the complement
i
c
according to the definition
above it must hold
d
(
i
,
c
) =
d
(
c
,
i
c
). Together with the triangle inequation we get
d
(
i
,
i
c
)
d
(
i
,
c
) +
d
(
c
,
i
c
) = 2
d
(
i
,
c
). On the other hand,
i
c
shall be the point farthest away
from
i
but still on the ball, i.e. its distance from
i
should be at least the diameter of the
ball, in other words,
d
(
i
,
i
c
)
≤
2
d
(
i
,
c
), so altogether
d
(
i
,
i
c
) = 2
d
(
i
,
c
). However, the
triangle inequation is only a necessary condition for the existence of such a point, not
a sufficient one.
An important concept in metric spaces is the
≥
ε
-
ball
(cf. [10]). An
ε
-ball centered at
some point
i
is the set
b
(
-ball
depends on the distance function. For the Euclidean distance the ball is defined by
(
ε
,
i
) = {
x
∈
S
:
d
(
i
,
x
) <
ε
}. Obviously, the form of the
ε
)
n
i
(
)
n
, a ball in
3
,
∑
=
n
i
or
∑
=
which is a hyperball in
ℜ
ℜ
2
2
2
x
−
y
<
ε
x
−
y
<
ε
i
i
i
i
1
1
2
. For the Manhattan distance, the
and a circle in
-ball is a hyperrhombus of
dimension
n
with 2
n
planes, i.e. in the three-dimensional case it is a regular diamond
with eight planes and in the two-dimensional case it is a rhombus, as is shown in [6].
Let us examine these two metrics with respect to complementary elements.
Clearly, in the Euclidean metric the complement
i
c
of
i
is a unique point. All other
points on the surface of the ball around
c
have a shorter distance from
i
than
i
c
. In the
Manhattan metric, things are different. Consider the case illustrated in figure 1 for two
dimensions. All points on the thick side of the rhombus have the same distance from
c
and therefore also from
i
, thus there is no unique complementary point
i
c
. This follows
from the Manhattan metric as can be easily proved. Consider the two points
p
and
q
with the coordinates (
c
1
,
c
2
-
L
) and (
c
1
+
L
,
c
2
) for some
L
> 0,
L
is half the length of
the diagonal. An arbitrary point
y
on the line between
p
and
q
has the coordinates (
ℜ
ε
λ
c
1
+ (1 −
λ
)(
c
1
+
L
),
λ
(
c
2
-
L
) + (1 −
λ
)
c
2
) = (
c
1
+ (1 −
λ
)
L
,
c
2
-
λ
L
) with 0
≤
λ
≤
1. The
distance of this point from
c
according to Manhattan distance is computed by
