Created in the 1970's, the Art Gallery Problem seeks to answer the question of how many security guards are necessary to fully survey the floor plan of any building. These floor plans are modeled by polygons, with guards represented by points inside these shapes. Shortly after the creation of the problem, it was theorized that for guards whose positions were limited to the polygon's vertices, the floor of n/3 guards are sufficient to watch any type of polygon, where n is the number of the polygon's vertices. Two proofs accompanied this theorem, drawing from concepts of computational geometry and graph theory.
Vuich, Megan, "Exploring Topics of the Art Gallery Problem" (2019). Senior Independent Study Theses. Paper 8534.
art gallery problem, art gallery theorem, watchman theorem, art gallery, polygon, polygon triangulation, guard, geometry, graph theory, graph, graph coloring, computational geometry
Bachelor of Arts
Senior Independent Study Thesis
© Copyright 2019 Megan Vuich