Problema da galeria de arte

Four cameras cover this gallery.

O problema da galeria de arte (também conhecido como o problema do museu) é um problema de visibilidade bem estudado em geometria computacional, que tem a sua origem no seguinte problema do mundo real:

"Numa galeria de arte de forma poligonal, qual é o número mínimo de guardas que juntos podem observar toda a galeria de arte"?

Formalmente, considere uma área poligonal , interpretada como a planta de uma galeria de arte. Escolher o menor número possível de pontos  (guardas) em  tal que para cada ponto em , e para um  o segmento de linha entre  e  não deixa o polígono.

Neste cenário, os guardas não são móveis e têm um campo visual de  graus, de modo a poderem ser interpretados como câmaras de vigilância.

• 

  Configuração 1

• 

  Configuração 2

• 

  Configuração 3

O problema da galeria de arte pode ser aplicado em vários domínios, tais como na robótica, quando as inteligências artificiais (IA) precisam de executar movimentos dependendo do seu ambiente. Outros domínios, onde este problema é aplicado, são a edição de imagens, problemas de iluminação de um palco ou a instalação de infra-estruturas para a alerta de catástrofes naturais.

Exemplos

• 

  Este pentágono regular pode ser completamente vigiado por um guarda, cuja posição não é importante. De facto, há um resultado que declara que para qualquer polígono convexo, apenas um guarda é suficiente para observar toda a galeria.

• 

  Neste caso, um guarda também é suficiente, embora a sua posição seja mais restrita. Por exemplo, o guarda não pode ser colocado numa das pernas, porque precisaríamos de um segundo guarda para a outra perna.

• 

  Para este 6-gon, um guarda não é suficiente para cobrir toda a galeria. De facto, dois guardas são sempre suficientes para cobrir uma galeria de -gon.

• 

  Para esta -gon, três guardas são suficientes para supervisionar toda a área. Isto vem na sequência do teorema da galeria de arte.

O teorema da galeria de arte

O teorema da galeria de arte, provado por Vaclav Chvátal, dá um limite superior para o número mínimo de guardas que são colocados nos cantos (vértices) de uma galeria de arte, e diz o seguinte:

"Para guardar um polígono simples com $n$ vértices, $\left\lfloor {\frac {n}{3}}\right\rfloor$ guardas são sempre suficientes e por vezes necessários."

História

O problema da galeria de arte foi apresentado pela primeira vez a Chvátal por Victor Klee em $1973$, o que ele conseguiu provar dois anos mais tarde. Contudo, a sua prova foi simplificada mais tarde por Steve Fisk, o que levou à existência de duas provas distintas. Chvátal tem uma abordagem mais geométrica, enquanto Fisk utiliza resultados bem conhecidos da Teoria dos grafos. De onde, a prova de Fisk é considerada mais curta e esteticamente mais agradável, de modo que é mesmo figurada em Provas conforme O Livro.

Prova

Em qualquer polígono simples com $n$ vértices, é possível ligar quaisquer dois vértices por um segmento de linha, de forma que o polígono se decomponha em, com exceção dos segmentos de ligação, triângulos de disjunção em pares. Esta decomposição é denominada triangulação e a sua existência é comprovada sob certas condições verificadas.

Além disso, os vértices de qualquer polígono triangulado podem ser coloridos apenas com três cores, de modo que quaisquer vértices vizinhos tenham cores diferentes. A escolha de o conjunto de vértices de qualquer uma das três cores, dá um conjunto de guardas válido. Na verdade, cada triângulo do polígono é guardado pelo seu vértice com essa cor. A cor com menos vértices ainda define um conjunto de guardas válido e tem no máximo $\left\lfloor {\frac {n}{3}}\right\rfloor$ guardas, porque as três cores dividem os  vértices do polígono.

Ilustração da prova

Para ilustrar a prova, reconsiderar o Exemplo 4. O primeiro passo consiste em triangular o polígono (Figura 1). Depois, aplica-se uma coloração de $3$ cores adequada (Figura 2) e observa-se que existem $4$ vértices vermelhos, $4$ azuis e $6$ verdes. A cor com menos vértices é azul ou vermelho, pelo que o polígono pode ser coberto por $4$ guardas (Figura 3). Isto concorda com o teorema da galeria de arte, porque o polígono tem $14$ vértices, e $\left\lfloor {\frac {14}{3}}\right\rfloor =4$.

• 

  Figura 1

• 

  Figura 2

• 

  Figura 3

Extensões do problema da galeria de arte

No teorema da galeria de arte, os guardas devem permanecer nos vértices, no entanto, o limite superior dado a Chvátal permanece válido se a restrição aos guardas nos cantos for solta aos guardas em qualquer ponto não exterior ao polígono. Além disto, foram estudadas várias outras generalizações e especificações do teorema original da galeria de arte, como por exemplo:

1. O problema da galeria de arte para polígonos ortogonais de $n$ vértices, onde todas as arestas formam ângulos rectos. Neste caso, um número de guardas de $\left\lfloor {\frac {n}{4}}\right\rfloor$ é sempre suficiente e por vezes necessário para supervisionar a sua superfície. Há muitas provas distintas deste resultado, uma de Kahn, Maria Klawe e Daniel Kleitman, outra de Anna Lube, e outra de Jörg-Rüdiger Sack e Godfried Toussaint, das quais nenhuma é simples.
2. O problema da fortaleza, que consiste em guardar o exterior de um polígono de $n$ vértices. Aqui se distinguem os dois casos seguintes.
   1. Guardas de vértices: Se a posição dos guardas se restringir ao limite do polígono, $\left\lceil {\frac {n}{2}}\right\rceil$ guardas são por vezes necessários e sempre suficientes. Foi também encontrado um limite superior melhor para o caso em que o polígono é ortogonal, a saber, $\left\lceil {\frac {n}{4}}\right\rceil +1$.
   2. Guardas pontuais: Se a posição dos guardas estiver em qualquer lugar fora do polígono, $\left\lceil {\frac {n}{3}}\right\rceil$ guardas são por vezes necessários e sempre suficientes.
3. O problema do pátio da prisão, que é uma combinação do problema da galeria de arte e o problema da fortaleza. Aqui, o objetivo é guardar o interior e o exterior de um polígono de $n$ vértices.
   1. Para polígonos em geral, é necessário um número de guardas de $\left\lceil {\frac {n}{2}}\right\rceil$.
   2. Para polígonos convexos, é necessário um número de guardas de $\left\lfloor {\frac {n}{2}}\right\rfloor$
   3. Para polígonos ortogonais, são necessários pelo menos $\left\lceil {\frac {n}{4}}\right\rceil +1$ guardas e no máximo $\left\lfloor {\frac {5n}{12}}\right\rfloor +2$.
4. O problema da galeria de arte para polígonos de $n$ vértices com $h$ buracos, onde os guardas não são capazes de ver através dos buracos. São considerados os dois casos seguintes.
   1. Polígonos em geral: Um limite inferior de $\left\lfloor {\frac {n+h}{3}}\right\rfloor$ guardas foi conjeturado por Shermer em $1982$ e provado por Hoffmann, Kaufmann e Kriegel em $1991$. Um limite superior de $\left\lfloor {\frac {n+2h}{3}}\right\rfloor$ guardas foi encontrado por O'Rourke em $1987$.
   2. Polígonos ortogonais: Um limite inferior de $\left\lfloor {\frac {n}{4}}\right\rfloor$ guardas foi declarado por Hoffmann em $1990$. Um limite superior de $\left\lfloor {\frac {n+2h}{4}}\right\rfloor$ guardas foi encontrado por O'Rourke em $1987$.
5. O problema da galeria de arte aplicado aos polígonos monótonos de $n$ vértices com guardas móveis que viajam ao longo das arestas ou diagonais. Para tal, devem ser considerados dois tipos de guardas móveis, os guardas móveis de bordo aberto e os guardas móveis de bordo fechado, onde a diferença entre eles é que os pontos finais de uma aresta ou diagonal estão incluídos no caminho de patrulha de um guarda móvel de bordo fechado, mas não no caminho de um guarda móvel de bordo aberto.
   1. $\left\lfloor {\frac {n}{3}}\right\rfloor$ guardas móveis de borda aberta são sempre suficientes e por vezes necessários para supervisionar todo o polígono.
   2. $\left\lfloor {\frac {n+1}{4}}\right\rfloor$ guardas móveis de bordo fechado que patrulham estritamente nos bordos são sempre suficientes e por vezes necessários para observar todo o polígono.
   3. $\left\lfloor {\frac {n}{4}}\right\rfloor$ guardas móveis de bordo fechado que podem viajar entre quaisquer dois vértices são suficientes e por vezes necessários para guardar todo o polígono.

Três dimensões

Um exemplo de um poliedro com pontos interiores que não são visíveis a partir de nenhum vértice.