[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
  Logo Login | Create Account

Guarding art galleries

Sandi Cof (2016) Guarding art galleries. Diploma thesis.

Download (984Kb)


    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.

    Item Type: Thesis (Diploma thesis)
    Keywords: art gallery problem, triangulation, y-monotone pieces, 3-coloring
    Number of Pages: 176
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    red. prof. dr. Matija CenceljMentor
    asist. dr. Boštjan GabrovšekComentor
    Link to COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11134793)
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 3661
    Date Deposited: 05 Sep 2016 12:29
    Last Modified: 05 Sep 2016 12:29
    URI: http://pefprints.pef.uni-lj.si/id/eprint/3661

    Actions (login required)

    View Item