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.
%0 Journal Article
%1 pssuw-lpw-Algorithmica03
%A Poon, Sheung-Hung
%A Shin, Chan-Su
%A Strijk, Tycho
%A Uno, Takeaki
%A Wolff, Alexander
%D 2003
%J Algorithmica
%K GIS combinatorial_optimization job_scheduling label_placement maximum_weight_independent_set myown sliding_labels throughput_maximization
%N 2
%P 341--362
%R 10.1007/s00453-003-1063-0
%T Labeling Points with Weights
%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(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.
@article{pssuw-lpw-Algorithmica03,
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 = {2024-07-14T10:03:47.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/awolff},
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 = {GIS combinatorial_optimization job_scheduling label_placement maximum_weight_independent_set myown sliding_labels throughput_maximization},
number = 2,
pages = {341--362},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/pssuw-lpw-03.pdf},
succeeds = {pssw-lpw-01i},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Labeling Points with Weights},
volume = 38,
year = 2003
}