Zusammenfassung
Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually referred to as label
placement. We define nine label-placement models for
labeling points with axis-parallel rectangles given
a weight for each point. There are two groups;
fixed-position models and slider models. We aim to
maximize the weight sum of those points that receive
a label. We first compare our models by giving
bounds for the ratios between the weights of
maximum-weight labelings in different models. Then
we present algorithms for labeling $n$ points with
unit-height rectangles. We show how an $O(nłog
n)$-time factor-2 approximation algorithm and a PTAS
for fixed-position models can be extended to handle
the weighted case. Our main contribution is the
first algorithm for weighted sliding labels. Its
approximation factor is $(2+\varepsilon)$, it runs
in $O(n^2/\varepsilon)$ time and uses
$O(n/\varepsilon)$ space. We show that other than
for fixed-position models even the projection to one
dimension remains NP-hard. For slider models we
also investigate some special cases, namely (a)~the
number of different point weights is bounded,
(b)~all labels are unit squares, and (c)~the ratio
between maximum and minimum label height is
bounded.
Nutzer