Trajectory-based dynamic map labeling

DOI10.1007/978-3-642-45030-3_39MaRDI QIDQ2872105zbMATH OpenOpenAlexFDO

Authors Andreas Gemsa, Benjamin Niedermann, Martin Nöllenburg

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.3963

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 NP-complete and 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.

Recommendations

• A unified model and algorithms for temporal map labeling
• Optimizing active ranges for consistent dynamic map labeling
• Approximation algorithms on consistent dynamic map labeling
• Dynamic point labeling is strongly PSPACE-complete
• Consistent labeling of rotating maps

Cited in

(10)

• A unified model and algorithms for temporal map labeling
• Consistent dynamic map labeling with fairness and importance
• Solving dynamic labeling problems to optimality using solution space reductions
• Labeling moving points with a trade-off between label speed and label overlap
• Placing arrows in directed graph drawings
• Minimum point-overlap labelling*
• Dynamic point labeling is strongly PSPACE-complete
• Evaluation of labeling strategies for rotating maps
• Minimum point-overlap labeling
• Quantum speedups for polynomial-time dynamic programming algorithms

This page was built for publication: Trajectory-based dynamic map labeling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872105)