Polyhedral Galleries
Format
Oral Presentation
Faculty Mentor Name
Larry Langley
Faculty Mentor Department
Mathematics
Abstract/Artist Statement
The Art Gallery Problem is one of the most famous problems that has ever been proven in the field of graph theory. The problem asks, “how many cameras are required when placed at the corners of a gallery for that set of cameras to be able to see the entire flooring of the gallery?” Using graph theory, we can answer this problem mathematically. The polygon (the gallery) has n vertices, and that polygon can be triangulated into a set of triangles, from which we can color the vertices through a process of vertex coloring. After the coloring is completed, we can then place cameras at the set of vertices that use the least amount of colors, and those cameras will be able to see the entire interior of the gallery. From this approach, an upper bound on the number of cameras required to see the interior was found by Chvátal, which is given by by the floor function of n/3. This problem has been expanded to include other versions, one of which is the gallery with holes (or columns), where Dr. O'Rourke found an upper bound on the number of cameras required given by the floor function of (n+2h)/3, where h is the number of holes in the polygon. In my research, I have used O'Rourke's research on galleries with holes as a basis for finding an upper bound of the floor function of (n+2(h-1))/3 cameras required to see the surfaces of three dimensional polyhedra. I will discuss the construction required to find this bound, showing how O'Rourke's theorem is used, and then show how this construction works applied to several simple polyhedra, including the cube and the tetrahedron.
Location
Sierra Learning Lab, William Knox Holt Memorial Library and Learning Center
Start Date
30-4-2022 11:20 AM
End Date
30-4-2022 11:39 AM
Polyhedral Galleries
Sierra Learning Lab, William Knox Holt Memorial Library and Learning Center
The Art Gallery Problem is one of the most famous problems that has ever been proven in the field of graph theory. The problem asks, “how many cameras are required when placed at the corners of a gallery for that set of cameras to be able to see the entire flooring of the gallery?” Using graph theory, we can answer this problem mathematically. The polygon (the gallery) has n vertices, and that polygon can be triangulated into a set of triangles, from which we can color the vertices through a process of vertex coloring. After the coloring is completed, we can then place cameras at the set of vertices that use the least amount of colors, and those cameras will be able to see the entire interior of the gallery. From this approach, an upper bound on the number of cameras required to see the interior was found by Chvátal, which is given by by the floor function of n/3. This problem has been expanded to include other versions, one of which is the gallery with holes (or columns), where Dr. O'Rourke found an upper bound on the number of cameras required given by the floor function of (n+2h)/3, where h is the number of holes in the polygon. In my research, I have used O'Rourke's research on galleries with holes as a basis for finding an upper bound of the floor function of (n+2(h-1))/3 cameras required to see the surfaces of three dimensional polyhedra. I will discuss the construction required to find this bound, showing how O'Rourke's theorem is used, and then show how this construction works applied to several simple polyhedra, including the cube and the tetrahedron.