2013 | OriginalPaper | Buchkapitel
Trajectory-Based Dynamic Map Labeling
verfasst von : Andreas Gemsa, Benjamin Niedermann, Martin Nöllenburg
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we introduce
trajectory-based labeling
, a new variant of dynamic map labeling where a movement trajectory for the map viewport is given. We define a general labeling model and study the active range maximization problem in this model. The problem is
$\cal NP$
-complete and
$\mathcal W[1]$
-hard. In the restricted, yet practically relevant case that no more than
k
labels can be active at any time, we give polynomial-time algorithms. For the general case we present a practical ILP formulation with an experimental evaluation as well as approximation algorithms.