Diagonals: Part II

4. Entering new territory

Whereas all of the polygons in the quadrilateralization in Figure 4 (in the previous section) are convex, it is possible to decompose this same polygon into quadrilaterals which are convex and non-convex.

 

There is even a way to do this so that all the quadrilaterals share a single vertex. This vertex is at the end of the internal diagonal that splits the only non-convex quadrilateral present into two triangles. This quadrilateralizaton shows that placing a single guard will suffice to guard the whole polygon. The vertex at which to place the single guard is shown in green.
 

 

In the diagram above, two of the quadrilaterals are actually trapezoids, and the vertices of the quadrilaterals are all vertices of the original polygon. In the diagram below, the original polygon's vertices are shown as small white dots but new vertices have been added on the edges of that polygon; they are shown in blue. The blue vertices are determined by extending those horizontal sides of the original polygon which when prolonged enter the interior of the polygon. The blue dots are placed where these extensions meet the vertical boundary lines of the polygon. This procedure can guarantee a subdivision of the original polygon into rectangles.

 

Had we started with an arbitrary polygon, a procedure such as this could have been used to divide a polygon into trapezoids (some of which might be "degenerate," and, hence, be triangles). These diagrams and examples chart out lots of new territory for mathematical investigation. When, if ever, can an orthogonal polygon be subdivided into rectangles using existing vertices of the polygon? What possibilities are added when one can add new internal vertices to the collection of potential vertices of the subdividing polygons of the original? Problems of this kind, where one is allowed to add new points in addition to those initially present, are often referred to as Steiner point variations on the original problem.

Invariably, when one ponders the details of a mathematical question one is led into new territory. This involves looking into new problems which are "nearby" in the sense that it seems natural to ask them as an outgrowth of what one is investigating. In the current context, for example, in the diagram below a polygon has been divided by the red diagonals into quadrilaterals which are convex.
 

This is not always possible because we know there exists a non-convex 4-gon. Under what conditions can a simple polygon be decomposed into convex 4-gons? Are there polygons with n vertices (n at least 5) for which one can be sure of convex 5-gons? Are there polygons with n vertices (n at least 5) for which one can be sure there is no convex quadrilateralizaton? (Here, I have in mind that the existing vertices of the polygon are to be used and no others.)

Another interesting variant of this type of problem is not to start with a polygon but with a plane set of points. Clearly, not all plane sets of points are such that the points of the set can serve as vertices of a simple polygon. For example, the points might all be on a straight line. Perhaps surprisingly, if P is a set of points which do not all lie on a straight line, there is a polygonalization of the points, that, is a simple polygon whose vertices coincide with points in the given set. Many questions about polygonalizations can be asked. For a fixed set of n points not all on a line, what is the largest number of different polygonalizations that can be obtained using these points? Alternatively, one might try to minimize the number of reflex angles for any (simple) polygonalization that passes through the points. Researchers have been successful in finding combinatorial bounds on this interesting "measure" associated with a set of non-collinear points.

Questions in the spirit of this discussion extend to planar sets of points. Thus, starting with the planar set of blue points, one can add additional lines to the point set so that the result consists of all quadrilaterals except for the infinite face of the associated graph. Such a decomposition is shown below. Can you see how to select some of the edges in the graph so that we obtain a polygon which together with the remaining edges forms the diagram shown?
 

 

One can now adopt the following perspective. Given a simple polygon, when can one pick points (and how few can one pick) in the interior of this polygon so that the original points together with the new points admit a convex quadrilaterization of the original point set? Problems such as these are still giving researchers plenty to think about.

Additional questions arise when one considers lattice polygons. These are polygons whose vertices can be assigned coordinates of the form (a, b) where a and b are integers. An example of such a polygon is shown below.

 

 

Some interesting work dealing with lattice point polygons is due to Sándor Fekete. Fekete considered the difficulty of solving some interesting polygonalization problems associated with point sets whose vertices are located at the points of an integer lattice. For example, given a set of size n of such lattice points such as the blue points below, is there a simple polygon that contains no other grid either in the polygon's interior or on its boundary? Fekete calls such a polygon a grid avoiding polygon. A solution to this problem is given by the polygon shown, but finding it is a bit like looking for a needle in a haystack.

 

 

By contrast, the set of points below differs from the one above in the omission of a single point. However, one can not find a grid avoiding polygon based on this point set.

 

Fekete proved that given a set of lattice points, the problem of determining if they give rise to a grid avoiding polygon is NP-complete. This suggests that it is unlikely that a polynomial time algorithm for finding such a polygon will ever be found.

It is natural to try to extend the work on Art Gallery Theorems to non-convex polyhedra in 3 dimensions. It is tempting to mimic the wonderful proof of Fisk, the first step of which would be to subdivide a non-convex 3-dimensional polyhedron into tetrahedra (the 3-dimensional analog of a triangle) using diagonals that lie in the polyhedron's interior. Like being able to triangulate a simple polygon, many find this an intuitively clear result--unfortunately, it is false! In 1911 the American topologist N. J. Lennes showed that there are non-convex 3-dimensional polyhedra with the property that the segment joining every pair of vertices which are joined by an edge of the polyhedron, lies in the exterior of the polyhedron. However, a simpler approach is due to the work of E. Schönhardt. He found that the simplest example of such a polyhedron is combinatorially a triangular antiprism (6 vertices, 8 triangular faces) where the parallel planed triangular faces are "twisted" with respect to one another. A diagram is shown below, with the hidden lines in blue:
 

The result is that all the edges that are not edges of the polyhedron are all in the exterior of the polyhedron. This provides an example of something that must be seen (or a model made) to be believed. Although one can not extend the Fisk argument directly, some partial results are known for what is true in 3 dimensions.

There are many appealing directions for generalizations of the Art Gallery Theorems. Some of these concern guarding the exterior of simple polygons, guarding the interior and exterior with guards, and using guards with x-ray vision. One particularly intriguing variant of the art gallery problem concerns the notion of guarded guards. We have seen that using vertex guards is sufficient to guard any n-sided polygon. However, what happens if one is nervous that guards may not be diligent? One way to deal with this is to make sure that every guard is visible by some other guard. This is the notion of guarded guards.

Two guards are required to guard the polygon below. For example, guards at u and x will do the job; however, guards at z and w guard each other and the rest of the polygon.


 

We now have the question of determining what is the number of guards which are sometimes necessary and always sufficient to guard an n-sided polygon, where we require that the guard set have the property that for any guard g there is some other guard h who can see g. This problem was solved very recently (2003) by T. Michael and V. Pinciu. For n-sided simple polygons with at least 5 sides there is a "guarded guard" set of points with points and for orthogonal polygons with at least 6 sides with points (this last result is due to G. Hernández-Peñalver).

We'll continue the discussion of diagonals in a later column.

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