Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Approximate Algorithm
Convex Body
Upper Bound
Subscribe
Academic
Publications
Piercing Translates and Homothets of a Convex Body
Piercing Translates and Homothets of a Convex Body,10.1007/s0045301094104,Algorithmica,Adrian Dumitrescu,Minghui Jiang
Edit
Piercing Translates and Homothets of a Convex Body
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Adrian Dumitrescu
,
Minghui Jiang
According to a classical result of Grünbaum, the transversal number τ(ℱ) of any family ℱ of pairwiseintersecting 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 constantfactor approximation algorithms for finding a minimumcardinality point set that pierces a set of translates or homothets of a convex body.
Journal:
Algorithmica
, vol. 61, no. 1, pp. 94115, 2011
DOI:
10.1007/s0045301094104
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
References
(29)
On Covering Problems of Rado
(
Citations: 2
)
Sergey Bereg
,
Adrian Dumitrescu
,
Minghui Jiang
Journal:
Algorithmica
, vol. 57, no. 3, pp. 538561, 2010
Piercing d Intervals
(
Citations: 11
)
Noga Alon
,
Beverly Sackler
Journal:
Discrete & Computational Geometry  DCG
, vol. 19, no. 3, pp. 333334, 1998
Piercing convex sets and the HadwigerDebrunner ()problem
(
Citations: 48
)
Noga Alon
,
Daniel J. Kleitman
Journal:
Advances in Mathematics  ADVAN MATH
, vol. 96, no. 1, pp. 103112, 1992
Maximum Area Independent Sets in Disk Intersection Graphs
(
Citations: 2
)
Sergey Bereg
,
Adrian Dumitrescu
,
Minghui Jiang
Journal:
International Journal of Computational Geometry and Applications  IJCGA
, vol. 20, no. 2, pp. 105118, 2010
Research problems in discrete geometry
(
Citations: 216
)
Peter Brass
,
William O. J. Moser
,
János Pach
Published in 2005.
Sort by:
Citations
(1)
Coloring translates and homothets of a convex body
(
Citations: 1
)
Adrian Dumitrescu
,
Minghui Jiang
Journal:
Computing Research Repository  CORR
, vol. abs/1008.1, 2010