A Unified Model and Algorithms for Temporal Map Labeling
- PDF / 3,816,574 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 19 Downloads / 205 Views
A Unified Model and Algorithms for Temporal Map Labeling Andreas Gemsa1 · Benjamin Niedermann2 · Martin Nöllenburg3
© The Author(s) 2020
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 algorithms. Keywords Dynamic map labeling · Unified map labeling model · Approximation algorithms · Complexity results · Geometric packing algorithms · Dynamic programming · Polynomial time algorithms
Preliminary versions of this paper have appeared as follows. Trajectory-Based Dynamic Map Labeling In: Proc. 24th Int. Symp. on Algorithms and Computation (ISAAC’13), volume 8283 of Lect. Notes in Comput. Sci., pages 413–423. Springer, 2013 and Temporal Map Labeling: A New Unified Framework with Experiments In: Proc. 24th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems (GIS’16), pages 23:1–23:10, ACM, 2016. * Benjamin Niedermann niedermann@uni‑bonn.de Martin Nöllenburg [email protected] 1
Karlsruhe Institute of Technology, Karlsruhe, Germany
2
University of Bonn, Bonn, Germany
3
TU Wien, Vienna, Austria
13
Vol.:(0123456789)
Algorithmica
(a) Zooming.
(b) Panning.
(c) Rotation.
Fig. 1 Illustration of interactive maps providing zooming, panning, and rotation as user interaction
1 Introduction Dynamic digital maps are becoming more and more ubiquitous, especially with the rising numbers of location-based services and smartphone users worldwide. Consumer applications that include personalized and interactive map views range from classic navigation systems to map-based search engines and social networking services. Likewise, interactive digital maps are a core component of professional geographic information systems. All these map services have in common that the content of the map view is changing over time based on interaction with the system (i.e., zooming, panning, rotating, content filtering, etc.; see Fig. 1 for a schematic illustration of interactive maps) or based on the physical movement of the user or a set of tracked entities. Creatin
Data Loading...
