Séminaire
|
Date : 12 octobre 2021 13:30 - Salle :Amphi Garcia
Chromatic art gallery problems for point and vertex guardsSubir Kumar GHOSH - Professeur Ramakrishna Mission Vivekananda Reseach and educational institute |
The art gallery problem is to determine the number of guards (or surveillance cameras) 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 an important problem 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.
Chromatic art gallery problems arise from applications in areas like landmark-based robot navigation and wireless networks. One such problem is the weak-conflict free guarding of polygons, where the objective is to colour a chosen guard set S for P using the minimum number of colours such that each point within P sees at least one guard from S with a unique colour. Note that the objective here is to minimize the number of colors rather than the number of guards in S. We present an algorithm for weak conflict-free guarding of P (without holes) where the point guard set is coloured using only O(log n) colours. If the guards are allowed to place only on vertices of P, the corresponding algorithm for weak conflict-free vertex guarding problem uses O(log2 n) colours. This algorithm uses funnel structures of weak visibility polygons for placing coloured guards.
Finally, we discuss a few open problems on weak conflict-free guarding of P for both point and vertex guards.
bio:
Subir Kumar Ghosh was a professor of computer science at Tata Institute of Fundamental Research, Mumbai, India till July, 2015. Since then, he is a professor of computer science at RKM Vivekananda Educational and Research Institute, Belur, West Bengal, India (formerly known as RKM Vivekananda University). He is a Fellow of Indian Academy of Sciences since 1998. He was an Adjunct Professor of the Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur during 2017-2018.
Prof. Ghosh worked as visiting scientists at many reputed universities and research institutes around the world, and gave several invited lectures in the international conferences, workshops and in the institutes in many countries. He is the author of a book entitled "Visibility Algorithms in the Plane", and published around seventy papers in the fields of computational geometry, discrete applied mathematics, geometric graph theory, algorithms and robot motion planning. Citations of his book and papers stand very high in international standards within the areas of algorithms and computational geometry.
Prof. Ghosh chaired many sessions in the International Conferences. He was a member of Program Committees for several International conferences. During 2008-2015, he conducted twenty-two introductory workshops on graph and geometric algorithms for teachers and students of engineering colleges and universities in India for motivating them towards algorithmic research. He has also organized seven international schools in India for Ph.D. students of computer science and discrete mathematics. In 2015, he initiated a new international conference on algorithms and discrete applied mathematics (CALDAM). Currently, he is the Chair of the Steering Committee of CALDAM.