Information Technology Reference
In-Depth Information
Tabl e 1 . Running times of the different label styles on three one-page documents D1,
D2, and D3 (in CPU seconds). The times were measured using a Intel Core 2 Duo
E8400 with 3.0 GHz. D1 is the instance with 9 comments shown in the figures above.
D2 has 15 comments, D3 has 25. For each document, we report two running times; for
label placement into one margin vs. both margins. We use a raster height of 1 cm for
po
-leaders, resulting in 28 horizontal strips. We couldn't use
po
-leaders for D3 with one
margin because the algorithm needed too much memory. For comparison we also give
the running times for the classical
todonotes
package (which does not support placing
labels in both margins) and the running times for the document without loading the
luatodonotes
package.
Document
D1
D2
D3
Number of margins
1
2
1
2
1
2
s
-leaders
1.8
1.7
1.9
1.9
2.2
2.2
Bézier leaders
5.7
5.4
33.2
11.1
322.9
116.3
po
-leaders
4.8
3.0
17.7
6.2
—
27.6
po
-leaders avoiding text lines
7.0
4.0
26.8
9.5
—
42.4
opo
-leaders
1.8
1.7
1.9
1.9
2.2
2.2
classical
todonotes
1.9
2.2
2.6
without
luatodonotes
1.4
1.4
1.3
6 Conclusion and Open Problems
All our algorithms turned out to work well in practice—some of them cannot
process too many labels on a single page. Using both margins helps in terms of
speed. By visual inspection we reached the conclusion that
s
-leaders or Bézier
leaders work better than the
os
-leaders used by other type-setting programs.
The reason may be that the reader's eye can follow leaders without bends more
easily. It would be interesting to verify this in a user study. With the modular
design of our Latex package it is easy to improve the label-placement algorithms
or add additional ones.
An interesting theoretical problem remains open: Given an instance with non-
uniform label heights, is it always possible to place the labels without gaps so
that
s
-leaders do not cross each other even if we insist that the ports are centered
vertically at each label?
We have some ideas for further improvements of our package. The force-
directed Bézier curve algorithm is quite slow at the moment. We think that
we could speed up the computation of the distances between curves by doing a
rough estimate first and computing the fine approximation only when needed.
It would be interesting to transform the
po
-leaders into Bézier curves. As our
algorithm yields a length-minimal
po
-labeling this could produce a shorter leader
length than our approach with
s
-leaders. But it is not clear how to inhibit inter-
sections between the curves.
Admittedly, our dynamic program for
po
-leaders is quite slow. Can we save
time by computing labelings that are just feasible rather than length-minimal?
For the other leader types, on the contrary, it would be interesting to minimize
