Defesa de Dissertação de Mestrado: Guilherme Kunigami

Mapas de Símbolos Proporcionais.

Nesta dissertação, realizamos um estudo extensivo de uma classe de

problemas envolvendo mapas de símbolos proporcionais, através de

programação linear inteira. Mapas de símbolos proporcionais são uma

ferramenta cartográfica para a representação de eventos associados a

intensidade e localização geográfica. Exemplos clássicos desses tipos

de mapas são ocorrências de terremotos e populações de cidades. Devido

à proximidade e ao tamanho dos símbolos, podem haver sobreposições

entre eles. Na ocorrência dessas sobreposições, a decisão sobre quais

símbolos ficarão por cima de outros, pode afetar a visibilidade dos

símbolos em um desenho. Os problemas envolvendo mapas de símbolos

proporcionais dos quais tratamos são restritos ao uso de círculos

opacos como símbolos e consistem em decidir a ordem em que estes serão

dispostos em vista das sobreposições, de forma a maximizar métricas

associadas à qualidade visual desses mapas. Tratam-se, portanto, de

problemas de otimização combinatória.

Em nosso trabalho, apresentamos modelos de programação linear inteira

para resolução de dois desses problemas, um deles foi provado

pertencer à classe NP-difícil e o outro tem complexidade ainda não

conhecida. Obtivemos resultados teóricos de combinatória poliédrica

acerca dos modelos, o que resultou em diversas desigualdades

definidoras de facetas que foram incorporadas aos

modelos. Desenvolvemos ainda técnicas de pré-processamento que

decompuseram as instâncias de entrada em um grande número de

componentes de menor tamanho. Essas técnicas permitiram resolver de

maneira ótima, pela primeira vez, diversas instâncias criadas a partir

de dados reais. Ademais, descrevemos um trabalho que aborda um desses

problemas através de uma heurística GRASP, ao qual também

contribuimos.

Instituto de Computação - UNICAMP