| Grant number: | 09/17044-5 |
| Support Opportunities: | Scholarships in Brazil - Scientific Initiation |
| Start date: | March 01, 2010 |
| End date: | June 30, 2011 |
| 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 research grant: | 07/52015-0 - Approximation methods for visual computing, AP.TEM |
Abstract 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) | |
| News published in Agência FAPESP Newsletter about the scholarship: | |
| More itemsLess items | |
| TITULO | |
| Articles published in other media outlets ( ): | |
| More itemsLess items | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |