izpis_h1_title_alt

Nadzor galerij
Cof, Sandi (Author), Cencelj, Matija (Mentor) More about this mentor... This link opens in a new window, Gabrovšek, Boštjan (Co-mentor)

URLURL - Presentation file, Visit http://pefprints.pef.uni-lj.si/3661/ This link opens in a new window

Abstract
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.

Language:Slovenian
Keywords:problem galerije
Work type:Undergraduate thesis (m5)
Tipology:2.11 - Undergraduate Thesis
Organization:PEF - Faculty of Education
Year:2016
COBISS.SI-ID:11134793 This link opens in a new window
Views:805
Downloads:152
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Secondary language

Language:English
Title:Guarding art galleries
Abstract:
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.

Keywords:art gallery problem

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back