Abstract: Introduced by Klee in 1973, the Art Gallery problem asks the following question. Given the top view of an art gallery in the form of a polygon, how many guards does one need to place inside the art gallery so that each wall is visible to at least one of them? It is easy to see that for convex polygons, one guard is always sufficient. The problem becomes nontrivial when the polygon has reflex vertices (vertices whose interior angle is more than 180 degrees).
In this talk, we study some variants of the Art Gallery problem. Using structural properties of almost convex polygons, we reduce an Art Gallery variant to a CSP (Constraint Satisfaction Problem) whose constraints have arity two and involve monotone functions. We then obtain a polynomial-time algorithm for the CSP, and consequently for the Art Gallery variant when parameterized by the number of reflex vertices. This is joint work with Kristine Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.
(A condensed version of this talk was presented at the TCS Women Spotlight Workshop at STOC 2020.)
