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!
2 Comments
Ahmed Gouda · November 12, 2010 at 6:56 pm
A few of some other students in my math team class last year and I had to present this problem. I believe you only need 3 for this one, assuming those tiny rooms aren’t typos. The idea is to make as many non-redundant triangles you can without crossing through walls, then picking the points that have the most triangles using them. The three you can use here are: The point to the far south east, the point on the west side that has five triangles touching it, and another point that isn’t really pointed out because of size I imagine. Its in the little room on the north east side though. It isn’t really important which as long as it can see that entire small room.
MrHonner · November 15, 2010 at 7:57 am
I think that works, and I think your assumptions are correct. An interesting challenge is to find the total number of acceptable three-guard arrangements, assuming that every guard must placed at a vertex of this triangulation.