Digital Commons Network^™

Exploring Topics Of The Art Gallery Problem, Megan Vuich

Senior Independent Study Theses

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 …