- Zoom link: https://zoom.us/j/92834710011?pwd=WURSa3JsRVpJYWhONEExYTdDcENDQT09
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.)