Problema galeriei de artă

Problema galeriei de artă (cunoscută și sub numele de problema muzeului) este o problemă de vizibilitate bine studiată în geometria computațională, care își are originea în următoarea problemă din lumea reală:

"Într-o galerie de artă de formă poligonală, care este numărul minim de paznici care împreună pot observa întreaga galerie de artă?"

În mod formal, considerăm o zonă poligonală $G$, interpretată ca planul unei galerii de artă. Alegem cât mai puține puncte $p_{1},p_{2},{...},p_{k}$ (paznici) din $G$ astfel încât, pentru fiecare punct $q$ din $G$ și pentru un anumit $i\in \{1,{...},k\}$, segmentul de dreaptă dintre $p_{i}$ și $q$ să nu părăsească poligonul.

În acest context, gărzile nu sunt mobile și au un câmp vizual de $360$ de grade, astfel încât pot fi interpretate ca fiind camere de supraveghere.

• 
  Situația 1
• 
  Situația 2
• 
  Situația 3

Problema galeriei de artă poate fi aplicată în mai multe domenii, cum ar fi în robotică, atunci când inteligențele artificiale (IA) trebuie să execute mișcări în funcție de mediul înconjurător. Alte domenii în care se aplică această problemă sunt editarea imaginilor, problemele de iluminare a unei scene sau instalarea de infrastructuri pentru avertizarea în caz de dezastre naturale.

Exemple

• 
  Exemplul 1: Acest pentagon regulat poate fi supravegheat complet de un singur paznic, a cărui poziție nu este importantă. De fapt, există un rezultat care afirmă că, pentru orice poligon convex, un singur paznic este suficient pentru a observa întreaga galerie.
• 
  Exemplul 2: În acest caz este suficientă și o singură gardă, însă poziția acesteia nu mai este una oarecare. De exemplu, garda nu poate fi plasată într-unul dintre picioare, deoarece am avea nevoie de o a doua pentru celălalt picior.
• 
  Exemplul 3: Pentru acest 6-gon, un singur paznic nu este suficient pentru a acoperi întreaga galerie. De fapt, două gărzi sunt întotdeauna suficiente pentru a acoperi un 6-gon.
• 
  Exemplul 4: Pentru acest 14-gon, trei paznici sunt suficienți pentru a supraveghea întreaga zonă. Acest lucru rezultă din teorema galeriei de artă.

Teorema galeriei de artă

Teorema galeriei de artă, demonstrată de Vaclav Chvátal, oferă o limită superioară pentru numărul minim de gardieni care sunt plasați pe colțurile (vârfurile) unei galerii de artă, și afirmă următoarele:

"Pentru a păzi un poligon simplu cu $n$ vârfuri, $\left\lfloor {\frac {n}{3}}\right\rfloor$ gărzi sunt întotdeauna suficiente și uneori necesare."

Istoric

Problema galeriei de artă i-a fost pusă pentru prima dată lui Chvátal de către Victor Klee în $1973$, problemă pe care acesta a reușit să o demonstreze doi ani mai târziu. Demonstrația sa a fost simplificată ulterior de Steve Fisk, ceea ce a dus la existența a două demonstrații distincte. Chvátal are o abordare mai geometrică, în timp ce Fisk folosește rezultate bine cunoscute din teoria grafurilor. De aceea, demonstrația lui Fisk este considerată mai scurtă și mai plăcută din punct de vedere estetic, astfel încât aceasta figurează chiar în demonstrațiile din THE BOOK.

Demonstrație

În orice poligon simplu cu $n$ vârfuri se pot conecta oricare două vârfuri printr-un segment de dreaptă astfel încât poligonul să se transforme, cu excepția segmentelor de legătură, în triunghiuri disjuncte pe perechi. Această descompunere se numește triangulare, iar existența sa este demonstrată în anumite condiții verificate.

În plus, vârfurile oricărui poligon triangulat pot fi colorate doar cu trei culori, astfel încât orice vârf vecin să aibă culori diferite. Alegerea oricăreia dintre cele trei culori și luarea în considerare a setului de vârfuri de această culoare oferă un set de gardă valid. De fapt, fiecare triunghi al poligonului este păzit de vârful său de acea culoare. Culoarea cu cele mai puține vârfuri definește în continuare un set de gardă valid și are cel mult $\left\lfloor {\frac {n}{3}}\right\rfloor$ gărzi, deoarece cele trei culori împart cele $n$ vârfuri ale poligonului.

Ilustrarea demonstrației

Pentru a ilustra demonstrația, reconsiderați exemplul 4. Primul pas constă în triangularea poligonului (vedeți Figura 1). Apoi, se aplică o colorare în $3$ culori corespunzătoare (vedeți Figura 2) și se observă că există $4$ vârfuri roșii, $4$ albastre și $6$ verzi. Culoarea cu cele mai puține vârfuri este albastră sau roșie, astfel încât poligonul poate fi acoperit de $4$ gărzi (vedeți Figura 3). Acest lucru este în concordanță cu teorema galeriei de artă, deoarece poligonul are $14$ vârfuri, iar $\left\lfloor {\frac {14}{3}}\right\rfloor =4$

• 
  Figura 1
• 
  Figura 2
• 
  Figura 3

Extensii ale problemei galeriei de artă

În teorema galeriei de artă, se presupune că gărzile trebuie să se afle pe vârfuri, însă limita superioară dată de Chvátal rămâne valabilă dacă restricția privind gărzile la colțuri este extinsă la gărzile din orice punct care nu este exterior poligonului. Pe lângă aceasta, au fost studiate diverse generalizări și specificații ale teoremei inițiale a galeriei de artă, cum ar fi:

1. Problema galeriei de artă pentru poligoane ortogonale cu $n$ vârfuri, în care toate marginile formează unghiuri drepte. În acest caz, un număr de $\left\lfloor {\frac {n}{4}}\right\rfloor$ gărzi este întotdeauna suficient și uneori necesar pentru a supraveghea suprafața sa. Există mai multe demonstrații diferite ale acestui rezultat, una de Kahn, Maria Klawe și Daniel Kleitman, alta de Anna Lube și una de Jörg-Rüdiger Sack și Godfried Toussaint, dintre care niciuna nu este simplă.
2. Problema fortăreței, care consistă în a păzi exteriorul unui poligon cu $n$ vârfuri. Aici se disting următoarele două cazuri.
   1. Gărzi de vârf: Dacă poziția gărzilor este limitată la limita poligonului, $\left\lceil {\frac {n}{2}}\right\rceil$ gărzi sunt uneori necesare și întotdeauna suficiente. S-a găsit, de asemenea, o limită superioară mai bună pentru cazul în care poligonul este ortogonal, și anume$\left\lceil {\frac {n}{4}}\right\rceil +1$.
   2. Gărzi de punct: Dacă poziția gărzilor este oriunde în exteriorul poligonului, $\left\lceil {\frac {n}{3}}\right\rceil$ paznici sunt uneori necesari și întotdeauna suficienți.
3. Problema curții închisorii, care este o combinație între problema galeriei de artă și problema fortăreței. Aici, obiectivul este de a păzi interiorul și exteriorul unui poligon cu $n$ vârfuri.
   1. Pentru poligoanele generale, un număr de $\left\lceil {\frac {n}{2}}\right\rceil$ de paznici este necesar.
   2. In cazul poligoanelor convexe, un număr de $\left\lfloor {\frac {n}{2}}\right\rfloor$ de paznici este necesar.
   3. Pentru poligoanele ortogonale, sunt necesare cel puțin $\left\lceil {\frac {n}{4}}\right\rceil +1$ și cel mult $\left\lfloor {\frac {5n}{12}}\right\rfloor +2$ gărzi.
4. Problema galeriei de artă pentru poligoane de $n$ vârfuri cu $h$ găuri, în care paznicii nu pot vedea prin găuri. Se iau în considerare următoarele două cazuri.
   1. Poligoane generale: O limită inferioară de $\left\lfloor {\frac {n+h}{3}}\right\rfloor$ gărzi a fost conjecturată de Shermer în $1982$ și dovedită de Hoffmann, Kaufmann și Kriegel în $1991$. O limită superioară de $\left\lfloor {\frac {n+2h}{3}}\right\rfloor$ gărzi a fost găsită de O'Rourke în $1987$.
   2. Poligoane ortogonale: O limită inferioară de $\left\lfloor {\frac {n}{4}}\right\rfloor$ gărzi a fost stabilită de Hoffmann în $1990$. O limită superioară de $\left\lfloor {\frac {n+2h}{4}}\right\rfloor$ gărzi a fost găsită de O'Rourke în $1987$.
5. Problema galeriei de artă aplicată la poligoane monotone cu $n$ vârfuri cu gărzi mobile care se deplasează de-a lungul marginilor sau diagonalelor. Pentru aceasta, trebuie luate în considerare două tipuri de gărzi mobile, gărzile mobile pe muchii deschise și gărzile mobile pe muchii închise, diferența dintre ele fiind reprezentată prin faptul că punctele finale ale unei muchii sau ale unei diagonale sunt incluse în traseul de patrulare a unei gărzi mobile pe muchii închise, dar nu și în traseul unei gărzi mobile pe muchii deschise.
   1. $\left\lfloor {\frac {n}{3}}\right\rfloor$ gărzi mobile cu margini deschise sunt întotdeauna suficiente și uneori necesare pentru a supraveghea întregul poligon.
   2. $\left\lfloor {\frac {n+1}{4}}\right\rfloor$ gărzi mobile cu muchii închise care patrulează strict pe muchii sunt întotdeauna suficiente și uneori necesare pentru a observa întregul poligon.
   3. $\left\lfloor {\frac {n}{4}}\right\rfloor$ gărzi mobile cu muchii închise care au voie să se deplaseze între oricare două vârfuri sunt suficiente și uneori necesare pentru a proteja întregul poligon.

Bibliografie

• Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2018), „The art gallery problem is $\exists \mathbb {R}$-complete”, În 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, arXiv:1704.06969 , doi:10.1145/3188745.3188868, MR 3826234 
• 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 (ed. 6th), Berlin: Springer, pp. 281–283, doi:10.1007/978-3-662-57265-8, ISBN 978-3-662-57264-1, MR 3823190 .
• Ashur, Stav; Filtser, Omrit; Katz, Matthew J.; Saban, Rachel (2019), „Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains”, În 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, arXiv:1409.4621 , doi:10.1016/j.dam.2016.12.015, MR 3662965 
• Bonnet, Édouard; Miltzow, Tillmann (2017), „An approximation algorithm for the art gallery problem”, În 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, arXiv:1607.05527 , doi:10.4230/LIPIcs.SoCG.2017.20, MR 3685692 .
• 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”, Art Gallery Problem Project, Instituto de Computação .
• 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, Lecture Notes in Computer Science, 4619, Springer-Verlag, pp. 163–174, doi:10.1007/978-3-540-73951-7_15, hdl:1721.1/36243 , ISBN 978-3-540-73948-7 .
• 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, arhivat din original (PDF) la 24 iunie 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, doi:10.1007/s00453-012-9653-3, hdl:2043/11487 , MR 3044626 .
• 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, pp. 97–106, doi:10.1145/323233.323247, ISBN 0-89791-163-6 .
• O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, Oxford University Press, ISBN 0-19-503965-3 .
• O'Rourke, Joseph; Supowit, Kenneth J. (1983), „Some NP-hard polygon decomposition problems”, IEEE Transactions on Information Theory, 29 (2): 181–190, doi:10.1109/TIT.1983.1056648, MR 0712374 .
• Sack, J. R.; Toussaint, G. T. (1988), „Guard placement in rectilinear polygons”, În 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”, În 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  .