Toopana Pathmanathan
This presentation is about the problem of finding the minimum number of camera positions outside a polygon in two dimension such that every point in the exterior of the polygon is visible from at least one of the chosen camera. This problem has practical importance in medical imaging and survillance. Also this problem can be seen as the optimization version of art-gallery problem thus can be shown to be NP-hard. So instead on relying on heuristic searches, we address the approximability of camera placement problem. And it is well known that this problem can be cast as a hitting set problem. In this presentation I'll go through the VC-dimension of set systems associated with the camera placement problem and will present an algorithm that uses at most one more than the optimal camera placement when the cameras are placed in the circumscribing circle around the polygon.