EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Boris Bukh iD, Jun Gao iD, Xizhi Liu iD, Oleg Pikhurko iD, Shumin Sun iD

Discrete & Computational Geometry · 2026-12 · 76 (4) · 2424-2442

DOI: 10.1007/s00454-026-00871-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete & Computational Geometry, online erschienen am 29.10.2026. Verfasst von Boris Bukh und 4 weiteren Autor:innen. Beteiligte Einrichtung: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, USA. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Simons Foundation, National Science Foundation, European Research Council.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 and extends this periodically) fails to work if the density is less than $$(1/2+o(1))n\ln n$$ ( 1 / 2 + o ( 1 ) ) n ln n ; in fact, this result remains true if we replace the ball by any convex body K . Also, we observe that a “worst” convex body K here is a cube, for which the covering density coming from random constructions is only $$(1+o(1))n\ln n$$ ( 1 + o ( 1 ) ) n ln n .

Schlagwörter

Stichwörter der Autor:innen

Convex bodiesCovering densityCovering multiplicityProbabilistic methodSphere coverings

Autor:innen und Institutionen

  • Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, USA.
  • Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100084, China.
  • School of Mathematical Sciences, University of Science and Technology of China, Hefei, China.
  • Mathematics Institute and DIMAP, University of Warwick, Coventry, UK.

ORCID-Profile: Boris Bukh, Jun Gao, Xizhi Liu, Oleg Pikhurko, Shumin Sun

Förderung

  • Simons Foundation
  • National Science Foundation
  • European Research Council
  • the Excellent Young Talents Program (Overseas) of the National Natural Science Foundation of China

Zitieren

APA

Bukh, B., Gao, J., Liu, X., Pikhurko, O., & Sun, S. (2026). Covering Large-Dimensional Euclidean Spaces by Random Translates of a Given Convex Body. Discrete & Computational Geometry, 76(4), 2424-2442. https://doi.org/10.1007/s00454-026-00871-5

Vancouver

Bukh B, Gao J, Liu X, Pikhurko O, Sun S. Covering Large-Dimensional Euclidean Spaces by Random Translates of a Given Convex Body. Discrete & Computational Geometry. 2026;76(4):2424-2442. doi:10.1007/s00454-026-00871-5

BibTeX
@article{Bukh2026,
  author = {Bukh, Boris and Gao, Jun and Liu, Xizhi and Pikhurko, Oleg and Sun, Shumin},
  title = {Covering Large-Dimensional Euclidean Spaces by Random Translates of a Given Convex Body},
  journal = {Discrete & Computational Geometry},
  year = {2026},
  volume = {76},
  number = {4},
  pages = {2424--2442},
  doi = {10.1007/s00454-026-00871-5}
}
Kostenlos starten →