On some covering problems in geometry

Naszódi, Márton

doi:10.1090/proc/12992

On some covering problems in geometry
HTML articles powered by AMS MathViewer

by Márton Naszódi PDF

Proc. Amer. Math. Soc. 144 (2016), 3555-3562 Request permission

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ász and Stein.

References

S. Artstein-Avidan and O. Raz, Weighted covering numbers of convex sets, Adv. Math. 227 (2011), no. 1, 730–744. MR 2782207, DOI 10.1016/j.aim.2011.02.009
Shiri Artstein-Avidan and Boaz A. Slomka, On weighted covering numbers and the levi-hadwiger conjecture, arXiv:1310.7892 [math] (2013-10).
Károly Böröczky Jr. and Gergely Wintsche, Covering the sphere by equal spherical balls, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 235–251. MR 2038476, DOI 10.1007/978-3-642-55566-4_{1}0
Ilya Dumer, Covering spheres with spheres, Discrete Comput. Geom. 38 (2007), no. 4, 665–679. MR 2365829, DOI 10.1007/s00454-007-9000-7
P. Erdős and C. A. Rogers, Covering space with convex bodies, Acta Arith. 7 (1961/62), 281–285. MR 149373, DOI 10.4064/aa-7-3-281-285
Z. Füredi and J.-H. Kang, Covering the $n$-space by convex bodies and its chromatic number, Discrete Math. 308 (2008), no. 19, 4495–4500. MR 2433777, DOI 10.1016/j.disc.2007.08.048
Gábor Fejes Tóth, A note on covering by convex bodies, Canad. Math. Bull. 52 (2009), no. 3, 361–365., DOI 10.4153/CMB-2009-039-x
Zoltán Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), no. 2, 115–206., DOI 10.1007/BF01864160
L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), no. 4, 383–390., DOI 10.1016/0012-365X(75)90058-8
Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002., DOI 10.1007/978-1-4613-0039-7
V. D. Milman and A. Pajor, Entropy and asymptotic geometry of non-symmetric convex bodies, Adv. Math. 152 (2000), no. 2, 314–335. MR 1764107, DOI 10.1006/aima.1999.1903
Márton Naszódi, Fractional illumination of convex bodies, Contrib. Discrete Math. 4 (2009), no. 2, 83–88. MR 2592425
C. A. Rogers, A note on coverings, Mathematika 4 (1957), 1–6. MR 90824, DOI 10.1112/S0025579300001030
C. A. Rogers, Covering a sphere with spheres, Mathematika 10 (1963), 157–164. MR 166687, DOI 10.1112/S0025579300004083
C. A. Rogers, Packing and covering, Cambridge Tracts in Mathematics and Mathematical Physics, No. 54, Cambridge University Press, New York, 1964. MR 0172183
Oded Schramm, Illuminating sets of constant width, Mathematika 35 (1988), no. 2, 180–189. MR 986627, DOI 10.1112/S0025579300015175
S. Stein, The symmetry function in a convex body, Pacific J. Math. 6 (1956), 145–148. MR 80321, DOI 10.2140/pjm.1956.6.145
S. K. Stein, Two combinatorial covering theorems, J. Combinatorial Theory Ser. A 16 (1974), 391–397. MR 340062, DOI 10.1016/0097-3165(74)90062-4