Piercing translates and homothets of a convex body

Details Piercing translates and homothets of a convex body Piercing translates and homothets of a convex body

2009-10-21

arxiv.org/abs/0910.4172v1

Computer Science

Computational Geometry

An earlier version of this manuscript appeared in ESA 2009

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Piercing translates and homothets of a convex body does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Piercing translates and homothets of a convex body, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Piercing translates and homothets of a convex body will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689441