Home Bookmarks Papers Blog

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:
    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

The complete applet
This includes the source to the applet, with the supporting libraries used.
Back to the Workshop home page