Publications in Scientific Journals:

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

English abstract:
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

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Electronic version of the publication:

Created from the Publication Database of the Vienna University of Technology.