Art Galleries and Sleepy Guards -
How many security guards does it take to protect an art gallery? In 1975, Chvátal showed that n/3 stationary guards are capable of monitoring any art gallery that has a polygonal floor plan with n walls. I’ll present Fisk’s proof of this fact, which elegantly distills this geometric question into a discrete one about graphs and combinatorics. I’ll discuss some modern-day applications of Chvátal's art gallery problem, as well as some interesting modifications, such as: What if the guards have a restricted range of view? What if they're prone to sleeping on the job? What if both?
This talk assumes no prior knowledge and should be accessible to first-year students. Portions of the talk will feature joint work with W&J students Daniel Florentino and Ethan Moy.
Thursday, September 24, 2020 at 4:45pm to 5:30pmVirtual Event
Reed Community Members
If you are a member of the Reed community, you MUST LOG IN to see events that are open ONLY to the Reed community. Log in with your Reed ID (your Kerberos account information). If you don’t remember your account username or password, go to reed.edu/cis/help/kerberos.html.Log in with Reed ID