Képtárprobléma

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

A művészeti galé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 halmazáról akkor mondjuk, hogy őrzi a sokszöget, ha a sokszög minden pontjához tartozik olyan , amire a és között húzott szakasz a sokszögön belül található.

Két dimenziós eset[szerkesztés]

Ehhez a galériához 4 kamerára van szükség

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[szerkesztés]

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 őr mindig elegendő, néha pedig szükséges egy 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[szerkesztés]

Egy háromszögelt sokszög színezése 3 színnel. A kék csúcsok alkotják a három őr halmazát, ami a művészeti galéria tétel által garantált legkevesebb számú őr. Ebben az esetben a halmaz nem optimális: ennek a sokszögnek az őrzéséhez két őr is elegendő lenne.

(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 őrrel.

Általánosítások[szerkesztés]

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 ő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”): 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[szerkesztés]

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 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ó[szerkesztés]

Példa olyan poliéderre, melynek egyes belső pontjai nem láthatók egyik csúcsból sem.

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[szerkesztés]