The Complexity of Guarding an Art Gallery
Suppose for a minute that you have decided to open an art gallery. There would be many things to consider before opening the door of the gallery to the public. Where should I put the paintings? What kind of lighting would best complement my Picasso? How badly do I want to gouge art patrons on the cost of a postcard? Where should I place guards so as to offer the best protection for the paintings? These are all valid questions, let us focus on the last one.
If you wish to protect the paintings in your gallery, you must have surveillance of some kind (say guards or cameras). In addition to being able to watch all points in your gallery, you'd like to maintain a decent hold on the cost of all this; the fewer guards there are, the less you are going to have to pay. The first problem is called the "Art-Gallery" Problem (thus, the gallery analogy). This is a well known problem in computational geometry.
Many results have been discovered with respect to this problem. This tutorial will focus on the difficulty of guarding an entire art gallery with the least number of guards.