Art Gallery Problem

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!

Placing four guards at the given points will guard the entire museum.

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 $P$ in the museum is visible to a guard if the line segment from the guard to point $P$ 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.

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?

What is the minimum number of guards needed to guard a museum whose floor plan is a polygon with $n$ 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 $\lfloor x \rfloor$ for any real number $x$ to be the largest integer less than or equal to $x$. Think of the floor function as rounding down to the nearest integer. For example,

$$\lfloor 3.4 \rfloor = 3, \lfloor 5.9 \rfloor = 5, \lfloor 10 \rfloor = 10.$$

Art Gallery Theorem: Any museum with $n$ walls can be guarded by at most $\lfloor \frac{n}{3} \rfloor$ 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 $15$ walls in the shape of a comb.

Then the guard for point $A$ must be stationed within the shaded triangle with vertex $A$, the guard for point $B$ must be stationed within the shaded triangle with vertex $B$, etc. Since these triangles do not overlap, at least $5$ guards are needed. But by the Art Gallery Theorem, $\lfloor \frac{15}{3} \rfloor = 5$ 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 $3n$ walls that requires exactly $\lfloor \frac{3n}{3} \rfloor = n$ 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 $90^\circ$ 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 $\lfloor \frac{n}{4} \rfloor$ 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 $P$ can be triangulated.

We prove this claim by induction on the number $n$ of vertices. For $n=3$, the polygon $P$ is a triangle, which is already triangulated. For $n \geq 4$, we will find a single diagonal (i.e., a line segment that lies within $P$ 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 $P$ is $(n-2) 180^{\circ}$, there is a vertex $u$ of $P$ with interior angle less than $180^{\circ}$. Let $v,w$ be the neighboring vertices of $u$ in the polygon. If the line segment $v,w$ lies within the polygon, then this line segment is the desired diagonal. Otherwise, triangle $\triangle uvw$ contains other vertices. Move the line segment $v,w$ towards $u$ until it hits the final vertex $x$ in triangle $\triangle uvw$. Then line segment $ux$ 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 $n=3$, the polygon is a triangle and we can choose three different colors for the three vertices. Now, consider any triangulated polygon with $n>3$ vertices. Pick any two vertices $u$ and $v$ 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 $(u,v)$ and by induction, the two triangulated polygons are 3-colorable. Let (red, blue, green) be the colors in the first triangulation $T_1$ and let $(1,2,3)$ be the colors for the second triangulation $T_2$. Then identify the color of $u$ in the first triangulation to the number labeling $u$ in the second triangulation, and identify the color of $v$ in the first triangulation to the number labeling $v$ 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 $(1,2,3)$ 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 $\leq \lfloor \frac{n}{3} \rfloor$, 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 $r$ of red vertices is less than or equal to the number $g$ of green vertices, which is less than or equal to the number $b$ of blue vertices. The total number of vertices is $n$, so $r+g+b=n.$ If $r > \lfloor \frac{n}{3} \rfloor$, then $g$ and $b$ would also be strictly greater than $\lfloor \frac{n}{3} \rfloor,$ and the identity $r+g+b=n$ cannot be satisfied. Therefore, $r \leq \lfloor \frac{n}{3} \rfloor.$ 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 $P$ in the museum is contained in a triangle in the triangulated polygon, and $P$ is visible from the vertex of the triangle colored by red. This gives a placement of at most $\lfloor \frac{n}{3} \rfloor$ guards that guard the entire museum, proving Claim 3.

Claims 1, 2, and 3 together give a proof of the Art Gallery Theorem. $_\square$

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 $\lfloor \frac{n}{3} \rfloor$ guards to guard the entire museum.