Activity‎ > ‎

Packing and Covering of Polygons with Geodesic Disks

posted Jun 24, 2013, 6:13 PM by dongwoo park
 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.