Point set labeling with sliding labels
Marc J. van Kreveld, Tycho Strijk, Alexander Wolff · 1998
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 allows more points to be labeled both in theory and in practice. We define six different models of labeling, and analyze how much better---more points get a label---one model can be than another. Maximizing the number of labeled points is NP-hard, but we show that all models have a polynomialtime approximation scheme, and all models have a simple and efficient factor- 1 2 approximation algorithm. Finally, we give experimental results based on the factor- 1 2 approximation algorithm to compare the models in practice. 1 Introduction Annotating sets of points is a common task to be performed in Geographic Information Systems. Cities on small-scale maps are shown as points with the city's name attached (Figure 1 shows names as rectangles), points of altitude usually are small "+"-signs with a value, and ...