Information Technology Reference
In-Depth Information
Case 1:
a
and
b
lie on a common root-leaf path; see
a
and
v
in Fig.4b.Obviously,
b
lies in sector III. W.l.o.g., assume that
b
lies on a path between
a
and
c
. By construc-
tion, all edges in sector III, seen as vectors directed towards
c
, lie between
x
=(0
,
1)
and
y
=(1
,
0).Thus, all edges on the path from
a
to
b
, and in particular
ab
, lie be-
tween
x
and
y
.Since
x
is perpendicular to
y
, the path from
a
to
b
is monotone with
respect to
x
and
y
. Following Lemma 6, the path between
a
and
b
is monotone with
respect to
ab
,andthusstrongly monotone.
Case 2:
b
lies in sector I; see
a
and
d
in Fig. 4b. In Case 1, we have shown that the
all edges on the path from
a
to
c
lie between
x
=(0
,
1) and
y
=(1
,
0).Analogously,
the same holds for the path from
c
to
b
.Thus, the path between
a
and
b
is monotone
with respect to
x
and
y
and, following Lemma 6, strongly monotone.
Case 3:
a
and
b
do not lie on a common root-leaf path, and
b
does not lie in
sector I; see
a
and
b
in Fig.4b.Let
d
be the lowest common ancestor of
a
and
b
.
Let
a
0
,a
1
,...,a
k−
1
,a
k
be the path from
d
to
a
where
a
0
=
d
and
a
k
=
a
.Now,
let
b
0
,b
1
,...,b
m−
1
,b
m
be the path from
d
to
b
where
d
=
b
0
and
b
=
b
m
. Finally, let
p
=
a
k
,a
k−
1
,...,a
0
,b
1
,...,b
m−
1
,b
m
be the path from
a
to
b
.
Below, we describe how to rotate and
mirror the drawing such that the any vec-
tor
−−−−ₒ
A
i
A
i
d
a
i−
1
B
k
lies between
x
=
(0
,
1) and
y
=(1
,
0), and any vector
−−−−ₒ
a
i
,a
i−
1
, 1
≤
i
≤
a
i
b
j−
1
,b
j
,
b
B
m
a
1
−
y
.This
statement is equivalent to
x
(
a
i
)
<x
(
d
)
<
x
(
b
j
)
,
1
≤
j
≤
m
lies between
x
and
A
Fig. 5.
Illustration of case 3 in the proof of
Lemma 7
m
and
y
(
a
k
)
<
...<y
(
a
1
)
<y
(
d
)
>y
(
b
1
)
>...>y
(
b
m
);
see Fig.5.If
b
lies in sector IV, then
d
=
c
and this statement is true by construction. If
b
lies in sector II, then
d
is a child of
c
. We rotate the drawing by
ˀ/
2 in counterclockwise
direction and then mirror it horizontally. If
b
lies in sector III, let
p
(
d
) be the parent of
d
.
We rotate the drawing such that the edge (
p
(
d
)
,d
) is drawn vertically. Recall that, by
construction, the ray from
d
in direction
−−−ₒ
≤
i
≤
k,
1
≤
j
≤
−
y
separates the subtrees of the two
children of
d
;seeFig.4a.Further, the angle between any edge (directed away from
d
)
in the subtree of
d
and
−−−ₒ
p
(
d
)
d
=
p
(
d
)
d
=
−
y
is at most
ˀ/
2, i.e., they are directed downwards.
k
be the straight line through
a
i
and perpendicular to
−−−−ₒ
a
i−
1
a
i
.
Let
A
i
be the parallel line to
A
i
that passes through
a
.Duetothe
x
-monotonicity of
p
the point
a
lies below
A
i
.During the construction of the tree, the line
A
i
defined a
circular sector in which the subtree rooted at
a
i
including
a
was exclusively drawn. It
follows that
a
and
b
lie on opposite sites of
A
i
.Thus,
b
lies above
A
i
and also above
A
i
.
Let
B
j
,
1
Let
A
i
,
1
≤
i
≤
m
be the straight line through
b
j
and perpendicular to
−−−−ₒ
b
j−
1
b
j
.Let
B
j
be the parallel line to
B
j
that passes through
a
. By construction,
b
lies below
B
j
and
a
lies above
B
j
.Thus,
b
lies below
B
j
.
Let
A
be the line
A
i
with maximum slope and let
B
be the line
B
j
with minimum
slope. First, we will show that the path is monotone with respect to the unit vector
A
on
A
directed to the right. By choice of
A
,theangle between any edge (
a
i
,a
i−
1
)
,
1
≤
j
≤
≤
k
and
A
is at most
ˀ/
2. Recall that any vector
−−−−ₒ
i
k
lies between
x
and
y
.Since
A
is perpendicular to one of these edges and directed to the right, it lies
≤
a
i
,a
i−
1
, 1
≤
i
≤
