Problém s galerií obrázků

Problém obrazové galerie nebo problém muzea je dobře prostudovaný problém viditelnosti (viditelnosti) ve výpočetní geometrii . Problém nastává v reálném světě jako úkol střežit uměleckou galerii s minimálním počtem strážců, kteří jsou schopni vidět celou galerii. Ve verzi problému s výpočetní geometrií je galerie reprezentována jako jednoduchý mnohoúhelník a každý strážný je reprezentován bodem uvnitř mnohoúhelníku. O množině bodů se říká, že střeží mnohoúhelník, pokud pro jakýkoli bod uvnitř mnohoúhelníku existuje bod takový, že se úsečka spojuje a leží zcela uvnitř mnohoúhelníku.

Dvourozměrný prostor

Existuje mnoho variant původního problému, z nichž všechny se nazývají galerijní problém. V některých případech musí být chrániče umístěny po obvodu nebo dokonce ve vrcholech polygonu. V některých provedeních je vyžadována ochrana pouze obvodu nebo části obvodu.

Řešení případu, kdy by měly být kryty umístěny pouze ve vrcholech a pouze vrcholy by měly být střeženy, je ekvivalentní řešení problému dominující množiny na grafu viditelnosti polygonu .

The Art Gallery Theorem

Věta o Chvátalově obrazárně (od pražského kanadského matematika Václava Chvatala ) udává horní hranici minimálního počtu stráží. Věta říká, že stráže jsou vždy dostatečné a někdy nutné, aby střežily jednoduchý mnohoúhelník s vrcholy.

Otázku počtu vrcholů/stráží položil pro Khvatala v roce 1973 Victor Klee [1] . Krátce nato Hvatal dokázal větu [2] . Chwatalův důkaz později zjednodušil Steve Fisk pomocí 3barevného zbarvení [ 3] (Fisk byl profesorem matematiky na Bowdoin College [4] ).

Fiskův krátký důkaz

Důkaz Steva Fiska [3] je tak krátký a elegantní, že je uveden v knize „ Proofs from the Book “.

Důkaz : triangulujte polygon (bez přidání vrcholů).

Všimněte si, že vrcholy výsledného triangulačního grafu mohou být obarveny třemi barvami , takže každý trojúhelník má vrcholy všech tří barev. Skutečně duální triangulační graf s jedním vrcholem pro každý trojúhelník a jednou hranou pro každou dvojici sousedních trojúhelníků je strom . Protože jakýkoli cyklus v duálním grafu by vytvořil díru uvnitř polygonu, což je v rozporu s podmínkou absence děr (podmínkou je mnohoúhelník jednoduchý). Pokud je v triangulaci více než jeden trojúhelník, duální graf (jako každý strom) musí mít vrchol, který má pouze jednoho souseda, což odpovídá trojúhelníku sousedícímu pouze s jedním dalším trojúhelníkem. Mnohoúhelník s menším počtem trojúhelníků, získaný odstraněním tohoto nejvzdálenějšího trojúhelníku, má tříbarevné zbarvení (pomocí matematické indukce ), takže je snadné rozšířit obarvení na další vrchol odstraněného trojúhelníku.

Dále si všimněte, že vrcholy stejné barvy tvoří správnou sadu chráničů, protože každý trojúhelník je zcela viditelný z vrcholu s vybranou barvou. Tři barvy rozdělují n vrcholů mnohoúhelníku do 3 sad a barva s méně vrcholy tvoří správnou sadu maximálních strážců.

Výpočetní složitost

Ve verzích bezpečnostního problému galerie představovaném jako problém řešitelnosti je na vstupu uveden polygon i číslo k a výsledkem řešení problému by měla být odpověď, zda k ochraně polygonu stačí k strážců. Tento problém a všechny jeho standardní varianty (jako např. omezení umístění chráničů ve vrcholech nebo na okrajích polygonu) jsou NP-hard [5] [6] [7] . Pro aproximační algoritmy problému stanovení minimálního počtu stráží Eidenbenz, Stamm a Widmeyer [8] prokázali, že problém je APX-těžký, z čehož vyplývá, že stěží existuje polynomiální-časový aproximační algoritmus s garantovanou účinností lepší než některé pevné konstantní. Zaručená konstanta účinnosti však není známa. Logaritmickou aproximaci pro minimální počet strážců ve vrcholu lze získat redukováním problému na daný problém krytí [9] . Jak ukázal Waltr [10] , problém pokrytí množin odvozený z problému galerie obrázků má ohraničenou dimenzi Vapnik-Chervonenkis , což umožňuje použití algoritmů pokrytí množin založených na ε-nets , jejichž garantovaná účinnost závisí logaritmicky na optimálním počtu strážců, a nikoli na počtu vrcholů polygonu [11] . Když není rozmístění stráží omezeno, nekonečný počet možných pozic stráží úkol ještě ztíží [12] .

Jsou však známé účinné algoritmy pro nalezení maximálního počtu stráží umístěných ve vrcholech, což odpovídá horní hranici Khvatala. David Avis a Godfried Toussaint [13] dokázali, že umístění stráže lze v nejhorším případě vypočítat v čase O(n log n) pomocí algoritmu rozděl a panuj . Kusches a Moret [14] navrhli algoritmus s lineárním časem , který používá Fiskův krátký důkaz a algoritmus planární triangulace Bernarda Chazelleho.

Přesný algoritmus pro stráže ve vrcholech navrhl Cote, de Resende, de Souza. Autoři provedli intenzivní výpočetní experimenty na některých třídách polygonů, které ukázaly, že i pro problémy s tisíci vrcholy lze nalézt optimální řešení v relativně krátkém výpočetním čase. Vstupní data a optimální řešení těchto problémů jsou k dispozici ke stažení [15] .


Variace a zobecnění

Existuje mnoho dalších zobecnění a konkretizací původní galerijní věty [16] . Například ortogonální polygony , kde jsou hrany/stěny v pravém úhlu, potřebují pouze kryty. Existují nejméně tři různé důkazy tohoto výsledku a žádný z nich není jednoduchý, toto jsou důkazy Kahna, Maria Clave a Daniela Kleitmana [17] , důkaz Anny Lubiv [18 ] a důkaz Jörga-Rüdigera Sacka a Toussainta [19] [20] .

Související problém se ptá na počet stráží k pokrytí vnější oblasti libovolného polygonu ("Problém pevnosti") - někdy je potřeba mít stráže a tento počet vždy stačí. Jinými slovy, nekonečnou vnější oblast je obtížnější chránit než konečnou vnitřní oblast [21] .

3D pouzdro

Pokud je muzeum zastoupeno v trojrozměrném prostoru jako mnohostěn , pak umístění stráží ve všech vrcholech neposkytuje přehled o celém muzeu. Přestože všechny povrchy mnohostěnu budou pozorovatelné, u některých mnohostěnů část prostoru uvnitř mnohostěnu pozorovatelná není [22] .

Viz také

Poznámky

  1. ↑ O'Rourke, 1987 , s. jeden.
  2. ↑ Chvátal, 1975 .
  3. ↑ 12 Fisk , 1978 .
  4. ↑ Gemma Leghorn. Profesor matematiky umírá na leukémii ve věku 63 (nedostupný odkaz) . Bowdoin Orient (2010). Archivováno z originálu 16. ledna 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.

Literatura