Reformulation of the covering and quantizer problems as ground states of interacting particles

作     者：S. Torquato 

作者机构：[]Department of Chemistry Princeton University Princeton New Jersey 08544 USA Department of Physics Princeton University Princeton New Jersey 08544 USA Princeton Center for Theoretical Science Princeton University Princeton New Jersey 08544 USA Program in Applied and Computational Mathematics Princeton University Princeton New Jersey 08544 USA and Princeton Institute for the Science and Technology of Materials Princeton University Princeton New Jersey 08544 USA 

出 版 物：《Physical Review E》 (物理学评论E辑：统计、非线性和软体物理学)

年 卷 期：2010年第82卷第5期

页      面：056109-056109页

核心收录：

学科分类：07[理学] 070203[理学-原子与分子物理] 0702[理学-物理学] 

基　　金：Office of Basic Energy Sciences  U.S. Department of Energy [DE-FG02-04-ER46108] 

主　　题：Ground state 

摘      要：It is known that the sphere-packing problem and the number-variance problem (closely related to an optimization problem in number theory) can be posed as energy minimizations associated with an infinite number of point particles in d-dimensional Euclidean space Rd interacting via certain repulsive pair potentials. We reformulate the covering and quantizer problems as the determination of the ground states of interacting particles in Rd 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 exemplify 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. In the first three space dimensions, the best known solutions of the sphere-packing and number-variance problems (or their “dual solutions) are directly related to those of the covering and quantizer problems, but such relationships may or may not exist for d≥4, depending on the peculiarities of the dimensions involved. Our reformulation sheds light on the reasons for these similarities and differences. 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 q