Polyhedral Galleries

Lead Author Major

Mathematics

Lead Author Status

Junior

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

This document is currently not available here.

Share

COinS
 
Apr 30th, 11:20 AM Apr 30th, 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.