Advanced search
Start date
Betweenand

A study of combinatorial optimization problems related to data visualization

Grant number: 12/00673-2
Support Opportunities:Scholarships in Brazil - Doctorate (Direct)
Effective date (Start): April 01, 2012
Effective date (End): 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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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.. Solving dynamic labeling problems to optimality using solution space reductions. THEORETICAL COMPUTER SCIENCE, v. 789, n. SI, p. 77-92, . (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., . (12/00673-2)
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, . (12/00673-2, 13/23571-3)
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, . (12/00673-2, 07/52015-0)
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., . (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.

Please report errors in scientific publications list using this form.