Covering Spheres with Spheres

Abstract Given a sphere of any radius r in an n-dimensional Euclidean space, we study the coverings of this sphere with solid spheres of radius one. Our goal is to design a covering of the lowest covering density, which defines the average number of solid spheres covering a point in a bigger sphere. For growing dimension n, we design a covering that gives the covering density of order (nln n)/2 for a sphere of any radius r>1 and a complete Euclidean space. This new upper bound reduces two times the order nln n established in the classic Rogers bound.

• Publication year

  2006

• Venue

  Discrete & Computational Geometry

• Publication date

  2006-05-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-007-9000-7arXiv math/0606002
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Covering spheres and balls with smaller balls

  2006influential reference
• Covering a Ball with Smaller Equal Balls in ℝn

  2005cited by this paper
• Finite Packing and Covering

  2004cited by this paper
• Covering the Sphere by Equal Spherical Balls

  2003cited by this paper
• Sphere Packings, Lattices and Groups

  1987cited by this paper
• New Results in the Theory of Packing and Covering

  1983cited by this paper
• Covering a sphere with spheres

  1963cited by this paper
• Covering space with equal spheres

  1959cited by this paper
• A note on coverings

  1957cited by this paper

• Taming Latency-Memory Trade-Off in MoE-Based LLM Serving via Fine-Grained Expert Offloading

  2025cites this paper
• New upper bound for lattice covering by spheres

  2025cites this paper
• Covering large-dimensional Euclidean spaces by random translates of a given convex body

  2025influential citation
• Minimal dispersion on the sphere

  2025influential citation
• MoE-Infinity: Efficient MoE Inference on Personal Machines with Sparsity-Aware Expert Cache

  2024cites this paper
• Maximum Mean Discrepancy Meets Neural Networks: The Radon-Kolmogorov-Smirnov Test

  2023cites this paper
• A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications

  2023cites this paper
• Integral Probability Metrics Meet Neural Networks: The Radon-Kolmogorov-Smirnov Test

  2023cites this paper
• Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual

  2023cites this paper
• Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries

  2022cites this paper
• Illuminating spiky balls and cap bodies

  2022cites this paper
• Packing and covering in higher dimensions

  2022cites this paper
• Democratic Source Coding: An Optimal Fixed-Length Quantization Scheme for Distributed Optimization Under Communication Constraints

  2021cites this paper
• Theoretical Bounds on Data Requirements for the Ray-Based Classification

  2021cites this paper
• On a relationship between the Hausdorff measure and the density of the thinnest covering of Rn

  2021cites this paper
• Efficient Randomized Subspace Embeddings for Distributed Optimization Under a Communication Budget

  2021cites this paper
• Estimation of Monotone Multi-Index Models

  2020cites this paper
• Spherical coverings and X-raying convex bodies of constant width

  2020cites this paper
• Optimal Gradient Compression for Distributed and Federated Learning

  2020cites this paper
• A five distance theorem for Kronecker sequences.

  2020cites this paper
• Convex Optimization Techniques for Geometric Covering Problems

  2019influential citation
• RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization

  2019cites this paper
• On sound ranging in proper metric spaces

  2018cites this paper
• On the Minimal Overcompleteness Allowing Universal Sparse Representation

  2018cites this paper
• A ug 2 01 8 On sound ranging in proper metric spaces

  2018cites this paper
• Covering a Ball by Smaller Balls

  2018cites this paper
• FULL-VIEW COVERAGE PROBLEMS IN CAMERA SENSOR NETWORKS

  2017cites this paper
• Covering compact metric spaces greedily

  2017influential citation
• Eigenvector Under Random Perturbation: A Nonasymptotic Rayleigh-Schr\"{o}dinger Theory

  2017influential citation
• Optimization Based Methods for Partially Observed Chaotic Systems

  2017cites this paper
• Distributed learning with infinitely many hypotheses

  2016cites this paper
• 2 PACKING AND COVERING

  2016cites this paper
• Flavors of Translative Coverings

  2016cites this paper
• Quantum State Complexity of Formal Languages

  2015cites this paper
• Dictionary descent in optimization

  2015influential citation
• On some covering problems in geometry

  2014cites this paper
• Nonnegative Sparse PCA with Provable Guarantees

  2014cites this paper
• Incoherent systems and coverings in finite dimensional Banach spaces

  2014cites this paper
• Некогерентные системы и покрытия в конечномерных банаховых пространствах@@@Íåêîãåðåíòíûå ñèñòåìû è ïîêðûòèÿ â êîíå÷íîìåðíûõ áàíàõîâûõ ïðîñòðàíñòâàõ

  2014cites this paper
• Covering a convex 3D polytope by a minimal number of congruent spheres

  2014cites this paper
• Compression for quadratic similarity queries via shape-gain quantizers

  2014cites this paper
• On-Line Video Motion Estimation by Invariant Receptive Inputs

  2014cites this paper
• Compression for Quadratic Similarity Queries: Finite Blocklength and Practical Schemes

  2014cites this paper
• Compression for Quadratic Similarity Queries

  2013cites this paper
• Lipschitz selections of the diametric completion mapping in Minkowski spaces

  2013cites this paper
• Proofs on Ball-Polyhedra and Spindle Convex Bodies

  2013cites this paper
• Quadratic Similarity Queries on Compressed Data

  2013influential citation
• Partial Covering of a Sphere with Random Number of Spherical Caps

  2013cites this paper
• Spherical coverage verification

  2011cites this paper
• Illuminating Spindle Convex Bodies and Minimizing the Volume of Spherical Sets of Constant Width

  2011cites this paper
• Covering a sphere with caps: Rogers bound revisited

  2011cites this paper
• Bounding the uncertainity in nonlinear robust model predictive control using sphere covering

  2011cites this paper
• Wireless Broadcast with Network Coding: Energy Efficiency, Optimality and Coding Gain in Lossless Wireless Networks

  2009cites this paper
• MoE-Infinity: Offloading-Efficient MoE Model Serving

  year unknowncites this paper