Seminars

View all Seminars  |  Download ICal for this event

Covering, partitioning, and searching polygons

Series: Bangalore Theory Seminars

Speaker: Prahlad Narasimhan, SUNY, Stony Brook,

Date/Time: Aug 26 11:30:00

Location: CSA auditorium [Room No. 104], ground floor

Abstract:
Decomposing a polygon into simpler pieces is a fundamental problem in computational geometry. In the Convex Cover problem, we wish to cover our polygonal environment with convex polygons. This problem has been studied for over 50 years from the lens of complexity theory as well as approximability. In this talk, we will look at the first constant-factor approximation algorithm for Convex Cover in simple polygons [Browne, Mitchell, Polischuk, Kasthurirangan; FoCS 23]. En route, we will describe the first constant-factor approximation algorithm for Hidden Set �?? how many points can you place in a simple polygon so that no two of them see each other?

We will also briefly consider the problem of converting a covering of a polygon into a partition of a polygon (where each piece of the partition is �??desirable�?�) [unpublished]. Finally, we will also touch upon the problem of finding a target in an environment that has already been compromised using a mobile robot with imperfect sensing capabilities [unpublished].


Microsoft team link:

Link

We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar