[Back]

A. Gemsa, B. Niedermann, M. Nöllenburg:
"A Unified Model and Algorithms for Temporal Map Labeling";
Algorithmica (online), 82 (2020), 2709 - 2736.

We consider map labeling for the case that a map undergoes a sequence of operations
such as rotation, zoom and translation over a specified time span. We unify
and generalize several previous models for dynamic map labeling into one versatile
and flexible model. In contrast to previous research, we completely abstract from the
particular operations and express the labeling problem as a set of time intervals representing
the labels´ presences, activities and conflicts. One of the model´s strength
is manifested in its simplicity and broad range of applications. In particular, it supports
label selection both for map features with fixed position as well as for moving
entities (e.g., for tracking vehicles in logistics or air traffic control). We study the
active range maximization problem in this model. We prove that the problem is NPcomplete
and W[1]-hard, and present constant-factor approximation algorithms. In
the restricted, yet practically relevant case that no more than k labels can be active at
any time, we give polynomial-time algorithms as well as constant-factor approximation
algorithms.

http://dx.doi.org/10.1007/s00453-020-00694-7

https://publik.tuwien.ac.at/files/publik_292475.pdf