Home > Challenge, Geometry > The Art Gallery Problem

## The Art Gallery Problem

I recently attended a function at the Museum of Modern Art hosted by Math for America.  In typical MfA fashion, the invitation was designed around a relevant mathematical idea, in this case, the Art Gallery problem.

The Art Gallery problem (aka the museum problem) basically asks “What is the minimum number of guards required to keep an entire region under watch?”.

We make the usual idealizing assumptions for the purposes of elegant mathematics.  For instance, we assume that the guards can see infinitely far, that there are no obstructions (other than the walls), that the guards can see everything in front of them, and the like.

So looking at the map at the right, how many guards would be needed to watch over the fifth floor at the MoMA?

The Art Gallery problem is a classic question from computational geometry, and its solution involves a lot of great ideas from graph theory and graph coloring.

There are a number of fun extensions to this problems, too, including the watchmen route problem (one watchman guarding the entire museum) and the fortress problem (guarding the exterior, rather than the interior).

The Art Gallery problem is the best kind of math problem:  easy to state and understand, surprisingly rich and complex, and lots of fun to play around with!