Labeling Points with Weights
, , , , und .
Algorithmica 38 (2): 341--362 (2003)

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.
  • @awolff
  • @dblp
  • @fink
Diese Publikation wurde noch nicht bewertet.

Durchschnittliche Benutzerbewertung0,0 von 5.0 auf Grundlage von 0 Rezensionen
    Bitte melden Sie sich an um selbst Rezensionen oder Kommentare zu erstellen.