The Art Gallery Theorem
Speaker: Emille Lawrence
(University of San Francisco)
Wednesday, April 18, 2012Abstract:
Suppose you own a one-room art gallery whose floor plan is a simple polygon. Given that your collection of art is quite valuable, suppose further that you would like to place cameras in your gallery so that every point in the space is visible to at least one of the cameras. Additionally, to cut down on the cost of your security system and to be as unintrusive as possible to the gallery guests, you'd like to install as few cameras as possible. How many cameras would you need, and where would you decide to place them? This question, known as the Art Gallery Problem, was first posed in 1973 by Victor Klee, and has been extended by mathematicians in many directions over the years. We will answer this question, and discuss a proof via a 3-coloring argument. We will also discuss some interesting related problems in computational geometry.