Desenho de mapas de símbolos proporcionais utilizando GRASP

• Processo: 09/17044-5
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Vigência (Início): 01 de março de 2010
• Vigência (Término): 30 de junho de 2011
• Á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
• Vinculado ao auxílio: 07/52015-0 - Métodos de aproximação para computação visual, AP.TEM
• Assunto(s): Geometria computacional Otimização combinatória Meta-heurística
• Palavra(s)-Chave do Pesquisador: Geometria Computacional | Grasp | Mapas de símbolos proporcionais | Otimização Combinatória | Otimização Combinatória

Resumo

Neste projeto de iniciação científica será estudado o problema do desenho de mapas de símbolos proporcionais. Eventos relacionados a localizações geográficas podem ser representados em mapas através de símbolos. Essa é uma ferramenta muito utilizada para transmitir informações graficamente. Nesse trabalho, os símbolos considerados serão discos opacos. A área de cada um deles é proporcional à intensidade do evento associado e seus centros indicam o local de sua ocorrência. Uma vez que os discos são opacos, partes deles podem ficar encobertas. Se a porção visível de um disco é muito pequena, não é possível determinar seu tamanho e isso leva a erros na interpretação dos dados. Portanto, é interessante desenvolver algoritmos que façam bons desenhos. Cabello et al. (Cabello et al., 2009) definem quatro variantes de um problema de otimização combinatória relacionado a esse tipo de mapa. Para uma delas foi fornecido um algoritmo polinomial enquanto que para duas outras foram obtidas provas que mostram que o problema é NP-difícil. O objetivo desse projeto é encontrar soluções para a quarta variante, cuja complexidade ainda está em aberto, utilizando a metaheurística GRASP. Nesta variante, os discos são organizados em uma estrutura de pilha e deseja-se maximizar o comprimento total dos arcos visíveis. A opção feita aqui pelo estudo de heurísticas deve-se ao caráter complementar desta pesquisa, uma vez que ela irá dar subsídios a uma dissertação de Mestrado onde estão sendo investigados métodos exatos para a resolver o problema. Pretende-se com estes dois projetos aumentar o conhecimento sobre o problema, o que poderá contribuir para decidir sobre sua complexidade. (AU)

Publicações científicas

(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.; KUNIGAMI, GUILHERME; DE SOUZA, CID C.; DE REZENDE, PEDRO J.. A hybrid GRASP heuristic to construct effective drawings of proportional symbol maps. Computers & Operations Research, v. 40, n. 5, p. 1435-1447, MAY 2013. (07/52015-0, 09/17044-5)