Problema da galeria de arte
O problema da galeria de arte é um problema de visibilidade bem estudado em geometria computacional, que tem a sua origem no seguinte problema do mundo real:
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:
História
O problema da galeria de arte foi apresentado pela primeira vez a Chvátal por Victor Klee em 1973 {\displaystyle 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 {\displaystyle 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 ⌊ n 3 ⌋ {\displaystyle \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 {\displaystyle 3} cores adequada (Figura 2) e observa-se que existem 4 {\displaystyle 4} vértices vermelhos, 4 {\displaystyle 4} azuis e 6 {\displaystyle 6} verdes. A cor com menos vértices é azul ou vermelho, pelo que o polígono pode ser coberto por 4 {\displaystyle 4} guardas (Figura 3). Isto concorda com o teorema da galeria de arte, porque o polígono tem 14 {\displaystyle 14} vértices, e ⌊ 14 3 ⌋ = 4 {\displaystyle \left\lfloor {\frac {14}{3}}\right\rfloor =4} .
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:
