Diagonals: Part I

5. Where do new problems come from?

The problem that Klee posed in 1973 was a geometry question of great simplicity and appeal. It is easy to state, and two lovely approaches to solving it are relatively self-contained and elementary compared to many other simple-to-state mathematical problems. (Fermat's Last Theorem is easy to state but to understand the details of the mathematics necessary to solve this problem requires great perseverance.) Yet Klee's problem did not end with the solutions of Chvátal and Fisk. Klee's question involved the development of new definitions and proof techniques that have been of value in solving not only problems that "sound like" Klee's original question, but also problems that seem very different. Mathematics grows not merely by the resolution of questions that have been raised hundreds of years ago (e.g. Fermat's Last Theorem) but when new problems are asked and methods to answer these questions evolve and spawn new questions.

Although Chvátal's proof of the Art Gallery Theorem has been mined for new ideas relatively recently, it was after Fisk's breakthrough in finding a powerful new approach to the Art Gallery Theorem that research in problems related to the Art Gallery Theorem exploded. Some of the work involved the computational complexity of problems associated with the Art Gallery Theorem: What was the time complexity of being able to triangulate a polygon with n vertices? How many different triangulations of a simple polygon are there? Could one be sure of being able to show a different bound for special polygons? At this point, work exploring different avenues inspired by the Art Gallery Theorem began to coalesce with the tools and problems that constitute the area of geometry on the interface between mathematics and computer science known ascomputational geometry. Loosely speaking, computational geometry is concerned with analyzing all aspects of how one gets computers to solve geometrical problems. This involves the time and space complexity of a variety of fundamental geometrical algorithms. Examples of topics that have become "standard" in computational geometry are point location, triangulation, Voronoi diagrams, arrangements of lines (hyperplanes) and pseudolines.

One of the valuable avenues of study in computational geometry was the investigation of simple polygons from a variety of perspectives. For example, initially people tended to act as if all simple polygons were the domain in which to investigate various mathematical problems. However, there are a surprisingly large number of ways to distinguish different kinds of simple polygons. They take advantage of ideas that are on the borderline of combinatorial and metrical ideas: The size of angles in a simple polygon, the number of components (connected pieces) in which every line perpendicular to a given direction meets the polygon, the "spiral quality" of polygons. Some polygons have the property that their interior is visible from a single point (e.g. they are star-shaped). Godfried Toussaint (McGill University) has been a pioneer in trying to tease out many different subclasses within the collection of simple polygons. One subclass results from the very useful idea of a monotone polygon, namely one for which there is a direction so that every line perpendicular to this direction intersects the polygon in a single segment. The polygon below, for example, shows a monotone polygon, where the special direction is vertical:
 

No one can truly pretend that there is much real applicability in the idea of using guards with 360 degree vision for protecting the security of museums with a floor plan consisting of a simple polygon. Certainly, the floor plans of many actual art galleries would have internal pillars, walls or corridors. However, such floor plans, a sample of which is shown below, are not simple polygons.
 

This situation represents a polygon with holes, where the "holes" consist of segments and polygons which lie in the interior of a simple polygon. Questions addressing the triangulation of polygons with holes and the number of guards sometimes necessary and always sufficient to guard the interior have been posed. The solutions of these problems are not as straightforward as Fisk's solution to the case for a simple polygon.

In the next column, I will discuss how these ideas have enriched the rapidly developing subtopic of Art Gallery Theorems within computational geometry and led to new and interesting accessible geometry problems. The interested reader should consult Joseph O'Rourke's book of 1987, which summarizes what was known at that time.

1. Introduction
2. What is a diagonal?
3. Triangulations and ears
4. Art gallery theorems
5. Where do new problems come from?
6. References

	Comments: webmaster@ams.org © Copyright 2004, American MathematicalSociety Privacy Statement		Search the AMS