Information Technology Reference
In-Depth Information
l
s
l
t
l
s
l
t
l
s
q
t
l
t
q
t
q
s
p
t
=
a
h
p
s
a
2
q
s
p
t
p
s
=
a
1
P
p
t
q
t
t
q
s
r
t
r
s
r
t
P
s
P
s
P
t
P
s
s
t
P
t
s
P
t
t
s
t
(a)
(b)
(c)
Fig. 3.
Paths
P
s
and
P
t
intersect if: (a)
x
(
p
s
)
≥ x
(
t
),(b)
x
(
s
)
<x
(
p
t
)
<x
(
p
s
)
<x
(
t
),and
(c)
x
(
s
)
<x
(
p
s
)
<x
(
p
t
)
<x
(
t
)
lie on the border of
H
P
. Denote by
l
s
and
l
t
the vertical half-lines starting at
s
and
t
,
respectively, and directed towards increasing
y
-coordinates; also, denote by
q
s
and
q
t
the intersection points of
l
s
and
l
t
with the border of
H
P
, respectively. Finally, denote
by
Q
the curve obtained by clockwise following the border of
H
P
from
q
s
to
q
t
.
P
s
starts at
s
and passes through
a point
r
s
on
l
t
(possibly
r
s
=
q
t
), given that
x
(
p
s
)
Assume that
x
(
p
s
)
≥
x
(
t
),asinFig. 3(a). Path
P
t
starts at
t
and
either passes through a point
r
t
on
l
s
, or ends at a point
p
t
on
Q
, depending on whether
x
(
p
t
)
≥
x
(
t
). Path
≤
x
(
s
) or
x
(
p
t
)
>x
(
s
), respectively. Since
P
s
is
x
-monotone and lies in
H
P
,
it follows that
r
t
and
p
t
are above or on
P
s
;also,
t
is below
P
s
given that
P
s
is a high
path. It follows
P
t
intersect, hence they share a vertex given that
G
is planar.
Analogously, if
x
(
p
t
)
P
s
and
≤
x
(
s
),then
P
s
and
P
t
share a vertex.
If
x
(
p
t
)=
x
(
p
s
),then
P
s
∪P
t
is a
ʸ
-path from
s
to
t
.
Next, if
x
(
s
)
<x
(
p
t
)
<x
(
p
s
)
<x
(
t
),asinFig. 3(b), then the end-points of
P
s
and
P
t
alternate along the boundary of the region
R
that is the intersection of
H
P
,ofthe
half-plane to the right of
l
s
, and of the half-plane to the left of
l
t
.Since
P
s
and
P
t
are
x
-monotone, they lie in
R
,thus they intersect, and hence they share a vertex.
Finally, assume that
x
(
s
)
<x
(
p
s
)
<x
(
p
t
)
<x
(
t
),asinFig. 3(c). Let
a
1
,...,a
h
be
the clockwise order of the points along
Q
, starting at
p
s
=
a
1
and ending at
a
h
=
p
t
.
By the assumption
x
(
p
s
)
<x
(
p
t
) we have
h ≥
2. We prove that
a
1
a
2
is a
ʸ
-edge.
Suppose, for a contradiction, that
a
1
a
2
is not a
ʸ
-edge. Since the slope of
a
1
a
2
is larger
than
−
90
ⓦ
and smaller than 90
ⓦ
, it is either larger than
ʸ
+45
ⓦ
and smaller than 90
ⓦ
,
or it is larger than
45
ⓦ
. First, assume that the slope of
a
1
a
2
is larger than
ʸ
+45
ⓦ
and smaller than 90
ⓦ
,asinFig. 4(a). Since the slope of
sa
1
is
between
ʸ
90
ⓦ
and smaller than
ʸ
−
−
45
ⓦ
and
ʸ
+45
ⓦ
, it follows that
a
1
is below the line composed of
sa
2
and
a
2
t
, which contradicts the assumption that
a
1
is on
Q
. Second, if the slope of
a
1
a
2
is
larger than
−
45
ⓦ
, then we distinguish two further cases. In
the first case, represented in Fig. 4(b), the slope of
a
1
t
is larger than
ʸ
90
ⓦ
and smaller than
ʸ
−
−
45
ⓦ
, hence
a
2
is below the line composed of
sa
1
and
a
1
t
, which contradicts the assumption that
a
2
is on
Q
. In the second case, represented in Fig. 4(c), the slope of
a
1
t
is in the interval
[
−
45
ⓦ
]. It follows that the slope of
ta
1
is in the interval [90
ⓦ
;
ʸ
+ 135
ⓦ
];since
the slope of
ta
h
is smaller than the one of
ta
1
,wehavethat
90
ⓦ
;
ʸ
−
−
P
t
is not a (
ʸ
+ 180
ⓦ
)-
path. This contradiction proves that
a
1
a
2
is a
ʸ
-edge. However, this contradicts the
assumption that
P
s
is a maximal
ʸ
-path, and hence concludes the proof of Claim 1.
We now prove Claim 2. First, we prove that, for
every
ʸ
in the interval [
45
ⓦ
;45
ⓦ
],
there exists a maximal
ʸ
-path starting at
s
that is low or high. Indeed, it suffices to prove
−
