Pritam Bhattacharya
Indian Institute of Technology – Kharagpur

Wednesday, April 18 at 3:00 PM


The art gallery problem deals with determining the minimum number of guards (or cameras) that are sufficient to cover or see every point in the interior of an art gallery, assuming that the guards have 360° visibility and can see an unbounded distance. An art gallery can be viewed as a polygon P (with or without holes) having a total of n vertices, while certain points in P can be specified as guards. Any point z in P is said to be visible from a guard g if the line segment joining z and g does not intersect the exterior of P. A polygon P is said to be guarded by a set of chosen guards if every interior point of P is visible from some guard within the guard set. This problem was first posed by Victor Klee at a conference in 1973, and in course of time it has become one of the important problems in computational geometry with extensive applications to surveillance of buildings like airport terminals, railway stations etc.

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 when dealing with polygons containing holes. They also proved that the approximation ratio of O(log n) obtained by Ghosh in 1986 is in fact tight for the case of polygons with holes. In 2015, Bhattacharya, Ghosh and Roy showed that the approximation ratio lower bound of O(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, the question of APX-hardness remains open, though it is worth mentioning that 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 simple polygons (without holes) using vertex guards.

In this talk, we present the hardness results for multiple variants of the art gallery problem, as mentioned above. We also outline a few approximation algorithms for solving some of these variants.

Download presentation (password protected)

Categories: Seminar