Guarding an Art Gallery

Applet By Michael Kleyman

It is easy to see that for a hall with n vertices [n/3] guards will always do the job. This is true because any polygon can be triangulated, and for any triangulation of a simple polygon, its vertices can be colored in three colors in such a way that every triangle in the triangulation will have vertices of all three colors. Now we can place guards in vertices of one color, and, obviously, there is a color used in no more than [n/3] vertices. Furthermore, it has been shown that there are polygons that actually need these [n/3] guards for full coverage.

So, what this algorithm is really about is triangulating a polygon, and then coloring its vertices in three colors as described. A naive triangulation algorithm would have been of O(n^2) complexity. This algorithm used here is more sophisticated and runs in O(n*log n) time. It is based on the fact that a y-monotone polygon can be triangulated in O(n*log n) time by a relatively simple greedy algorithm. (A polygon is called y-monotone if any horizontal line crossing the polygon enters and exits it exactly once.) Therefore, the algorithm first partitions a polygon into y-monotone piece (in O(n*log n) time), and then these piece are triangulated by the greedy algorithm.

The algorithm is described in detail in the book:

Computational Geometry, Algorithms and Applications
by Mark de Berg, Marc van Kreveld Mark Overmars, and Otfried Schwarzkopf
Springer-Verlag, 1997.

Art Gallery Theorems and Algorithms
by Joseph O'Rourke
Oxford University Press, 1987

Also, there is also a nice webpage and applet here for the art-gallery problem.

The Applet

You need a browser supporting JDK 1.1 for this applet (i.e. netscape 4.06).

Source Code