Diagonals: Part II

Posted March 2004.

1. Introduction

In the last column we began a discussion of diagonals of polygons. Part of the discussion concerned placing guards at points along a polygon. Given any simple polygon with n sides (such as the one below) it is possible to locate (the largest integer less than or equal to n/3) guards at vertices from which the whole polygon is visible. Visibility refers to being able to see points along a line which lies in the interior of the polygon.

 

One suitable set of places to put the guards for the polygon above is at the blue-colored vertices in the diagram below:
 

One could also place the guards at the vertices which are either green or red but this would be less efficient because more guards are needed. However, there are actually two vertices where guards can be placed so as to have the whole polygon visible from these vertices. Can you find two such vertices?

The above example illustrates Steve Fisk's approach to proving the Chvátal Art Gallery Theorem, in response to a problem posed by Victor Klee. The key idea is how to make use of the interior diagonals of a simple plane polygon. Our goal is to show how these ideas together with other notions emerging in the burgeoning field of computational geometry have led to many interesting new geometrical results, problems, and methods.

Joseph Malkevitch
York College (CUNY)

Email: malkevitch@york.cuny.edu

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