Covering Large-Dimensional Euclidean Spaces by Random Translates of a Given Convex Body

Abstract

Abstract Determining the minimum density of a covering of $$\mathbb {R}^{n}$$ R n by Euclidean unit balls as $$n\rightarrow \infty $$ n → ∞ is a major open problem, with the best known results being the lower bound of $$\left( \textrm{e}^{-3/2}+o(1)\right) n$$ e - 3 / 2 + o ( 1 ) n by Coxeter, Few and Rogers [ Mathematika 6 , 1959] and the upper bound of $$\left( 1/2+o(1) \right) n \ln n$$ 1 / 2 + o ( 1 ) n ln n by Dumer [ Discrete Comput. Geom. 38 , 2007]. We prove that there are ball coverings of $$\mathbb {R}^n$$ R n attaining the asymptotically best known density $$\left( 1/2+ o(1)\right) n \ln n$$ 1 / 2 + o ( 1 ) n ln n such that, additionally, every point of $$\mathbb {R}^n$$ R n is covered at most $$\left( 1.79556... + o(1)\right) n \ln n$$ 1.79556 . . . + o ( 1 ) n ln n times. This strengthens the result of Erdős and Rogers [ Acta Arith. 7 , 1961/62] who had the maximum multiplicity at most $$\left( \textrm{e} + o(1)\right) n \ln n$$ e + o ( 1 ) n ln n . On the other hand, we show that the method that was used for the best known ball coverings (when one takes a random subset of centres in a fundamental domain of a suitable lattice in $$\mathbb {R}^n$$ R n

The authors' abstract, as published at the source. Discrete & Computational Geometry, 2026 · DOI ↗