Zurück zu den Preprints des Jahres 2008


2008-19

Complexity and algorithms for computing Voronoi cells of lattices

by Mathieu Dutour Sikiric and Achill Schürmann and Frank Vallentin.


Series: 2008-19, Preprints

MSC:
03D15 Complexity of computation (including implicit computational complexity)
11H56 Automorphism groups of lattices
11H06 Lattices and convex bodies
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