S. Poon, C. Shin, T. Strijk, and A. Wolff. Proc. 17th European Workshop on Computational
Geometry (EWCG'01), page 97--100. Berlin, (2001)
Abstract
Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually refered 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 unit-height labels. We
give an $O(nn)$-time factor-2 approximation
algorithm for fixed-position models and the first
algorithm for labeling weighted points with sliding
labels. Its approximation factor is
$(2+\varepsilon)$ and its runtime in
$O(n^2/\varepsilon)$ for any $\varepsilon>0$.
%0 Conference Paper
%1 pssw-lpw-01
%A Poon, Sheung-Hung
%A Shin, Chan-Su
%A Strijk, Tycho
%A Wolff, Alexander
%B Proc. 17th European Workshop on Computational
Geometry (EWCG'01)
%C Berlin
%D 2001
%K myown
%P 97--100
%T Labeling Points with Weights
%X Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually refered 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 unit-height labels. We
give an $O(nn)$-time factor-2 approximation
algorithm for fixed-position models and the first
algorithm for labeling weighted points with sliding
labels. Its approximation factor is
$(2+\varepsilon)$ and its runtime in
$O(n^2/\varepsilon)$ for any $\varepsilon>0$.
@inproceedings{pssw-lpw-01,
abstract = {Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually refered 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 unit-height labels. We
give an $O(n\log n)$-time factor-2 approximation
algorithm for fixed-position models and the first
algorithm for labeling weighted points with sliding
labels. Its approximation factor is
$(2+\varepsilon)$ and its runtime in
$O(n^2/\varepsilon)$ for any $\varepsilon>0$.},
added-at = {2024-07-14T10:03:47.000+0200},
address = {Berlin},
author = {Poon, Sheung-Hung and Shin, Chan-Su and Strijk, Tycho and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2cbc2f2e28b1d1d4acb684f4c2b59f812/awolff},
booktitle = {Proc. 17th European Workshop on Computational
Geometry (EWCG'01)},
cites = {bd-itmrt-00, c-accgc-96, ejs-ptasg-01, htc-eafmw-92,
i-mlp-99, sk-pepls-99, ksw-plsl-99, ZZZ},
confmonth = {{26--28~}#mar},
interhash = {4cb63dc42599fb1da7aa8fbc67741e56},
intrahash = {cbc2f2e28b1d1d4acb684f4c2b59f812},
keywords = {myown},
pages = {97--100},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/pssw-lpw-01.pdf},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Labeling Points with Weights},
year = 2001
}