2009/10/21 by Adrian Dumitrescu, Dumitrescu, Adrian, Minghui Jiang +1 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.0910.4172
An earlier version of this manuscript appeared in ESA 2009
arxiv created 2009/10/21 · arxiv updated 2009/12/01
According to a classical result of Grünbaum, the transversal number τ(\F) of any family \F of pairwise-intersecting translates or homothets of a convex body C in \RRd is bounded by a function of d. Denote by α(C) (resp. β(C)) the supremum of the ratio of the transversal number τ(\F) to the packing number ν(\F) over all families \F of translates (resp. homothets) of a convex body C in \RRd. Kim et al. recently showed that α(C) is bounded by a function of d for any convex body C in \RRd, and gave the first bounds on α(C) for convex bodies C in \RRd 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 \RRd, and present new or improved bounds on both α(C) and β(C) for various convex bodies C in \RRd for all dimensions d. 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.