Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, April 17, 2014 |
| Time | 11:00 am |
| Concludes | 12:00 pm |
| Location | Gould-Simpson 906 |
| Details | Please join us for coffee and light refreshments at 10:45am in the 9th floor atrium. Faculty Host: Stephen Kobourov |
| Speaker | Ivo Vigan |
| Title | Ph.D. Candidate |
| Affiliation | Graduate Center of CUNY |
Packing and Covering a Polygon with Geodesic Disks
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 in 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 finding 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 finding 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. In the context of barrier coverage, we present a 2-approximation for covering the polygon boundary with geodesic unit disks. 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.
Biography
Ivo Vigan received his MSc degree in Computer Science at ETH Zürich in 2009. The same year he started work on PhD in Computational Geometry at the Graduate Center of CUNY under the supervision of Professor Peter Brass. He has worked on problems such as separating a set of points with few disks, packing three space with thin tori, or extending the idea of orthogonal range searching by not only reporting the points in a query window, but by computing some extent measures, such as their width or the radius of the smallest enclosing disk.