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
Additional Information
- Márton Naszódi
- Affiliation: Department of Geometry, Lorand Eötvös University, Pázmány Péter Sétány 1/C Budapest, Hungary 1117
- MR Author ID: 729840
- Email: marton.naszodi@math.elte.hu
- Received by editor(s): March 30, 2015
- Received by editor(s) in revised form: October 1, 2015
- Published electronically: January 26, 2016
- Additional Notes: The author acknowledges the support of the János Bolyai Research Scholarship of the Hungarian Academy of Sciences, and the Hung. Nat. Sci. Found. (OTKA) grant PD104744.
- Communicated by: Patricia L. Hersh
- © Copyright 2016 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 144 (2016), 3555-3562
- MSC (2010): Primary 52C17, 05B40, 52A23
- DOI: https://doi.org/10.1090/proc/12992
- MathSciNet review: 3503722