Problem at the Art Gallery

The Crystal Art Gallery was being readied for its grand opening, and, in my role as a security consultant, I had to work out how many guards were needed to make sure that every wall of paintings was under scrutiny. I was also required 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).

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

Graph theory often involves coloring problems. In effect, 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 sufficient 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. Once the conjecture was proposed, mathematicians took 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.

I could now 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 are 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 with 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 assignment. Maybe I'll get to work on the Taj Mahal Gallery, which is currently being built as a 21-walled enclosure.

But what if the guards were mobile? Is that anything like routing a robot through an obstacle-filled room?

Photos by I. Peterson