Login
Talks & Seminars
Title: Approximation and Inapproximability of Guarding Polygons
Mr. Pritam Bhattacharya, IIT Kharagpur
Date & Time: June 21, 2018 16:00
Venue: Conference Room, 01st Floor, C Block, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
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. 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.
Speaker Profile:
Pritam Bhattacharya is a PhD candidate in the Department of Computer Science and Engineering at IIT-Kharagpur. His research is focused on designing approximation algorithms for different variants of polygon guarding and the art gallery problem, which is a classical problem in the domain of computational geometry. He is the recipient of the TCS PhD Fellowship since July 2015. Prior to joining IIT-Kharagpur, he obtained his MS in Computer Science from the Tata Institute of Fundamental Research, Mumbai.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback