Introduction Complexity The Art-Gallery The Proofs Conclusions References |
The Art GalleryIn 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 ![]() ![]() 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 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 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. |