The Art Gallery Problem
This paper was co-authored by Jeriko Jacinto.
In 1994, Edvard Munch’s famous painting, “The Scream,” was swiped from a museum in Oslo, Norway. The thieves smashed a window, cut the painting’s frame from the wall, and left a note reading, “Thousand thanks for the bad security!”
So what could the museum have done to up their security? An obvious answer is to increase the number of security guards or cameras monitoring the museum’s interior, but this leads us to another question.
What is the minimum amount of guards necessary to completely guard an art museum? This is the famous Art Gallery Problem, first posed in 1973.
The short answer is that for an n-sided art gallery (or museum), one needs at most n⁄3 guards to have a fully secure interior. But how did we get this answer?
While there are many different proofs for the Art Gallery Problem, we chose to analyze the decidedly most elegant one.
In 1978, Steve Fisk gave a proof to this solution using a theory called triangulation. It works like this:
We have our funky-shaped polygonal art gallery here:
This art gallery has 12 sides. We want to protect all spaces within this art gallery. This means that we need to have enough security guards so that a guard can see all areas within the borders at any point in time. We assume that these guards are stationary and can see in all directions unless something is blocking their way. An area is visible to a guard if the viewpoint connecting the guard and the seen object lies within the boundary of the polygon art gallery.
We first have to understand that we only need one guard to protect an area in the shape of a convex polygon. A convex polygon is a “bulging” polygon, where all angles are less than 180°, and all vertices point outwards. We can see a demonstration of this in the figure below.
Therefore, we can suggest that if we cut our polygon art gallery up into n-convex polygons, we will only need at most n security guards to protect all areas within it.
Let’s divide our art gallery into the simplest polygon, the triangle, through a process called triangulation. Each triangle should share its vertices with the polygon’s vertices and edges connecting these vertices only within the polygon. There are a variety of ways to partition a polygon through triangulation.
Here’s one version of our triangulated art gallery:
We know we can triangulate any polygon, due to the Two Ears Theorem, which was presented in 1899 by Max Dehn. Dehn’s proof observes that each polygon has at least 3 convex vertices (less than 180°). We can say that a polygon P has an ear at vertex X if the diagonal connecting X’s two adjacent vertices, Y and Z, lies fully inside of P. Two ears overlap if the triangles formed by their respective vertices share a vertex.
We can prove this theorem by induction.
Theorem: Every triangulated simple polygon with greater than or equal to 4 sides has at least two ears.
Inductive Hypothesis: We assume that every triangulated simple polygon with fewer than n and at least 4 sides has two ears.
Base Case: Every simple polygon with n = 4 sides has 1 diagonal and two triangles. Thus, a polygon with n = 4 sides has only two ears:
Inductive Step: Let P be a simple polygon with n > 4 sides. Consider vertex pi, a vertex of P where the interior angle formed by pᵢ₋₁, pᵢ, and pᵢ₊₁ is less than 180°.
There are two possible cases: Either P has an ear at vertex pᵢ or P does not have a vertex at pᵢ.
Case 1: Polygon P has an ear at vertex pᵢ. If we remove this vertex, we get a resulting simple polygon P’ with n-1 and more than 3 vertices. By the induction hypothesis, there are two non-overlapping ears E₁ and E₂ for P’. Since they are non-overlapping, at least one of these ears is not at either of the vertices pᵢ₋₁ or pᵢ₊₁. Since all ears of P’ are also ears of P, polygon P has two ears at E₁ or E₂ and pᵢ.
Case 2: Polygon P does not have an ear at vertex pi. This means that the triangle formed by pᵢ₋₁, pᵢ and pᵢ₊₁ contains at least one vertex of P in its interior (by the definition of an ear). Let q be the vertex of the interior of P in the triangle formed by pᵢ₋₁, pᵢ, and pᵢ₊₁. Let L be the line through q that runs parallel to pᵢ₋₁ and pᵢ₊₁ and that is as close to pᵢ as possible. We let a and b be L’s intersection points with P’s edges (pᵢ, pᵢ₊₁ and pᵢ, pᵢ₋₁). Therefore, we can say that the triangle formed by a, pᵢ, and b does not contain any vertex of P in its interior.
Next, if we draw a line segment Q from vertex q to pᵢ, we know that Q can also be drawn such that it does not intersect any edges of P. Q divides P into 2 simple polygons, P₁ (contains pᵢ, pᵢ₊₁, …,q) and P2 (contains pᵢ, pᵢ₋₁,…q).
There are two sub-cases of case 2:
Case 2a: Polygon P₁ is a triangle. Therefore, P₁ is an ear for polygon P. By the induction hypothesis, polygon P₂ must have at least two non-overlapping ears E₁ and E₂ (otherwise P₂ would be a triangle and P would only have 4 vertices). Since they are non-overlapping, at least one of these ears is not at either of the vertices pᵢ or q. This ear does not overlap with the other ear formed by P₁, so it is the second ear in polygon P.
Case 2b: Polygon P₁ is not a triangle. So, by the induction hypothesis, polygon P₁ has two ears. Let us call these ears E₁₋₁ and E₁₋₂. Similarly, polygon P₂ has two ears E₂₋₁ and E₂₋₂. Since they are non-overlapping, at least one of the ears in P₁ is not at vertex pᵢ or q, and at least one of the ears in P₂ is not at vertex pᵢ or q either. These two non-overlapping ears will be the ears of polygon P.
Thus, by the Two Ears Theorem, we know that any simple polygon has at least two ears.
If we can always find an ear in a simple polygon P, we know that we can always triangulate P. We take a vertex V, which is an ear of P. If we remove V and add an edge between its adjacent vertices, vᵢ₊₁ and vᵢ₋₁. We save this new edge. We now have a new polygon P₁. We continue to find an ear in P₁, draw a diagonal from its adjacent vertices and remove the ear. We continue to do this until we are left with a triangle. The edges that we drew to connect the vertices will be the diagonals that triangulate P.
By triangulating our polygon art gallery, we know that our entire art gallery can be guarded by n guards (one guard for every convex polygon within the gallery space). But this seems a little extraneous.
We can reduce the number of guards necessary by finding points to station a guard, such that they are capable of securing more than one triangle area.
We can do this via a 3-coloring of our polygon gallery. This is where we color each vertex of our gallery one of 3 colors. No vertex can be adjacent to a vertex that is the same color. Our gallery will look something like this:
We have 4 yellow vertices, 5 red vertices, and 3 blue vertices. If we take the color with the least amount of vertices and only keep the guards that are these colors, we know that we will have the lowest number of guards that can secure our entire gallery. In our case, this looks something like:
Fisk proved that one needs at most n⁄3 guards for an n-vertex simple polygon in order to protect all of the interior. In this case, we only need 3 guards at each of the blue vertices.
But would this theory really have helped protect the Oslo museum from being broken into?
The obvious flaws in this theorem reflect on the fact that this is an unrealistic situation. No human guards are capable of standing still, with a 360° view, at all times. Some versions of the Art Gallery Problem switch over to using security cameras, but these situations also have flaws.
Over the years, people have been contributing their own versions of the Art Gallery Problem. The Watchmen Route is another optimization problem where one asks what is the shortest route a guard in the art gallery would need to take in order to guard an entire area. The Fortress Problem asks how many guards are necessary and sufficient to protect the infinite exterior of an art gallery (n⁄2).
Another case points out that most art galleries have pieces in their interiors, whether it be sculptures, displays, or types of furniture. O’Rourke gave a proof in 1987 such that a gallery with n vertices and h obstacles could be guarded by (n + 2h)⁄3 guards.
What about orthogonal polygon art galleries?
These are art galleries whose walls meet at right angles, restricting the placement of guards at vertices. Kahn-Klawe-Kleitman gave a proof showing that n⁄4 guards can protect the interior.
And finally, many mathematicians are still working on an algorithm to procure the securement of a 3-D polyhedron art gallery. Triangulation gets trickier in three dimensions, and putting a guard at each vertex does not ensure that all of the museum is under surveillance.
While any single theorem may not completely address the issue of providing air-tight security to an art gallery, or protecting a world-famous Munch painting, we can see that the Art Gallery Problem has allowed scientists to address situations within the field of computational geometry.
Computational geometry is a branch of computer science dedicated to algorithms that can be stated in terms of geometry. Scientists involved with robot navigation (perhaps on foreign or extraterrestrial terrain), computer vision (dealing with occlusion in image recognition methods), and Geographic Information Systems (GIS) rely on advancements in computational geometry. The Art Gallery Problem allows scientists to simulate situations using evidence-based theorems to explore new and more areas of this field.
If you are interested in learning more, check out our sources below!
