Speaker: |
Pritam Bhattacharya (Indian Institute of Technology Dept. of Computer Science and Engineering Kharagpur, West Bengal 721302) |

Organiser: |
Jaikumar Radhakrishnan |

Date: |
Wednesday, 20 Jun 2018, 14:00 to 15:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

Most of the standard variants of the art gallery problem have been known to be NP-hard (though not NP-complete) since a long time, and very recently, these problems were shown to be ETR-complete. In 1998, Eidenbenz, Stamm and Widmayer established that the art gallery problem is APX-hard. They also proved that, especially when dealing with input polygons containing holes, the approximation ratio of O(log n) obtained by Ghosh in 1986 is in fact tight. In 2015, Bhattacharya, Ghosh and Roy showed that the approximation ratio lower bound of Ω(log n) holds even for the subclass of polygons with holes that are weakly visible from an edge. However, for the case of simple polygons without holes, a PTAS has been proposed very recently by Katz for vertex guarding the subclass of simple polygons that are weakly visible from an edge.

Ghosh also conjectured in 1986 that a constant-factor approximation algorithm exists for the art gallery problem when only vertex or edge guards are used and the input is restricted to only simple polygons without holes. In 2015, Bhattacharya, Ghosh and Roy settled this conjecture for the special class of simple polygons (without holes) that are weakly visible from an edge by presenting a 6-approximation algorithm for this problem. Recently, Bhattacharya, Ghosh and Pal designed constant factor approximation algorithms for guarding general simple polygons (without holes) using vertex guards. In this talk, we present the outline of these approximation algorithms and explain the core ideas behind how they achieve the constant ratios.