Information Technology Reference
In-Depth Information
If we wish to have more control over the aspect ratio in ourfinaldrawing, we can pick
a set of primitive vectors contained inside a triangle spanned by the grid points (0
,
0),
(
m
x
,
0)
,
(
m
x
,m
y
). By stretching the triangle and keeping its area fixed, we may end
up with fewer primitive vectors. This will result in an (only slightly) smaller constant
compared to the case
m
x
=
m
y
.AsprovenbyBarany and Rote [5, Thm. 2], any such
triangular domain contains at least
m
x
m
y
/
4 primitive vectors. This implies that we
can adapt the algorithm easily to control the aspect ratio by selecting the box for the
primitive vectors accordingly. For the sake of simplicity, we detail ouralgorithms only
for the most interesting case (
m
x
=
m
y
).
Lemma 1.
Let
P
ↆ
P
d
be a set of
k
=
|
P
d
|
/c
primitive vectors withno coordinate
greater than
d
for someconstant
c
≥
1
.Then any twoprimitive vectors of
P
are
separated by an angle of
ʩ
(1
/k
)
.
2
ˀ
2
ck/
3. Any line with
slope
m
encloses an angle
ʱ
with the
x
-axis, such that tan(
ʱ
)=
m
.Let
m
1
and
m
2
be the slopes of two lines and let
ʱ
1
and
ʱ
2
be the corresponding angles with respect
to the
x
-axis. By the trigonometric addition formulas we have that the separating angle
of these two lines equals
=3
d
2
/ˀ
2
+
O
(
d
log
d
) we have that 2
d
2
Proof.
Since
|
P
d
|
≈
ʱ
2
)=
tan
ʱ
1
−
tan
ʱ
2
1+tan
ʱ
1
tan
ʱ
2
=
m
2
1+
m
1
m
2
.
m
1
−
tan
ˆ
:= tan(
ʱ
1
−
For any two neighboring entries
p/q
and
r/s
in the Farey sequence, it holds that
qr
−
ps
=1[8, Thm. 3.1.2], and therefore
p/q
and
r/s
differ by exactly (
qr
ps
)
/
(
qs
)=
1
/
(
qs
). As a consequence, tan
ˆ
=1
/
(
pr
+
qs
).Theangle
ˆ
is minimized if
pr
+
qs
is maximized. Clearly, we have that
pr
+
qs <
2
d
2
−
2
ˀ
2
ck/
3. By the Taylor
≈
x
2
ʾ/
(1 +
ʾ
2
)
2
for some value 0
expansion, arctan(
x
)=
x
−
≤
ʾ
≤
x
.Substituting
x
with 3
/
(2
ˀ
2
ck
) yields, for
k
≥
2,that
3
2
ˀ
2
ck
−
9
ʾ
4
ˀ
4
c
2
k
2
(1 +
ʾ
2
)
2
>
3
2
ˀ
2
ck
−
9
4
ˀ
4
c
2
k
2
=
ʩ
(1
/k
)
.
ˆ
≥
Since the best possible resolution for a set of
k
primitive vectors is 2
ˀ/k
, Lemma 1
shows that the resolution of our set differs from the optimum by at most a constant.
3
Monotone Grid Drawings with Good Angles
We s t a r t b y e n suring that convex tree drawings are crossing-free. This has already been
stated by Carlson and Eppstein [6].
Lemma 2.
Any convex straight-linedrawing of a tree is crossing-free.
We now present a simple method for drawing atreeonagrid in a strictly convex,
and therefore monotone and, by Lemma 2, crossing-free way. We name ourstrategy
the
inorder-algorithm
.Thealgorithm first computes a reasonable large set of primitiv
vectors, then selects a subset of these vectors and finally assigns the slopes to the edges.
