08-19
Complexity and algorithms for computing Voronoi cells of lattices
by Mathieu Dutour Sikiric and Achill Schürmann and Frank Vallentin
Preprint series: 08-19, Preprints
- MSC:
- 03D15 Complexity of computation, See also {68Q15}
- 11H56 Automorphism groups of lattices
- 11H06 Lattices and convex bodies, See also {11P21, 52C05, 52C07}
- 52B55 Computational aspects related to convexity, {For computational geometry and algorithms, See 68Q20, 68Q25, 68U05; for numerical algorithms, See 65Yxx}
- 52B12 Special polytopes (linear programming, centrally symmetric, etc.)
Abstract: In this paper we are concerned with finding the vertices of the Voronoi cell of a Euclidean lattice. Given a basis of a lattice, we prove that computing the number of vertices is a \sharpp-hard problem. On the other hand we describe an algorithm for this problem which is especially suited for low dimensional (say dimensions at most $12$) and for highly-symmetric lattices. We use our implementation, which drastically outperforms those of current computer algebra systems, to find the vertices of Voronoi cells and quantizer constants of some prominent lattices.
Keywords: lattice, Voronoi cell, Delone cell, covering radius, quantizer constant, lattice isomorphism problem, zonotope
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.