Lecture by Dr. Akanksha Agrawal

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Department of Computer Science and Automation
Theory Seminar Series

Speaker : Dr. Akanksha Agrawal
Postdoctoral Researcher
Department of Computer Science
Ben-Gurion University of the Negev
Israel

Title : Guarding Polygons via CSP

Date : Friday, August 30, 2019

Time : 1:00 PM

Venue : CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract

The Art Gallery problem is a fundamental visibility problem in Computational Geometry, introduced by Klee in 1973.  The input consists of a simple polygon P, (possibly infinite) sets X and Y of points within P, and an integer k, and the objective is to decide whether at most k guards can be placed on points in X so that every point in Y is visible to at least one guard. In the classic formulation of Art Gallery, X and Y consist of all the points within P. Other well-known variants restrict X and Y to consist either of all the points on the boundary of P or of all the vertices of P. The above mentioned  variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA’16]. Given the above result, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016].

“Is Art Gallery FPT with respect to the number of reflex vertices?”

In this talk, we will obtain a positive answer to the above question, for some variants of the Art Gallery problem. By  utilising the structural properties of “almost convex polygons”, we design a two-stage reduction from (Vertex,Vertex)-Art Gallery to a new CSP problem where constraints have arity two and involve monotone functions. For the above special version of CSP, we obtain a polynomial time algorithm. Sieving these results, we obtain an FPT algorithm for  (Vertex,Vertex)-Art Gallery, when parameterized by the number of reflex vertices. We note that our approach also extends to (Vertex,Boundary)-Art Gallery and (Boundary,Vertex)-Art Gallery.

Biography of the speaker

I am a postdoctoral researcher at the Department of Computer Science, Ben-Gurion University of the Negev, Israel,  where I work in the group of Prof. Meirav Zehavi. Before moving to Israel, I was a postdoctoral researcher at the Institute  for Computer Science and Control, Hungarian Academy of Sciences, Hungary. I did my Ph.D at the  Department of Informatics, University of Bergen, Norway, under the guidance of Prof. Saket Saurabh and Prof. Daniel Lokshtanov. My research interests include Parameterized Complexity, Computational Geometry, Exact Algorithms, and Fine Grained Complexity.

Host Faculty : Dr. Anand Louis

ALL ARE WELCOME