Zurück zu den Preprints des Jahres 2004


2004-07

Computational Approaches to Lattice Packing and Covering Problems

by Achill Schürmann, Frank Vallentin.


Series: 2004-07, Preprints

MSC:
11H31 Lattice packing and covering

Abstract:
We describe algorithms which solve two classical problems in lattice geometry for any fixed dimension d: the lattice covering and the simultaneous lattice packing-covering problem. 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$. Our implementations verify all known results in dimensions $d <= 5$. Beyond that we attain complete lists of all locally optimal solutions for $d = 5$. For
$d = 6$ our computations produce new best known covering as well as packing-covering lattices which are closely related to the lattice $E_6^*$.

Keywords:
lattice, packing, covering, quadratic forms, semidefinite programming