TY - JOUR
T1 - Optimizing active ranges for consistent dynamic map labeling
AU - Been, Ken
AU - Nöllenburg, Martin
AU - Poon, Sheung Hung
AU - Wolff, Alexander
N1 - Funding Information:
E-mail addresses: kbeen@cyrusinnovation.com (K. Been), spoon@cs.nthu.edu.tw (S.-H. Poon). URLs: http://www.iti.uka.de/group/noelle (M. Nöllenburg), http://www.win.tue.nl/~awolff (A. Wolff). 1 Supported by grant WO 758/4-3 of the German Research Foundation (DFG). 2 Supported by grant 97-2218-E-007-006 of the National Science Council (NSC), Taiwan, ROC.
PY - 2010/4
Y1 - 2010/4
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. We use a model for consistent dynamic labeling in which a label is represented by 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 intersect and the sum of the heights of the active ranges is maximized. Simple ARO 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. 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.
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. We use a model for consistent dynamic labeling in which a label is represented by 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 intersect and the sum of the heights of the active ranges is maximized. Simple ARO 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. 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.
KW - Active range optimization
KW - Approximation algorithms
KW - Consistent dynamic map labeling
KW - NP-hardness
UR - http://www.scopus.com/inward/record.url?scp=84867962715&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2009.03.006
DO - 10.1016/j.comgeo.2009.03.006
M3 - Article
AN - SCOPUS:84867962715
SN - 0925-7721
VL - 43
SP - 312
EP - 328
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 3
ER -