The Art Gallery
In computational geometry, the art gallery has been the inspiration for many questions with many interesting answers. Stemming back to a problem posed by Victor Klee in a conversation with Vasek Chvatal, Klee asked how many guards would be required to guard an art gallery whose floor would be represented by a simple polygon.
It turns out that n/3 is always sufficient and sometimes necessary to guard an art gallery with n vertices in its polygonal representation. To learn more, browse this excellent tutorial or see Joseph O'Rourke's exquisite monograph "Art Gallery Theorems and Algorithms".
In O'Rourke's book, many offshoots of the original problem have been explored. In fact, many questions still remain unanswered to this day. The art gallery has yielded problems that have fascinated many and prove to be an excellent medium in which to pose new questions.
Finally, we come to the topic of this tutorial, optimal guard placement in the art gallery. Above it was stated that n/3 guards are always sufficient and sometimes necessary to guard a polygon but, even though any n-gon can be guarded with n/3 guards, we hardly ever need all of them. For example, below we have two polygons, both with 12 vertices, one which requires n/3 guards and one which does not. So, the question arises of whether or not there are efficient algorithms for minimal guard placement.
Unfortunately, if has been proved that both for polygons with holes and ones without, the problem is NP-hard. The proof lies in the fact that any minimal guard placement would arise from splitting the polygon into star-shaped sub-polygons which, as it turns out is NP-hard. The proofs will be presented.