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(nn)$-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.
%0 Journal Article
%1 pssuw-lpw-03
%A Poon, Sheung-Hung
%A Shin, Chan-Su
%A Strijk, Tycho
%A Uno, Takeaki
%A Wolff, Alexander
%D 2003
%J Algorithmica
%K
%N 2
%P 341--362
%R 10.1007/s00453-003-1063-0
%T Labeling Points with Weights
%U http://dx.doi.org/10.1007/s00453-003-1063-0
%V 38
%X 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(nn)$-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.
@article{pssuw-lpw-03,
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\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. 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.},
added-at = {2010-04-13T09:41:39.000+0200},
author = {Poon, Sheung-Hung and Shin, Chan-Su and Strijk, Tycho and Uno, Takeaki and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2c00886ac095c96a3c4a9c9af0340f754/fink},
cites = {af-aesam-84, aks-lpmis-98, bd-mpatm-00, c-cgitf-99, cms-esapf-95, ejs-ptasg-01, fw-ppalm-91, gimprw-lsl-01, gj-cigtn-79, h-aanpa-82, hm-ascpp-85, htc-eafmw-92, i-mlp-99, m-ctcc-80, pssw-lpw-01i, sk-pepls-02, ksw-plsl-99, ws-mlb-96, z-sl01i-90, ZZZ},
doi = {10.1007/s00453-003-1063-0},
interhash = {f2c789c64b0b1a22f752ed99d0720c3d},
intrahash = {c00886ac095c96a3c4a9c9af0340f754},
journal = {Algorithmica},
keywords = {},
number = 2,
pages = {341--362},
pdf = {#AWPUBURL#pssuw-lpw-03.pdf},
succeeds = {pssw-lpw-01i},
timestamp = {2010-04-13T09:41:39.000+0200},
title = {Labeling Points with Weights},
url = {http://dx.doi.org/10.1007/s00453-003-1063-0},
volume = 38,
year = 2003
}