Texto completo
| |
| Autor(es): |
Rafael Ghussn Cano
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2016-12-12 |
| Membros da banca: |
Cid Carvalho de Souza;
Yoshiko Wakabayashi;
Manoel Bezerra Campêlo Neto;
Carlile Campos Lavor;
Flávio Keidi Miyazawa
|
| Orientador: | Pedro Jussieu de Rezende; Cid Carvalho de Souza |
| Resumo | |
Conjuntos de dados podem ser representados de muitas maneiras. Tabelas são, provavelmente, a forma mais simples de apresentação e mostram-se úteis quando se deseja consultar valores associados a objetos específicos. No entanto, se o objetivo é identificar relações entre diferentes objetos, outras formas de representação podem ser mais adequadas. Para este fim, uma visualização em forma esquemática através de imagens e diagramas pode, frequentemente, revelar novos aspectos dos dados. Isto ocorre especialmente em se tratando de dados cartográficos, isto é, dados associados a regiões ou localizações geográficas. Nestes casos, visualizações apropriadas podem evidenciar relações e padrões espaciais anteriormente desconhecidos, possibilitando uma análise mais aprofundada dos fenômenos observados. A construção manual de mapas necessita de cartógrafos experientes e consome muito tempo. Portanto, é interessante o desenvolvimento de algoritmos que permitam a automação desta tarefa. Cada tipo de visualização apresenta restrições e métricas de qualidade específicas. Originam-se, então, diversos problemas de otimização combinatória, os quais são, com frequência, computacionalmente difíceis. Esta tese propõe-se a estudar alguns destes problemas. Foram considerados quatro tipos de visualização para dados cartográficos: mapas de símbolos proporcionais, mapas rotacionáveis, cartogramas em mosaicos e cartogramas retangulares. Mapas de símbolos proporcionais representam dados através de símbolos opacos, que podem se sobrepor. O problema abordado consiste em determinar a ordem na qual os símbolos devem ser desenhados de forma a maximizar sua visibilidade de acordo com métricas estabelecidas na literatura. Nossas contribuições incluem um novo modelo de programação linear inteira e uma análise poliédrica do mesmo, um algoritmo de branch-and-cut com rotinas eficientes de separação de desigualdades e procedimentos de lifting. Mapas rotacionáveis são mapas que permitem ao usuário executar rotações. Nosso estudo teve como objetivo encontrar soluções ótimas para um problema de rotulação. Como em problemas tradicionais, deseja-se colocar rótulos textuais no mapa sem que ocorram sobreposições. Porém, conforme o mapa é rotacionado, todos os rótulos devem permanecer alinhados na direção horizontal, o que pode causar o surgimento de novos conflitos. Em nosso trabalho, provamos várias propriedades de soluções ótimas e mostramos como reduzir em centenas de vezes o número de variáveis e restrições de um modelo de programação linear inteira da literatura. Finalmente, cartogramas são mapas usados para representar dados estatísticos sobre regiões (e.g., estados ou países). Cada região tem seu tamanho alterado de forma que sua área seja proporcional ao dado que se deseja retratar. Nós propomos o primeiro algoritmo para construção de cartogramas em mosaicos. Além disso, expandimos um método existente de construção de cartogramas retangulares com uma heurística que cria as chamadas regiões de mar (AU) | |
| Processo FAPESP: | 12/00673-2 - Estudo de problemas de otimização combinatória relacionados a visualização de dados |
| Beneficiário: | Rafael Ghussn Cano |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado Direto |