Bildgalleri problem

Bildgalleriproblemet eller museiproblemet är ett väl studerat synlighetsproblem (synbarhet) inom beräkningsgeometri . Problemet uppstår i den verkliga världen som uppgiften att vakta ett konstgalleri med det minsta antalet vakter som kan se hela galleriet. I den beräkningsgeometriska versionen av problemet representeras galleriet som en enkel polygon och varje skydd representeras av en punkt inuti polygonen. En uppsättning punkter sägs skydda en polygon om det för någon punkt inuti polygonen finns en punkt så att linjesegmentet sammanfogar och ligger helt innanför polygonen.

Tvådimensionellt utrymme

Det finns många varianter av det ursprungliga problemet, som alla kallas galleriproblemet. I vissa fall måste skydden vara placerade runt omkretsen eller till och med vid polygonens hörn. I vissa utföringsformer krävs skydd av endast omkretsen eller en del av omkretsen.

Att lösa fallet där skydd endast ska placeras vid hörn och endast hörn ska skyddas motsvarar att lösa det dominerande uppsättningsproblemet på polygonsynlighetsgrafen .

The Art Gallery Theorem

Chvatals bildgallerisats (av den Pragfödde kanadensiske matematikern Václav Chvatal ) ger en övre gräns för det minsta antalet vakter. Teoremet säger att skydd alltid är tillräckliga, och ibland nödvändiga, för att skydda en enkel polygon med hörn.

Frågan om antalet hörn/vakter ställdes för Khvatala 1973 av Victor Klee [1] . Kort därefter bevisade Hvatal satsen [2] . Chwatals bevis förenklades senare av Steve Fisk med hjälp av en 3- färgsfärg [3] (Fisk var professor i matematik vid Bowdoin College [4] ).

Fisks korta bevis

Steve Fisks bevis [3] är så kort och elegant att det ges i boken " Proofs from the Book ".

Bevis : triangulera polygonen (utan att lägga till hörn).

Observera att hörnen på den resulterande trianguleringsgrafen kan färgas med tre färger , så att varje triangel har hörn av alla tre färgerna. En verkligt dubbeltrianguleringsgraf med en vertex för varje triangel och en kant för varje par intilliggande trianglar är ett träd . Eftersom vilken cykel som helst i den dubbla grafen skulle bilda ett hål inuti polygonen, vilket motsäger villkoret om frånvaro av hål (genom villkoret är polygonen enkel). Om det finns mer än en triangel i en triangulering måste den dubbla grafen (som vilket träd som helst) ha en vertex som bara har en granne, vilket motsvarar en triangel som gränsar till endast en annan triangel. Polygonen med färre trianglar, som erhålls genom att ta bort den här yttersta triangeln, har en trefärgad färgning (med matematisk induktion ), så det är lätt att utöka färgningen till ytterligare vertex av den borttagna triangeln.

Observera vidare att hörn av samma färg bildar den korrekta uppsättningen av skydd, eftersom varje triangel är helt synlig från vertexen med den valda färgen. Tre färger delar upp polygonens n hörn i 3 uppsättningar, och färgen med färre hörn bildar den korrekta uppsättningen av maximala skydd.

Beräkningskomplexitet

I versioner av gallerisäkerhetsproblemet som ställs som ett lösbarhetsproblem ges både en polygon och ett nummer k vid ingången, och resultatet av att lösa problemet bör vara svaret på om k -skydd är tillräckligt för att skydda polygonen. Detta problem och alla dess standardvarianter (som att begränsa placeringen av skydd vid hörn eller på kanterna av polygonen) är NP-hårda [5] [6] [7] . För approximationsalgoritmer för problemet med att bestämma det minsta antalet vakter, bevisade Eidenbenz, Stamm och Widmeyer [8] att problemet är APX-hårt, vilket innebär att det knappast finns en polynom- tidsapproximationsalgoritm med garanterad effektivitet bättre än någon fastställd konstant. Den garanterade verkningsgradskonstanten är dock inte känd. En logaritmisk approximation för det minsta antalet skydd vid en vertex kan erhållas genom att reducera problemet till det uppsättningstäckande problemet [9] . Som Waltr [10] visade , har uppsättningstäckningsproblemet som härrör från bildgalleriproblemet begränsat Vapnik-Chervonenkis dimension , som tillåter användning av settäckande algoritmer baserade på ε-nets , vars garanterade effektivitet beror logaritmiskt på det optimala antalet skydd, och inte på antalet hörn av polygonen [11] . När placeringen av vakterna inte är begränsad gör det oändliga antalet möjliga vaktpositioner uppgiften ännu svårare [12] .

Effektiva algoritmer är dock kända för att hitta maximalt antal skydd som är placerade vid hörnen, vilket motsvarar den övre gränsen för Khvatala. David Avis och Godfried Toussaint [13] bevisade att vaktplacering kan beräknas i värsta fall i O(n log n) tid med hjälp av en divide and conquer-algoritm . Kusches och Moret [14] föreslog en linjär-tidsalgoritm som använder Fisks kortbevis och Bernard Chazelles linjär-tid planar trianguleringsalgoritm.

En exakt algoritm för vakterna vid hörnen föreslogs av Cote, de Resende, de Souza. Författarna genomförde intensiva beräkningsexperiment på vissa klasser av polygoner, som visade att optimala lösningar kan hittas på en relativt kort beräkningstid även för problem med tusentals hörn. Indata och optimala lösningar på dessa problem finns tillgängliga för nedladdning [15] .


Variationer och generaliseringar

Det finns många andra generaliseringar och konkretiseringar av den ursprungliga gallerisatsen [16] . Till exempel, ortogonala polygoner där kanter/väggar är i räta vinklar behöver bara skydd. Det finns åtminstone tre olika bevis på detta resultat, och inget av dem är enkelt, det här är beviset från Kahn, Maria Clave och Daniel Kleitman [17] , beviset för Anna Lubiv [18 ] och beviset för Jörg -Rüdiger Sack och Toussaint [19] [20] .

Ett relaterat problem frågar om antalet vakter för att täcka det yttre området av en godtycklig polygon ("Fortress Problem") - ibland är det nödvändigt att ha vakter och detta antal är alltid tillräckligt. Med andra ord är en oändlig yttre region svårare att skydda än en finit inre region [21] .

3D-fodral

Om museet är representerat i tredimensionellt utrymme som en polyeder , ger placeringen av vakterna vid alla hörn inte en överblick över hela museet. Även om alla ytor av polyedern kommer att vara observerbara, för vissa polyeder, är en del av utrymmet inuti polyedern inte observerbar [22] .

Se även

Anteckningar

  1. ↑ O'Rourke, 1987 , sid. ett.
  2. ↑ Chvatal, 1975 .
  3. ↑ 12 Fisk , 1978 .
  4. ↑ Gemma Leghorn. Matematikprofessor dör i leukemi vid 63 år (inte tillgänglig länk) . The Bowdoin Orient (2010). Arkiverad från originalet den 16 januari 2017. 
  5. ↑ O'Rourke, 1987 , sid. 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 , sid. 31–80.
  20. ↑ Sack, Toussaint, 1988 .
  21. ↑ O'Rourke, 1987 , sid. 146–154.
  22. ↑ O'Rourke, 1987 , sid. 255.

Litteratur