Labeling Points with Weights
Source file as Postscript Document
Portable Document Format
Preprint series: Preprint-Reihe Mathematik, 7/2001
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\log 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.
Next we describe a factor-2 approximation for the case that the number of different weights is bounded and a PTAS for labeling points with sliding unit-square labels. Finally, for instances with a constant ratio $\beta$ of maximum to minimum label height we give algorithms with approximation factors of $3 \lceil \log_2 \beta \rceil$ and $(3+\varepsilon) \lceil \log_2 \beta \rceil$ assuming fixed-position and slider models, respectively.