| Processo: | 09/17044-5 |
| Modalidade de apoio: | Bolsas no Brasil - Iniciação Científica |
| Data de Início da vigência: | 01 de março de 2010 |
| Data de Término da vigência: | 30 de junho de 2011 |
| Área de 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 - Metodos de aproximacao para computacao 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) | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |