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 st-path 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 2-approximation 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 4-approximation 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 2-approximation 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 >