February 15, 2012
How to guard an art gallery
Speaker: Vida Dujmović, Adjunct Research Professor, School of Computer Science
Abstract: 

What is the minimum number of guards or cameras that can monitor an entire art gallery? In the most basic version of this problem in computational geometry, the floor-plan of the gallery is represented by a simple polygon and each guard is represented by a point in the polygon. I will present an optimal solution for this problem using one of the most widely applicable mathematical tools, namely colourings of graphs. View a video teaser of this week's talk.