| Full text | |
| Author(s): |
Cano, Rafael G.
;
de Souza, Cid C.
;
de Rezende, Pedro J.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | THEORETICAL COMPUTER SCIENCE; v. 789, p. 16-pg., 2019-10-15. |
| Abstract | |
Interactive maps are maps that allow users to execute operations that alter the state of the visualization. Two of the most common operations are rotation and scaling. As one of these operations is executed, labels must maintain their size, shape and orientation. This may cause labels that were previously disjoint to overlap. For each label, we must determine a set of active ranges (i.e., intervals of angles or scales during which the label is visible) such that no pair of overlapping labels is ever active simultaneously. The objective is to maximize the total length of the active ranges of all labels. We prove a number of properties of optimal solutions which allow us to significantly reduce the size of an integer programming formulation from the literature. These properties are independent of the particular choice of operation, which makes our reduction techniques extremely flexible. We report the results of several experiments employing operations of rotation and scaling, and 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 formulation, which led to a decrease of up to three orders of magnitude in running times. (C) 2018 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 12/00673-2 - A study of combinatorial optimization problems related to data visualization |
| Grantee: | Rafael Ghussn Cano |
| Support Opportunities: | Scholarships in Brazil - Doctorate (Direct) |