Abstract
We study a dynamic labeling problem on rotating maps, i.e., maps that allow for continuous rotations. As the map is rotated, labels must remain horizontally aligned. Rotations may cause labels that were previously disjoint to overlap. For each label, we must determine a set of active ranges (i.e., angular ranges during which the label is visible) such that at any rotation angle all active labels are disjoint. The objective is to maximize the sum of the angular length of all active ranges. We prove a number of properties of optimal solutions which allow us to significantly reduce the size of an integer programming model from the literature. We report the results of several experiments using two existing benchmarks with 180 real-world instances. We obtained reductions of over 100 times in the number of variables and constraints of the model. The compact formulation solved all but 5 instances to optimality in under a minute.
Supported by Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), grant 2012/00673-2, and Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), grants #155498/2016-9, #311140/2014-9 and #304727/2014-8.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Been, K., Daiches, E., Yap, C.: Dynamic map labeling. IEEE Trans. Vis. Comput. Graph. 12(5), 773–780 (2006)
Gemsa, A., Nöllenburg, M., Rutter, I.: Consistent labeling of rotating maps. J. Comput. Geom. 7(1), 308–331 (2016)
Gemsa, A., Nöllenburg, M., Rutter, I.: Evaluation of labeling strategies for rotating maps. ACM J. Exp. Algorithmics 21(1), 1.4:1–1.4:21 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Cano, R.G., de Souza, C.C., de Rezende, P.J. (2017). Fast Optimal Labelings for Rotating Maps. In: Poon, SH., Rahman, M., Yen, HC. (eds) WALCOM: Algorithms and Computation. WALCOM 2017. Lecture Notes in Computer Science(), vol 10167. Springer, Cham. https://doi.org/10.1007/978-3-319-53925-6_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-53925-6_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53924-9
Online ISBN: 978-3-319-53925-6
eBook Packages: Computer ScienceComputer Science (R0)