According to a classical result of Gr"unbaum, the transversal number of any family of pairwise-intersecting translates or homothets of a convex body in is bounded by a function of . Denote by (resp. ) the supremum of the ratio of the transversal number to the packing number over all families of translates (resp. homothets) of a convex body in . Kim et al. recently showed that is bounded by a function of for any convex body in , and gave the first bounds on for convex bodies in and on for convex bodies in the plane. Here we show that is also bounded by a function of for any convex body in , and present new or improved bounds on both and for various convex bodies in for all dimensions . 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.

生成讲解博客的中文版本

生成AI智能校验的中文版本