%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 %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 = {2010-04-13T09:41:43.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/fink}, 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 = {}, pages = {97--100}, pdf = {#AWPUBURL#pssw-lpw-01.pdf}, timestamp = {2010-04-13T09:41:43.000+0200}, title = {Labeling Points with Weights}, year = 2001 }