Problem at the Art Gallery

In my role as a security consultant, it looked like one of my tougher assignments. The Crystal Art Gallery was being readied for its grand opening, and I had to figure out how many guards were needed to make sure that every wall of paintings was under scrutiny. I was also ordered to keep costs as low as possible.

The trouble was that the art gallery had a distinctive shape. Its walls didn't meet at the usual right angles. Instead, its perimeter consisted of 11 walls forming a highly irregular, sharply cornered, deeply indented polygon. It looked stunning, both inside and out. But the geometry also complicated my task of determining the minimum number of guards that I would need to post.

I started by assuming that a guard stationed at a corner would be able to see down the two walls that meet at that corner. Then, as I was idly sketching the gallery's layout on a paper napkin, I noticed that this configuration was really just a graph, which is what mathematicians call a set of points (known as vertices) and a set of lines (known as edges) joining pairs of these points. I realized I could draw the polygonal art gallery as a graph consisting of 11 vertices (for the corners) and 11 edges (for the walls).

I liked that because it reminded me of the days long past when I had dabbled in computational geometry at night school. I had wanted to generate my own animated cartoon characters on the computer screen, and I had started taking some courses to learn computer graphics. Graphs turned out to be a great way of organizing and analyzing information. But that's another story.

Polygonal art gallery represented as a graph with 11 vertices and
11 edges (left), and one possible triangulation of that polygon (right).

What I vaguely remembered was that graph theory often involves coloring problems. In other words, you try to color a graph by assigning colors to each vertex so that no two adjacent vertices are the same color.

There's a famous, closely related problem in which you have to decide whether four colors are enough to fill in every conceivable map that can be drawn on a flat piece of paper so that no territories sharing a common boundary are the same color. It took mathematicians more than 100 years to prove that four colors are always enough.

It seemed to me that one way to find a solution to my art gallery problem was to subdivide the 11-sided polygon into triangles. I had to do it carefully, making sure that none of the lines I added crossed one another or passed outside the polygon's boundary. There are actually lots of different ways to do this, and any one way is as good as another.

That was a clever move, I thought to myself, because then I could apply a theorem stating that the vertices of any triangulated polygon can be three-colored. Using just red, green, and blue, I could color all 11 vertices of my polygon so that no two adjacent vertices were the same color. Thus, each triangle ends up with one corner of each color.

I could then pick one of the colors and put a guard at each corner having that color. For 11 vertices, two colors are used four times and one color is used three times. So I realized that the smallest number of posted guards that I could get away would be three. The great thing about math is that you can often figure out a general answer that works for a host of different cases. For an art gallery with n walls and n corners, the answer is n/3 or the next smallest whole number if 3 doesn't divide evenly into n. So, I'm now all set for another gallery assignment. Maybe I'll get to work on the Taj Mahal Gallery, which is currently being built as a 21-walled enclosure.

Now, what if the guards were mobile? Is that anything like routing a robot through an obstacle-filled room, as I saw on television recently? Let me think about that a little.

References:

O'Rourke, J. 1987. Art Gallery Theorem and Algorithms. New York: Oxford University Press.

Peterson, Ivars. 1988. The Mathematical Tourist: Snapshots of Modern Mathematics. New York: W.H. Freeman.

Tucker, Alan. 1994. The Art Gallery Problem. Math Horizons (Spring):24-26.

Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.