RECENT RESULTS IN ART GALLERIES

Two points in a polygon are called visible if the straight line segment between them lies entirely inside the polygon. The art gallery problem for a polygon P is to find a minimum set of points G in P such that every point of P is visible from some point of G. This problem has been shown to be NP-hard by Lee and Lin [71]. However, Chvatal showed that the number of points of G will never exceed [n/3] for a simple polygon of n sides [21]. This latter result is referred to as the art gallery theorem. Many variations on the art gallery problem have been studied, and work in this area has accelerated after the publication of the monograph of O'Rourke [92], which deals exclusively with this topic. This paper provides an introduction to art gallery theorems, and surveys the recent results of the field. The emphasis is on the results rather than the techniques. In addition, this paper examines several new problems that have the same geometric flavor as art gallery problems.