Nadzor galerij

diplomsko delo

Sandi Cof (Avtor), Matija Cencelj (Mentor), Boštjan Gabrovšek (Komentor)

Povzetek

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.

Ključne besede

problem galerije;varovanje galerij;varnostniki;triangulacija;poligoni;primeri simuliranja algoritmov;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2016
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[S. Cof]
UDK:	51:069:7(043.2)
COBISS:	11134793
Št. ogledov:	950
Št. prenosov:	154
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Guarding art galleries
Sekundarni povzetek:	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.
Sekundarne ključne besede:	galery;mathematics;galerija;matematika;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Ljubljani, Pedagoška fak., Matematika in računalništvo
Strani:	VIII, 176 str.
ID:	9166313