On some covering problems in geometry
From MaRDI portal
Publication:2809209
DOI10.1090/PROC/12992zbMATH Open1341.52031arXiv1404.1691OpenAlexW2964310552MaRDI QIDQ2809209FDOQ2809209
Authors: Márton Naszódi 
Publication date: 27 May 2016
Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)
Abstract: We present a method to obtain upper bounds on covering numbers. As applications of this method, we reprove and generalize results of Rogers on economically covering Euclidean -space with translates of a convex body, or more generally, any measurable set. We obtain a bound for the density of covering the -sphere by rotated copies of a spherically convex set (or, any measurable set). Using the same method, we sharpen an estimate by Artstein--Avidan and Slomka on covering a bounded set by translates of another. The main novelty of our method is that it is not probabilistic. The key idea, which makes our proofs rather simple and uniform through different settings, is an algorithmic result of Lov'asz and Stein.
Full work available at URL: https://arxiv.org/abs/1404.1691
Recommendations
Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial aspects of packing and covering (05B40) Asymptotic theory of convex bodies (52A23)
Cites Work
- Entropy and asymptotic geometry of non-symmetric convex bodies
- On the ratio of optimal integral and fractional covers
- Title not available (Why is that?)
- Title not available (Why is that?)
- Matchings and covers in hypergraphs
- Title not available (Why is that?)
- A note on coverings
- Covering a sphere with spheres
- Covering space with convex bodies
- Covering spheres with spheres
- Fractional illumination of convex bodies
- On weighted covering numbers and the Levi-Hadwiger conjecture
- Weighted covering numbers of convex sets
- Covering the \(n\)-space by convex bodies and its chromatic number
- Illuminating sets of constant width
- Two combinatorial covering theorems
- A Note on Covering by Convex Bodies
- The symmetry function in a convex body
Cited In (17)
- On a problem about covering lines by squares
- A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space
- Covering the \(n\)-space by convex bodies and its chromatic number
- Approximate CVP_p in Time 2^{0.802 n}
- Covering compact metric spaces greedily
- On a relation between packing and covering densities of convex bodies
- Upper bounds for the chromatic numbers of Euclidean spaces with forbidden Ramsey sets
- ECONOMICAL COVERS WITH GEOMETRIC APPLICATIONS
- Chromatic numbers of spheres
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- Approximating set multi-covers
- Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl
- On the density of the thinnest covering of \(\mathbb{R}^n\)
- Flavors of translative coverings
- Regular random sections of convex bodies and the random quotient-of-subspace theorem
- Improved bounds for Hadwiger's covering problem via thin-shell estimates
- Spherical coverings and X-raying convex bodies of constant width
This page was built for publication: On some covering problems in geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2809209)
