A study of combinatorial optimization problems related to data visualization

• Grant number: 12/00673-2
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)
• Start date: April 01, 2012
• End date: August 04, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Rafael Ghussn Cano
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated scholarship(s): 13/23571-3 - Optimization algorithms for GeoVisualization, BE.EP.DD

Abstract

The process of decision making, in the context of operations research, consists of analyzing data that is relevant for the considered application. Frequently, visualizing data in maps and diagrams significantly increases the effectiveness of this process and can be of great help for managers. The necessity of automatically producing such visualizations gives rise to several computationally hard combinatorial optimization problems. In this document, we describe two problems related to this topic. In one of them, events are represented by opaque symbols, which might overlap. The goal is to determine the order in which they must be drawn so that the loss of information due to overlap is minimized. The other problem is related to the selection and placement of labels on interactive maps, in which the user is allowed to change the scale or the rotation angle. As the user executes one of these operations, the labels are expected to maintain their size and orientation on the screen. They must be placed in such a way that no two labels overlap in any scale or rotation angle. The objective of this project is to study methods to obtain optimal or near optimal solutions for these and, possibly, other similar problems. Exact algorithms will be developed using integer linear programming, while heuristics will be used to find high quality solutions quickly. The algorithms will be evaluated through several experiments with real world instances. (AU)

Scientific publications

(5)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

CANO, RAFAEL G.; DE SOUZA, CID C.; DE REZENDE, PEDRO J.; YUNES, TALLYS. Arc-based integer programming formulations for three variants of proportional symbol maps. DISCRETE OPTIMIZATION, v. 18, p. 87-110, NOV 2015. (12/00673-2, 07/52015-0)

CANO, R. G.; BUCHIN, K.; CASTERMANS, T.; PIETERSE, A.; SONKE, W.; SPECKMANN, B.. Mosaic Drawings and Cartograms. COMPUTER GRAPHICS FORUM, v. 34, n. 3, p. 361-370, JUN 2015. (12/00673-2, 13/23571-3)

CANO, RAFAEL G.; DE SOUZA, CID C.; DE REZENDE, PEDRO J.. Solving dynamic labeling problems to optimality using solution space reductions. THEORETICAL COMPUTER SCIENCE, v. 789, p. 16-pg., 2019-10-15. (12/00673-2)

CANO, RAFAEL G.; DE SOUZA, CID C.; DE REZENDE, PEDRO J.. Solving dynamic labeling problems to optimality using solution space reductions. THEORETICAL COMPUTER SCIENCE, v. 789, n. SI, p. 77-92, OCT 15 2019. (12/00673-2)

CANO, RAFAEL G.; DE SOUZA, CID C.; DE REZENDE, PEDRO J.; POON, SH; RAHMAN, MS; YEN, HC. Fast Optimal Labelings for Rotating Maps. WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, v. 10167, p. 13-pg., 2017-01-01. (12/00673-2)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

CANO, Rafael Ghussn. Problemas de otimização combinatória em visualização de dados cartográficos. 2016. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.