Information Technology Reference
In-Depth Information
Luatodonotes:
Boundary Labeling for Annotations in Texts
Philipp Kindermann, Fabian Lipp, and Alexander Wolff
Lehrstuhl für Informatik I, Universität Würzburg, Germany
http://www1.informatik.uni-wuerzburg.de/en/staff
Abstract. We present a tool for annotating Latex documents with com-
ments. Our annotations are placed in the left, right, or both margins,
and connected to the corresponding positions in the text with arrows
(so-called leaders ). Problems of this type have been studied under the
name boundary labeling . We consider various leader types (straight-line,
rectilinear, and Bézier) and modify existing algorithms to allow for anno-
tations of varying height. We have implemented our algorithms in Lua;
they are available for download as an easy-to-use Luatex package.
1
Introduction
Many word processing systems support annotations for the text. The most com-
mon case for this annotations are comments, which can be inserted in arbitrary
positions inside the text. The comments themselves are placed as labels in the
margin next to the text and connected to the corresponding position, called site ,
by a line called leader . The endpoint of a leader at a label is called a port . Such
comments are available, for example, in LibreOce (see Fig. 1) and Microsoft
Word. This task can be expressed in the boundary labeling notion introduced by
Bekos et al. [5]: the sites to be annotated lie inside the text area and the labels are
to be placed outside the text area. They describe several types of leaders, such
as straight-line leaders ( s -leaders), rectilinear leaders with one bend ( po -leaders)
and rectilinear leaders with two bends ( opo -leaders).
Previous work. Boundary labeling has been extensively investigated in the last
few years, see a survey on the interaction between cartography and graph draw-
ing [17]. For labels of uniform size, the problem is well-studied. Most algorithms
try to minimize the total leader length. For s -leaders, it suces to compute a
minimum-weight perfect matching, which can be done in O ( n 2+ ʵ ) time [1]. For
opo -leaders, Bekos et al. [5] gave three different algorithms for the number of sides
used by the labels, with running times O ( n log n ) (one-sided), O ( n 2 ) (two-sided),
and O ( n 2 log 3 n ) (four-sided). Further, they presented an O ( n 2 )-time algorithm
for po -leaders that lie on one side or on two opposite sides of the text. The result
for po -leaders was improved by Benkert et al. [6] for the one-sided case. They
gave an O ( n log n )-time algorithm for length minimization and an O ( n 3 )-time
algorithm for a very general class of objective functions, including, for example,
Search WWH ::




Custom Search