SCIENCE@home

Piercing Translates and Homothets of a Convex Body

A. Dumitrescu,Minghui Jiang

Published 2009 in Algorithmica

ABSTRACT

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-45 of 45 references · Page 1 of 1

CITED BY

Showing 1-19 of 19 citing papers · Page 1 of 1