Galeria de Arte

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

About these ads

Os comentários estão fechados.

Seguir

Get every new post delivered to your Inbox.

%d bloggers like this: