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 ${\displaystyle n}$ vértices, ${\displaystyle \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 ${\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 ${\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 ${\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 ${\displaystyle 3}$ cores adequada (Figura 2) e observa-se que existem ${\displaystyle 4}$ vértices vermelhos, ${\displaystyle 4}$ azuis e ${\displaystyle 6}$ verdes. A cor com menos vértices é azul ou vermelho, pelo que o polígono pode ser coberto por ${\displaystyle 4}$ guardas (Figura 3). Isto concorda com o teorema da galeria de arte, porque o polígono tem ${\displaystyle 14}$ vértices, e ${\displaystyle \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 ${\displaystyle n}$ vértices, onde todas as arestas formam ângulos rectos. Neste caso, um número de guardas de ${\displaystyle \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 ${\displaystyle 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, ${\displaystyle \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, ${\displaystyle \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, ${\displaystyle \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 ${\displaystyle n}$ vértices.
   1. Para polígonos em geral, é necessário um número de guardas de ${\displaystyle \left\lceil {\frac {n}{2}}\right\rceil }$.
   2. Para polígonos convexos, é necessário um número de guardas de ${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$
   3. Para polígonos ortogonais, são necessários pelo menos ${\displaystyle \left\lceil {\frac {n}{4}}\right\rceil +1}$ guardas e no máximo ${\displaystyle \left\lfloor {\frac {5n}{12}}\right\rfloor +2}$.
4. O problema da galeria de arte para polígonos de ${\displaystyle n}$ vértices com ${\displaystyle 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 ${\displaystyle \left\lfloor {\frac {n+h}{3}}\right\rfloor }$ guardas foi conjeturado por Shermer em ${\displaystyle 1982}$ e provado por Hoffmann, Kaufmann e Kriegel em ${\displaystyle 1991}$. Um limite superior de ${\displaystyle \left\lfloor {\frac {n+2h}{3}}\right\rfloor }$ guardas foi encontrado por O'Rourke em ${\displaystyle 1987}$.
   2. Polígonos ortogonais: Um limite inferior de ${\displaystyle \left\lfloor {\frac {n}{4}}\right\rfloor }$ guardas foi declarado por Hoffmann em ${\displaystyle 1990}$. Um limite superior de ${\displaystyle \left\lfloor {\frac {n+2h}{4}}\right\rfloor }$ guardas foi encontrado por O'Rourke em ${\displaystyle 1987}$.
5. O problema da galeria de arte aplicado aos polígonos monótonos de ${\displaystyle 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. ${\displaystyle \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. ${\displaystyle \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. ${\displaystyle \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.

Notas

Referências

• Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2018), «The art gallery problem is ${\displaystyle \exists \mathbb {R} }$-complete», in: Diakonikolas, Ilias; Kempe, David; Henzinger, Monika, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25–29, 2018, ACM, pp. 65–73, MR 3826234, arXiv:1704.06969, doi:10.1145/3188745.3188868 
• Aggarwal, A. (1984), The art gallery theorem: Its variations, applications, and algorithmic aspects, Ph.D. thesis, Johns Hopkins University .
• Aigner, Martin; Ziegler, Günter M. (2018), «Chapter 40: How to guard a museum», Proofs from THE BOOK, ISBN 978-3-662-57264-1 6th ed. , Berlin: Springer, pp. 281–283, MR 3823190, doi:10.1007/978-3-662-57265-8  Parâmetro desconhecido |title-link= ignorado (ajuda).
• Ashur, Stav; Filtser, Omrit; Katz, Matthew J.; Saban, Rachel (2019), «Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains», in: Bampis, Evripidis; Megow, Nicole, Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12–13, 2019, Revised Selected Papers, Lecture Notes in Computer Science, 11926, Berlin: Springer, pp. 1–17, doi:10.1007/978-3-030-39479-0_1 .
• Avis, D.; Toussaint, G. T. (1981), «An efficient algorithm for decomposing a polygon into star-shaped polygons» (PDF), Pattern Recognition, 13 (6): 395–398, Bibcode:1981PatRe..13..395A, doi:10.1016/0031-3203(81)90002-9 .
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Pal, Sudebkumar (2017), Constant Approximation Algorithms for Guarding Simple Polygons using Vertex Guards, arXiv:1712.05492 
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, Bodhayan (2017), «Approximability of guarding weak visibility polygons», Discrete Applied Mathematics, 228: 109–129, MR 3662965, arXiv:1409.4621, doi:10.1016/j.dam.2016.12.015 
• Bonnet, Édouard; Miltzow, Tillmann (2017), «An approximation algorithm for the art gallery problem», in: Aronov, Boris; Katz, Matthew J., 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, LIPIcs, 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 20:1–20:15, MR 3685692, arXiv:1607.05527, doi:10.4230/LIPIcs.SoCG.2017.20 .
• Brönnimann, H.; Goodrich, M. T. (1995), «Almost optimal set covers in finite VC-dimension», Discrete and Computational Geometry, 14 (1): 463–479, doi:10.1007/BF02570718 .
• Chvátal, V. (1975), «A combinatorial theorem in plane geometry», Journal of Combinatorial Theory, Series B, 18: 39–41, doi:10.1016/0095-8956(75)90061-1 .
• Couto, M.; de Rezende, P.; de Souza, C. (2011), «An exact algorithm for minimizing vertex guards on art galleries», International Transactions in Operational Research, 18 (4): 425–448, doi:10.1111/j.1475-3995.2011.00804.x .
• de Rezende, P.; de Souza, C.; Couto, M.; Tozoni, D. (2011), «The Art Gallery Problem with Vertex Guards», Instituto de Computação, Art Gallery Problem Project .
• Deshpande, Ajay; Kim, Taejung; Demaine, Erik D.; Sarma, Sanjay E. (2007), «A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems», Proc. Worksh. Algorithms and Data Structures, ISBN 978-3-540-73948-7, Lecture Notes in Computer Science, 4619, Springer-Verlag, pp. 163–174, doi:10.1007/978-3-540-73951-7_15, hdl:1721.1/36243 .
• Eidenbenz, S.; Stamm, C.; Widmayer, P. (2001), «Inapproximability results for guarding polygons and terrains» (PDF), Algorithmica, 31 (1): 79–113, doi:10.1007/s00453-001-0040-8, cópia arquivada (PDF) em 24 de junho de 2003 .
• Fisk, S. (1978), «A short proof of Chvátal's watchman theorem», Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X .
• Ghosh, S. K. (1987), «Approximation algorithms for art gallery problems», Proc. Canadian Information Processing Society Congress, pp. 429–434 .
• Kahn, J.; Klawe, M.; Kleitman, D. (1983), «Traditional galleries require fewer watchmen», SIAM J. Algebr. Discrete Methods, 4 (2): 194–206, doi:10.1137/0604020 .
• Kooshesh, A. A.; Moret, B. M. E. (1992), «Three-coloring the vertices of a triangulated simple polygon», Pattern Recognition, 25 (4): 443, Bibcode:1992PatRe..25..443K, doi:10.1016/0031-3203(92)90093-X .
• Krohn, Erik A.; Nilsson, Bengt J. (2013), «Approximate guarding of monotone and rectilinear polygons», Algorithmica, 66 (3): 564–594, MR 3044626, doi:10.1007/s00453-012-9653-3, hdl:2043/11487 .
• Lee, D. T.; Lin, A. K. (1986), «Computational complexity of art gallery problems», IEEE Transactions on Information Theory, 32 (2): 276–282, doi:10.1109/TIT.1986.1057165 .
• Lubiw, A. (1985), «Decomposing polygonal regions into convex quadrilaterals», Proc. 1st ACM Symposium on Computational Geometry, ISBN 0-89791-163-6, pp. 97–106, doi:10.1145/323233.323247 .
• O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, ISBN 0-19-503965-3, Oxford University Press  Parâmetro desconhecido |title-link= ignorado (ajuda).
• O'Rourke, Joseph; Supowit, Kenneth J. (1983), «Some NP-hard polygon decomposition problems», IEEE Transactions on Information Theory, 29 (2): 181–190, MR 712374, doi:10.1109/TIT.1983.1056648 .
• Sack, J. R.; Toussaint, G. T. (1988), «Guard placement in rectilinear polygons», in: Toussaint, G. T., Computational Morphology, North-Holland, pp. 153–176 .
• Shermer, Thomas (1992), «Recent Results in Art Galleries» (PDF), Proceedings of the IEEE, 80 (9): 1384–1399, doi:10.1109/5.163407 .
• Urrutia, Jorge (2000), «Art gallery and illumination problems», in: Sack, J. -R.; Urrutia, Jorge, Handbook of Computational Geometry, North-Holland, pp. 973–1027, doi:10.1016/B978-044482537-7/50023-1 .
• Valtr, P. (1998), «Guarding galleries where no point sees a small area», Israel Journal of Mathematics, 104 (1): 1–16, doi:10.1007/BF02897056 .
• Vuich, Megan (2019), «Exploring Topics of the Art Gallery Problem», Senior Independent Study Theses .
• Kaul, Hemanshu; Jo, YoungJu, «The Art Gallery Problem», Illinois Institute of Technology .

Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Editor: considere marcar com um esboço mais específico.