Information Technology Reference
In-Depth Information
W
ʸ
(
a
)
p
1
p
k
a
Fig. 2.
Wedge
W
ʸ
(
a
) contains path
P
a
between
a
and
q
. By definition of
ʸ
-path, for every point
a
on
, the closed wedge
W
ʸ
(
a
) with an angle of 90
ⓦ
incident to
a
and whose delimiting lines have slope
ʸ
P
45
ⓦ
−
and
ʸ
+45
ⓦ
contains the subpath
P
a
of
P
from
a
to
p
k
. Hence, by Lemma 3 in [9],
P
is
self-approaching from
p
1
to
p
k
.Ananalogous proof shows that
P
is self-approaching
is a (
ʸ
+ 180
ⓦ
)-path from
p
k
to
p
1
.
from
p
k
to
p
1
, given that
P
We now prove that Gabriel triangulations contain
ʸ
-paths.
Lemma 4.
Let
G
be aGabriel triangulation onapointset
P
.Forevery two points
s, t
∈
P
,there exists an angle
ʸ
such that
G
contains a
ʸ
-path from
s
to
t
.
P
. Clockwise rotate
G
of an angle
ˆ
so that
y
(
s
)=
y
(
t
) and
x
(
s
)
<x
(
t
). Observe that, if there exists a
ʸ
-path from
s
to
t
after the
rotation, then there exists a (
ʸ
+
ˆ
)-path from
s
to
t
before the rotation.
A
ʸ
-path (
p
1
,...,p
k
) in
G
is
maximal
if there is no
z
Proof.
Consider any two points
s, t
∈
∈
P
such that
p
k
z
is a
ʸ
-
edge. For every maximal
ʸ
-path
H
P
.
Namely, assume the converse, for a contradiction. Since
G
is a Gabriel triangulation, the
angle between any two consecutive edges incident to an internal vertex of
G
is smaller
than 90
ⓦ
,thusthereisa
ʸ
-edgeincidentto
p
k
. This contradicts the maximality of
P
=(
p
1
,...,p
k
) in
G
,
p
k
lies on the border of
.
A maximal
ʸ
-path (
s
=
p
1
,...,p
k
) is
high
if either (a)
y
(
p
k
)
>y
(
t
) and
x
(
p
k
)
<
x
(
t
),or(b)
p
i
p
i
+1
intersects the vertical line through
t
at a point above
t
,forsome
1
P
1. Symmetrically, a maximal
ʸ
-path (
s
=
p
1
,...,p
k
) is
low
if either (a)
y
(
p
k
)
<y
(
t
) and
x
(
p
k
)
<x
(
t
),or(b)
p
i
p
i
+1
intersects the vertical line through
t
at a
point below
t
,forsome1
≤
i
≤
k
−
1.Highandlow(
ʸ
+ 180
ⓦ
)-paths starting at
t
can
be defined analogously. The proof of the lemma consists of two main claims.
Claim 1.
If a maximal
ʸ
-path
≤
i
≤
k
−
P
s
starting at
s
and a maximal (
ʸ
+180
ⓦ
)-path
P
t
starting
45
ⓦ
≤
45
ⓦ
,
at
t
exist such that
P
s
and
P
t
are both high or both low, for some
−
ʸ
≤
then there exists a
ʸ
-path in
G
from
s
to
t
.
Claim 2.
For some
45
ⓦ
≤
45
ⓦ
, there exist a maximal
ʸ
-path
−
ʸ
≤
P
s
starting at
s
and
a maximal (
ʸ
+ 180
ⓦ
)-path
P
t
starting at
t
that are both high or both low.
Observe that Claims 1 and 2 imply the lemma.
We now prove Claim 1. Suppose that
G
contains a maximal high
ʸ
-path
P
s
starting
at
s
and a maximal high (
ʸ
+ 180
ⓦ
)-path
45
ⓦ
≤
45
ⓦ
.
P
t
starting at
t
,forsome
−
ʸ
≤
If
P
s
and
P
t
share a vertex
v
∈
P
, then the subpath of
P
s
from
s
to
v
and the subpath
of
P
t
from
v
to
t
form a
ʸ
-path in
G
from
s
to
t
.Thus, it suffices to show that
P
s
and
P
t
share a vertex. For a contradiction assume the converse. Let
p
s
and
p
t
be the
end-vertices of
P
s
and
P
t
different from
s
and
t
, respectively. Recall that
p
s
and
p
t
