PROBLEM UMETNOSTNE GALERIJE
ALEKSANDRA FRANC
Fakulteta za računalništvo in informatiko Univerza v Ljubljani
Math. Subj. Class. (2010): 52B55, 55R05
Predstavimo Kleejev problem umetnostne galerije in Fiskovo elegantno reSitev. Nato si ogledamo stevilne zanimive izpeljanke in končamo s sorodnim in trenutno se neresenim problemom vsiljivca.
ART GALLERY PROBLEM
Klee's art gallery problem and Fisk's elegant solution are presented. We then explore several variations on the original problem and conclude with a somewhat related and currently unsolved Evasion Problem.
Uvod
Probleme, ki si jih bomo ogledali, bi lahko motivirali s pripovedko o rav-barjih, ki ž elijo s plenom pobegniti na varno, in ž andarjih, ki jih želijo pri tem ujeti. Mi se bomo seveda postavili na stran pravice, ampak da ne bo vse skupaj prevec suhoparno, bomo raje ostali zvesti zgodovinskim formulacijam, tako da bodo ž andarje enkrat zamenjali pazniki, drugic pa vitezi ali senzorji. Le nepridipravi bodo ostali nepridipravi, in v zadnjem primeru bomo za trenutek sami prestopili na temno stran.
Najprej si oglejmo problem, ki se je znasel v naslovu tega clanka in ki je bil tudi zgodovinsko prvi.
Denimo, da moramo v prostore na sliki 1 namestiti paznike tako, da bodo lahko nadzorovali prav vsako točko. Pazniki vidijo 360° okoli sebe (lahko se vrtijo na mestu), ne morejo pa videti skozi zidove, prav tako pa se ne smejo sprehajati naokrog. Vsak paznik nas nekaj stane, zato jih seveda zelimo najeti cim manj.
Hitro opazimo, da lahko drugi prostor nadzorujemo z enim samim spretno postavljenim paznikom, medtem ko sta za vsakega od preostalih dveh prostorov potrebna po dva. Kaj pa, ce so tlorisi prostorov, ki jih zelimo nadzorovati, se bolj zapleteni?
Naslednji problem je avgusta leta 1973 na konferenci v Stanfordu zastavil ameriski matematik Victor Klee [7]:
Problem 1. Tloris umetnostne galerije ima obliko (ravninskega) mnogoko-tnika z n oglišči. Najmanj koliko paznikov potrebujemo, da bo vsako točko v galeriji nadziral vsaj eden?
Obzornik mat. fiz. 61 (2014) 5
161
Aleksandra Franc
(a)
(b)
(c)
Slika 1. Kam naj postavimo paznike, Ce želimo nadzorovati ves prostor, pri tem pa uporabiti cim manj paznikov?
V osnovni različici problema pazniki ves čas stojijo vsak na svojem mestu in vidijo 360° okoli sebe. Na sliki 2 sta dva primera postavitve, pri čemer smo vsakič osenčili območje, ki ga paznik nadzira.
Za začetek predpostavimo se, da galerija nima notranjih dvorisč. Tedaj je mnogokotnik, ki predstavlja tloris galerije, enostavno povezan, tj. brez lukenj. V splosnem bo odgovor močno odvisen od geometrije tlorisa, ampak problem nas spras uje po zgornji meji za stevilo paznikov, ki bodo zagotovo lahko nadzirali vso galerijo. Zelimo torej univerzalni odgovor, ki bo odvisen le od stevila ogli sč. Seveda bo včasih, ko bo geometrija prostora dovolj lepa, dovolj ze manj paznikov.
Naloga 1. Na sliki 1 označi, kam moramo postaviti paznike.
Naloga 2. Narisi tloris galerije, ki ima 8 oglisč, pa jo vseeno lahko nadzorujemo z enim samim paznikom. Nato narisi se tloris galerije z 8 oglisči, za katero nujno potrebujemo vsaj dva paznika.
162	Obzornik mat. fiz. 61 (2014) 5
Slika 2. Kaj vidi paznik?
Problem umetnostne galerije
Problem umetnostne galerije
Zadostno število paznikov dobimo tako, da število ogli šč delimo s 3 in rezultat zaokrožimo navzdol:
Izrek 1 (Problem umetnostne galerije). Za nadzor mnogokotnika z n oglišči brez lukenj vedno zadošča paznikov.
Zgornjo trditev je prvi dokazal Vašek Chvatal [2] leta 1975, leta 1978 pa je Steve Fisk [5] na š el kraj š i in nadvse eleganten dokaz, ki si ga bomo ogledali tudi mi.
Dokaz. Mnogokotnik najprej trianguliramo (da triangulacija obstaja, lahko pokaz emo z indukcijo na š tevilo ogli š č ), nato pa njegovih n ogli š č pobarvamo s tremi barvami (recimo rdečo, modro in zeleno) tako, da ima vsak trikotnik natanko eno oglišče vsake barve. Ce zelimo dokazati, da tako barvanje obstaja pri n > 4, se moramo najprej prepričati, da vsaj eden od trikotnikov v triangulačiji, označimo ga s T, vsebuje tri zaporedna oglišča mnogokotnika (in torej natanko dve straniči mnogokotnika in eno diagonalo). To ni čisto trivialno (glej [4, Corollary 1.9]). Nato lahko spet uporabimo indukčijo na število ogli šč, da konstruiramo iskano barvanje. Ce namreč izvzamemo tisto oglišče trikotnika T, ki pripada straničama, potem lahko preostala oglišča po indukčijski predpostavki pobarvamo s tremi barvami. Ker je to ogli šče povezano le z dvema sosednjima ogliščema, ga gotovo lahko pobarvamo s tretjo barvo (sosednji oglišči sta različnih barv, ker sta povezani z diagonalo).
Po Diričhletovem prinčipu zagotovo obstaja barva, ki ne more biti na več kot ogli ščih. Rečimo, da smo pri barvanju najmanjkrat uporabili rdečo. Ni tez ko videti, da tedaj zadošč a postaviti straz arje v rdeča ogli šča, pa bodo imeli pod nadzorom vso galerijo. Vsak trikotnik ima namreč vsaj eno rdeče ogli šče in iz tega ogli šča zagotovo vidimo ves trikotnik.	■
Slika 3. Fiskova rešitev: Paznike postavimo v oglišča, ki so pobarvana z najmanj pogosto barvo.
161-172	163
Aleksandra Franc
Ne smemo pozabiti, da je to samo zgornja meja in bo marsikdaj zadoščalo že manj paznikov. Na posameznih primerih lahko z nekaj spretnosti določimo minimalno stevilo paznikov, ki jih potrebujemo za nadzor celotnega mnogokotnika, in v nadaljevanju si bomo ogledali nekaj takih primerov. Omenimo se, da so algoritmi, ki bi določili minimalno stevilo paznikov za dani mnogokotnik, računsko zahtevni. Natančneje: Problem, ki za dani mnogokotnik M in dano stevilo k odloči, ali k paznikov zados č a za nadzor M, sodi med NP-tezke probleme. Ce bi nasli algoritem, ki bi ta problem res il v polinomskem času, bi s tem pokazali, da je P = NP in si prisluzili milijon dolarjev [3].
Naloga 3. Za prostora na sliki 4 poi s č i kaksno minimalno razporeditev paznikov.
Relativno enostavno pa se lahko prepričamo, daje zgornja meja iz izreka 1 v splosnem res najboljsa moz na. Na sliki 5 je primer poligona s 3n ogli s č i,
Slika 5. Primer mnogokotnika, za katerega je zgornja meja dosežena.
Seveda so v resničnem zivljenju prostori redko taki kot v tem ekstre-mnem primeru. Stene se običajno stikajo pravokotno. Ce se omejimo na n-kotnike, v katerih so vsi koti enaki 90° ali 270°, se izkaze, da vedno zado-s ča manj paznikov kot v posplo senem primeru. Naslednji izrek so dokazali Jeff Kahn, Maria Klawe in Daniel Kleitman [8] leta 1980.
164
Obzornik mat. fiz. 61 (2014) 5
Problem umetnostne galerije
Izrek 2 (Problem ortogonalne galerije). Za nadzor mnogokotnika z n oglišči, v katerem se nosilke zaporednih stranic sekajo pod pravim kotom, vedno zadošča paznikov.
Kaj pa, če paznikom dovolimo, da se sprehajajo naokrog? Denimo, da se lahko vsak od njih premika po enem od robov n-kotnika in ima pod nadzorom vse točke, ki jih lahko vidi z vsaj ene točke na tem robu. Jasno je, da bomo v tem primeru za popoln nadzor potrebovali manj paznikov, vendar natančna zgornja meja ni znana. Godfried Toussaint je postavil domnevo, da za velike n za nadzor poljubnega n-kotnika zadosča [jj paznikov (glej [4], str. 18, ali [9], 3. poglavje).
Naloga 4. Koliko potujočih paznikov bi potrebovali za nadzor galerije s slike 5?
Ker pa smo se paznikov z e malo navelič ali, jih lahko zamenjamo z modernimi svetlobnimi plosčami, ki celotno steno spremenijo v vir svetlobe, in se vprasamo, najmanj koliko takih plosč potrebujemo, da bomo lahko osvetlili celotno galerijo.
Domneva 1 (Toussaint). Za osvetlitev galerije potrebujemo svetlobnih sten.
Kaj pa, če stene galerije prekrijemo z ogledali? Ni znano, ali takrat zado s č a ze en sam točkast vir svetlobe (upo s tevamo, da velja odbojni zakon).
Naloga 5. Premislimo, kaj se zgodi, če ima galerija notranja dvorisča, ki imajo prav tako kot galerija obliko mnogokotnika. Poi s č i zgornjo mejo za stevilo paznikov, ki lahko nadzorujejo galerijo z n ogli s č i in h luknjami, če ves , da za triangulačijo take galerije potrebujemo n + 2h — 2 trikotnikov.
Naloga 6. Koliko vitezov potrebujemo, da bodo nadzorovali prav vsako toč ko grajskega obzidja, prikazanega na sliki 6 (ne pa nujno tudi grajskih dvori s č )? Koliko lokostrelčev moramo razporediti po zunanjem robu obzidja, da bodo nadzorovali vso okoličo gradu (zunaj obzidja)? Koliko lokostrelčev pa potrebujemo, če zelimo, da nadzorujejo tudi notranji dvorisči?
Prej s nja naloga nas je pripeljala do sorodnega problema, kjer zelimo namesto notranjosti nadzorovati zunanjost n-kotnika. V tem primeru poznamo natančno zgornjo mejo tudi pri nestačionarnih paznikih.
Problem trdnjave
Problem trdnjave sta neodvisno drug od drugega zastavila Deričk Wood in Joseph Malkelvitčh. Zanima nas, koliko strazarjev potrebujemo, da bodo nadzorovali zunanjost n-kotnika. O'Rourke in Wood sta leta 1983 pokazala,
161-172
165
Aleksandra Franc
Slika 6. Koliko vitezov potrebujemo, da bodo nadzorovali vsako tocko grajskega obzidja? Koliko lokostrelcev, da bodo nadzorovali vso okolico gradu?
da vedno zadošča paznikov in da vcasih manj paznikov ni dovolj (glej [9], 6. poglavje). Yiu in Choi [1] sta predlagala izpeljanko problema, kjer se vsak paznik lahko premika po enem od robov n-kotnika, in dokazala, da je v tem primeru natančna zgornja meja [']. Yiu [10] je nato oba problema posplosil:
Izrek 3 (Posplošeni problem trdnjave). Denimo, da lahko paznike postavljamo tako, da se vsak lahko premika po k — 1 zaporednih robovih n-
kotnika. Tedaj za nadzor zunanjosti n-kotnika vedno zadošča
kov.
k+1
pazni-
Posledica 4 (Problem trdnjave).
zadošča stacionarnih paznikov.
Za nadzor zunanjosti n-kotnika vedno
Naloga 7. Kaj nam posledica 4 pove za primer trdnjave s slike 6 v primeru stacionarnih lokostrelcev? Primerjaj oceno z natančnim rezultatom iz naloge 6. Koliko lokostrelcev pa potrebujemo pri k = 2, tj. ko se lahko vsak od njih premika vzdolz ene stranice? Primerjaj tocni odgovor z zgornjo mejo iz izreka 3.
Problem ubeZnika
Nazadnje si oglejmo se bolj realisticno verzijo problema, v kateri se pazniki lahko prosto premikajo po galeriji. V tem primeru bi seveda ze z enim samim paznikom lahko s primerno izbranim obhodom zagotovili, da bo vsaka tocka galerije pod nadzorom vsaj enkrat med obhodom. Vendar pa lahko v vsakem danem trenutku tudi pri uporabi vec mobilnih paznikov obstajajo obmocja, ki niso pod nadzorom.
Bodimo spet moderni in tokrat zamenjajmo paznike z mobilnimi senzorji, n-kotnik, ki je predstavljal galerijo, pa s poljubnim ravninskim obmo-cjem D. Denimo, da se senzorji premikajo po obmocju D in da lahko vsak
166
Obzornik mat. fiz. 61 (2014) 5
Problem umetnostne galerije
zazna vsiljivce, ki so od njega oddaljeni za največ d. Medtem ko bodo nasi senzorji potovali po območju D, bodo obstajali deli območja, ki ne bodo pod nadzorom. Ta nenadzorovana območja zeli izkoristiti nepridiprav, ki hoče pobegniti s plenom. Slika 7 prikazuje situačijo v nekem trenutku t. S časom se slika spreminja, osenčena območja se lahko zdruzujejo, lahko izginjajo ali pa nastajajo nova.
Slika 7. Ravninsko območje D s senzorji. Osenčena območja niso pokrita, v njih se lahko neopazen zadrZuje vsiljivec.
Nepridiprav je ob času 0 v točki x0, ki ni pod nadzorom, in zeli neopazen v času 1 priti do toč ke xi. Za vsak čas t € [0,1] naj bo Pt podmnoz iča območja D, kije v tem trenutku pokrita s senzorji, medtem ko je Nt = D\Pt nepokrito območje, v katerem je ob času t nas dolgoprsti kolega varen. Situačijo lahko predstavimo grafično, če os x predstavlja č asovno, osi y in z pa prostorski komponenti. Pri vsakem t € [0,1] nari semo v ravnini x = t območji Pt in Nt in tako dobimo prostor
D x [0,1] = |J (Pt U Nt). te[0,i]
Ker bo pomembna samo topoloska informačija, lahko sliko nekoliko poenostavimo. Območje D zamenjamo z diskom, prav tako pa tudi vsak kos nepokritega območja. Rezultat bo tedaj podoben kot v primeru na sliki 8.
Primer 1. Kot primer si oglejmo situačijo, prikazano na sliki 8. Ob času 0 imamo tri nepokrita območja. Ob času ti se prvi dve območji zdruzita v eno, ob času t2 iz tretjega območja nastaneta dve, ki se ob času t3 spet zdruzita. Ob času t4 se prvo od območij spet razdeli na dve, ampak ena od komponent ob času t6 izgine. Ob času t5 nastane novo nepokrito območje, ki obstane do konča. Ob času 1 imamo tako spet tri nepokrita območja, vendar je lahko vsiljiveč le v dveh izmed njih. Ce je bil na začetku varen v prvem ali drugem nepokritem območju, potem je lahko na konču neopazen v prvem območju, če pa je bil na začetku v tretjem območju, potem lahko konča v drugem. V tretjem končnem območju ne more biti, ne da bi ga vmes zaznali senzorji.
161-172
167
Aleksandra Franc
Slika 8. Grafični prikaz spreminjanja pokritosti s časom.
Med situacijama na slikah 7 in 8 je pomembna razlika. Na prvi sliki obstajajo nepokriti kosi na robu območja D, medtem ko je v vsakem trenutku t na drugi sliki rob dD vedno povsem pod nadzorom. V nadaljevanju bomo predpostavljali, da je rob dD vedno pod nadzorom senzorjev, tj. dD C Pt za vse t € [0,1].
Vin de Silva in Robert Grist [6] sta nasla preprost kriterij, ki nam pove, kdaj se vsiljivec zagotovo ne bo mogel izmuzniti.
Izrek 5. Ce obstaja topoločki disk B, ki v celoti lezi v pokritem območju, tj. B C Ute[0 1] Pt, z robom dB C dD x I, potem pobeg ni mogoč.
(a)	(b)
Slika 9. (a) Obstoj diska, ki v celoti leZi v nadzorovanem območju, nam pove, da vsiljivec ne more pobegniti. (b) Vsiljivec lahko pobegne po označeni poti.
Preprost primer, ko tak disk B obstaja, je prikazan na sliki 9(a), kjer očitno vsiljivec nima moznosti za pobeg, medtem ko lahko na sliki 9(b) vsiljivec pobegne po označeni poti.
Poudariti moramo, da obratna trditev ne velja. Lahko se zgodi, da tovrsten disk ne obstaja, pa vsiljivec vseeno ne more pobegniti, ker bi vsak uspesen pobeg vključeval potovanje v preteklost. Taka situacija je ilustrirana na sliki 10. Kriterija, ki bi znal iz topoloske informacije o prostoru
168
Obzornik mat. fiz. 61 (2014) 5
Problem umetnostne galerije
Utefo 1] P c D x I vedno odločiti, ali vsiljivec lahko pobegne ali ne, za zdaj se ne poznamo.
Slika 10. Pobeg ni mogoč, ker bi pri vseh možnih poteh morali na določenem odseku potovati nazaj v času, vendar pa tudi disk iž izreka 5 ne obstaja.
Rešitve nalog
Rešitev naloge 1. Možnih postavitev je seveda več, za vsak primer je narisana po ena na sliki 11, kjer so pazniki označeni z zvezdicami. Vsak od osenčenih trikotnikov v primerih (a) in (c) mora vsebovati vsaj enega paznika, ker sicer ne bi imeli pod nadzorom ogličč, označenih s krogci. Ker sta v obeh primerih osenčena kosa disjunktna, je jasno, da potrebujemo vsaj dva paznika. Poleg tega moramo pri postavljanju tudi paziti, da oba paznika skupaj vidita celotno nepokrito območje.
(a)	(b)	(c)
Slika 11. Resitev naloge 1: Vsako od osenčenih območij mora vsebovati vsaj enega paznika.
Rešitev naloge 2. Prva dva primera na sliki 12 prikazujeta galeriji z 8 ogličči, ki ju lahko nadzoruje en sam paznik. V tretjem primeru sta očitno potrebna dva paznika, sicer nimamo pod nadzorom točk, označenih s krogci, ki sta vidni samo z osenčenih območij.
Rešitev naloge 3. Vsako od osenčenih območij na sliki mora vsebovati vsaj enega paznika, sicer ne vidimo točk, označenih s polnimi krogci. V
161-172
169
Aleksandra Franc
prvem primeru torej potrebujemo vsaj pet paznikov, v drugem vsaj tri. Hitro se lahko prepričamo), da imajo pod nadzorom celotno galerijo, ce jih postavimo na mesta, označena z zvezdicami.
Rešitev naloge 4. Samo enega, seveda. Naročimo mu, naj se sprehaja po najdaljši vodoravni stranici. Za galerijo v obliki glavnika z n zobci torej potrebujemo vseh n = |_3fJ stacionarnih paznikov (doseze zgornjo mejo iz izreka 1), vendar pa zadosca ze en sam potujoci paznik.
Rešitev naloge 5. Preprost odgovor bi bil n + 2h — 2, saj je galerija gotovo pod nadzorom, ce dobi vsak trikotnik svojega paznika. Seveda se da to zgornjo mejo precej izboljsati, vendar ne moremo slepo posnemati Fiskovega dokaza, ker se lahko hitro prepricamo, da v tem primeru za barvanje oglisc grafa, ki ga dobimo s triangulacijo, vcasih potrebujemo vec kot tri barve. Dokazemo pa lahko, da zadosca |^ra+2fej paznikov. Ideja je, da mnogokotnik popravimo tako, da se s tem znebimo lukenj. Za vsako luknjo obstaja vsaj ena diagonala mnogokotnika iz triangulacije, ki jo povezuje z zunanjim ob-mocjem ali z drugo luknjo. Ce mnogokotnik prerezemo vzdolz te diagonale, dobimo nov mnogokotnik, ki ima eno luknjo manj, poleg tega pa dve novi oglisci (in dve novi stranici). Preprost primer je prikazan na sliki 14. Z nekaj truda lahko pokazemo, da diagonale lahko izbiramo tudi tako, da pri rezanju mnogokotnik ne razpade na vec kosov. Ko koncamo, dobimo mno-gokotnik brez lukenj z n + 2h oglisci, od koder z uporabo izreka 1 dobimo rezultat.
170
Obzornik mat. fiz. 61 (2014) 5
Problem umetnostne galerije
Slika 14. Rešitev naloge 5: Mnogokotnik z luknjo lahko z rezom vzdolž ene od diagonal spremenimo v mnogokotnik brez luknje in z dvema oglišcema vec.
Rešitev naloge 6. V prvem delu naloge moramo spet poiskati čim več točk, ki jih lahko nadzorujemo samo iz disjunktnih območij. Tokrat nam jih uspe najti 6, kar nam da spodnjo mejo za .Število vitezov. Hitro vidimo, da je 6 vitezov tudi dovolj, če jih postavimo v točke, ki so na sliki 15 označene z zvezdičami.
Zdaj pa poglejmo, kam postaviti lokostrelče, da jih bomo za nadzor okoliče trdnjave potrebovali čim manj. Spet poisčemo točke, tokrat v ravnini zunaj obzidja, ki jih lahko nadziramo le z majhnega kosa zunanjega robu obzidja. Na sliki 16 smo jih označili s krogči, pripadajoče kose na robu obzidja pa narisali z odebeljeno črto. Od tu sklepamo, da bomo potrebovali vsaj 6 loko-strelčev. Hitro se prepričamo, da jih 6 zadosča, če jih na primer postavimo na mesta, ki so na sliki 16 označena z zvezdičami. Kaj pa notranji dvorisči? Vsako od njiju lahko nadzorujemo z enim samim lokostrelčem, ki ga lahko postavimo kamorkoli na rob dvorisča, zato za nadzor čelotnega območja skupaj potrebujemo 8 lokostrelčev.
Rešitev naloge 7. Po poslediči 4 potrebujemo kvečjemu [nfl lokostrelčev, če je n stevilo oglisč. Hitro vidimo, da je n = 22, kar pomeni, da potrebujemo največ 11 lokostrelčev. Pri prejsnji nalogi smo premislili, da jih v re-sniči potrebujemo le 6. Ce se lokostrelči lahko premikajo vzdolč ene straniče,
161-172
171
Aleksandra Franc
potem jih po izreku 3 potrebujemo kvečjemu = 7. V resnici zadoščajo trije. Do postavitve lahko hitro pridemo tako, da 6 odebeljenih lomljenk s slike 16 razdelimo v tri pare tako, da sta v vsakem paru dve lomljenki, ki sta na obzidju zaporedni. Lokostrelce lahko potem postavimo na tiste stranice, ki povezujejo po dve lomljenki iz istega para.
LITERATURA
[1]	A. K. O. Choi in S. M. Yiu, Edge guards for the fortress problem, Journal of Geometry 72 (2001), 47-64.
[2]	V. Chvatal, A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B 18 (1975), 39-41.
[3]	Clay Mathematics Institute, Millenium problems. http://www.claymath.org/ millennium-problems, ogled 9. 12. 2014.
[4]	S. L. Devadoss in J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.
[5]	S. Fisk, A short proof of Chvatal's watchman theorem, J. Combin. Theory Ser. B 24 (1978), 374.
[6]	R. Ghrist in V. de Silva, Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology, International Journal of Robotics Research 25 (2006), 1205-1222.
[7]	R. Honsberger, Mathematical Gems II, Mathematical Association of America, 1976, 104-110.
[8]	J. Kahn, M. M. Klawe in D. J. Kleitman, Traditional galleries require fewer watchmen, SIAM Journal on Algebraic Discrete Methods, 4 (1983), 194-206.
[9]	J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press,1987, http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html, ogled 9. 12. 2014.
[10] S. M. Yiu, A generalized fortress problem using k-consecutive vertex guards, Journal of Geometry 72 (2001), 188-198.
172
Obzornik mat. fiz. 61 (2014) 5