Estudo de problemas de otimização combinatória relacionados a visualização de dados

• Processo: 12/00673-2
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto
• Vigência (Início): 01 de abril de 2012
• Vigência (Término): 04 de agosto de 2016
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Rafael Ghussn Cano
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Bolsa(s) vinculada(s): 13/23571-3 - Algoritmos de otimização para GeoVisualização, BE.EP.DD
• Assunto(s): Otimização combinatória Visualização de dados Programação linear inteira Geometria computacional Heurística
• Palavra(s)-Chave do Pesquisador: Geometria Computacional | heuristicas | Otimização Combinatória | programação linear inteira | visualização de dados | Otimização Combinatória

Resumo

O processo de tomada de decisão, no contexto de pesquisa operacional, envolve, fundamentalmente, a análise de dados relevantes à aplicação considerada. Em diversas situações, a visualização dos dados em mapas e diagramas torna esse processo muito mais eficaz e pode ser de grande valia para gerentes e administradores. A necessidade de produzir tais visualizações automaticamente dá origem a diversos problemas computacionalmente difíceis de otimização combinatória. Neste documento, discutimos dois problemas relacionados ao tema. Em um deles, eventos são representados por símbolos opacos, os quais podem se sobrepor. Assim, deve-se determinar a ordem na qual eles devem ser desenhados para evitar que alguns deles sejam encobertos. O outro problema envolve a disposição de rótulos em mapas interativos, nos quais é permitido alterar a escala ou efetuar rotações. Porém, deseja-se que a orientação e o tamanho dos rótulos na visualização permaneçam constantes. Conforme o usuário altera a escala ou rotaciona o mapa, sobreposições entre rótulos podem surgir. Dessa forma, deve-se determinar em quais escalas ou ângulos de rotação cada rótulo pode ser exibido, de forma a eliminar sobreposições. O objetivo deste projeto é desenvolver métodos para a obtenção de soluções ótimas ou quase ótimas para esses problemas e, possivelmente, para outros semelhantes. Algoritmos exatos serão desenvolvidos através de técnicas de programação linear inteira, enquanto que heurísticas serão utilizadas para encontrar soluções de alta qualidade rapidamente. A eficiência dos algoritmos implementados será avaliada através de experimentos com instâncias baseadas em dados reais. (AU)

Publicações científicas

(5)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

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, 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, 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, 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)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

CANO, Rafael Ghussn. Combinatorial optimization problems in cartographic data visualization. 2016. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.