On some covering problems in geometry

DOI10.1090/PROC/12992MaRDI QIDQ2809209zbMATH OpenOpenAlexFDO

Authors Márton Naszódi

Publication date 27 May 2016

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.1691, http://real.mtak.hu/40254/1/AsAppearedCovering.pdf

zbMATH Keywords

densitycoveringspherical capset-coverRogers' bound

Mathematics Subject Classification ID

Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial aspects of packing and covering (05B40) Asymptotic theory of convex bodies (52A23)

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 $n$-space with translates of a convex body, or more generally, any measurable set. We obtain a bound for the density of covering the $n$-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.

Recommendations

• A Note on Covering by Convex Bodies
• Flavors of translative coverings
• Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl
• On coverings of spheres by convex sets
• Covering spheres with spheres

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3282420 (Why is no real title available?)
• scientific article; zbMATH DE number 2209717 (Why is no real title available?)
• A Note on Covering by Convex Bodies
• A note on coverings
• Covering a sphere with spheres
• Covering space with convex bodies
• Covering spheres with spheres
• Covering the n-space by convex bodies and its chromatic number
• Entropy and asymptotic geometry of non-symmetric convex bodies
• Fractional illumination of convex bodies
• Illuminating sets of constant width
• Matchings and covers in hypergraphs
• On the ratio of optimal integral and fractional covers
• On weighted covering numbers and the Levi-Hadwiger conjecture
• The symmetry function in a convex body
• Two combinatorial covering theorems
• Weighted covering numbers of convex sets

Cited in

(17)

• Spherical coverings and X-raying convex bodies of constant width
• A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space
• On a problem about covering lines by squares
• Covering the n-space by convex bodies and its chromatic number
• Covering compact metric spaces greedily
• Approximate CVP_p in Time 2^{0.802 n}
• 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
• On the density of the thinnest covering of \(\mathbb{R}^n\)
• Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl
• 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

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)