caa a22 4500 445805110 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9410-4 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9410-4 Piercing Translates and Homothets of a Convex Body [Elektronische Daten] [Adrian Dumitrescu, Minghui Jiang] According to a classical result of Grünbaum, the transversal number τ(ℱ) of any family ℱ of pairwise-intersecting translates or homothets of a convex body C in ℝd is bounded by a function ofd. Denote by α(C) (resp.β(C)) the supremum of the ratio of the transversal number τ(ℱ) to the packing number ν(ℱ) over all finite families ℱ of translates (resp.homothets) of a convex body C inℝd. Kim etal. recently showed that α(C) is bounded by a function of d for any convex body C inℝd, and gave the first bounds on α(C) for convex bodies C in ℝd and on β(C) for convex bodies C in the plane. Here we show that β(C) is also bounded by a function of d for any convex body C in ℝd, and present new or improved bounds on both α(C) and β(C) for various convex bodies C in ℝd for all dimensionsd. Our techniques explore interesting inequalities linking the covering and packing densities of a convex body. Our methods for obtaining upper bounds are constructive and lead to efficient constant-factor approximation algorithms for finding a minimum-cardinality point set that pierces a set of translates or homothets of a convex body. Springer Science+Business Media, LLC, 2010 Geometric transversals nationallicence Gallai-type problems nationallicence Packing and covering nationallicence Approximation algorithms nationallicence Dumitrescu Adrian Department of Computer Science, University of Wisconsin-Milwaukee, 53201-0784, Milwaukee, WI, USA aut Jiang Minghui Department of Computer Science, Utah State University, 84322-4205, Logan, UT, USA aut Algorithmica Springer-Verlag 61/1(2011-09-01), 94-115 0178-4617 61:1<94 2011 61 453 https://doi.org/10.1007/s00453-010-9410-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9410-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dumitrescu Adrian Department of Computer Science, University of Wisconsin-Milwaukee, 53201-0784, Milwaukee, WI, USA aut NATIONALLICENCE 700 1- Jiang Minghui Department of Computer Science, Utah State University, 84322-4205, Logan, UT, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 94-115 0178-4617 61:1<94 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer