Problem čuvara umjetničke galerije

master's thesis

• Author: Goran Pavičić
• Mentor: Juraj Šiftar (mentor)
• Committee member: Juraj Šiftar (predsjednik povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Committee member: Mirko Primc (član povjerenstva)
• Committee member: Dragutin Svrtan (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: problem nadzora umjetničke galerije; konveksni mnogokut; ortogonalni poligon
• Keywords (english): art gallery problem; convex polygon; orthogonal polygon
• Language: croatian
• URN:NBN: urn:nbn:hr:217:043667
• Study programme: Title: Mathematics Education; specializations in: Mathematics Education; Course: Mathematics Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike (magistar/magistra edukacije matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-03-13 14:26:29