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.
%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-07-14T10:03:47.000+0200},
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-07-14T10:03:47.000+0200},
title = {Point Labeling with Sliding Labels},
volume = 13,
year = 1999
}