Nadzor galerij

Cof, Sandi (avtor), Cencelj, Matija (mentor), Gabrovšek, Boštjan (komentor)

Obravnavamo osnovni problem varovanja galerij, katerih tlorisi so enostavni poligoni z n oglišči, varnostnike pa postavljamo v oglišča. Preko primera poligona z n oglišči pokažemo, da obstaja poligon, ki za nadzor potrebuje floor(n / 3) varnostnikov. S triangulacijo poligona in 3-barvanjem podamo algoritem, ki nam najde postavitev varnostnikov pri kateri floor(n / 3) varnostnikov zadosti za nadzor celotne galerije. Obravnavamo tudi delitev poligona na y-monotone dele in njihovo triangulacijo. Delovanje algoritmov ponazorimo na primerih.

• Jezik: Slovenski jezik
• Ključne besede: problem galerije
• Vrsta gradiva: Diplomsko delo
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: PEF - Pedagoška fakulteta
• Leto izida: 2016
• PID: 20.500.12556/RUL-84830
• COBISS.SI-ID: 11134793
• Datum objave v RUL: 09.09.2016

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Guarding art galleries

Izvleček

We present the classical art gallery problem where the floor is a simple polygon with n vertices and we guard it by vertex guards. With an example which needs floor(n / 3) vertex guards, we proof that floor(n / 3) vertex guards might be necessary. By a triangulation of polygon and 3-coloring we give an algorithm which finds a placement for vertex guards where floor(n / 3) guards are sufficient to cover the entire polygon. We continue with presenting a division of the polygon into y-monotone pieces which we further triangulate. We simulate algoritms on examples.

• Ključne besede: art gallery problem