Fast Optimal Labelings for Rotating Maps

Autor(es)

Cano, Rafael G. ; de Souza, Cid C. ; de Rezende, Pedro J. ; Poon, SH ; Rahman, MS ; Yen, HC

• Tipo de documento: Artigo Científico
• Fonte: WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017; v. 10167, p. 13-pg., 2017-01-01.

Resumo

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. (AU)

• Processo FAPESP: 12/00673-2 - Estudo de problemas de otimização combinatória relacionados a visualização de dados
• Beneficiário: Rafael Ghussn Cano
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto