Problém s uměleckou galerií - Art gallery problem

The problém s uměleckou galerií nebo muzejní problém je dobře studovaný problém s viditelností v výpočetní geometrie. Vychází z reálného problému střežení galerie umění s minimálním počtem strážců, kteří mohou společně sledovat celou galerii. V geometrické verzi problému je rozložení umělecké galerie reprezentováno a jednoduchý mnohoúhelník a každý strážce je reprezentován a směřovat v mnohoúhelníku. Sada bodů říká, že chrání polygon, pokud pro každý bod v polygonu nějaké jsou takové, že úsečka mezi a neopustí mnohoúhelník.

Dva rozměry

Tuto galerii pokrývají čtyři fotoaparáty.

Existuje řada variací původního problému, které se také označují jako problém s uměleckou galerií. V některých verzích jsou stráže omezeny na obvod nebo dokonce na vrcholy mnohoúhelníku. Některé verze vyžadují k hlídání pouze obvod nebo podmnožinu obvodu.

Řešení verze, ve které musí být stráže umístěny na vrcholech a je třeba střežit pouze vrcholy, je ekvivalentní řešení dominující množinový problém na graf viditelnosti mnohoúhelníku.

Věta o Chvátalově galerii

Věta o umělecké galerii Chvátal, pojmenovaná po Václav Chvátal, dává horní hranice o minimálním počtu strážných. Uvádí to stráže jsou vždy dostatečné a někdy nutné k ochraně jednoduchého mnohoúhelníku vrcholy.

Chvátal položil otázku, kolik vertexů / hlídačů / stráží bylo zapotřebí Victor Klee v roce 1973.[1] Chvátal to krátce poté dokázal.[2] Chvátalov důkaz později zjednodušil Steve Fisk prostřednictvím a 3-zbarvení argument.[3]

Fiskův krátký důkaz

Trojbarevnost vrcholů trojúhelníkového mnohoúhelníku. Modré vrcholy tvoří sadu tří stráží, tak málo, jak je zaručeno teorémem umělecké galerie. Tato sada však není optimální: stejný polygon lze střežit pouze dvěma strážci.

Důkaz Steva Fiska je tak krátký a elegantní, že byl vybrán pro zařazení do Důkazy z KNIHY.[4]Důkaz je následující:

Nejprve je mnohoúhelník trojúhelníkové (bez přidání dalších vrcholů). Vrcholy výsledného triangulačního grafu mohou být 3-barevné.[5] Je zřejmé, že pod 3 barvami musí mít každý trojúhelník všechny tři barvy. Vrcholy s libovolnou barvou tvoří platnou ochrannou sadu, protože každý trojúhelník mnohoúhelníku je střežen jeho vrcholem s touto barvou. Protože tři barvy rozdělují n vrcholy mnohoúhelníku, barva s nejmenším počtem vrcholů definuje platnou ochrannou sadu maximálně stráže.

Zobecnění

Chvátalova horní mez zůstává v platnosti, pokud je omezení na stráže v rozích uvolněno na stráže v kterémkoli bodě, který není vně polygonu.

Existuje řada dalších zevšeobecnění a specializací původní věty o galeriích.[6] Například pro ortogonální polygony, ti, jejichž hrany / stěny se setkávají pouze v pravém úhlu jsou potřeba stráže. Existují nejméně tři odlišné důkazy tohoto výsledku, žádný z nich není jednoduchý: autor Kahn, Klawe, a Kleitman; podle Lubiw; a tím Pytel a Toussaint.[7]

Související problém vyžaduje, aby počet stráží pokryl vnější stranu libovolného polygonu („problém pevnosti“): jsou někdy nutné a vždy dostatečné. Jinými slovy, nekonečný exteriér je obtížnější zakrýt než konečný interiér.[8]

Výpočetní složitost

v rozhodovací problém verze problému umělecké galerie, jedna je uvedena jako vstup polygon i číslo k, a musí určit, zda lze polygon chránit k nebo méně stráží. Tento problém je -kompletní, stejně jako verze, kde jsou stráže omezeny na hrany mnohoúhelníku.[9] Kromě toho většina ostatních standardních variant (například omezení umístění stráží na vrcholy) je NP-tvrdé.[10]

Ohledně aproximační algoritmy pro minimální počet strážců, Eidenbenz, Stamm & Widmayer (2001) prokázal, že problém je tvrdý APX, což znamená, že je nepravděpodobné, že by nějaký byl přibližný poměr lepší než určité pevné konstanty lze dosáhnout pomocí a polynomiální čas aproximační algoritmus. Algoritmus dosahující konstantní aproximační poměr však nebyl znám až do nedávné doby. Ghosh (1987) ukázal, že a logaritmický aproximace může být dosažena pro minimální počet strážců vrcholů diskretizací vstupního polygonu do konvexních podoblastí a potom redukcí problému nastavit kryt problém. Tak jako Valtr (1998) Ukázalo se, že množinový systém odvozený od problému umělecké galerie má hranice VC rozměr, umožňující použití algoritmů sady krytí založených na ε-sítě jehož aproximační poměr je spíše logaritmem optimálního počtu stráží než počtu polygonových vrcholů.[11] U neomezených stráží tento problém ještě více zkomplikuje nekonečné množství potenciálních strážných pozic. Složitější však omezením stráží ležet na jemné mřížce logaritmický algoritmus aproximace lze odvodit za určitých mírných zvláštních předpokladů, jak ukazuje Bonnet & Miltzow (2017). Efektivní algoritmy jsou však známé pro vyhledání sady maximálně vrcholové stráže, odpovídající Chvátalově horní hranici.David Avis a Godfried Toussaint  (1981 ) prokázal, že umístění pro tyto stráže lze vypočítat v O (č log n) čas v nejhorším případě prostřednictvím a algoritmus rozděl a panuj.Kooshesh & Moret (1992) dal lineární čas algoritmus pomocí Fiskova krátkého důkazu a Bernard Chazelle lineární algoritmus triangulace v časové rovině.

U jednoduchých polygonů, které neobsahují díry, Ghosh předpokládal existenci algoritmu aproximace konstantních faktorů pro vrcholy a hranové stráže. Ghoshova domněnka byla původně prokázána jako pravdivá pro vrcholové stráže ve dvou speciálních podtřídách jednoduchých polygonů, viz. monotónní polygony a polygony slabě viditelné z okraje. Krohn & Nilsson (2013) představil aproximační algoritmus, který vypočítává v polynomiálním čase sadu vrcholových stráží pro monotónní polygon tak, že velikost sady stráží je maximálně 30krát vyšší než optimální počet strážců vrcholů. Bhattacharya, Ghosh & Roy (2017) představil aproximační algoritmus, který počítá v O (n2) načasujte sadu vrcholových stráží pro jednoduchý polygon, který je slabě viditelný z okraje tak, že velikost sady zástěn je maximálně šestinásobek optimálního počtu ochranných vrcholů. Následně Bhattacharya, Ghosh & Pal (2017) tvrdil, že dohad zcela vyřešil předložením algoritmů aproximace konstantních faktorů pro hlídání obecných jednoduchých polygonů pomocí ochranných vrcholů a ochranných okrajů. Pro střežení podtřídy jednoduchých polygonů, které jsou slabě viditelné z hrany, a schéma aproximace v polynomiálním čase byl navržen uživatelem Ashur a kol. (2019).

Přesný algoritmus navrhl Couto, de Rezende & de Souza (2011) pro vrcholové stráže. Autoři provedli rozsáhlé výpočetní experimenty s několika třídami polygonů, které ukázaly, že optimální řešení lze nalézt v relativně malých časech výpočtu i pro instance spojené s tisíci vrcholů. Vstupní data a optimální řešení pro tyto instance jsou k dispozici ke stažení.[12]

Tři rozměry

Příklad mnohostěnu s vnitřními body, které nejsou viditelné z žádného vrcholu.

Pokud je muzeum zastoupeno ve třech rozměrech jako a mnohostěn, pak uvedení stráže na každý vrchol nezajistí, aby bylo celé muzeum pod dohledem. Ačkoli by byl prozkoumán celý povrch mnohostěnu, u některých mnohostěnů jsou ve vnitřku body, které nemusí být pod dohledem.[13]

Viz také

Poznámky

  1. ^ O'Rourke (1987), str. 1.
  2. ^ Chvátal (1975).
  3. ^ Fisk (1978).
  4. ^ Aigner & Ziegler (2018).
  5. ^ Abychom prokázali 3barevnost polygonálních triangulací, pozorujeme slabé duální graf k triangulaci ( neorientovaný graf mající jeden vrchol na trojúhelník a jednu hranu na pár sousedních trojúhelníků) je a strom, protože jakýkoli cyklus v duálním grafu by vytvořil hranici díry v mnohoúhelníku, na rozdíl od předpokladu, že nemá žádné díry. Kdykoli existuje více než jeden trojúhelník, musí mít duální graf (jako každý strom) vrchol pouze s jedním sousedem, což odpovídá trojúhelníku, který sousedí s ostatními trojúhelníky pouze po jedné z jeho stran. Menší mnohoúhelník vytvořený odstraněním tohoto trojúhelníku má 3 zbarvení matematická indukce a toto zbarvení lze snadno rozšířit na jeden další vrchol odstraněného trojúhelníku (O'Rourke 1987, str. 13).
  6. ^ Shermer (1992).
  7. ^ O'Rourke (1987), s. 31–80; Kahn, Klawe & Kleitman (1983); Lubiw (1985); Sack & Toussaint (1988).
  8. ^ O'Rourke (1987), s. 146–154.
  9. ^ Abrahamsen, Adamaszek & Miltzow (2018).
  10. ^ O'Rourke & Supowit (1983); Lee & Lin (1986).
  11. ^ Brönnimann & Goodrich (1995).
  12. ^ Couto, de Rezende & de Souza (2011).
  13. ^ O'Rourke (1987), str. 255.

Reference

  • Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2018), „Problém s uměleckou galerií je -complete ", Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Sborník z 50. výročního sympozia ACM SIGACT o teorii výpočtů, STOC 2018, Los Angeles, CA, USA, 25. – 29. Června 2018, ACM, str. 65–73, arXiv:1704.06969, doi:10.1145/3188745.3188868, PAN  3826234
  • Aggarwal, A. (1984), Věta umělecké galerie: její variace, aplikace a algoritmické aspekty, Ph.D. práce, Johns Hopkins University.
  • Aigner, Martin; Ziegler, Günter M. (2018), „Kapitola 40: Jak hlídat muzeum“, Důkazy z KNIHY (6. vyd.), Berlin: Springer, str. 281–283, doi:10.1007/978-3-662-57265-8, ISBN  978-3-662-57264-1, PAN  3823190.
  • 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 (eds.), Aproximace a online algoritmy - 17. mezinárodní workshop, WAOA 2019, Mnichov, Německo, 12. – 13. Září 2019, revidované vybrané příspěvky, Přednášky v informatice, 11926, Berlín: Springer, s. 1–17, doi:10.1007/978-3-030-39479-0_1.
  • Avis, D.; Toussaint, G. T. (1981), „Efektivní algoritmus pro rozklad polygonu na hvězdicovité polygony“ (PDF), Rozpoznávání vzorů, 13 (6): 395–398, doi:10.1016/0031-3203(81)90002-9.
  • Bhattacharya, Pritam; Ghosh, Subir Kumar; Pal, Sudebkumar (2017), Algoritmy konstantní aproximace pro hlídání jednoduchých polygonů pomocí vertexových stráží, arXiv:1712.05492
  • Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, Bodhayan (2017), „Přibližnost střežení polygonů se slabou viditelností“, Diskrétní aplikovaná matematika, 228: 109–129, arXiv:1409.4621, doi:10.1016 / j.dam.2016.12.015, PAN  3662965
  • Bonnet, Édouard; Miltzow, Tillmann (2017), „Aproximační algoritmus pro problém umělecké galerie“, Aronov, Boris; Katz, Matthew J. (eds.), 33. mezinárodní symposium o výpočetní geometrii, SoCG 2017, 4. – 7. Července 2017, Brisbane, Austrálie, LIPIcs, 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, str. 20: 1–20: 15, arXiv:1607.05527, doi:10.4230 / LIPIcs.SoCG.2017.20, PAN  3685692.
  • Brönnimann, H .; Goodrich, M. T. (1995), „Téměř optimální sada pokrývá konečnou dimenzi VC“, Diskrétní a výpočetní geometrie, 14 (1): 463–479, doi:10.1007 / BF02570718.
  • Chvátal, V. (1975), „Kombinatorická věta v rovinné geometrii“, 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), „Přesný algoritmus pro minimalizaci stráží vrcholů v galeriích“, Mezinárodní transakce v operačním výzkumu, 18 (4): 425–448, doi:10.1111 / j.1475-3995.2011.00804.x.
  • Couto, M .; de Rezende, P .; de Souza, C. (2011), Srovnávací instance pro problém s uměleckou galerií s ochranami vrcholů.
  • Deshpande, Ajay; Kim, Taejung; Demaine, Erik D.; Sarma, Sanjay E. (2007), „Pseudopolynomiální čas O (logn) - aproximační algoritmus pro problémy umělecké galerie“, Proc. Worksh. Algoritmy a datové struktury, Přednášky v informatice, 4619, Springer-Verlag, str. 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), „Výsledky nepřístupnosti pro střežení polygonů a terénů“ (PDF), Algorithmica, 31 (1): 79–113, doi:10.1007 / s00453-001-0040-8, archivovány z originál (PDF) dne 24. 6. 2003.
  • Fisk, S. (1978), „Krátký důkaz Chvátalovy hlídací věty“, Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016 / 0095-8956 (78) 90059-X.
  • Ghosh, S. K. (1987), "Aproximační algoritmy pro problémy umělecké galerie", Proc. Kanadský kongres společnosti pro zpracování informací, str. 429–434.
  • Kahn, J .; Klawe, M.; Kleitman, D. (1983), „Tradiční galerie vyžadují méně strážných“, SIAM J. Algebr. Diskrétní metody, 4 (2): 194–206, doi:10.1137/0604020.
  • Kooshesh, A. A .; Moret, B. M. E. (1992), „Tři zbarvení vrcholů trojúhelníkového jednoduchého mnohoúhelníku“, Rozpoznávání vzorů, 25 (4): 443, doi:10.1016 / 0031-3203 (92) 90093-X.
  • Krohn, Erik A .; Nilsson, Bengt J. (2013), „Přibližná ochrana monotónních a přímých polygonů“, Algorithmica, 66 (3): 564–594, doi:10.1007 / s00453-012-9653-3, hdl:2043/11487, PAN  3044626.
  • Lee, D. T.; Lin, A. K. (1986), „Výpočetní složitost problémů umělecké galerie“, Transakce IEEE na teorii informací, 32 (2): 276–282, doi:10.1109 / TIT.1986.1057165.
  • Lubiw, A. (1985), „Rozklad polygonálních oblastí na konvexní čtyřúhelníky“, Proc. 1. ACM Symposium on Computational Geometry, str. 97–106, doi:10.1145/323233.323247, ISBN  0-89791-163-6.
  • O'Rourke, Josephe (1987), Věty a algoritmy umělecké galerie, Oxford University Press, ISBN  0-19-503965-3.
  • O'Rourke, Josephe; Supowit, Kenneth J. (1983), „Some NP-hard polygon decomposition problems“, Transakce IEEE na teorii informací, 29 (2): 181–190, doi:10.1109 / TIT.1983.1056648, PAN  0712374.
  • Sack, J. R.; Toussaint, G. T. (1988), "Umístění stráží v přímých polygonech", v Toussaint, G. T. (vyd.), Výpočetní morfologie, Severní Holandsko, str. 153–176.
  • Shermer, Thomas (1992), „Nedávné výsledky v galeriích umění“ (PDF), Sborník IEEE, 80 (9): 1384–1399, doi:10.1109/5.163407.
  • Valtr, P. (1998), „Strážné galerie, kde žádný bod nevidí malou oblast“, Israel J. Math., 104 (1): 1–16, doi:10.1007 / BF02897056.