Given the layout of a museum, what is the minimum number of guards needed to guard every point in the museum? This problem, often called the Art Gallery Problem, is an example of a problem at the intersection of several areas, including geometry, discrete math, and optimization. By working through this problem, one can explore ideas from different areas of mathematics, and see how these ideas can be combined to solve real-world problems!
First, let's define mathematically what we mean to guard a museum. In this problem, guards must stay at fixed positions but are able to see every angle from their position by rotating. To represent this mathematically, a point in the museum is visible to a guard if the line segment from the guard to point lies within the museum or along the boundary.
The guard in the museum on the left can see all points from his position. The guard in the museum on the right cannot see past the wall (shaded in black), so the lower right corner of the museum is unguarded.
We will assume our museums have straight walls, so the floor plan of the museum is a polygon in the plane (this analysis does not apply to museums such as Frank Gehry's Guggenheim Museum Bilbao). A polygon is convex if the entire line segment joining any two points in the polygon lies in the polygon. Let's start by thinking about a triangle, which is the simplest convex polygon.
How many guards does it take to guard a museum in the shape of a triangle?
Details and Assumptions: A point in the museum is visible to a guard if the line segment from the guard to lies within the triangle (or along the boundary).
See Guarding a Museum for more details on guarding a museum.
Since a triangle is convex, by positing a guard anywhere in the museum, the line segment between the line and any other point in the museum lies in the museum. This holds for any convex shape, so any convex polygon can be guarded by a single guard. Is the opposite direction also true?
Suppose a museum in the shape of a polygon can be guarded by a single guard. Does this imply the museum is convex?
Details: A point in the museum is visible to a guard if the line segment from the guard to lies within the triangle (or along the boundary).
See Guarding a Museum for details on guarding a museum.
What is the minimum number of guards needed to guard a museum whose floor plan is a polygon with walls? Note that in order to answer this question, we need to show
- there exist positions for the guards such that every point in the museum is guarded
- no fewer guards can guard every point in the museum.
First, we define the floor function for any real number to be the largest integer less than or equal to . Think of the floor function as rounding down to the nearest integer. For example,
Art Gallery Theorem: Any museum with walls can be guarded by at most guards.
This problem was first solved by Vasek Chvatal in 1975 and below, we will give the beautiful proof due to Steve Fisk in 1978. In fact, Fisk's proof of this theorem is constructive, giving an algorithm (or sequence of steps) that tells us exactly where to place the guards. To show that bound in the theorem is tight, consider the museum with walls in the shape of a comb.
Then the guard for point must be stationed within the shaded triangle with vertex , the guard for point must be stationed within the shaded triangle with vertex , etc. Since these triangles do not overlap, at least guards are needed. But by the Art Gallery Theorem, guards are also sufficient, which we can observe by placing the guards at the lower left corner of each shaded triangle. In general, the comb museum layout gives an example of a museum with walls that requires exactly guards, which shows that the bound in the theorem is best possible.
It seems that the worst case example of a comb museum occurs because there are very sharp "corners" that restrict the placement of guards. What if we consider museums whose walls meet at right angles, creating corners? These floor plans correspond to orthogonal polygons, and three proofs given by Kahn-Klawe-Kleitman, Lubiw, and Sack-Toussaint show that there is always a configuration of guards that will guard the entire museum.
Problems from computational geometry also naturally arise in video game programming, where it is often necessary to perform computations based on a virtual world to create a realistic user experience. Think about a video game you have played involving a virtual world and how the game must solve challenges such as detecting when objects collide, representing the surface or terrain of the virtual world, detecting motion from your input to the game, and determining the appearance/visibility of objects as you move through the world. All of these problems involve elements of computational geometry, computer graphics, computer science, and algorithms.
Other applications of computational geometry include
- route planning for GPS: determining location, speed, and direction
- integrated circuit design
- designing and building objects such as cars, ships, and aircraft
- computer vision, to determine lines of sight and designing special effects in movies
- robotics, to plan motion and visibility
We will prove this theorem through a sequence of claims. First, a triangulation of a polygon is a decomposition of the polygon into triangles by drawing non-intersecting diagonals between pairs of vertices.
Claim 1: Any polygon can be triangulated.
We prove this claim by induction on the number of vertices. For , the polygon is a triangle, which is already triangulated. For , we will find a single diagonal (i.e., a line segment that lies within connecting a pair of vertices), which splits the polygon into two smaller parts. Then the triangulation of the entire polygon can be obtained by pasting together the triangulation of the two different parts. Since the sum of the interior angles of is , there is a vertex of with interior angle less than . Let be the neighboring vertices of in the polygon. If the line segment lies within the polygon, then this line segment is the desired diagonal. Otherwise, triangle contains other vertices. Move the line segment towards until it hits the final vertex in triangle . Then line segment lies within the polygon and can be taken as the desired diagonal, proving the claim.
Our second claim involves coloring the vertices of the triangulated polygon in the following way: given a triangulated polygon, a 3-coloring is a coloring of the vertices such that every triangle has 3 different colored vertices.
Claim 2: Any triangulated polygon is 3-colorable.
We will proceed by induction on the number of vertices in the polygon. For , the polygon is a triangle and we can choose three different colors for the three vertices. Now, consider any triangulated polygon with vertices. Pick any two vertices and that are connected by a diagonal (i.e., connected by an edge in the triangulation but not in the original polygon). We can split the polygon into two triangulated polygons using edge and by induction, the two triangulated polygons are 3-colorable. Let (red, blue, green) be the colors in the first triangulation and let be the colors for the second triangulation . Then identify the color of in the first triangulation to the number labeling in the second triangulation, and identify the color of in the first triangulation to the number labeling in the second triangulation. Finally, identify the last remaining colors in both triangulations with each other.
Then we obtain a coloring for the entire triangulation by preserving the color of all vertices in the first triangulation and using the colors identified with for the vertices in the second triangulation. This gives a 3-coloring of the entire triangulated polygon and proves Claim 2.
Claim 3: For any 3-coloring of a triangulation, there exists a color such that the number of vertices of this color is , and placing guards on these vertices will guard the entire museum.
Without loss of generality, suppose the colors of the vertices are red, green, blue such that the number of red vertices is less than or equal to the number of green vertices, which is less than or equal to the number of blue vertices. The total number of vertices is , so If , then and would also be strictly greater than and the identity cannot be satisfied. Therefore, Now, by placing a guard at every vertex colored by red, observe that every triangle in the triangulation has exactly one red node and thus, exactly one guard. Also, any point in the museum is contained in a triangle in the triangulated polygon, and is visible from the vertex of the triangle colored by red. This gives a placement of at most guards that guard the entire museum, proving Claim 3.
Claims 1, 2, and 3 together give a proof of the Art Gallery Theorem.
Since there are many different possible triangulations and 3-colorings, there may be multiple ways to place the guards, but each choice will result in at most guards to guard the entire museum.