February 15, 2012
How to guard an art gallery
Speaker: Vida Dujmović, Adjunct Research Professor, School of Computer Science
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.