# Guarding an Art Gallery

## Applet By Michael Kleyman

This applet demonstrates the algorithm for "Guarding an Art Gallery" problem. As its name suggests, this problems deals with setting a minimal number of guards (or cameras) in a gallery hall of a complex polygonal shape (without holes), so that they could see every point in the hall.

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.
In fact, alot of work had gone into this problem and its variants. There is a book dedicated to this problem:

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

The complete applet
This includes the source to the applet, with the supporting libraries used.