BibSonomy now supports HTTPS. Switch to HTTPS.

Abstract

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. \par 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. \par 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.

Links and resources

URL:
BibTeX key:
pssuw-lpw-Algorithmica03
search on:

Comments and Reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication