In this note we prove that for any compact subset S of a Busemann surface @math (S,d) (in particular, for any simple polygon with geodesic metric) and any positive number @math ź, the minimum number of closed balls of radius @math ź with centers at @math S and covering the set S is at most 19 times the maximum number of disjoint closed balls of radius @math ź centered at points of S: @math ź(S)≤ź(S)≤19ź(S), where @math ź(S) and @math ź(S) are the covering and the packing numbers of S by @math ź-balls. Busemann surfaces represent a far-reaching generalization not only of simple polygons, but also of Euclidean and hyperbolic planes and of all planar polygonal complexes of global non-positive curvature. Roughly speaking, a Busemann surface is a geodesic metric space homeomorphic to @math R2 in which the distance function is convex.
Due to this analogy, one can formulate the previous question about @math for their continuous counterparts @math --- polygons in @math endowed with the (intrinsic) geodesic metric. It turns out that this question was not yet considered even for simple polygons (in this case, only a factor 2 approximation algorithm for packing number was recently given in @cite_13 ). The geodesic metric on simple polygons was studied in several papers in connection with algorithmic problems. In particular, in was shown in @cite_23 , that balls are convex, implying that simple polygons are Busemann spaces. In this paper, we consider the relationship between the packing and covering numbers not only for simple polygons in the Euclidean or hyperbolic planes but also for (compact subsets of) general Busemann surfaces.
@cite_13 @cite_23
2407537893 1975883249
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. The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon withn vertices in timeO(n logn).