Billedgalleri problem

Billedgalleriproblemet eller museumsproblemet er et velundersøgt synlighedsproblem (synbarhed) i beregningsgeometri . Problemet opstår i den virkelige verden som opgaven med at bevogte et kunstgalleri med det mindste antal vagter, der er i stand til at se hele galleriet. I den beregningsmæssige geometriske version af problemet er galleriet repræsenteret som en simpel polygon , og hver beskyttelse er repræsenteret af et punkt inde i polygonen. Et sæt punkter siges at beskytte en polygon, hvis der for ethvert punkt inde i polygonen eksisterer et punkt, således at linjestykket forbinder og ligger helt inde i polygonen.

Todimensionelt rum

Der findes adskillige varianter af det oprindelige problem, som alle kaldes galleriproblemet. I nogle tilfælde skal afskærmningerne være placeret rundt om perimeteren eller endda ved polygonens spidser. I nogle udførelsesformer er beskyttelse af kun perimeteren eller en del af perimeteren påkrævet.

At løse det tilfælde, hvor afskærmninger kun skal placeres ved toppunkter, og kun toppunkter skal beskyttes, svarer til at løse det dominerende sæt- problem på polygonsynlighedsgrafen .

The Art Gallery Theorem

Chvatals billedgallerisætning (af den Prag-fødte canadiske matematiker Václav Chvatal ) giver en øvre grænse for minimumsantallet af vagter. Sætningen siger, at afskærmninger altid er tilstrækkelige, og nogle gange nødvendige, til at beskytte en simpel polygon med hjørner.

Spørgsmålet om antallet af hjørner/vagter blev stillet for Khvatala i 1973 af Victor Klee [1] . Kort efter beviste Hvatal sætningen [2] . Chwatals bevis blev senere forenklet af Steve Fisk ved hjælp af en 3-farve farve [3] (Fisk var professor i matematik ved Bowdoin College [4] ).

Fisks korte bevis

Steve Fisks bevis [3] er så kort og elegant, at det er givet i bogen " Proofs from the Book ".

Bevis : triangulér polygonen (uden at tilføje toppunkter).

Bemærk, at hjørnerne af den resulterende trianguleringsgraf kan farves med tre farver , så hver trekant har hjørner af alle tre farver. En ægte dobbelttrianguleringsgraf med et toppunkt for hver trekant og en kant for hvert par tilstødende trekanter er et træ . Da enhver cyklus i den dobbelte graf ville danne et hul inde i polygonen, hvilket modsiger betingelsen om fravær af huller (ved betingelsen, at polygonen er enkel). Hvis der er mere end én trekant i en triangulering, skal den dobbelte graf (som ethvert træ) have et toppunkt, der kun har én nabo, hvilket svarer til en trekant, der støder op til kun én anden trekant. Polygonen med færre trekanter, opnået ved at fjerne denne yderste trekant, har en trefarvet farvning (ved hjælp af matematisk induktion ), så det er nemt at udvide farvningen til det ekstra toppunkt i den fjernede trekant.

Bemærk endvidere, at hjørner af samme farve danner det korrekte sæt af skærme, da hver trekant er helt synlig fra toppunktet med den valgte farve. Tre farver opdeler polygonens n hjørner i 3 sæt, og farven med færre hjørner danner det korrekte sæt af maksimale skærme.

Beregningsmæssig kompleksitet

I versioner af gallerisikkerhedsproblemet, der er opstillet som et løselighedsproblem , er både en polygon og et tal k givet ved input, og resultatet af løsningen af ​​problemet bør være svaret på, om k guards er nok til at beskytte polygonen. Dette problem og alle dets standardvarianter (såsom at begrænse placeringen af ​​afskærmninger ved hjørnerne eller på polygonens kanter) er NP-hårde [5] [6] [7] . For tilnærmelsesalgoritmer for problemet med at bestemme minimumsantallet af vagter beviste Eidenbenz, Stamm og Widmeyer [8] , at problemet er APX-hårdt, hvilket indebærer, at der næppe findes en polynomisk- tidstilnærmelsesalgoritme med garanteret effektivitet bedre end nogle faste konstant. Den garanterede effektivitetskonstant kendes dog ikke. En logaritmisk tilnærmelse for det mindste antal afskærmninger ved et toppunkt kan opnås ved at reducere problemet til det sæt, der dækker problemet [9] . Som Waltr [10] viste , har sætdækningsproblemet afledt af billedgalleriproblemet afgrænset Vapnik-Chervonenkis dimension , som tillader brugen af ​​sætdækkende algoritmer baseret på ε-nets , hvis garanterede effektivitet afhænger logaritmisk af det optimale tal vagter, og ikke på antallet af hjørner af polygonen [11] . Når placeringen af ​​vagterne ikke er begrænset, gør det uendelige antal mulige vagtstillinger opgaven endnu mere vanskelig [12] .

Imidlertid er effektive algoritmer kendt for at finde et maksimum af vagter placeret ved hjørnerne, hvilket svarer til den øvre grænse for Khvatala. David Avis og Godfried Toussaint [13] beviste, at vagtplacering i værste fald kan beregnes i O(n log n) tid ved hjælp af en divider and conquer-algoritme . Kusches og Moret [14] foreslog en lineær-tids- algoritme , der bruger Fisks korte bevis og Bernard Chazelles lineær-tid plane trianguleringsalgoritme.

En nøjagtig algoritme for vagterne ved hjørnerne blev foreslået af Cote, de Resende, de Souza. Forfatterne udførte intensive beregningseksperimenter på nogle klasser af polygoner, som viste, at optimale løsninger kan findes på en relativt kort beregningstid selv for problemer med tusindvis af hjørner. Inputdata og optimale løsninger på disse problemer er tilgængelige for download [15] .


Variationer og generaliseringer

Der er mange andre generaliseringer og konkretiseringer af den oprindelige gallerisætning [16] . For eksempel behøver ortogonale polygoner , hvor kanter/vægge er i rette vinkler, kun afskærmninger. Der er mindst tre forskellige beviser for dette resultat, og ingen af ​​dem er enkle, disse er beviset fra Kahn, Maria Clave og Daniel Kleitman [17] , beviset for Anna Lubiv [18 ] og beviset for Jörg -Rüdiger Sack og Toussaint [19] [20] .

Et relateret problem spørger om antallet af vagter til at dække det ydre område af en vilkårlig polygon ("Fortress Problem") - nogle gange er det nødvendigt at have vagter, og dette antal er altid nok. Med andre ord er et uendeligt ydre område sværere at bevogte end et endeligt indre område [21] .

3D sag

Hvis museet er repræsenteret i tredimensionelt rum som et polyeder , så giver placeringen af ​​vagter ved alle hjørner ikke et overblik over hele museet. Selvom alle overflader af polyederet vil kunne observeres, er en del af rummet inde i polyederet for nogle polyeder ikke observerbart [22] .

Se også

Noter

  1. ↑ O'Rourke, 1987 , s. en.
  2. ↑ Chvatal, 1975 .
  3. ↑ 12 Fisk , 1978 .
  4. ↑ Gemma Leghorn. Matematikprofessor dør af leukæmi som 63-årig (utilgængeligt link) . The Bowdoin Orient (2010). Arkiveret fra originalen den 16. januar 2017. 
  5. ↑ O'Rourke, 1987 , s. 239-242.
  6. ↑ Aggarwal, 1984 .
  7. ↑ Lee, Lin, 1986 .
  8. ↑ Eidenbenz, Stamm, Widmayer, 2001 .
  9. ↑ Ghosh, 1987 .
  10. ↑ Valtr, 1998 .
  11. ↑ Brönnimann, Goodrich, 1995 .
  12. ↑ Deshpande, Kim, Demaine, Sarma, 2007 .
  13. ↑ Avis, Toussaint, 1981 .
  14. ↑ Kooshesh, Moret, 1992 .
  15. ↑ Couto, de Rezende, de Souza, 2011 .
  16. ↑ Shermer, 1992 .
  17. ↑ Kahn, Klawe, Kleitman, 1983 .
  18. ↑ Lubiw, 1985 .
  19. ↑ O'Rourke, 1987 , s. 31-80.
  20. ↑ Sack, Toussaint, 1988 .
  21. ↑ O'Rourke, 1987 , s. 146-154.
  22. ↑ O'Rourke, 1987 , s. 255.

Litteratur