Keywords
art gallery theorem, art gallery problem, computational geometry, visibility problem, geometry, graph theory, math, mathematics, math education, education, logic, proofs
Disciplines
Discrete Mathematics and Combinatorics | Education | Geometry and Topology | Logic and Foundations | Mathematics | Other Mathematics | Science and Mathematics Education
Abstract
The art gallery problem is a geometry question that seeks to find the minimum number of guards necessary to guard an art gallery based on the qualities of the museum’s shape, specifically the number of walls. Solved by Václav Chvátal in 1975, the resulting Art Gallery Theorem dictates that ⌊n/3⌋ guards are always sufficient and sometimes necessary to guard an art gallery with n walls. This theorem, along with the argument that proves it, are accessible and interesting results even to one with little to no mathematical knowledge, introducing readers to common concepts in both geometry and graph theory. Furthermore, the Art Gallery Theorem and its proof have many extensions, leading to other related theorems on guarding galleries, as well as various applications, including the use of its methods in robotics and GPS. This paper serves as a cursory introduction to the theorem, its most commonly referenced proof, and these extensions and applications, particularly for those with little familiarity with visibility problems or mathematics in general.
Recommended Citation
Petruzelli, Natalie. "How to Guard an Art Gallery: A Simple Mathematical Problem." The Review: A Journal of Undergraduate Student Research 23 (2022): -. Web. [date of access]. <https://fisherpub.sjf.edu/ur/vol23/iss1/7>.
Additional Files
figure 1.PNG (15 kB)figure 1.PNG (15 kB)
figure 2.PNG (22 kB)
figure 3.PNG (27 kB)
Included in
Discrete Mathematics and Combinatorics Commons, Geometry and Topology Commons, Logic and Foundations Commons, Other Mathematics Commons, Science and Mathematics Education Commons