Talks & Seminars
Title: Old and New Algorithms for Guarding Polygons
Prof. Subir Kumar Ghosh, RKM Vivekananda University Belur
Date & Time: October 7, 2015 15:00
Venue: Conference Room, C Block, 01st Floor, Dept. of CSE, Kanwal Rekhi (KReSIT) Bldg.
The art gallery problem is to determine the number of guards (or cameras) that are sufficient to cover or see every point in the interior of an art gallery. An art gallery can be viewed as a polygon P (with or without holes) with a total of n vertices, and guards as points in P. 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. This problem was first posed by Victor Klee in a conference in 1973, and in the 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. A polygon 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. In this lecture, we will first present an O(log n)-approximation algorithm to find the minimum number of guards necessary for guarding P, which was designed by Ghosh way back in 1986. For this problem, the pproximation ratio was improved to O(loglog OPT) by King and Kirkpatrickin 2011. Ghosh had also conjectured in 1986 that a constant-factor approximation algorithm exists for this problem in case of polygons without holes. This conjecture was settled recently for a special class of P (without holes) by Bhattacharya, Ghosh and Roy, when they presented a 6-approximation algorithm for this problem. An outline of this algorithm will be provided in the lecture. Chromatic art gallery problems arise from applications in areas like landmark-based navigation and wireless networks. One such problem is the weak-conflict free guarding of polygons, where the objective is to colour a guard set for P using minimum number of colours such that each point within P sees at least one guard with an unique colour. So finally, we will present an algorithm for weak conflict-free guarding of P (without holes) where the guard set is coloured using only O(log n) colours.
Speaker Profile:
Details available at :http://cs.rkmvu.ac.in/~sghosh/
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback