Information Technology Reference
In-Depth Information
leaf of f .Atvertex v we have at least two outgoing edges. Let e 1 be the first outgoing
edgeand e 2 be the last outgoing edgeat v - one of the edges is e . By the selection of
the slope ranks we have s ( e 1 ) <s ( e ) <s ( e 2 ). As a consequence, the supporting line
of e separates e 1 and e 2 , and hence both faces containing e have an angle less than ˀ
at v and therefore ʱ<ˀ .
Next, we show that the edges and rays of a face do not intersect. Then, by Lemma 2,
no edges will cross. Assume that there are two edges/rays and r in a common face
that have an intersection in some point x .Let t be the lowest common ancestor of
and r and assume that lies on the path to the left leaf and r on the path to the right
leaf. We define a closed polygonal chain P of as follows. The chain starts with the path
from t to , continues via x to r , and finally returns to t . We direct the edges according
to this walk (for measuring the directed slopes) and call them e 1 ,e 2 ,...,e k .Wemay
assume that P is simple, otherwise we find another intersection point. By Lemma 4, the
slopes are monotone when we traverse P .For i =1 ,...,k
1,let ʱ i be the difference
between the directed slopes of the edges e i and e i +1 . Then the sum i<k ʱ i equals
the angle between the slopes of e 1 and e k .Duetorequirement (R2), this angle is less
than ˀ .Let ʲ i = ˀ
ʱ i be the angle between e i and e i +1 in P ,andlet ʲ 0 > 0 be the
“interior” angle at t .Wehavethat
ʲ i = ʲ 0 +
1 ≤i<k
( ˀ
ʱ i ) > 0+( k
1) ˀ
ˀ =( k
2) ˀ.
0 ≤i<k
This, however, contradicts the fact that the angle sum of the polygon with boundary P
is ( k
2) ˀ .Thus, ourassumption that two edges/rays cross was wrong.
Since the drawing is assembled from n
1 vectors whose absolute coordinates are at
most O ( n ), the complete drawinguses a grid of dimension O ( n 1 . 5 )
O ( n 1 . 5 ).Since
all vectors are reflections of (a subset of) vectors defined by a Farey sequence with at
most n entries, Lemma 1 yields that the angular resolution is bounded by ʩ (1 /n ).
×
We conclude this section with comparing ourresult with the drawing algorithm of
Carlson and Eppstein [6]. Their algorithm produces a drawing with optimal angular res-
olution. It draws trees convex, but, in contrast to ouralgorithm, not necessarily strictly
convex. Allowing parallel leaf edges can have a great impact on the angular resolution.
However, our ideas can be applied to modify the algorithm of Carlson and Eppstein.
For the leaf edges, their algorithm uses a set of k slopes and picks the slopes such that
they are separated by an angle of 2 ˀ/k . The slopes of interior edges have either one
of the slopes of the leaf edges, or are chosen such that they bisect the wedge spanned by
their outermost child edges. However, it suffices to assure that the slope of an interior
edge differs from the extreme slopes in the following subtree by at least 2 ˀ/ (2 k ).
We can now modify the algorithm as follows. We pick 2 k/ 8 primitive vectors and
reflect them such that they fill the whole angular space with 2 k distinct integral vectors.
We use every other vector of this set for the leaf edges. For an interior edgewetakeany
vector from our preselected set whose slope lies in between the extreme slopes of the
edges in its subtree. We can always find such a vector, since we have sufficiently spaced
outour set of primitive vectors. By this we obtain a drawing on the O ( n 1 . 5 )
O ( n 1 . 5 )
grid. Clearly, the drawing doesn't have optimal angular resolution. However, since we
×
Search WWH ::




Custom Search