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

Anúncios

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