Kuratowski e a planaridade de grafos

Julho 14, 2012

Kazimierz Kuratowski (1896-1980) foi um matemático polonês cuja pesquisa se concentrou na área de topologia.

Ele viveu em um época e local diretamente afetados por duas guerras mundiais. Em 1913 foi estudar engenharia na Escócia mas seus estudos foram logo interrompidos devido ao início da primeira guerra. Entre 1927 e 1934 ele lecionou na politécnica de Lviv, onde frequentava a Cafeteria Escocesa, um estabelecimento famoso por ser o local onde se reuniam membros da escola de matemática de Lviv.

A partir de 1934 ele se transferiu para a Universidade de Varsóvia. Durante a segunda guerra ele passou a dar aulas clandestinamente pois a educação superior na Polônia foi proibida durante a ocupação alemã. Com a reabertura da Universidade em 1945, Kuratowski voltou a lecionar, tendo depois ocupado diversos cargos importantes e contribuído com a reconstrução da vida científica na Polônia [1].

Neste post gostaria de falar sobre um resultado obtido por Kuratowski em teoria dos grafos, mais especificamente na caracterização de grafos planares.

Grafos Planares

Grafos planares formam uma classe de grafos com a propriedade que existe algum desenho deles no plano de forma que suas arestas não se cruzem.

Exemplos de grafos planares são o K_4 (grafo completo de 4 vértices) e árvores, como mostra a Figura 1.

Figura 1: exemplo de grafos planares

Exemplos de grafos não planares são o K_5 (grafo completo de 5 vértices) e o K_{3,3} (grafo bipartido completo com ambas partições de tamanho 3), conforme a Figura 2.

Figura 2: Exemplos de grafos não-planares

Teorema de Kuratowski. Kuratowski mostrou que um grafo é planar se e somente se ele não contém um subgrafo que é uma subdivisão do K_5 e nem do K_{3,3}.

Uma subdivisão de um grafo consiste em colocar vértices “no meio” das arestas. Por exemplo, na Figura 3 temos uma subdivisão do K_{3,3} e segundo o teorema de Kuratowski, este não é um grafo planar.

Figura 3: Uma subdivisão do K_{3,3}

Característica de Euler. Grafos planares possuem a característica de Euler. Dado um desenho de um grafo planar conexo, com v vértices, e arestas e f faces, então v - e + f = 2

Grafos-moeda. (coin graphs) Comentei brevemente sobre grafos-moeda em um post sobre grafos de discos (disk graphs). Voltamos a falar dessa classe de grafos pois o teorema de Koebe diz que grafos-moeda e grafos planares são equivalentes [3].

Mais especificamente, o teorema diz que dado um grafo planar G, existe um conjunto de discos cujo grafo moeda é G. O grafo moeda de um conjunto de discos é um grafo com um vértice para cada disco e uma aresta entre dois vértices se seus discos correspondentes se tocam (lembrando que não é permitida sobreposição dos discos).

Por outro lado, dado um conjunto de discos no plano, podemos desenhar um grafo planar. Desenhe cada vértice do grafo no centro de cada disco e ligue por um segmento de reta os centros de dois discos que se tangenciam. É possível ver que o grafo desenhado é planar e ainda, todas as arestas são linhas retas.

A conclusão é que para todo grafo planar existe um desenho que utiliza apenas linhas retas para representar as arestas, que é justamente o que afirma o Teorema de Fáry.

Teste de Planaridade

Embora Kuratowski tenha dado uma caracterização bastante simples de grafos planares, não é trivial verificar essa condição para um grafo qualquer.

Foram desenvolvidos diversos algoritmos de teste de planaridade lineares no tamanho do grafo, ou seja, O(V + E) (portanto assintoticamente ótimos). O primeiro desses algoritmos a ser publicado foi desenvolvido por Hopcroft e Tarjan [4] (ganhadores do prêmio Turing em 1986).

Essa primeira versão era bastante complexa e portanto novas abordagem foram publicadas ao longo dos anos buscando um algoritmo mais simples. Um breve histórico pode ser conferido na Wikipedia.

A mais recente data de 2004 e é devida a Boyer e Myrvold [5], sobre a qual falaremos a seguir.

O Algoritmo de Boyer e Myrvold

Vamos analisar alguns conceitos chaves desse algoritmo, sem entrar em detalhes, pois o intuito do post é apenas passar uma ideia geral do algoritmo. Para mais detalhes, consulte [5, 6].

Considere um grafo G = (V, E) não direcionado. Sem perda de generalidade, vamos supor que G é conexo. Se não for, é fácil ver podemos analisar a planaridade de cada componente separadamente.

1. Busca em profundidade

Inicialmente fazemos uma busca em profundidade (DFS) sobre G, gerando a árvore da DFS, cujas arestas são denominadas arestas da árvore. As arestas que ficaram de fora são as chamadas arestas de retorno. Note que como o grafo é não direcionado, as arestas de retorno sempre unem um vértice com seu ancestral na árvore da DFS.

2. Componentes biconexas

Antes de prosseguir, vamos relembrar dois conceitos: um ponto de articulação em um grafo conexo é um vértice cuja remoção origina duas ou mais componentes conexas. Uma componente biconexa é uma componente conexa que não tem pontos de articulação.

O algoritmo sempre trabalha com as componentes biconexas do grafo, replicando o ponto de articulação em cada uma delas. Note que em uma árvore, todo nó interno é um ponto de articulação e portanto inicialmente temos uma componente biconexa para cada aresta da árvore. Denotaremos esse grafo intermediário de \tilde G.

3. Adição das arestas de retorno

O restante do algoritmo consiste basicamente em adicionar as arestas de retorno uma a uma sempre garantindo que não haja cruzamento delas ou caso contrário conclui que o grafo não é planar. A ideia central é deixar “livres” os vértices que ainda têm arestas por adicionar.

Os vértices são então processados em ordem contrária a que foram processados na DFS. Assim, os filhos são sempre processados antes do pai na árvore da DFS. Consideremos então o processamento de um vértice v. Vamos adicionar as arestas de retorno de v a seus descendentes.

4. Aglutinação das componentes

Ao adicionar uma aresta de retorno, duas ou mais componentes biconexas podem ser aglutinadas. No exemplo da Figura 4, a inclusão da aresta de retorno (v, w) fará com que as duas componentes da Figura 4 (c) se tornem uma única componente, como pode ser observado na Figura 4 (d).

Figura 4: (a) Grafo real; (b) r é um ponto de articulação pois sua remoção gera duas componentes; (c) representamos as componentes biconexas; (d) ao adicionar a aresta de retorno (v, w) é preciso inverter a componente inferior para que a aresta (x, y) possa ser adicionada posteriomente.

5. Espelhamento das componentes

Outra operação necessária é a chamada espelhamento de uma componente biconexa. Voltando ao exemplo da Figura 4, temos que a aresta (x, y) será adicionada posteriormente (supondo que x é ancestral de v na árvore da DFS).

Porém, se adicionarmos a aresta (v, w) no grafo da Figura 4 (c), isolaremos x de y (note que não podemos “passar” a aresta entre r e sua cópia porque as componentes serão aglutinadas). Uma alternativa é “espelhar” a componente inferior como é feito na Figura 4 (d). Desta forma, os vértices x e y ainda podem ser conectados por uma aresta.

6. Ordem de adição das arestas de retorno

Como dissemos, o algoritmo itera sobre os vértices na ordem inversa da que foram processados pela DFS. Porém, um vértice v pode ter mais de uma aresta de retorno a adicionar a seus descendentes. Qual a ordem em que essas arestas devem ser adicionadas?

O algoritmo executa uma outra busca em profundidade a partir de v percorrendo apenas os vértices que estão na face externa e vai adicionando as arestas conforme vai encontrando os vértices com os quais v tem arestas de retorno a adicionar.

Se a busca terminar sem ter adicionado todas as arestas de retorno de v, então o grafo não é planar.

Conclusão

Esse algoritmo é bastante complicado e usa muitos truques para alcançar a complexidade linear no tamanho do grafo de entrada. Para quem tem mais interesse nos detalhes do algoritmo, pode consultar o artigo original [5]. Para detalhes de implementação, é possível estudar o código-fonte desse algoritmo da biblioteca de grafos da Boost [7].

No problema atacado durante meu mestrado, usamos uma ideia parecida com essa de trabalhar com componentes biconexas com o ponto de articulação replicado em cada uma delas. Mais especificamente, na tentativa de diminuir o tamanho das instâncias de entrada, fizemos a decomposição em componentes biconexas que podem ser resolvidas de maneira independente. Comentei sobre essa estratégia em um post anterior.

Referências

[1] Wikipédia – Kazimierz Kuratowski
[2] Wikipedia – Planarity Testing
[3] Kontaktprobleme der konformen Abbildung – Koebe P.
[4] Efficient Planarity Testing – Hopcroft J., Tarjan R.
[5] On the cutting edge: Simplified O(n) Planarity by Edge Addition – Boyer, Myrvold. (pdf)
[6] Dr Dobbs: Planarity By Edge Addition
[7] Boost: Boyer-Myrvold Planarity Testing


Mapas de Símbolos Fisicamente Realizáveis: a função Max-Min

Junho 5, 2012

Já escrevi sobre o tema de pesquisa do meu mestrado — otimização da visualização de mapas de símbolos proporcionais — em outros posts [1], [2] e [3].

Desta vez gostaria de falar sobre uma das variantes desse problema proposta por Cabello et al [4] onde o objetivo é basicamente dispor os símbolos no mapa de modo a maximizar a visibilidade do disco menos visível. Mais formalmente, dado um conjunto de discos S e uma disposição deles no plano, denotamos por b_i o comprimento da borda visível do disco i \in S.

O objetivo é encontrar uma disposição dos discos que maximize \min \{b_i\}. Não por acaso tal função é chamada de Max-Min.

Cabello et al. apresentaram um algoritmo guloso que maximiza essa função objetivo quando os discos só podem ser empilhados (não podem ser entrelaçados). A ideia é bem simples: dado um conjunto de n discos S, escolha o disco i^* que se posto por baixo de todos os outros teria o maior comprimento de borda visível (ou seja, b_i^* é máximo). Coloque i^* na base e determine a ordem dos outros discos recursivamente.

A versão “força-bruta” desse algoritmo é O(n^3), mas eles apresentam uma versão O(n^2 \log n) usando árvores de segmentos.

Se permitirmos que os discos possam ser entrelaçados, conforme a figura abaixo à esquerda, o problema se torna NP-difícil!

Disposição com entrelaçamento vs. disposição em pilha

Já havíamos atacado a versão que objetiva maximizar a soma das bordas visíveis considerando todos os discos (chamada de Max-Total) e permitindo entrelaçamento usando Programação Linear Inteira. Esse trabalho foi apresentado no Sibgrapi de 2011.

Após esse congresso, fomos convidados a estender nosso trabalho com pelo menos 30% de novo conteúdo e submeter para a publicação em um jornal científico, o The Visual Computer.

Decidimos então atacar a versão com função objetivo Max-Min usando PLI também. A formulação é bastante parecida com aquela que apresentamos no Sibgrapi, mas resolvedores de PLI têm bastante dificuldade em lidar com formulações do tipo max-min, onde se quer maximizar o menor valor de uma função.

Em nossos experimentos, instâncias para as quais o resolvedor achava a solução ótima da função Max-Total em segundos, não eram resolvidas mesmo rodando durante algumas horas para a versão Max-Min.

Uma possível causa para esse comportamento é que para formulações max-min temos muitas soluções com mesmo valor (platôs) e isso faz com que os otimizadores se percam.

Para um exemplo, considere as soluções na figura abaixo. Embora sejam bastante diferentes, elas possuem o mesmo valor da função Max-Min porque o disco destacado em vermelho é tão pequeno, que é ele que define o valor da função objetivo não importando a disposição entre o restante dos discos.

Soluções com mesmo valor da função Max-Min (definida pela borda do disco vermelho)

Como muitas das nossas instâncias podem ser decompostas em componentes menores, usamos a seguinte ideia para tentar melhorar o desempenho do nosso algoritmo. Considere as componentes decompostas c_1, c_2, \cdots, c_k. Seja s(c_i) o valor da solução ótima de c_i para Max-Min limitado a desenhos em pilha e p(c_i) permitindo também desenhos entrelaçados.

Suponha que as componentes estão numeradas de forma que s(c_1) \le s(c_2) \le \cdots \le s(c_k). Assim, a solução ótima da instância completa para desenhos em pilha é igual a s(c_1).

Temos também que s(c_i) \le p(c_i), pois estamos maximizando uma função e p considera tanto desenhos em pilha quanto entrelaçados.

Infelizmente não podemos afirmar que p(c_i) \le p(c_{i+1}). Porém, seja i^* = \mbox{argmin}_i\{p(c_i)\}. Se p(c_{i'}) \le s(c_{i'+1}) para algum i' \le k-1, então temos que p(c_{i'}) \le s(c_{j}) para i' < j e portanto p(c_{i'}) \le s(c_{j}) para i' < j, ou seja, i^* \le i'.

A ideia do algoritmo é resolver cada componente com o algoritmo polinomial de Cabello e ordená-las pelo valor da solução, obtendo s(c_1) \le s(c_2) \le \cdots \le s(c_k). Em seguida resolvemos as componentes nessa ordem usando a formulação do Max-Min permitindo desenhos entrelaçados, obtendo a cada passo p(c_i). Se em algum passo encontramos p(c_{i}) \le s(c_{i+1}), podemos parar pois já encontramos o valor ótimo.

Esse nosso trabalho foi aceito, tendo sido publicado online recentemente [5].

Referências

[1] Blog do Kunigami: Mapas de Símbolos Proporcionais
[2] Blog do Kunigami: Mapas de símbolos proporcionais e a meia integralidade da cobertura de vértices
[3]Blog do Kunigami: Visualização ótima de desenhos fisicamente realizáveis
[4] S. Cabello, H. Haverkort, M. van Kreveld, and B. Speckmann, “Algorithmic aspects of proportional symbol maps”, Algorithmica, 2010.
[5] G. Kunigami, P. de Rezende, C. de Souza and T. Yunes, “Generating Optimal Drawings of Physically Realizable Symbol Maps with Integer Programming”, 2012


Visualização ótima de desenhos fisicamente realizáveis

Outubro 23, 2011

Hoje vou descrever o trabalho que apresentei no Sibgrapi 2011, entitulado “Determining an Optimal Visualization of Physically Realizable Symbol Maps“, escrito em conjunto com meus orientadores (professores Pedro e Cid) e o professor Tallys da Universidade de Miami. Há um

Trata-se de uma extensão do estudo que realizamos para o problema de mapas de símbolos proporcionais usando desenhos em pilha, sobre o qual comentei em um post anterior.

Desenho fisicamente realizável

Um desenho fisicamente realizável é uma generalização de um desenho em pilha, pois este permite ordens cíclicas, como no exemplo abaixo.


Desenho fisicamente realizável e desenho em pilha

Podemos pensar que desenhos fisicamente realizáveis são aqueles feitos a partir de discos de papel, desde que estes não sejam dobrados nem cortados.

O problema é encontrar um desenho fisicamente realizável que maximize a soma dos comprimentos das bordas visíveis. Esse problema é chamado Max-Total para desenhos fisicamente realizáveis.

Tínhamos desenvolvido um modelo de programação linear inteira para o problema Max-Total para desenhos em pilha e mostramos que um subconjunto das desigualdades desse modelo, resolvia o problema Max-Total para desenhos fisicamente realizáveis.

Discutimos aspectos teóricos sobre as desigualdades utilizadas no modelo, argumentando que elas tornam a formulação apertada. Na prática um modelo com formulação apertada tende a ser resolvido mais rapidamente pelo algoritmo de branch and bound.

Técnica de decomposição

Desenvolvemos uma técnica de decomposição nova, que só serve para esse tipo de desenho. A ideia básica das decomposições é quebrar o conjunto de discos de entrada em componentes menores e mostrar que podemos resolver a cada componente de maneira independente e então combiná-las em tempo polinomial para gerar a solução ótima da instância completa. Uma decomposição óbvia é considerar conjuntos de discos disjuntos no plano.

Para desenhos fisicamente realizáveis, podemos ignorar a interseção de discos em alguns casos. Isso por sua vez pode gerar novas componentes disjuntas. No exemplo abaixo, mostramos que é possível ignorar a interseção dos discos nas faces amarelas. Isso quebra a componente em duas que podem ser resolvidas isoladamente.

Exemplo de decomposição

Junto com as outras decomposições que já havíamos desenvolvido para desenhos em pilha, conseguimos diminuir o tamanho das instâncias de teste.

Resultados computacionais

Após resolvermos a formulação do problema para desenhos fisicamente realizáveis, constatamos que na grande maioria dos casos, o valor da solução era exatamente igual ao da solução para desenhos em pilha.

Mesmo para as instâncias onde houve diferença, esse valor foi muito pequeno e visualmente é muito difícil distinguir as soluções, conforme pode ser visto na figura a seguir.

Zoom de uma solução ótima usando desenho em pilha e desenho fisicamente realizável

Entretanto, também tivemos uma boa surpresa, que foi o tempo de execução desse novo modelo. Em média, ele foi aproximadamente 2 ordens de magnitude mais rápido do que modelo para desenhos fisicamente realizáveis.

Conclusão

Devido aos tempos obtidos com o novo modelo e o fato de as soluções obtidas serem muito próximas a desenhos em pilha, uma ideia é usarmos esse modelo para resolver o problema de desenhos em pilha, adicionando restrições para remover os eventuais ciclos que apareçam.

Podemos adicionar essas restrições de remoção de ciclo através de um algoritmo de planos de corte, de um modo similar ao usado para resolver o problema do caixeiro viajante.


Mapas de símbolos proporcionais e a meia integralidade da cobertura de vértices

Julho 31, 2011

O problema que ataquei no mestrado consistia em achar uma ordem de empilhamento entre símbolos em um mapa, de modo a maximizar uma dada função objetivo. Não se sabe a complexidade desse problema e por isso usei programação linear inteira.

Há uma variante desse problema, que consiste em maximizar uma outra função objetivo, para a qual existe um algoritmo polinomial.

Depois de obter as soluções para o meu problema, precisei fazer uma comparação entre as soluções desses dois problemas. Aconteceu que a diferença visual entre as duas soluções não é tão perceptível, sendo que apenas alguns discos estão em posição diferente. Para se ter uma idea, veja um dos casos


Jogo dos 7 erros ;) (clique na imagem para aumentar)

Decidi fazer um programa para destacar apenas os discos que mudaram de lugar. A minha primeira ideia foi marcar todos os discos que estavam em níveis diferentes entre as duas soluções.

Isso não funciona bem quando temos duas componentes disjuntas de discos, por exemplo na figura abaixo, com duas componentes disjuntas {A, B, C} e {D, E}. Note que as ordens {A > B > C > D > E} e {D > E > A > B > C} resultam visualmente na mesma figura, embora nenhum disco esteja exatamente na mesma posição na ordenação e portanto o programa vai marcar todos os discos.

Desenho que pode ser representado por mais de uma ordem dos discos

Uma segunda ideia foi marcar, considerando todos os pares de discos que se interceptam, apenas aqueles em que a ordem relativa do par foi invertida. Com essa estratégia, nenhum disco do exemplo acima seria destacado, o que está de acordo com nossas expectativas.

Porém, essa abordagem ainda apresenta um efeito indesejável. Se tivermos uma pilha de discos, onde todos se interceptam e um disco que está no topo em uma solução aparece na base na outra, sendo que todos os outros discos permaneceram intactos, como por exemplo {A > B > C > D} e {B > C > D > A}, ainda assim todos os discos serão destacados pois todos os pares formados com A tiveram sua ordem relativa invertida. Note que seria suficientemente informativo destacar apenas o disco A.

Assim, para todo par de discos que se intercepta, basta destacarmos um deles. Como então destacar o menor número possível para diminuir a poluição visual?

Se olharmos para o grafo de discos desse problema, existem algumas arestas que queremos destacar (cobrir), usando pelo menos um dos vértices mas tentando minimizar a quantidade desses vértices. Soa familiar?

Sim, reduzimos para o problema da cobertura de vértices (vertex cover).

Cobertura de vértices

O problema da cobertura de (arestas por) vértices é sabidamente NP-difícil. Assim, é pouco provável um algoritmo polinomial para resolvê-lo de maneira ótima. No meu trabalho, usei uma heurística simples: percorra os vértices começando por aqueles de maior grau. Se todas as arestas incidentes a esse vértice já foram cobertas por algum vértice da cobertura, ignore-o. Caso contrário adicione-o à cobertura.

Aplicando esse algoritmo nas figuras do começo do post, ficamos com o seguinte resultado:

Ficou mais fácil encontrar as diferenças entre as soluções (clique na imagem para aumentar)

Esse método ainda tem um problema que é quando um par de discos tem sua ordem relativa trocada, mas a parte que foi visualmente modificada está encoberta por um outro disco. Um exemplo disso pode ser visto no canto inferior direito da figura acima. Para consertar esse problema teríamos que fazer um pré-processamento e só considerar vértices cujos discos têm alguma parte do seu borda diferente entre uma solução e outra.

Modelo de programação linear

Como não poderia deixar de ser, apresento aqui o modelo de programação linear inteira da versão mais geral desse problema, na qual os vértices têm um custo associado. Dado um grafo G = (V, E) com uma função de custo c : V \rightarrow \mathbb{R}^+, definimos a variável binária x_v para cada v \in V, que vale 1 se o vértice v está na cobertura e 0 caso contrário. O modelo então fica:

Sujeito a

(1) Para todo (u, v) \in E,

(2) Para todo v \in V,

Meia integralidade

O modelo apresentado tem uma propriedade interessante chamada de meia-integralidade. Isso quer dizer que, dada a relaxação linear desse modelo, existe uma solução ótima onde os valores das variáveis x_v são 0, 1/2 ou 1. A prova é relativamente curta e está descrita na Seção 14.3 de [1].

Assim, dada uma solução fracionária do modelo, podemos usar a técnica de arredondamento, criando uma solução x'_v com x'_v = 1 sempre que x_v \ge 1/2. É possível mostrar que essa solução é uma cobertura de vértices válida e que seu custo não é maior do que 2 vezes o valor da solução ótima, resultando em um algoritmo 2-aproximado.

Referências

[1] Approximation Algorithms – Vijay V. Vazirani (2003)


Mapas de Símbolos Proporcionais

Abril 17, 2011

Sexta-feira passada apresentei uma palestra na série de seminários do LOCo. Falei sobre o problema que estou atacando no mestrado.

Um mapa de símbolos proporcionais emprega símbolos para exibir eventos associados a alguma localidade e intensidade. O símbolo é posicionado no local de ocorrência do evento e a sua área fica sendo proporcional à intensidade desse evento. Focamos em mapas que usam círculos opacos como símbolos. A figura abaixo é um exemplo representando as populações das maiores cidades do Brasil.

Note que há sobreposição entre os discos. Dependendo da ordem em que os empilhamos, pode ser que haja mais ou menos porções dos discos visíveis. Há casos ruins em que a borda do disco fica totalmente encoberta, como na figura abaixo.


Não podemos inferir o centro nem o raio do disco com bordo escondido.

Para tentar fazer com que o desenho tenha bastante borda visível, usamos uma métrica que consiste em maximizar o comprimento visível total dos discos. Com isso em mente, é possível definir um modelo de programação linear inteira, com um modelo que atribui cada disco a um nível.

Além do modelo básico, desenvolvemos algumas desigualdades adicionais para tornar o modelo mais forte, nos baseando em propriedades geométricas, que impedem certas configurações de acontecerem.

Também desenvolvemos duas técnicas de decomposição de instâncias. Um jeito trivial de decompor instâncias é considerar componentes de discos conexas de maneira independente.

Nossa primeira técnica de decomposição vem da observação que um disco que está contido no outro sempre pode ser desenhado por cima em uma solução ótima. Dessa forma, em uma instância como a da figura abaixo, a componente {a, b} pode ser desenhada de maneira independente de {c, d, e, f} e na hora de construir a solução ótima, basta desenhar a solução obtida para {a, b} em cima da solução {c, d, e, f}.

Componente {a,b} está contida em {f} e pode ser resolvida separadamente.

Podemos definir um grafo Gs sobre os discos de S, com conjunto de vértices correspondendo aos discos e há uma aresta (i, j) em Gs se os discos correspondentes se interceptam. Falei sobre esse tipo de grafo em um post anterior.

A outra técnica consiste em remover um ponto de articulação de Gs e replicá-lo nas componentes conexas resultantes, como na figura abaixo.


O disco f representa um ponto de articulação em Gs. As figuras (ii), (iii) e (iv) são as componentes resultantes de sua remoção, com f replicado.

Mostramos que é possível resolver cada componente com o ponto de articulação replicado de maneira independente. Depois, basta juntar os discos mantendo a ordem relativa de cada sub-solução. Isso pode ser feito através de uma ordenação topológica.

Implementamos todas essas ideias e reportamos os resultados. As instâncias testadas foram as mesmas de um trabalho anterior no qual nos baseamos. As técnicas de decomposição foram efetivas na redução do tamanho das instâncias e o resolvedor XPRESS conseguiu resolver nosso modelo para quase todas as instâncias. Porém, ficaram algumas componentes sem serem resolvidas, o que nos motiva a procurar novos modelos e novas desigualdades.

Esse nosso trabalho foi aceito na Computational Geometry and Applications 2011.


Ponto dentro de polígono

Novembro 19, 2010

Recentemente precisei implementar um algoritmo que detecta se um dado ponto está dentro ou fora de um polígono simples.

Para o caso especial em que o polígono é convexo, existe um algoritmo que faz a consulta em . Uma descrição do algoritmo e um exemplo de execução podem ser encontrados na minha página pessoal.

Para o caso geral, existe um algoritmo O(n) que é bem diferente daquele do caso convexo, mas igualmente simples e engenhoso.

Problema: Decidir se o ponto está dentro ou fora do polígono.

A ideia é a seguinte: traçamos uma semi-reta a partir do ponto de consulta até o infinito, em uma direção arbitrária, e contamos quantas vezes ela cruzou a borda do polígono. Desconsiderando casos especiais, o polígono estará dentro se e somente se, o número de cruzamentos for ímpar.

O algoritmo é simples de descrever, mas como boa parte de algoritmos geométricos, a parte difícil está em implementar. Para contar o número de cruzamentos, processamos cada segmento do polígono. Supondo que o polígono P é dado por uma lista de pontos em sentido horário (se estiver em sentido anti-horário basta inverter a lista). Assim, um segmento é dado por um par de pontos , incluindo o par . Vamos supor também que um dado ponto p possui coordenadas . Sem perda de generalidade, também consideramos que a semi-reta está na direção horizontal e se estende para a direita (tal qual a Figura 1).

Uma condição necessária para que a semi-reta do ponto p intercepte um segmento qualquer (a, b), é de que p esteja verticalmente entre a e b, ou seja, supondo que , então

(1) .

Figura 1: Para a semi-reta cruzar o segmento, o ponto deve estar verticalmente entre seus extremos.

Porém, como se trata de uma semi-reta com sentido para a direita, queremos considerar apenas os segmentos “à direita” do ponto. Vemos pela Figura 2, que não basta verificar se o ponto p está à esquerda do ponto mais a esquerda do segmento. Para decidir de qual “lado” do segmento está um ponto, podemos usar produto vetorial.

Figura 2: Não basta verificar se o ponto p está à esquerda do ponto mais a esquerda do segmento

Dados dois vetores e , podemos decidir a orientação entre eles através de um produto vetorial . Dependendo do sentido do vetor resultante, é possível dizer se possui orientação horária ou anti-horária em relação a .

Com os três pontos p, a e b, podemos obter os vetores e e usar a ideia do produto vetorial para decidir a orientação de p em relação ao segmento ab. Mais especificamente, podemos usar a seguinte equação [1]:

Se , então o vetor está orientado em sentido anti-horário em relação ao vetor . Se a orientação é horária e se , os vetores são paralelos.

Figura 3: Valor de r e a correspondência geométrica.

Casos especiais

Há dois casos especiais que devemos tratar: o caso em que está na borda do polígono e o caso em que o raio cruza um segmento no seu extremo. Vamos analisar o segundo caso. A figura abaixo elenca todos os possíveis casos.

Figura 4: Casos especiais.

A presença dos casos (a), (b), (d) e (e), não muda de que “lado” do polígono o ponto está, ao contrário dos casos (c) e (f). Assim, as interseções do raio com (a), (b), (d) e (e), não devem mudar a paridade do número de cruzamentos, enquanto as interseções com (c) e (f) sim. Note porém, que no algoritmo apresentado, (d) e (e) aumentarão o número de cruzamentos em 3 (mudando a paridade dos cruzamentos) e (c) aumentará em 2 (mantendo a paridade dos cruzamentos).

Uma maneira bem elegante de se tratar tais casos, é considerar que o raio só intercepta segmentos cujo extremo inferior esteja estritamente abaixo de p e com extremo superior acima ou na mesma altura de p. Ou seja, a equação (1) fica,

(2) .

Agora, o número de cruzamentos com os casos (a) e (d) é 0; com (b) e (e) é 2; e com (c) e (f) é 1, preservando a paridade como gostaríamos.

Finalmente, vamos tratar o caso em que o ponto esteja na borda do polígono. Uma condição necessária, mas não suficiente, é que o ponto p seja colinear a algum dos segmentos do polígono. Além disso, é preciso que p esteja entre os pontos de tal segmento.

Uma vez que sabemos que p é colinear ao segmento , podemos determinar se ele está no meio de a e b através de um produto escalar!

Lembre que o produto escalar entre dois vetores e é equivalente a:

onde é o ângulo entre e .

Podemos definir os vetores e e calcular o produto escalar entre eles. Por hipótese, esses vetores são paralelos. Se p estiver entre a e b, e têm sentido oposto, o ângulo entre eles é . Caso contrário, têm mesmo sentido e o ângulo é 0.

Figura 5: Possíveis orientações entre a, b e p colineares.

Observando que o módulo é sempre positivo e e , concluimos que p está entre a e b se e somente se . Há o caso em que p é coincidente com a ou b. Nesse caso o produto escalar é 0. Resumindo, p está na borda do polígono se existe segmento tal que

Pseudo-código

O pseudo-código abaixo recebe como parâmetros um ponto p e um polígono P, conforme especificado anteriormente, e decide se o ponto está dentro, fora ou na borda do polígono.

Aplicação

Estou desenvolvendo um aplicativo web usando Google Maps onde o usuário define um polígono simples e apenas cidades dentro da região delimitada são consideradas. O algoritmo verifica, para cada cidade, se o ponto correspondente ao centro dela está dentro do polígono definido.

Figura 6: Interface do aplicativo

São necessárias algumas projeções, pois as coordenadas estão em latitude-longitude e o polígono é construído com coordenadas cartesianas,  mas essencialmente o algoritmo usado é o de detecção de ponto
dentro de polígono.

Referências

[1] Wikipedia – Cross Product


Disk Graphs

Outubro 1, 2010

Semana passada teve início a série de seminários em teoria de computação dos membros do Laboratório de Otimização e Combinatória. Essas palestras ocorrerão intercaladas com os seminários do DTC (Departamento de Teoria de Computação), ocorrendo, a priori, às Sextas-feitas, 10h. Acabei estreando essa série com uma palestra intitulada “Disk Graphs”. A ideia central era definir a classe de grafos chamada disk graphs e mostrar dois problemas clássicos de teoria dos grafos sobre essa classe: o problema da clique máxima e da coloração. Neste post, vou apresentar um pequeno resumo da apresentação (disponível aqui).

Dado um conjunto de discos no plano, definimos um grafo com vértices correspondendo aos centros dos discos. Dois vértices são conectados por uma aresta se seus discos correspondentes se interceptam com área não nula. Denominamos tal grafo Disk Graph (DG).

Exemplo de Disk Graph

Um Disk Graph onde todos os discos têm mesmo tamanho é chamado de Unit Disk Graph.

Exemplo de Unit Disk Graph

No caso particular em que os discos não podem se sobrepor, apenas se tangenciar, chamamos o DG de Coin Graph (CG).

Exemplo de um Coin Graph

Em seguida falei sobre a relação entre diferentes classes de grafos. A mais interessante é devido ao Teorema de Koebe (também conhecido como circle packing theorem) que diz basicamente que grafos planares e coin graphs são equivalentes. Eu desconfiava que todo grafo planar é também um disk graph. O prof. Stolfi, que estava presente, provou com um argumento bem simples: dado um coin graph, a menor distância entre bordos de discos que não se tangenciam é positiva, enquanto a de discos que se tangenciam é exatamente 0. Assim, existe um valor suficientemente pequeno do qual podemos aumentar o raio dos discos de forma que os círculos tangentes passem a ter interseção não nula e os não tangentes assim continuem.

Problemas

Um aspecto importante ao enunciar um problema para essa classe de grafos é especificar se a entrada é dada na forma de discos ou na forma de grafo. Observe que se for dada na primeira forma, conseguimos obter a segunda. Porém, mesmo para unit disk graphs, se a entrada estiver na forma de grafo, foi provado que é NP-difícil encontrar um conjunto de discos que formem tal grafo [1]. (Para coin graphs existe um algoritmo que constrói o conjunto de discos a partir de um grafo planar [2]). Para os problemas apresentados, vamos assumir que a entrada é dada na forma de discos.

Primeiramente apresentei o problema da clique máxima para unit disk graphs. Embora seja NP-difícil encontrar a clique máxima em um grafo geral, para unit disk graphs, existe um algoritmo polinomial . Não se sabe, porém, se o problema da clique máxima para disk graphs está em P ou NP.

Depois apresentei o problema da coloração, que continua NP-difícil, mesmo para unit disk graphs e a entrada sendo dada na forma de discos. Foram desenvolvidos algoritmos aproximados e algoritmos online para unit disk graphs e disk graphs. Para unit disk graphs o melhor algoritmo aproximado até agora tem fator de aproximação 3 (limite superior), sendo que não existe algoritmo aproximado com melhor fator de aproximação menor do que 4/3 (limite inferior) a não ser que P=NP. O melhor algoritmo online tem fator de competitividade 5 (limite superior) e não existe algoritmo com fator de competitividade menor do que 2 (limite inferior) a menos que P=NP. Para disk graphs, o algoritmo aproximado tem limites inferior e superior iguais a 4/3 e 5, respectivamente, e o algoritmo online tem ambos limites inferior e superior iguais a log n, ou seja, o algoritmo online para unit disk graphs é o melhor que se pode conseguir.

Sumário com os limites dos fatores de aproximação e competitividade.

Aplicações

Na palestra acabei não falando das aplicações práticas dos disks graphs. Porém, eles são muito utilizados para projetar topologias de rede wireless. Podemos pensar que cada disco representa uma antena wireless posicionada no centro do disco, com alcance equivalente ao raio do mesmo. Assim, o problema da coloração pode ser usado para encontrar uma atribuição de frequências às antenas, considerando que há interferência entre os sinais de antenas cujos círculos se interceptam.

Referências

[1] Breu, H. and Kirkpatrick, D. G. – Unit Disk graph recognition is NP-Hard
[2] Collins, C. R. and K, Stephenson – A Circle packing algorithm


Galeria de Arte

Setembro 10, 2010

O Marcelo Couto é ex-membro no Laboratório de Otimização e Combinatória que defendeu sua tese de mestrado recentemente. Orientado pelo Cid Souza e Pedro Rezende, ele pesquisou durante seu mestrado o problema da Galeria de Arte. Vou tentar explicar resumidamente seu trabalho, me baseando em sua apresentação na defesa e alguns slides na página do prof. Rezende, de onde também peguei as figuras desse post.

Introdução

Dado um polígono simples, sem buracos, queremos determinar o menor número de vértices que enxergam todo o interior do polígono. Há várias versões desse problema, mas a que eu vou apresentar aqui é a versão em que os guardas são fixos em vértices e têm visão de 360 graus. Uma aplicação prática que pode ser modelada como esse problema é minimizar o número de câmeras no interior de um museu que cubram toda a sua extensão.

Inicialmente os polígonos considerados eram ortogonais, ou seja, todos os seus lados são paralelos a algum dos eixos. Lee e Lin [1] provaram que, mesmo para polígonos ortogonais, o problema da galeria de arte é NP-difícil.

Em sua tese de mestrado, o Marcelo ataca o problema com Programação Linear Inteira. O problema da galeria de arte pode ser reduzido para o problema da cobertura de conjuntos: O universo de elementos são todos os infinitos pontos internos do polígono. Cada vértice do polígono representa o subconjunto de pontos que um guarda cobre estando naquele vértice. Queremos encontrar o menor número de subconjuntos (guardas) que cobrem todo o conjunto de pontos. O problema dessa abordagem é que há infinitos elementos, o que torna impossível explicitá-los no modelo.

Para resolver esse problema, foi usada uma técnica muito interessante de discretização: Escolha apenas alguns pontos interiores do polígono. Com isso é possível construir o modelo PLI e calcular a cobertura de conjuntos mínima. Algumas regiões vão ficar descobertas. Adicione mais pontos das regiões não cobertas ao modelo e re-execute o algoritmo até que não restem mais dessas regiões. É possível mostrar que esse algoritmo converge em tempo finito.

Modelo de PLI

Seja U o conjunto universo de pontos e S um conjunto de subconjuntos de U, de forma que a união dos subconjuntos em S é igual a U. Em geral, existe um custo associado a cada subconjunto i de S. O objetivo é escolher alguns subconjuntos em S que cubram U e tenham custo mínimo.

Definimos a variável binária que é igual a 1 se o subconjunto i está na solução e 0 caso contrário. Ficamos com o seguinte modelo:

Sujeito a:

(1) Para todo elemento u em U,

O lado direito da restrição (1) consiste da soma das variáveis de todos os subconjuntos que contém um dado elemento u. Assim, essa restrição garante que cada elemento é coberto por pelo menos um subconjunto. No problema da galeria de arte padrão não há custo associado à colocação dos guardas de forma que no modelo do Marcelo os custos são unitários.

Estratégias de discretização

A primeira ideia para discretizar esses pontos foi considerar apenas pontos que pertencessem a um grid imaginário, conforme a figura abaixo:

Discretização em Grid: pontos vermelhos são os elementos a serem cobertos.

Dependendo do espaçamento do grid, podem haver muitos pontos no modelo e a maioria deles podem ser irrelevantes. Então, porque não começar com poucos pontos e deixar o algoritmo encontrar as regiões não cobertas? Surgiu então a ideia de colocar apenas os vértices do polígono como pontos iniciais do modelo.

Uma outra opção para não depender do espaçamento do grid, foi considerar um grid induzido pelos lados do polígono. Para isso, basta estender para uma reta, cada segmento de reta que forma o lado do polígono. As interseções dessas retas que estiverem dentro do polígono são colocadas no modelo inicialmente. A ordem de pontos aqui é O(n^2).

Discretização com grid induzido

Depois foi provado que é possível determinar um número finito de pontos de forma que nenhuma região fique descoberta após a resolução do modelo. A ideia é que as regiões de visibilidade dos vértices particionam o polígono em regiões. Para entender melhor, considere a região de visibilidade do vértice 12 da figura abaixo.

Regiao de Visibilidade do vértice 12

Considere os segmentos de reta que formam as fronteiras entre as regiões cinza e branca. A união desses segmentos induzidos pela região de visibilidade particiona o polígono em um conjunto de regiões, chamadas AVP’s (Atomic Visibility Polygons). Colocar um ponto no centróide de cada uma dessas regiões é suficiente para que todas as regiões sejam cobertas com apenas uma iteração do algoritmo.

Partição induzida pelas regiões de visibilidade dos vértices

Foi provado que o número dessas regiões é O(n^3), o que representa um número bem grande de pontos. Além disso, a construção dessas regiões leva um tempo considerável. Assim, tem-se um tradeoff entre tempo de pré-processamento e número de iterações. No final das contas, a maior parcela do tempo total do algoritmo com discretização em AVP’s foi devido a pré-processamento, como pode ser visto no gráfico abaixo. Surpreendentemente, começar com apenas os vértices apresentou o melhor desempenho, mesmo na fase de processamento.

Resultados Computacionais

Conclusão

Depois o trabalho também passou a resolver polígonos não-ortogonais e com buracos. Além disso, foi muito eficiente na prática, resolvendo instâncias muito maiores do que se tinha conhecimento até então. Com isso, foram possíveis diversas publicações internacionais.

Referências:

[1] Computational complexity of art gallery problems, D Lee, A Lin – IEEE Transactions on Information Theory, 1986 – ieeexplore.ieee.org


Triangulação de Custo Mínimo

Julho 23, 2010

Considere n pontos em posição geral no plano. Considere todos os segmentos de reta que unem dois desses pontos quaisquer e com um custo associado. Uma triangulação desses pontos é um subconjunto maximal desses segmentos tal que dois segmentos nesse subconjunto não se interceptem (exceto nas pontas). O problema da triangulação de custo mínimo consiste em encontrar uma triangulação que minimize a soma dos custos dos segmentos. Existe uma variante muito famosa  em geometria computacional, onde a função objetivo é maximizar o menor ângulo entre dois lados de algum triângulo da triangulação, conhecida também como triangulação de Delaunay .

Exemplo de triangulação

Recentemente (2008) foi provado que esse problema é NP-difícil [1]. Entretanto, encontrei um artigo de 1997 que apresenta um modelo de PLI para esse problema [2]. Estou tentando uma abordagem parecida na minha tese, ou seja, atacando um problema cuja pertinência a classe NPC é um problema em aberto. Enfim, vamos ao modelo.

Modelo

Começamos com um teorema:
O número de segmentos em uma triangulação com n pontos é:

Além do mais, considere o grafo Gs, onde cada vértice corresponde a um segmento e existe uma aresta ligando dois vértices se seus segmentos correspondentes se interceptam. É possível mostrar que conjuntos independentes maximais nesse tipo de grafo têm uma correspondência um pra um com triangulações, ou seja queremos um conjunto independente de tamanho .

Como os segmentos têm custo associado (geralmente dado pela distância euclidiana), associamos esses mesmos custos aos vértices. Desta forma, seja o custo de cada vértice v. Definimos a variável se o vértice está no conjunto independente e 0 caso contrário.

O modelo fica:

(1)

(2)

(3)

A desigualdade (2) impede que dois vértices adjacentes estejam em no conjunto independente. A desigualdade (3) garante que o conjunto independente é maximal.

Trabalhei com o Pedro Hokama em cima desse problema no trabalho 2 da disciplina de Programação linear inteira. Consideramos algumas desigualdades adicionais para fortalecer o modelo e que estão presentes em [2,3], além de usar alguma delas como cortes para o algoritmo de Branch and Cut. Um relatório deste trabalho pode ser encontrado aqui.

Referências:

[1] Mulzer, W. and Rote, G. – Minimum-weight triangulation is NP-hard (http://arxiv.org/abs/cs.CG/0601002)
[2] Yoda, Y. and Imai, K. and Takeuchi, F. and Tajima, A. – A branch-and-cut approach for minimum weight triangulation
[3] Nemhauser, G.L. and Sigismondi, G.A – Strong cutting plane/branch-and-bound algorithm for node packing


Hypar

Fevereiro 23, 2010

Esse termo representa um parabolóide hiperbólico (hyperbolic paraboloid) e foi utilizado por Erik Demaine [1]. Essa forma pode ser representada parametricamente pela seguinte equação:

ou

Plot de

O Demaine descobriu que é possível construir tal forma, que vamos chamar de hipar, através de dobraduras de papel (origami). O seguinte diagrama mostra o passo-a-passo:

(Clique para aumentar)

k-chapéu

Juntando vários hipars, é possível formar o que Erik chama de um k-chapéu. Para isso, devemos colar as laterais de k hipars de modo que a ponta mais alta fique no centro. Para ficar mais fácil de entender, eis um 4-chapéu:

4-chapéu

Hiparedro

O interessante é que o artigo do Demaine [2] ensina a construir um sólido platônico com k-chapéus. A idéia é simples: cada face de k lados, vira um k-chapéu e para juntar duas faces ligamos uma ponta de um k-chapéu à ponta de outro.

Assim, um cubo que tem seis faces de quatro lados, pode ser construído com seis 4-chapéus, ou seja, 24 hypar.

Construção

Com a ajuda da Annelise, que, ao contrário de mim, tem talento para dobrar origamis, construímos o hiparedro correspondente ao cubo, que apelidamos de “cubo hiparédrico”. Com uma folha 15cm x 15cm construímos 24 hypars e obtivemos o seguinte resultado:

“Cubo hiparédrico”

Achei que os outros sólidos na página do Demaine não ficaram tão bonitos quanto o cubo e fiquei sem vontade de montá-los. Porém, gostaria de ver outros sólidos não-platônicos construídos dessa forma. Uma ideia seria construir um icosaedro truncado, um sólido de arquimedes. No momento não pretendo fazê-lo, mas seria interessante ver a cara de tal sólido.

Para concluir, gostaria de observar que a técnica de colar/juntar origamis para formar uma nova forma é conhecida como kusudama, e eu a aprecio muito.

Referências:

[1] http://erikdemaine.org/hypar/
[2] http://erikdemaine.org/papers/BRIDGES99/paper.pdf