| Reformulation of the covering and quantizer problems as ground states of interacting particles. | |
| | |
MedLine Citation:
|
PMID: 21230547 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
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 R(d) interacting via certain repulsive pair potentials. We reformulate the covering and quantizer problems as the determination of the ground states of interacting particles in 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 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 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. |
| | |
Authors:
|
S Torquato |
Related Documents
:
|
22535327 - User interaction in smart ambient environment targeted for senior citizen. 21300257 - Controlled tooth movement to correct an iatrogenic problem. 19593817 - The agatston urban nutrition initiative: working to reverse the obesity epidemic throug... 21234487 - Formation of chiral mesostructured porphyrin-silica hybrids. 563507 - Simulated patients as a learning resource in the study of reproductive medicine. 10961197 - Survival by aids defining condition in rural uganda. |
Publication Detail:
|
Type: Journal Article Date: 2010-11-11 |
Journal Detail:
|
Title: Physical review. E, Statistical, nonlinear, and soft matter physics Volume: 82 ISSN: 1550-2376 ISO Abbreviation: Phys Rev E Stat Nonlin Soft Matter Phys Publication Date: 2010 Nov |
Date Detail:
|
Created Date: 2011-01-14 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101136452 Medline TA: Phys Rev E Stat Nonlin Soft Matter Phys Country: United States |
Other Details:
|
Languages: eng Pagination: 056109 Citation Subset: - |
Affiliation:
|
Department of Chemistry, Princeton University, Princeton, New Jersey 08544, USA. torquato@electron.princeton.edu |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Aging of the frictional properties induced by temperature variations.
Next Document: Spectral dimensions of hierarchical scale-free networks with weighted shortcuts.