Diagonals: Part I
4. Art gallery problems
Note that the line segment beyond v along the line joining u and v up to the boundary of the polygon is part of the visibility region. A guard for the interior of a simple polygon can be placed at a vertex (usually called a vertex guard), on an edge, or in the interior. Intriguingly, for some types of guarding problems (which may involve the interior or the exterior of a polygon, and have special conditions on the type of polygon to be guarded), the number of guards needed when guards are required to be vertex guards is the same as for other types of guards. However, in other problems what can be achieved with vertex guards is vastly different from the general case. To help understand the issue, convince yourself that no vertex guard can see all of the interior of the polygon below, while there is a point in the interior of the polygon from which all of the interior can be seen.
Vasek Chvátal (pictured below), who first answered Klee's question, no doubt experimented with determining the minimum number of guards a particular polygon requires.
When contemplating finding the minimum number of guards for a polygon, quickly one notes that some many-sided polygons require only one guard: A convex polygon, regardless of the number of sides, requires only one guard, as do many non-convex polygons. It's a nice "exercise" to find the smallest number of sides that a polygon must have which requires it to have at least 2 guards. The answer to this exercise is 6. For example, the polygon below requires 2 guards.
This polygon can be triangulated in a variety of ways, one of which is shown below:
The vertices of this triangulation are now 3-colored with red, blue, and green. Since each triangle is colored with each of the 3 colors, if we place guards at all the red vertices, or all the green vertices, or all the blue vertices, we will have the whole polygon guarded. Clearly, it makes sense to put the guards at the set of vertices of the three different colors which has the minimum size! This will always give rise to a coloring with no more than colors.
If we place guards at the 6 blue vertices, the whole polygon will be successfully guarded. However, you should be able to convince yourself that in fact only 3 guards are required. Fisk's approach shows that no more than will ever be needed but for a particular polygon it does not say what the minimum number of guards would be. In fact, if you look back at Figure 2 you will find that no single guard located at a vertex will see all of the polygon, while there is an interior point where a guard can be placed from which all of the polygon is visible.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance