Title : Packing and Covering of Polygons with Geodesic Disks  Speaker : Ivo Vigan  Date & Time : 19 June , 2013 (Wed.) 14:00~15:00  Place : The GAIA (Math Science building room 106)
 Abstract Given a polygon P, for two points s and t contained in the polygon, their geodesic distance is the length of the shortest stpath within P. A geodesic disk of radius r centered at a point v 2 P is the set of points in P whose geodesic distance to v is at most r. We present a polynomial time 2approximation algorithm for nding a densest geodesic unit disk packing in P. Allowing arbitrary radii but constraining the number of disks to be k, we present a 4approximation algorithm for nding a packing in P with k geodesic disks whose minimum radius is maximized. We then turn our focus on coverings of P and present a 2approximation algorithm for covering P with k geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are NP hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius.

Activity >