Diagonals: Part II
4. Entering new territory
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.
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.
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.
We'll continue the discussion of diagonals in a later column.
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