Zusammenfassung
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.
Nutzer