%0 Journal Article %1 ksw-plsl-CGTA99 %A van Kreveld, Marc %A Strijk, Tycho %A Wolff, Alexander %D 1999 %J Computational Geometry: Theory and Applications %K approximation_scheme greedy_approximation_algorithm map_labeling myown point_annotation %N 1 %P 21--47 %R 10.1016/S0925-7721(99)00005-X %T Point Labeling with Sliding Labels %V 13 %X This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some finite number of positions. We show that continuously sliding labels allow more points to be labeled both in theory and in practice. We define six different models of labeling. We compare models by analyzing how many more points can receive labels under one model than another. We show that maximizing the number of labeled points is NP-hard in the most general of the new models. Nevertheless, we give a polynomial-time approximation scheme and a simple and efficient factor-1/2 approximation algorithm for each of the new models. Finally, we give experimental results based on the factor-1/2 approximation algorithm to compare the models in practice. We also compare this algorithm experimentally to other algorithms suggested in the literature.

@article{ksw-plsl-CGTA99, abstract = {This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some finite number of positions. We show that continuously sliding labels allow more points to be labeled both in theory and in practice. We define six different models of labeling. We compare models by analyzing how many more points can receive labels under one model than another. We show that maximizing the number of labeled points is NP-hard in the most general of the new models. Nevertheless, we give a polynomial-time approximation scheme and a simple and efficient factor-1/2 approximation algorithm for each of the new models. \par Finally, we give experimental results based on the factor-1/2 approximation algorithm to compare the models in practice. We also compare this algorithm experimentally to other algorithms suggested in the literature.}, added-at = {2024-02-18T09:53:56.000+0100}, author = {van Kreveld, Marc and Strijk, Tycho and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/21f2e95569cc7a24ed335815e882d7234/awolff}, doi = {10.1016/S0925-7721(99)00005-X}, interhash = {45578184d9de2158ec23008ea839dcbc}, intrahash = {1f2e95569cc7a24ed335815e882d7234}, journal = {Computational Geometry: Theory and Applications}, keywords = {approximation_scheme greedy_approximation_algorithm map_labeling myown point_annotation}, number = 1, pages = {21--47}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/ksw-plsl-99.pdf}, timestamp = {2024-02-18T12:36:59.000+0100}, title = {Point Labeling with Sliding Labels}, volume = 13, year = 1999 }