Information Technology Reference
In-Depth Information
II
I
b
v
d
D
l
D
r
v
l
r
v
c
D
v
f
v
a
s
v
III
IV
(a) sketch of the inductive step
(b) outputofouralgorithm for a tree of height 3
Fig. 4.
Strongly monotone drawings of proper binary trees
Duetoourinductive construction that uses disjoint disk sections for different sub-
trees, it is clear that the two paths do not intersect. Moreover, each vertex on the two
paths is convex, that is, the angle that such a vertex forms inside
f
is less than
ˀ
.This
is due to the fact that we always turn right when we go from
v
to
a
, and we always turn
left when we goto
b
.Vertex
v
is also convex since the two edges from
v
to its children
lie in the same half-plane (bounded by
s
v
).
It remains to show that the two rays
a
and
b
(defined analogously to
v
above) don't
intersect. To this end, recall that
v
=
v
∩
C
.Byour construction,
a
and
b
are orthogonal
to two chords of
C
that are both incident to
v
. Clearly, the two chords form an angle of
less than
ˀ
in
v
. Hence, the two rays diverge, and the face
f
is strictly convex.
For the proof that the algorithm described above yields a strongly monotone draw-
ing, we need the following tools. Let
v
1
and
v
2
be two vectors. We say that
v
3
lies
between
v
1
and
v
2
if
v
3
is a positive linear combination of
v
1
and
v
2
. For two vec-
tors
v
and
w
,wedefine
v
,
w
=
|
v
||
w
|
cos(
v
,
w
) as the scalar product of
v
and
w
.
Lemma 6.
If a path
p
is monotone with respect to two vectors
v
1
and
v
2
,then it is
monotone with respect to any vector
v
3
between
v
1
and
v
2
.
Proof.
Let
v
3
=
ʻ
1
v
1
+
ʻ
2
v
2
with
ʻ
1
,ʻ
2
>
0.Assume that the path
p
is given by the
sequence of vectors
w
1
,
w
2
,...,
w
k
.Since
p
is monotone with respect to vectors
v
1
and
v
2
,wehavethat
v
1
,
w
i
>
0 and
v
2
,
w
i
>
0 for all
i
≤
k
. This yields, for all
i
≤
k
,
v
3
,
w
i
=
ʻ
1
v
1
+
ʻ
2
v
2
,
w
i
=
ʻ
1
v
1
,
w
i
+
ʻ
2
v
2
,
w
i
>
0
,
since
ʻ
1
,ʻ
2
>
0. It follows that
p
is monotone with respect to
v
3
.
Lemma 7.
Fo r a proper binary tree rooted inadummy vertex, thedisk-algorithm yields
a stronglymonotonedrawing.
Proof.
We split the drawing into four sectors: I, II, III and IV; see Fig.4b.Let
a
and
b
be two vertices in the graph. We will show that the path that connects
a
and
b
in the
drawing outputbyouralgorithm is strongly monotone. Let
c
be the root of the tree.
W. l . o .g., assume that
a
lies in sector III. Then, we distinguish three cases.
