Pritam Bhattacharya Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha R
Tuesday, 24 May 2011 (All day)
- A-212 (STCS Seminar Room)
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.