Tata Institute of Fundamental Research

Art Gallery Problem

Student Seminar
Speaker: Pritam Bhattacharya Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha R
Date: Tuesday, 24 May 2011 (all day)
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  This talk will provide a brief introduction to the art gallery problem, which was first posed to Chvátal by Victor Klee in 1973. It basically deals with finding out the minimum number of watchmen/guards needed to keep watch over an entire art gallery shaped like a simple polygon having n vertices. I will be stating some theorems/conjectures (alongwith proof sketches) regarding the number of guards that should be sufficient and necessary for guarding different types of simple polygons having n vertices. Then, I will describe an elegant approximation algorithm for solving this problem which was suggested by Ghosh in 1986, that closely follows the greedy approach for the minimum set-cover problem.

References: http://en.wikipedia.org/wiki/Art_gallery_problem