•  
  •  
 

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.

Download

Additional Files

figure 1.PNG (15 kB)
figure 1.PNG (15 kB)
figure 2.PNG (22 kB)
figure 3.PNG (27 kB)
COinS