| Title | : | Old and New Algorithms for Guarding Polygons |
| Speaker | : | Subir Kumar Ghosh (Ramakrishna Mission Vivekananda University, Kolkata) |
| Details | : | Wed, 25 Oct, 2017 12:00 AM @ A M Turing Hall |
| Abstract: | : | 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 approximation 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. |
