Title: Sweeping a Polygonal Domain with a Variable Length Line Segment

Speaker: Kien Huynh, Stony Brook University

Date and time: 6pm (New York time), Tuesday, November 7, 2023

Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

... and on Zoom, details on the seminar mailing list

We consider sweeping a polygonal domain using a variable-length segment whose endpoints can be considered to be two mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to the segment. The objective is to sweep the domain as quickly as possible. We prove that the problem is NP-hard even in simple polygons and give constant-factor approximation algorithms, both for simple polygons and polygons with holes.