Problemas de otimização combinatória em visualização de dados cartográficos

Author(s)

Rafael Ghussn Cano

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2016-12-12

Examining board members

Cid Carvalho de Souza; Yoshiko Wakabayashi; Manoel Bezerra Campêlo Neto; Carlile Campos Lavor; Flávio Keidi Miyazawa

• Advisor: Pedro Jussieu de Rezende; Cid Carvalho de Souza

Abstract

Data can be represented in various ways. Tables are likely to be the simplest form of presenting it. Still, they are useful when it is necessary to retrieve data values associated with specific objects. However, if one is interested in identifying relations between different objects, other forms of representation might be more suitable. To that end, a schematic visualization in images and diagrams can often reveal new aspects of the data. This is true especially for cartographic data, i.e., data that is associated with locations or regions of a map. In these cases, appropriate visualizations can exhibit spatial patterns and relations that were previously unknown, enabling a deeper analysis of the observed phenomena. Manually constructing maps requires experienced cartographers and is extremely time-consuming. Therefore, there is a need for algorithms to automate this task. Each type of visualization has specific constraints and quality metrics. These give rise to several combinatorial optimization problems, which are, frequently, computationally hard. This thesis aims at studying some of these problems. We consider four types of visualizations for cartographic data: proportional symbol maps, rotating maps, mosaic cartograms and rectangular cartograms. Proportional symbol maps represent data through opaque symbols, that might overlap. The problem we address consists in determining the order in which the symbols must be drawn, such that their visibility is maximized according to established metrics. Our contributions include a novel integer linear programming model and an analysis of the associated polytope, a branch-and-cut algorithm with fast separation routines, and lifting procedures. Rotating maps are maps that allow the user to rotate the view. The goal of our study was to find optimal solutions to a labeling problem. Just as in classic problems, labels must be placed on the map without overlap. However, as the map is rotated, all labels must remain horizontally aligned, and this may cause new conflicts to arise. In our work, we prove several properties of optimal solutions and show how to reduce the number of variables and constraints of an existing integer programming model by up to two orders of magnitude. Finally, cartograms are maps used to depict statistical data about regions (e.g., states or countries). Each region is scaled in such a way that its area becomes proportional to the associated numerical value. We propose the first algorithm for the construction of mosaic cartograms. In addition, we extend an existing method to build rectangular cartograms with a heuristic that creates so-called sea regions (AU)

• FAPESP's process: 12/00673-2 - A study of combinatorial optimization problems related to data visualization
• Grantee: Rafael Ghussn Cano
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)