TY - GEN
T1 - Optimizing active ranges for consistent dynamic map labeling
AU - Been, Ken
AU - Nöllenburg, Martin
AU - Poon, Sheung Hung
AU - Wolff, Alexander
PY - 2008
Y1 - 2008
N2 - 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 ld-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 ld-ARO are NP-complete, even for quite simple shapes. We solve simple ld-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants.
AB - 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 ld-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 ld-ARO are NP-complete, even for quite simple shapes. We solve simple ld-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants.
KW - Approximation algorithms
KW - Dynamic map labeling
KW - NP-hard-ness
UR - http://www.scopus.com/inward/record.url?scp=57349152103&partnerID=8YFLogxK
U2 - 10.1145/1377676.1377681
DO - 10.1145/1377676.1377681
M3 - Conference contribution
AN - SCOPUS:57349152103
SN - 9781605580715
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 10
EP - 19
BT - Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
T2 - 24th Annual Symposium on Computational Geometry, SCG'08
Y2 - 9 June 2008 through 11 June 2008
ER -