Diagonals: Part II
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 bluecolored 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

Introduction

Orthogonal polygons

Guarding orthogonal art galleries

Entering new territory

References