December 11, 2012 - Art Gallery Problem => Math Works!

A Challenging Art Gallery

Nothing is more intriguing (to me, at least), than a recalcitrant example of a math problem I thought I had mastered but which refuses to cooperate. In our recent work on graph theory, we had looked last week at a family of related problems called "art gallery problems." We worked through the thinking that led to Fisk's constructive proof of the "art gallery theorem" that Chvatal had proved through more formal (and difficult to understand) means on a few years earlier. Fisk demonstrated precisely how to calculate and arrange the minimum number of "vertex guards" in a polygonal art gallery so as to "cover" the entire interior of the gallery. In simpler terms, this means finding the minimum necessary number of stationary guards placed only at vertices of a simple (non-intersecting) polygonal-shaped "gallery" so that every point inside or on the interior walls of the gallery are in view of at least one guard. We could test such an arrangement by drawing a straight line that stayed entirely inside the gallery between a given point and at least one vertex guard. If such a line exists for every point in the gallery, we have "covered" it and all the art works on the walls or "free standing" (e.g., sculptures, mobiles) are protected 

As I said in a previous post, this number can be found by taking the integer portion (or "floor") of n/3, where n = the number of vertices (or edges) of the gallery. The resulting number is the smallest number of guards that are sufficient for a given gallery and also the smallest number necessary for a "worst-case" arrangement of n vertices. Fisk showed that by triangulating the graph, it is always possible to have n - 2 triangles created by adding n - 3 diagonals connecting vertices which stay completely inside the figure. 

As the above graph has 20 vertices, the floor of n/3 is 6. So 6 vertex guards are sufficient. But are they also necessary or are fewer possible (because it turns out that this is NOT a worst-case for 20 vertices)? 

Assuming we have triangulated correctly, we proceed in Fisk's method by doing a proper (minimal) graph coloring of the vertices (so that no two vertices that are connected by an edge have the same color). Since we have nothing but triangles, it should always be possible to do this with exactly 3 colors. We then count how many vertices have a given color, and whatever the minimum-appearing color turns out to be is where we should place guards.

When we worked on the above-pictured gallery last week, I found a triangulation and coloring for which two colors appeared six times each, and the third color was used seven times. Since six was the number the formula produced, I assumed that this was indeed a worst-case scenario.

However, Taylor pointed out that he placed guards at five of the vertices and could (apparently) "cover" every point in the gallery. This was very strange. If the math worked, then something was wrong. One possibility was that Taylor only thought he had every point in the gallery covered with his five vertex guards, but really there was at least some tiny area that they couldn't cover. Unfortunately (for me), I couldn't see any way that this was actually the case. In fact, it seemed that his five guards were sufficient. And that meant only one of two things: math doesn't work, or I had not found the best way to triangulate and/or color the graph. 

I left the problem "unsolved" over the weekend with the thought that this was an opportunity for the students to grapple with a seeming paradox and to find out if math does indeed have to make sense (at least in this case). In all honesty, I was convinced that I was just stuck in a visual rut and that one or more students, looking with fresher eyes and a more flexible mind, would figure out something that satisfied both the obvious fact that Taylor was right and that the algorithm makes sense. 

Students worked diligently on finding a better way to triangulate and color this gallery. Some found clever but, it turned out, flawed solutions. One easy way to check if the triangulation and coloring are correct is first to see if the resulting triangulation uses exactly 17 diagonals to form 18 triangles. Second, there must be a total of 20 vertices in any coloring. It was this last criterion that showed the mistake students made in trying to draw a "continuous" straight line between the bottom point (labeled 6) and, say, point 20 and point 9. But that is NOT a straight line, as can be seen clearly above. Rough sketches sometimes mask this point. 

A very careful check of the graph above, however, shows that everything is correct. We have exactly 18 triangles created with exactly 17 diagonals, each of which connects two vertices  and none of which is ever external to the polygon. And this better triangulation than mine allowed this student to find a coloring for which, as indicated, only five vertices needed to be colored orange, while six are blue and 9 are purple. The total of 20 is correct, and checking the triangles, no connected vertices have the same color. And so Taylor's informal arrangement of 5 guards, while not unique (his placement differed from the above), was indeed minimal and correct. 

I still have to check a few other student papers, but the one I've shown here was done by Denali. I thank her for pulling my chestnuts out of the fire and proving once again that mathematics makes sense.