Abstract

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.

Advisor

Kelvey, Robert

Department

Mathematics

Keywords

art gallery problem, art gallery theorem, watchman theorem, art gallery, polygon, polygon triangulation, guard, geometry, graph theory, graph, graph coloring, computational geometry

Publication Date

2019

Degree Granted

Bachelor of Arts

Document Type

Senior Independent Study Thesis

Share

COinS
 

© Copyright 2019 Megan Vuich