Diagonals: Part II

3. Guarding orthogonal art galleries

The appropriate result for "guarding" orthogonal polygons turned out to be the following:

Theorem (J. Kahn, M. Klawe, and D. Kleitman):

For a simple orthogonal polygon with n sides, guards are sometimes necessary and always sufficient to guard the polygon.

While the approach of Kahn, Klawe and Kleitman was based on Fisk's work, this theorem's proof is much more complex than that for a general polygon. What these researchers attempted to do was to show that instead of triangulating a polygon and 3-coloring the result, one could quadrilateralize the diagram and 4-color the result. Whereas a simple polygon can have n sides (n at least 3), orthogonal polygons can only have n sides where n is an even number which is at least 4. Furthermore, the number of diagonals which will subdivide any polygon into triangles is n-2, but the number of diagonals which subdivide an orthogonal polygon into 4-gons is n/2 - 2. However, there are intriguing complications. First of all, not all quadrilaterals are convex. If one has a non-convex quadrilateral, one can not place a guard at any of its 4 vertices and guarantee vision of the entire quadrilateral! As for coloring, if one places a guard at the vertex having a "reflex angle" (an interior angle measuring more than 180 degrees) or at the far end of a diagonal at that vertex, then the guard can see the whole polygon, but when one 4-colors the vertices of the quadrilaterals the vertices involved may not all receive the same color. Furthermore, even if one has a convex quadrilateralizaton of an orthogonal polygon, a vertex-coloring of the original polygon plus the subdividing diagonals may only be two-vertex colorable. Placing guards at all the vertices of one of these two colors may use many more guards than is needed to guard the polygon.
 

The quadrilateralization above not only involves using convex quadrilaterals but even using trapezoids. However, placing vertex guards at the vertices which are colored red yields an unnecessarily large guard set. Exactly 2 vertex guards are necessary to guard this polygon. This contrasts with the situation for triangulating a polygon where the triangulated polygon can only be colored with exactly 3 colors but not fewer.

Although inspired by the Fisk proof, the Kahn, Klawe, and Kleitman proof required an interesting strategy of its own. First they proved the result below.

Theorem:

Every simple orthogonal polygon can be decomposed by internal diagonals into convex quadrilaterals.

Rather than color the graph associated with this convex quadrilateralized polygon, Kahn, Klawe, and Kleitman added additional edges to this graph to force the four vertices of each of the quadrilaterals to get different colors. You can get the flavor of their proof by seeing how it would work for the orthogonal polygon below.
 

.

The first step is to find a convex quadrilateralization, which is achieved using the red diagonals:
 

 

We can now add blue diagonal edges joining opposite vertices of the quadrilaterals.
 

Figure 4

(Note that intersections of the blue edges are not considered vertices of the resulting graph.) We can now 4-color the vertices of the graph whose edges consist of the thin black, medium blue, and thick red lines. The four colors used are green, purple, yellow and turquoise. Unlike the situation for triangulated polygons when they are 3-colored, the ways to extend the initial coloring of one of the convex quadrilaterals to the rest of the graph are not unique. In the coloring shown below, we wind up with 3 yellow vertices, 3 turquoise vertices, 2 purple vertices, and 2 green vertices. If two guards are placed at either the 2 purple vertices or 2 green vertices, we can guard the whole orthogonal polygon of 12 sides (and vertices). In fact, there is one green-colored vertex and one purple-colored vertex from which the whole polygon can be guarded!

It is tempting to try to prove this theorem by finding an analogue of the ear concept (explained here in last month's column) that generalizes to the case of an orthogonal polygons. The idea of a quad-ear presents a variety of possibilities and difficulties.

1. Introduction
2. Orthogonal polygons
3. Guarding orthogonal art galleries
4. Entering new territory
5. References