Practical extensions of point labeling in the slider model

Abstract

This paper extends on research by the authors together with Alexander Wolff on point label placement using a model where labels can be placed at any position that touches the point (the slider model). Such models have been shown to perform better than methods that allow only a fixed number of positions per label. The novelties in this paper include respecting other map features that must be avoided by the labels, and incorporating labels with different height. The result is an efficient and simple O((n + m) log(n + m)) time algorithm with a performance guarantee for label placement in the slider model. Here n is the number of points to be labeled and m is the combinatorial complexity of the map features that must be avoided. Due to its efficiency, the algorithm can be used m interactive and on-line mapping.