Practical Extensions of Point Labeling in the Slider Model* |
| |
Authors: | Tycho Strijk Marc van Kreveld |
| |
Affiliation: | (1) ASM Lithography, Veldhoven, The Netherlands;(2) Department of Computer Science, Utrecht University, The Netherlands |
| |
Abstract: | This paper extends 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 in interactive and on-line mapping. |
| |
Keywords: | point feature label placement algorithms computational geometry |
本文献已被 SpringerLink 等数据库收录! |