Busca avançada
Ano de início
Entree

Desenho de mapas de símbolos proporcionais utilizando GRASP

Processo: 09/17044-5
Linha de fomento: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

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.

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. Citações Web of Science: 4.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.