ABSTRACT
Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning-an application with increasing practical importance. In consistent dynamic map labeling, distracting behavior such as popping and jumping is avoided. In the model for consistent dynamic labeling that we use, a label becomes a 3d-solid, with scale as the third dimension. Each solid can be truncated to a single scale interval, called its active range, corresponding to the scales at which the label will be selected. The active range optimization (ARO) problem is to select active ranges so that no two truncated solids overlap and the sum of the heights of the active ranges is maximized. The simple ARO problem is a variant in which the active ranges are restricted so that a label is never deselected when zooming in. We investigate both the general and simple variants, for 1d- as well as 2d-maps. The 1d-problem can be seen as a scheduling problem with geometric constraints, and is also closely related to geometric maximum independent set problems. Different label shapes define different ARO variants. We show that 2d-ARO and general 1d-ARO are NP-complete, even for quite simple shapes. We solve simple 1d-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants.
- P. K. Agarwal, M. van Kreveld, and S. Suri. Label placement by maximum independent set in rectangles. Comput. Geom. Theory Appl., 11:209--218, 1998. Google ScholarDigital Library
- K. Been, E. Daiches, and C. Yap. Dynamic map labeling. IEEE Trans. Visualization and Computer Graphics, 12(5):773--780, 2006. Google ScholarDigital Library
- B. Chazelle and 36 co-authors. The computational geometry impact task force report. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223, pages 407--463. AMS, 1999.Google ScholarCross Ref
- M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. Google ScholarDigital Library
- J. Christensen, J. Marks, and S. Shieber. An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics, 14(3):203--232, 1995. Google ScholarDigital Library
- M. Formann and F. Wagner. A packing problem with applications to lettering of maps. In Proc. 7th Annu. ACM Sympos. Comput. Geom. (SoCG'91), pages 281--288, 1991. Google ScholarDigital Library
- D. S. Hochbaum and W. Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32:130--136, 1985. Google ScholarDigital Library
- D. E. Knuth and A. Raghunathan. The problem of compatible representatives. SIAM J. Discr. Math., 5(3):422--427, 1992. Google ScholarDigital Library
- D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329--343, 1982.Google ScholarDigital Library
- I. Petzold, G. Gröger, and L. Plümer. Fast screen map labeling?data-structures and algorithms. In Proc. 23rd Internat. Cartographic Conf. (ICC'03), pages 288--298. Durban, South Africa, 2003.Google Scholar
- I. Petzold, L. Plümer, and M. Heber. Label placement for dynamically generated screen maps. In Proc. 19th Internat. Cartographic Conf. (ICC'99), pages 893--903. Ottawa, Canada, 1999.Google Scholar
- S.-H. Poon and C.-S. Shin. Adaptive zooming in point set labeling. In M. Liškiewicz and R. Reischuk, editors, Proc. 15th Internat. Sympos. Fundam. Comput. Theory (FCT'05), volume 3623 of Lecture Notes Comput. Sci., pages 233--244. Springer-Verlag, 2005. Google ScholarDigital Library
- M. van Kreveld, T. Strijk, and A. Wolff. Point labeling with sliding labels. Comput. Geom. Theory Appl., 13:21--47, 1999. Google ScholarDigital Library
- A. Wolff and T. Strijk. The map-labeling bibliography. i11www.ira.uka.de/map-labeling/bibliography, 1996.Google Scholar
Index Terms
- Optimizing active ranges for consistent dynamic map labeling
Recommendations
Evaluation of Labeling Strategies for Rotating Maps
Special Issue SEA 2014, Regular Papers and Special Issue ALENEX 2013We consider the following problem of labeling points in a dynamic map that allows rotation. We are given a set of feature points in the plane labeled by a set of mutually disjoint labels, where each label is an axis-aligned rectangle attached with one ...
Optimizing active ranges for consistent dynamic map labeling
Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning-an application with increasing practical importance. In consistent dynamic map labeling, distracting behavior such as popping and jumping is ...
Approximation algorithms on consistent dynamic map labeling
We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every scale and the sum of total visible ...
Comments