Reformulation of the Covering and Quantizer Problems as Ground States of Interacting Particles

Abstract

We reformulate the covering and quantizer problems as the determination of the ground states of interacting particles in ${\mathbb{R}}^d$ that generally involve single-body, two-body, three-body, and higher-body interactions. This is done by linking the covering and quantizer problems to certain optimization problems involving the "void" nearest-neighbor functions that arise in the theory of random media and statistical mechanics. These reformulations, which again exemplifies the deep interplay between geometry and physics, allow one now to employ theoretical and numerical optimization techniques to analyze and solve these energy minimization problems. The covering and quantizer problems have relevance in numerous applications, including wireless communication network layouts, the search of high-dimensional data parameter spaces, stereotactic radiation therapy, data compression, digital communications, meshing of space for numerical analysis, and coding and cryptography, among other examples. The connections between the covering and quantizer problems and the sphere-packing and number-variance problems are discussed. We also show that disordered saturated sphere packings provide relatively thin (economical) coverings and may yield thinner coverings than the best known lattice coverings in sufficiently large dimensions. In the case of the quantizer problem, we derive improved upper bounds on the quantizer error using sphere-packing solutions, which are generally substantially sharper than an existing upper bound in low to moderately large dimensions. We also demonstrate that disordered saturated sphere packings yield relatively good quantizers. Finally, we remark on possible applications of our results for the detection of gravitational waves.

52 pages, 9 figures, 8 tables; Changes reflect improvements made during the refereeing process

References in corpus (10)

• Classical Disordered Ground States: Super-Ideal Gases, and Stealth and Equi-Luminous Materials
• Soft Spheres Make More Mesophases
• Point processes in arbitrary dimension from fermionic gases, random matrix theory, and number theory
• Template-based searches for gravitational waves: efficient lattice covering of flat parameter spaces
• Divide and concur: A general approach to constraint satisfaction
• Exactly Solvable Disordered Sphere-Packing Model in Arbitrary-Dimension Euclidean Spaces
• Computational Approaches to Lattice Packing and Covering Problems
• Estimates of the optimal density and kissing number of sphere packings in high dimensions
• New Duality Relations for Classical Ground States
• A hierarchical search for gravitational waves from supermassive black hole binary mergers

Cited by in corpus (32)

• Hyperuniform States of Matter
• Hyperuniform long-range correlations are a signature of disordered jammed hard-particle packings
• Basic Understanding of Condensed Phases of Matter via Packing Models
• Precise Algorithm to Generate Random Sequential Addition of Hard Hyperspheres at Saturation
• Transport, Geometrical and Topological Properties of Stealthy Disordered Hyperuniform Two-Phase Systems
• Hyperuniformity, quasi-long-range correlations, and void-space constraints in maximally random jammed particle packings. I. Polydisperse spheres
• Anomalous local coordination, density fluctuations, and void statistics in disordered hyperuniform many-particle ground states
• Improved reconstructions of random media using dilation and erosion processes
• Local Number Fluctuations in Hyperuniform and Nonhyperuniform Systems: Higher-Order Moments and Distribution Functions
• Dimension reduction techniques for the minimization of theta functions on lattices
• Effect of Dimensionality on the Percolation Thresholds of Various $d$-Dimensional Lattices
• Characterization of Maximally Random Jammed Sphere Packings. III. Transport and Electromagnetic Properties via Correlation Functions
• Characterization of Maximally Random Jammed Sphere Packings: II. Correlation Functions and Density Fluctuations
• Optimal Filling of Shapes
• Dynamic Measure of Hyperuniformity and Nonhyperuniformity in Heterogeneous Media via the Diffusion Spreadability
• Critical pore radius and transport properties of disordered hard- and overlapping-sphere models
• Gap Sensitivity Reveals Universal Behaviors in Optimized Photonic Crystal and Disordered Networks
• On the best lattice quantizers
• An Efficient Linear Programming Algorithm to Generate the Densest Lattice Sphere Packings
• High-dimensional generalizations of the kagome and diamond crystals and the decorrelation principle for periodic sphere packings
• Local order metrics for many-particle systems across length scales
• Low-temperature statistical mechanics of the QuanTizer problem: fast quenching and equilibrium cooling of the three-dimensional Voronoi Liquid
• Random Sequential Covering
• Glued lattices are better quantizers than $K_{12}$
• Potential theory with multivariate kernels
• Multifunctional Hyperuniform Cellular Networks: Optimality, Anisotropy and Disorder
• Dynamic Space Packing
• Diffusion Spreadability as a Probe of the Microstructure of Complex Media Across Length Scales
• Random sequential covering of a one-dimensional lattice by $k$-mers
• Defects and Frustration in the Packing of Soft Balls
• Can one hear the shape of a crystal?
• Performance of Random Template Banks