Computational approaches to lattice packing and covering problems

DOI10.1007/S00454-005-1202-2zbMATH Open1091.52009arXivmath/0403272OpenAlexW2119637517MaRDI QIDQ818684FDOQ818684

Authors: Achill Schürmann, Frank Vallentin 

Publication date: 21 March 2006

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We describe algorithms which address two classical problems in lattice geometry: the lattice covering and the simultaneous lattice packing-covering problem. Theoretically our algorithms solve the two problems in any fixed dimension d in the sense that they approximate optimal covering lattices and optimal packing-covering lattices within any desired accuracy. Both algorithms involve semidefinite programming and are based on Voronoi's reduction theory for positive definite quadratic forms, which describes all possible Delone triangulations of Z^d. In practice, our implementations reproduce known results in dimensions d <= 5 and in particular solve the two problems in these dimensions. For d = 6 our computations produce new best known covering as well as packing-covering lattices, which are closely related to the lattice (E6)*. For d = 7, 8 our approach leads to new best known covering lattices. Although we use numerical methods, we made some effort to transform numerical evidences into rigorous proofs. We provide rigorous error bounds and prove that some of the new lattices are locally optimal.

Full work available at URL: https://arxiv.org/abs/math/0403272

Recommendations

• A Note on Lattice Packings via Lattice Refinements
• Computational geometry of positive definite quadratic forms. Polyhedral reduction theories, algorithms, and applications
• Complexity and algorithms for computing Voronoi cells of lattices
• Covering radius of two-dimensional lattices
• scientific article; zbMATH DE number 863488

zbMATH Keywords

coveringpackingDelone triangulationdeterminant maximization problemsemidefinite programming problemVoronoi's reduction theory

Mathematics Subject Classification ID

Semidefinite programming (90C22) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Cited In (18)

• Upper bounds on chromatic number of \(\mathbb{E}^n\) in low dimensions
• Random sequential covering
• Application of an idea of Voronoĭ to lattice zeta functions
• When is the ball a local pessimum for covering?
• Application of an idea of Voronoĭ to lattice packing
• A generalization of Voronoi's reduction theory and its application
• Lattice packing and covering of convex bodies
• Computational geometry of positive definite quadratic forms. Polyhedral reduction theories, algorithms, and applications
• Uniformity of point samples in metric spaces using gap ratio
• On approximating the covering radius and finding dense lattice subspaces
• Complexity and algorithms for computing Voronoi cells of lattices
• \(\varepsilon\)-coverings of Hölder-Zygmund type spaces on data-defined manifolds
• Inhomogeneous extreme forms
• On the Voronoi conjecture for combinatorially Voronoi parallelohedra in dimension 5
• Simultaneous packing and covering in sequence spaces
• Covering radius of two-dimensional lattices
• Multiple covers with balls. I: Inclusion-exclusion
• Covering and packing with spheres by diagonal distortion in \(\mathbb R^n\)

This page was built for publication: Computational approaches to lattice packing and covering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q818684)