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  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

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  ő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. Chvátal nem sokkal később elvégezte a bizonyítást. 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.

Fisk rövid bizonyítása 

 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
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. 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.

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

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. 
Az őrök minimális számát közelítési algoritmusokkal való becsléséről  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. Ahogy  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.
Ha az őrök bárhol elhelyezkedhetnek, a végtelen számú potenciális őrhely a problémát még nehezebbé teszi.

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.
 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.
 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  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.

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.

Jegyzetek

Források
.
.
.
.
.
.
.
 .
.
.
.
.
.
.
.
.
.
.

Számítási geometria
Sokszögek
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-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 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 ő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átalnakban . Chvátal nem sokkal később elvégezte a bizonyítást . Chvátal bizonyítását később Steve Fisk egyszerűsítetteszínnel színezési meggondolások segítségével . Fisk rövid bizonyítása 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 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 . 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 . 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ő . 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 . Az őrök minimális számát közelítési algoritmusokkal való becsléséről 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 . Ahogy 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 . Ha az őrök bárhol elhelyezkedhetnek , a végtelen számú potenciális őrhely a problémát még nehezebbé teszi . 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. 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. 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 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 . 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 . Jegyzetek Források . . . . . . . \ . . . . . . . . . . . Számítási geometria Sokszögek