Academic
Publications
Piercing Translates and Homothets of a Convex Body

Piercing Translates and Homothets of a Convex Body,10.1007/s00453-010-9410-4,Algorithmica,Adrian Dumitrescu,Minghui Jiang

Piercing Translates and Homothets of a Convex Body   (Citations: 1)
BibTex | RIS | RefWorks Download
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 of d. 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 et al. 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 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.
Journal: Algorithmica , vol. 61, no. 1, pp. 94-115, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: