Feature Column

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 floor function n/3 (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.

 

A simple polygon


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

Previous polygon triangulated and 3-vertex colored


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

Welcome to the
Feature Column!

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.
Read more . . .

Search Feature Column

Feature Column at a glance


Show Archive

Browse subjects