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
| 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
References: http://en.wikipedia.org/wiki/Art_gallery_problem