BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1077
DTSTAMP:20230914T125949Z
SUMMARY:Guarding Polygons via CSPs
DESCRIPTION:Speaker: Akanksha Agrawal (Ben-Gurion University\, Israel)\n\nA
 bstract: \nAbstract: Introduced by Klee in 1973\, the Art Gallery problem 
 asks the following question. Given the top view of an art gallery in the f
 orm of a polygon\, how many guards does one need to place inside the art g
 allery 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 proble
 m becomes nontrivial when the polygon has reflex vertices (vertices whose 
 interior angle is more than 180 degrees).\n\nIn 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 S
 atisfaction Problem) whose constraints have arity two and involve monotone
  functions. We then obtain a polynomial-time algorithm for the CSP\, and c
 onsequently for the Art Gallery variant when parameterized by the number o
 f reflex vertices. This is joint work with Kristine Knudsen\, Daniel Loksh
 tanov\, Saket Saurabh\, and Meirav Zehavi.\n\n(A condensed version of this
  talk was presented at the TCS Women Spotlight Workshop at STOC 2020.)\n
URL:https://www.tcs.tifr.res.in/web/events/1077
DTSTART;TZID=Asia/Kolkata:20200821T171500
DTEND;TZID=Asia/Kolkata:20200821T181500
LOCATION:Zoom link: https://zoom.us/j/92834710011?pwd=WURSa3JsRVpJYWhONEExY
 TdDcENDQT09
END:VEVENT
END:VCALENDAR