Complexity and algorithms for computing Voronoi cells of lattices
Mathematics of Computation , Volume 78 p. 1713- 1731
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 #P-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|
|MSC||Complexity of computation (including implicit computational complexity) (msc 03D15)|
|THEME||Logistics (theme 3)|
|Journal||Mathematics of Computation|
Dutour Sikiric, M, Schuermann, A, & Vallentin, F. (2009). Complexity and algorithms for computing Voronoi cells of lattices. Mathematics of Computation, 78, 1713–1731.