| Description |
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
|