Given a polygon @math , for two points @math and @math contained in the polygon, their is the length of the shortest @math -path within @math . A of radius @math centered at a point @math is the set of points in @math whose geodesic distance to @math is at most @math . We present a polynomial time @math -approximation algorithm for finding a densest geodesic unit disk packing in @math . Allowing arbitrary radii but constraining the number of disks to be @math , we present a @math -approximation algorithm for finding a packing in @math with @math geodesic disks whose minimum radius is maximized. We then turn our focus on of @math and present a @math -approximation algorithm for covering @math with @math geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are @math -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.
Exact coverings of @math points in the plane with two Euclidean disks of minimum maximal radius, commonly referred to as the problem, has been heavily studied. The best deterministic algorithm runs in @math time @cite_37 and in @cite_6 an expected @math time algorithm is presented. For polygons, in @cite_39 a @math time algorithm for covering a convex polygon with two Euclidean disks of minimum maximal radius is presented.
@cite_37 @cite_6 @cite_39
2052051124 2006614694
We present an (O(n ^ 9 n) ) -time algorithm for computing the 2-center of a set S of n points in the plane (that is, a pair of congruent disks of smallest radius whose union covers S), improving the previous (O(n^2 n) ) -time algorithm of [10]. Improving on a recent breakthrough of Sharir, we find two minimum-radius circular disks covering a planar point set, in randomized expected time O(n log n).