Művészeti galéria probléma

A számítógép-tudomány , pontosabban algoritmikus geometria , a probléma a művészeti galéria egy jól tanulmányozott látási probléma ihlette egy valós probléma. A következőképpen van megfogalmazva:

- Hány őrre van szükség egy művészeti galéria őrzéséhez , és hova kell őket helyezni? "

Formálisan a művészeti galériát egy egyszerű sokszög , az egyes gyámokat pedig a sokszög egy pontja képviseli. Egy sor pont azt mondta, hogy figyelemmel kíséri , vagy fedezze sokszög, ha bármely pontja a sokszög, van egy pont olyan, hogy a vonal szegmens belép , és teljes mértékben tartalmazza a sokszög. Az őröket térfigyelő kameraként is értelmezhetjük, és kérhetjük, hogy az egész galéria látható legyen a szkennelés során. $S$ $o$ ${\ displaystyle q \ S-ben}$ $o$ $q$

A művészeti galéria tétele

A művészeti galéria tétele, amelyet Václav Chvátal demonstrált , felső korlátot ad a gyámok minimális számához. Mondja :

"Egy egyszerű sokszög csúcsokkal történő megtartásához elegendőek az őrök, és ez a határ elérhető

nem

{\ displaystyle \ lfloor n / 3 \ rfloor}

. "

Történelmi

A szükséges kapusok számával kapcsolatos kérdést Victor Klee tette fel Chvátal számára 1973-ban. Chvátal hamarosan bebizonyította. Chvátal igazolását Steve Fisk egyszerűsítette, a gráf színezésén alapuló argumentummal . Fisk a matematika professzora volt a Bowdoin Főiskolán .

A művészeti galéria problémája és tétele kevésbé ismert, mint a szokásos algoritmikus geometriai témák, mint például a domború burkolás , a sokszög háromszögelése vagy a Voronoi diagram kiszámítása , de különféle algoritmikus geometria tankönyvekben és tanfolyamokban szerepel.

A Fisk bemutatója

Steve Fisk igazolása rövid és elegáns: megjelenik az Isteni okoskodás könyvben . A bizonyítás többnyire a következő. Kezdjük a sokszög háromszögelésével (új csúcsok hozzáadása nélkül). A háromszögeléshez hasonlóan járunk el: Azt a tényt használjuk, hogy minden egyszerű, legalább négy csúcsú sokszögnek legalább két „füle” van. A fül egy háromszög, amelynek két éle a sokszög határához tartozik, a harmadik pedig a sokszög belsejében helyezkedik el. Az algoritmus abból áll, hogy megtalálunk egy ilyen fület, eltávolítjuk azt a sokszögből, ami új, kisebb sokszöget eredményez, ezért háromszor színezhető megismétlődéssel , és ez a színezés könnyen kiterjeszthető a fül további csúcsának a maradék színnel történő színezésével. Három színű színezésnél minden háromszögnek mind a három színnek tartalmaznia kell. Az egyik szín csúcsa érvényes őrzőkészletet képez, mivel a sokszög minden háromszögét az adott színű csúcsa őrzi. Mivel a három szín felosztja a sokszög n csúcsát, a legkevesebb csúcsú szín meghatározza az érvényes, legfeljebb gyámokkal rendelkező gyámok halmazát . ${\ displaystyle \ lfloor n / 3 \ rfloor}$

Változatok

A Chvátal felár akkor marad érvényben, ha a csúcson lévő állattartók korlátozása gyengül az állattartókra bármely olyan ponton, amely nincs a sokszögön kívül.

Az általános művészeti galéria tételnek vannak más általánosításai vagy specializációi. Például az ortogonális sokszögekhez, vagyis azokhoz a sokszögekhez, amelyek oldalai derékszögben csatlakoznak, csak az őrökre van szükség . Ennek az eredménynek legalább három különböző bemutatója van, egyik sem egyszerű, egyet Kahn, Maria Klawe és Daniel Kleitman ; egy másik Anna Lubiw ; és még egyet Jörg-Rüdiger Sack és Godfried Toussaint (en) . ${\ displaystyle \ lfloor n / 4 \ rfloor}$

Hasonló probléma a poligon külsejének lefedéséhez szükséges védőburkolatok minimális számának meghatározása (ez a „várprobléma”): elegendőek és néha szükségesek is. Más szavakkal, a végtelen külső burkolása igényesebb, mint a kész belső burkolása. $\ lceil n / 2 \ rceil$

Algoritmikus összetettség

A számítási probléma

Hatékony algoritmusok léteznek a sokszög csúcsain elhelyezett, és a Chvátal jelölést igazoló, és ennélfogva legfeljebb gyámok őrcsoportjainak megtalálásához. ${\ displaystyle \ lfloor n / 3 \ rfloor}$

David Avis és Godfried Toussaint bebizonyította, hogy egy ilyen elhelyezés a legrosszabb esetként számolható el , oszd meg és hódítsd módszerrel . Kooshesh és Moret 1992 egy lineáris időalgoritmust adott Fisk bizonyító algoritmusával és Bernard Chazelle lineáris háromszögelési algoritmusával . $O (n \ log n)$

Számítási algoritmust javasolt Couto, de Rezende és de Souza 2011 a csúcsra helyezett kapusok számára. A szerzők számos tesztet végeztek különböző sokszögosztályokkal, amelyek azt mutatták, hogy optimális megoldások viszonylag rövid idő alatt megtalálhatók a több ezer csúcsú sokszögek esetében is.

A döntési probléma

Döntési problémának tekintve a művészeti galéria problémája annak meghatározása, hogy egy sokszöget és egy k egész számot figyelembe véve , hogy ez a sokszög legfeljebb k őrzővel tartható-e . Ez a probléma -teljes , hol van a komplexitás osztálya, amely megfelel a zárt valós testek elméletének egzisztenciális töredékének . A szokásos variációk (például az őrző pozícióinak korlátozása a sokszög csúcsaira vagy széleire) NP-nehézek . ${\ displaystyle \ létezik \ mathbb {R}}$ ${\ displaystyle \ létezik \ mathbb {R}}$

Közelítés

A gyámok minimális számának közelítő algoritmusát illetően Eidenbenz, Stamm és Widmayer 2001 kimutatták, hogy a probléma nehéz APX ; Ez azt jelenti, hogy nem valószínű, hogy a közelítő arány jobb, mint egy fix konstans lehet elérni egy közelítő algoritmus a polinomiális időben . Nem ismert azonban állandó közelítési arányú algoritmus. Ezzel szemben a gondnokok minimális számának logaritmikus közelítése úgy érhető el, hogy a problémát a beállított lefedettségi problémára redukáljuk . Pavel Valtr megmutatta, hogy a művészeti galéria problémájából levezetett halmazrendszer korlátozott Vapnik-Tchervonenkis dimenzióval rendelkezik , amely lehetővé teszi olyan ε-hálózatokon (en) alapuló halmaz lefedettségi algoritmusok alkalmazását, amelyek közelítési aránya az optimális logaritmusa inkább a gyámok száma, mint a sokszög csúcsainak száma. A kapusok helyzetének korlátozása nélkül a potenciálisan végtelen számú helyzet még nehezebbé teszi a problémát. Ha arra kényszerítjük a gyámokat, hogy foglaljanak helyet egy finom rácson, bonyolultabb logaritmikus közelítési algoritmus nyerhető további alacsony korlátozású feltételezések mellett.

Kiváló méretek

Ha a múzeumot nagyobb dimenzióban egy poliéder képviseli , akkor nem biztos, hogy elegendő minden csúcson őrt elhelyezni, hogy lefedje a teljes múzeumot. Még akkor is, ha a poliéder felületei megfigyelés alatt állnak, lehetséges, hogy a poliéder belsejében lévő pontok nem láthatók.

Megjegyzések

O'Rourke 1987 , p. 1.
Chvátal 1975 .
Fisk 1978 .
Leghorn, " Matematika professzor 63 évesen meghal leukémiában " [ archív du2017. január 14] , The Bowdoin Orient,2010.
Berg és mtsai. 2008 .
Castelli Aleardi és Oudot 2012 .
Boissonnat 2017 .
Goodman és O'Rourke 2004 .
Edelsbrunner 1987 .
Pach és Agarwal 1995 .
Mehlhorn és Naeher 1999 .
Fisk 1978 .
Isteni okok , 35. fejezet: "Hogyan nézzünk meg egy múzeumot".
Shermer 1992 .
O'Rourke 1987 , p. 37-80, Kahn, Klawe és Kleitman 1983 , Lubiw 1985 és Sack és Toussaint 1988 .
O'Rourke 1987 , p. 146-154.
Avis és Toussaint 1981 .
. Ezekre a tesztekre vonatkozó adatok és megoldások a Couto, de Rezende és de Souza 2011 címen érhetők el .
Abrahamsen, Adamaszek és Miltzow 2017 .
O'Rourke 1987 , p. 239–242; Aggarwal 1984 ; Lee és Lin 1986 .
Kumar Ghosh 2010 .
Valtr 1998 .
Brönnimann és Goodrich 1995 .
Deshpande és mtsai. 2007
Bonnet és Miltzow 2017 .
O'Rourke 1987 , p. 255.

Hivatkozások

Könyvek

Joseph O'Rourke, Művészeti Galéria tételei és algoritmusai , Oxford University Press ,1987( ISBN 0-19-503965-3 , online olvasás ).
Mark de Berg, Otfried Cheong, Marc van Kreveld és Mark Overmars , Számítási geometria: algoritmusok és alkalmazások , Springer Verlag ,2008, 3 e . , 386 p. ( ISBN 978-3-540-65620-3 és 3-540-65620-0 , online előadás , online olvasás ) , fej . 3. („Sokszög háromszögelés”), p. 45-61.
Luca Castelli Aleardi és Steve Oudot, Bevezetés a számítási geometriába és alkalmazásaiba , École polytechnique de Paris, coll. "INF562 tanfolyam",2012, 123. o. ( online olvasás ).
Jean-Daniel Boissonnat, Algoritmikus geometria: a geometriai adatoktól az adatgeometriáig : A tanfolyam kezdő órája, Párizs, Librairie Arthème Fayard és Collège de France,2017, 73 p. ( ISBN 978-2-213-70765-5 és 978-2-213-70512-5 , online olvasás ).
Jacob E. Goodman és Joseph O'Rourke (szerk.), A diszkrét és számítási geometria kézikönyve , CRC Press,2004, 2 nd ed. ( ISBN 1-58488-301-4 ).
en) Herbert Edelsbrunner, Algoritmusok a kombinatorikus geometriában , Berlin / Heidelberg / Párizs stb., Springer-Verlag , coll. "EATCS Monographs on Theoretical Computer Science" ( n o 10),1987, 423 p. ( ISBN 3-540-13722-X , online olvasás ).
en) Pach János és Pankaj K. Agarwal, kombinatorikus geometria , New York / Chichester / Brisbane stb., John Wiley & Sons ,1995, 354 p. ( ISBN 0-471-58890-3 ).
(en) Pach János és Micha Sharir, kombinatorikus geometria és algoritmikus alkalmazásai: The Alcala Lectures , Providence, RI, American Mathematical Society, coll. "Matematikai felmérések és Monographs" ( n o 152)2009, 235 p. ( ISBN 978-0-8218-4691-9 , online olvasás ).
en) Kurt Mehlhorn és Stefan Naeher, a LEDA, a kombinatorikus és geometriai számítástechnika platformja , Cambridge, Cambridge University Press ,1999, 1018 p. ( ISBN 0-521-56329-1 , online olvasás ).

Cikkek

Mikkel Abrahamsen, Anna Adamaszek és Tillmann Miltzow „ The Art Gallery Probléma -teljes ${\ displaystyle \ létezik \ mathbb {R}}$ ” preprint (arXiv) ,2017( arXiv 1704.06969 ).
Alok Aggarwal, A művészeti galéria tétele: Változatai, alkalmazásai és algoritmikus aspektusai (Ph.D. értekezés), Johns Hopkins Egyetem,1984.
David Avis és Godfried T. Toussaint, „ Hatékony algoritmus a sokszög csillag alakú sokszögekké bontására ”, Pattern Recognition , vol. 13, n o 6,tizenkilenc nyolcvan egy, P. 395–398 ( DOI 10.1016 / 0031-3203 (81) 90002-9 , online olvasás ).
Édouard Bonnet és Tillmann Miltzow, „ A művészeti galéria problémájának közelítő algoritmusa ”, Szimpózium a számítási geometriáról ,2017, P. 20: 1-20: 15, cikk n o 20 ( arXiv 1.607,05527 , olvasható online ).
Hervé Brönnimann és Michael T. Goodrich, „ Majdnem optimális burkolatok a véges VC-dimenzióban ”, Diszkrét és számítási geometria , vol. 14, n o 1,1995, P. 463–479 ( DOI 10.1007 / BF02570718 ).
Václav Chvátal, „ A kombinatorikus tétel a síkgeometriában ”, Journal of Combinatorial Theory, B sorozat , vol. 18,1975, P. 39–41 ( DOI 10.1016 / 0095-8956 (75) 90061–1 ).
Marcelo C. Couto , Pedro J. de Rezende és Cid C. de Souza , „ Pontos algoritmus a művészeti galériák csúcsvédőinek minimalizálására ”, Nemzetközi tranzakciók az operatív kutatásban , vol. 18, n o 4,2011, P. 425–448 ( DOI 10.1111 / j.1475-3995.2011.00804.x ).
Marcelo C. Couto , Pedro J. de Rezende és Cid C. de Souza , a műcsarnok problémájának összehasonlító példái a csúcsvédőkkel ,2011( online olvasás ).
Ajay Deshpande, Taejung Kim, Erik Demaine és Sanjay E. Sarma, „A pseudopolynomial Time O (logn) -Aproximation Algorithm for Art Gallery Problems” , Proc. Műhely-algoritmusok és adatszerkezetek , Springer-Verlag, koll. "Lecture Notes in Computer Science" ( n o 4619),2007( ISBN 978-3-540-73948-7 , DOI 10.1007 / 978-3-540-73951-7_15 ) , p. 163–174.
.
Steve Fisk, „ A Chvátal őrszemének tételének rövid bizonyítása ”, Journal of Combinatorial Theory, B sorozat , vol. 24, n o 3,1978, P. 374 ( DOI 10.1016 / 0095-8956 (78) 90059-X ).
Subir Kumar Ghosh, „ Approximation algorithms for art gallery problems in polygons ”, Diszkrét alkalmazott matematika , 1. évf. 158, n o 6,2010, P. 718-722.
J. Kahn, Maria M. Klawe és Daniel J. Kleitman: „A hagyományos galériákhoz kevesebb őrre van szükség ”, SIAM J. Alg. Lemez. Meth. , vol. 4, n o 21983, P. 194–206 ( DOI 10.1137 / 0604020 ).
Ali A. Kooshesh és Bernard ME Moret, „ Egy háromszög alakú egyszerű sokszög csúcsainak háromszínezése ”, Pattern Recognition , vol. 25, n o 4,1992, P. 443 ( DOI 10.1016 / 0031-3203 (92) 90093-X ).
Der-Tsai Lee és AK Lin, „ A művészeti galéria problémáinak számítási bonyolultsága ”, IEEE Transaction on Information Theory , vol. 32, n o 21986, P. 276–282 ( DOI 10.1109 / TIT.1986.1057165 ).
Anna Lubiw: „A sokszögű régiók konvex négyszögekre bomlása” , Proc. 1. ACM szimpózium a számítási geometriáról ,1985( ISBN 0-89791-163-6 , DOI 10.1145 / 323233.323247 ) , p. 97–106.

Jörg-Rüdiger Sack és Godfried Toussaint, „Gárda elhelyezése egyenes vonalú sokszögekben” , Godfried Toussaint (szerkesztő), Számítási morfológia , Észak-Holland,1988, P. 153–176.
Thomas Shermer, „ Legutóbbi eredmények a művészeti galériákban ”, Proceedings of the IEEE , vol. 80, n o 9,1992, P. 1384–1399 ( DOI 10.1109 / 5.163407 , online olvasás ).
Pavel Valtr, „Olyan galériák őrzése, ahol nincs értelme egy kis területnek ”, Israel J. Math. , vol. 104, n o 1,1998, P. 1–16 ( DOI 10.1007 / BF02897056 ).

Kapcsolódó cikkek