Point Labeling with Sliding Labels
, , and .
Computational Geometry: Theory and Applications 13 (1): 21--47 (1999)

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.
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).