Problem čuvara umjetničke galerije

diplomski rad

• Autor: Goran Pavičić
• Mentor: Juraj Šiftar (mentor)
• Član povjerenstva: Juraj Šiftar (predsjednik povjerenstva)
• Član povjerenstva: Tina Bosner (član povjerenstva)
• Član povjerenstva: Mirko Primc (član povjerenstva)
• Član povjerenstva: Dragutin Svrtan (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2017-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Razmatranjem problema nadzora umjetničke galerije ustanovili smo kako je ključni korak napraviti dobru podjelu poligona pritom misleći na podjelu u konveksne mnogokute. Podjelom poligona s \(n\) vrhova na konveksne mnogokute ustanovljeno je kako će za bilo koji poligon biti dovoljno \(\lfloor n/3 \rfloor\) čuvara. Ipak, promatrajući jednu posebnu klasu poligona (ortogonalnih) dobili smo još bolje rješenje kako je za njih dovoljno \(\lfloor n/4 \rfloor\) čuvara za nadgledanje njihove unutrašnjosti. Nakon što smo razmotrili problem koji je postavljen 1973. godine promotrili smo i neke druge varijante problema. Za nadzor galerije koja ima oblik općeg poligona bit će dovoljno \(\lfloor n/4 \rfloor\), a za ortogonalne poligone \(\lfloor (3n+4)/16 \rfloor\) čuvara koji se mogu kretati po nekoj od dužina unutar poligona. Ukoliko je potrebno nadzirati vanjštinu poligona tada će nam biti dovoljno \(\lceil n/2 \rceil\) čuvara i što je zanimljivo, to ne ovisi o tome je li poligon konveksan ili ne, dok će za istovremeni nadzor unutrašnjosti i vanjštine biti potrebno \(\lfloor 2n/3 \rfloor\) za opći, odnosno \(\lfloor 7n/16\rfloor +5 \) čuvara za bilo koji ortogonalni poligon.

Sažetak (engleski)

Considering the art gallery problem, we have found that the key step is to make a good division of polygons, or more accurately, a division into convex polygons. It was found that by dividing any polygon with \(n\) vertices into convex polygons you’ll never need more than\(\lfloor n/3 \rfloor\) guards. Still, observing a specific type of polygon (orthogonal) it was proved that \(\lfloor n/4 \rfloor\) vertex guards are sufficient to supervise its inside. After considering the problem that was set in 1973., we also looked at some other variations of the problem. To supervise a gallery, that is shaped like a general polygon, it will be sufficient \(\lfloor n/4 \rfloor\) mobile guards and for orthogonal polygons \(\lfloor (3n+4)/16 \rfloor\). If it is necessary to monitor the polygon outside, \(\lceil n/2 \rceil\) guards will be sufficient, and interestingly, it does not depend on whether the polygon is convex or not. As for simultaneous control of the inside and outside, it will be needed \(\lfloor 2n/3 \rfloor\) guards for general and \(\lfloor 7n/16\rfloor +5 \) for any orthogonal polygon.

• Ključne riječi: problem nadzora umjetničke galerije; konveksni mnogokut; ortogonalni poligon
• Ključne riječi (engleski): art gallery problem; convex polygon; orthogonal polygon
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:043667
• Studijski program: Naziv: Matematika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike (mag. educ. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2018-03-13 14:26:29