Képtárprobléma

A művészetigaléria-probléma vagy képtárprobléma (art gallery problem/museum problem) a számítási geometria egy jól tanulmányozott láthatósági problémája.

A probléma ihletője a valós életből vett feladat; minimálisan hány őr (360°-os kamera) szükséges egy múzeum őrzéséhez úgy, hogy az őrök egyszerre belássák az épület egészét. A feladat számítási geometriai átfogalmazásában a múzeumot egyszerű sokszög reprezentálja, az őrök pedig a sokszögön belül elhelyezkedő pontok. Pontok ${\displaystyle H}$ halmazáról akkor mondjuk, hogy őrzi a sokszöget, ha a sokszög minden ${\displaystyle p}$ pontjához tartozik olyan ${\displaystyle q\in H}$, amire a ${\displaystyle p}$ és ${\displaystyle q}$ között húzott szakasz a sokszögön belül található.

Két dimenziós eset

Az eredeti problémafelvetésnek számos variációja létezik. Egyes változatokban az őrök csak a sokszög élein helyezkedhetnek el, még szigorúbb verziókban a csúcsokra vannak száműzve. Egyes változatok csak azt követelik meg, hogy a sokszög egy részhalmazát, vagy éleit őrizzék.

A változat, amikor az őröket a csúcsokra kell helyezni és csak a csúcsokat kell őrizniük, ekvivalens a sokszög láthatósági gráfja domináló halmazának megkeresésével.

Chvátal művészeti galéria tétele

Chvátal művészeti galéria tétele (Václav Chvátalról) felső korlátot ad az őrök minimális számára. Kimondja, hogy ${\displaystyle \left\lfloor n/3\right\rfloor }$ őr mindig elegendő, néha pedig szükséges egy ${\displaystyle n}$ csúcsú sokszög őrzéséhez.

A kérdést, hogy hány őrre van szükség, Victor Klee tette fel Chvátalnak 1973-ban.^[1] Chvátal nem sokkal később elvégezte a bizonyítást.^[2] Chvátal bizonyítását később Steve Fisk egyszerűsítette 3 színnel színezési meggondolások segítségével.^[3]

Fisk rövid bizonyítása

(Fisk 1978) a következőképpen bizonyítja a képtártételt.

Először háromszögeljük a sokszöget (új csúcsok hozzáadása nélkül). A sokszög csúcsait ezután három színnel kiszínezzük, úgy, hogy minden háromszög mind a három színt tartalmazza. Ennek eléréséhez vegyük észre, hogí háromszögelt gráf duálisa (itt az az irányítatlan gráf, amiben az eredeti gráf minden háromszögéhez egy csúcsot rendelünk, éllel pedig a szomszédos háromszögeket jelképező csúcsokat kötjük össze) egy fa, hiszen a duális gráf bármely köre a sokszögben egy lyuk határát alkotná, ami ellentmondana a feltételezésnek, hogy nem tartalmaz lyukakat. Ha egynél több háromszögünk van, a duális gráf (mint minden fa) rendelkezik olyan csúccsal, aminek csak egy szomszédja van, ami egy olyan háromszögnek felel meg, ami csak egy háromszöggel szomszédos. Az ennek a háromszögnek az eltávolításával kapott egyszerűbb sokszög teljes indukcióval igazolhatóan színezhető három színnel, majd a színezés egyszerűen kiterjeszthető az eltávolított háromszög plusz egy csúcsára.

Ha a három színnel színezés előállt, az azonos színű csúcsok mindhárom szín esetében érvényes őrhalmazt alkotnak, mivel a sokszög bármely háromszögét őrzi valamely színű csúcs. Mivel a három szín particionálja a sokszög n csúcsát, a legkevesebb csúcshoz rendelt szín érvényes őrhalmazt alkotnak, legfeljebb ${\displaystyle \lfloor n/3\rfloor }$ őrrel.

Általánosítások

Chvátal felső korlátja érvényes marad akkor is, ha az őrök bármely, a sokszög belsejében lévő ponton is tartózkodhatnak.

Az eredeti képtárproblémának számos általánosítása és speciális esete létezik.^[4] Például a derékszögű sokszögek esetében mindössze ${\displaystyle \lfloor n/4\rfloor }$ őrre van szükség. Ennek az eredménynek legalább három különböző bizonyítása ismert, egyik sem egyszerű: Kahn, Klawe és Kleitman által; Lubiw által; Sack és Toussaint által.^[5]

Egy kapcsolódó probléma, hogy hány őrre van szükség egy tetszőleges sokszög külsejének őrzéséhez (az „erődprobléma”): ${\displaystyle \lceil n/2\rceil }$ néha szükséges és mindig elegendő. Más szavakkal, a végtelen külső tartomány problémásabb, mint a véges belső.^[6]

Számítási bonyolultság

A képtárprobléma eldöntési problémaváltozataiban a bemenet egy sokszög és egy k szám, az algoritmusnak pedig el kell döntenie, hogy a sokszög őrizhető-e k vagy kevesebb őr segítségével. Ez a probléma és standard változatai (mint pl. az őr helyének csúcsokra vagy élekre való korlátozása) mind NP-nehezek.^[7] Az őrök minimális számát közelítési algoritmusokkal való becsléséről (Eidenbenz, Stamm & Widmayer 2001) bizonyította, hogy APX-nehéz, rámutatva, hogy valószínűtlen, hogy egy polinomiális idejű közelítési algoritmussal valamely fix konstansú közelítési aránynál jobbat ki lehet hozni. Konstans approximációs arányt azonban nem ismerünk. Ehelyett, logaritmikus approximáció használható a minimális csúcs-őrzők esetére a probléma a fedőhalmaz-problémára való visszavezetésével.^[8] Ahogy (Valtr 1998) megmutatta, a képtárproblémából kapott halmazrendszer VC-dimenziója korlátos, ami miatt lehetővé válik az epszilon-hálók alkalmazása (melyek approximációs aránya az őrök optimális számának logaritmusa) a sokszög csúcsainak száma helyett.^[9] Ha az őrök bárhol elhelyezkedhetnek, a végtelen számú potenciális őrhely a problémát még nehezebbé teszi.^[10]

Léteznek azonban hatékony algoritmusok a legfeljebb ${\displaystyle \left\lfloor n/3\right\rfloor }$ csúcs-őr megtalálására, ami megfelel a Chvátal-féle felső korlátnak. David Avis and Godfried Toussaint (1981) igazolta, hogy az őrök elhelyezkedése a legrosszabb esetben O(n log n) időben kiszámolható egy oszd meg és uralkodj algoritmus segítségével. (Kooshesh & Moret 1992) megadott egy lineáris idejű algoritmust Fisk rövid bizonyításának és Bernard Chazelle lineáris idejű síkháromszögelési algoritmusának felhasználásával.

Egzakt algoritmust csúcsban elhelyezkedő őrök esetére (Couto, de Rezende & de Souza 2011) adott. A szerzők kiterjedt számítási kísérleteket végeztek sokszögek különböző osztályaira, megmutatva, még több ezer csúcspontú sokszögek esetében is viszonylag alacsony számítási idővel el lehet érni az optimális megoldásig. A bemeneti adatok és a hozzájuk tartozó optimális megoldások letölthetők.^[11]

Három dimenzió

Ha a múzeumot három dimenzióban tekintjük poliéderként, akkor az őrök csúcsokba állításával nem mindig garantálható a teljes múzeum megfigyelése. Bár a poliéder teljes felszínét figyelik az őrök, némelyik poliéderben léteznek olyan belső pontok, melyek nem láthatók egyik csúcsból sem.^[12]

Jegyzetek

Források

• Aggarwal, A. (1984), The art gallery theorem: Its variations, applications, and algorithmic aspects, Ph.D. thesis, Johns Hopkins University.
• Avis, D. & Toussaint, G. T. (1981), "An efficient algorithm for decomposing a polygon into star-shaped polygons", Pattern Recognition 13 (6): 395–398, doi:10.1016/0031-3203(81)90002-9, <http://cgm.cs.mcgill.ca/~godfried/publications/star.pdf>.
• Brönnimann, H. & Goodrich, M. T. (1995), "Almost optimal set covers in finite VC-dimension", Discrete and Computational Geometry 14 (1): 463–479, DOI 10.1007/BF02570718.
• Chvátal, V. (1975), "A combinatorial theorem in plane geometry", 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), "An exact algorithm for minimizing vertex guards on art galleries", International Transactions in Operational Research: no–no, DOI 10.1111/j.1475-3995.2011.00804.x.
• Couto, M.; de Rezende, P. & de Souza, C. (2011), Benchmark instances for the art gallery problem with vertex guards, <http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/>.
• Deshpande, Ajay; Kim, Taejung & Demaine, Erik D. et al. (2007), "A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems", Proc. Worksh. Algorithms and Data Structures, vol. 4619, Lecture Notes in Computer Science, Springer-Verlag, pp. 163–174, ISBN 978-3-540-73948-7, DOI 10.1007/978-3-540-73951-7_15.
• Eidenbenz, S.; Stamm, C. & Widmayer, P. (2001), "Inapproximability results for guarding polygons and terrains", Algorithmica 31 (1): 79–113, doi:10.1007/s00453-001-0040-8, <http://www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf>. Hozzáférés ideje: 2010-03-15 Archiválva 2003. június 24-i dátummal a Wayback Machine-ben.
• Fisk, S. (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B 24 (3): 374, DOI 10.1016/0095-8956(78)90059-X.
• Ghosh, S. K. (1987), "Approximation algorithms for art gallery problems", Proc. Canadian Information Processing Society Congress, pp. 429–434.
• Kahn, J.; Klawe, M. & Kleitman, D. (1983), "Traditional galleries require fewer watchmen", SIAM J. Alg. Disc. Meth. 4 (2): 194–206, DOI 10.1137/0604020.
• Kooshesh, A. A. & Moret, B. M. E. (1992), "Three-coloring the vertices of a triangulated simple polygon", Pattern Recognition 25 (4): 443, DOI 10.1016/0031-3203(92)90093-X.
• Lee, D. T. & Lin, A. K. (1986), "Computational complexity of art gallery problems", IEEE Transactions on Information Theory 32 (2): 276–282, DOI 10.1109/TIT.1986.1057165.
• Lubiw, A. (1985), "Decomposing polygonal regions into convex quadrilaterals", Proc. 1st ACM Symposium on Computational Geometry, pp. 97–106, ISBN 0-89791-163-6, DOI 10.1145/323233.323247.
• O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, Oxford University Press, ISBN 0-19-503965-3, <http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html>.
• Sack, J. R. & Toussaint, G. T. (1988), "Guard placement in rectilinear polygons", in Toussaint, G. T., Computational Morphology, North-Holland, pp. 153–176.
• Shermer, Thomas (1992), "Recent Results in Art Galleries", Proceedings of the IEEE 80 (9): 1384–1399, doi:10.1109/5.163407, <http://www.cs.ubc.ca/nest/theory/thread/papers/shermer2002.pdf>.
• Valtr, P. (1998), "Guarding galleries where no point sees a small area", Israel J. Math. 104 (1): 1–16, DOI 10.1007/BF02897056.