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 # 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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1090/S0025-5718-09-02224-8 | MATHEMATICS OF COMPUTATION |
Keywords | DocType | Volume |
Lattice,Voronoi cell,Delone cell,covering radius,quantizer constant,lattice isomorphism problem,zonotope | Journal | 78 |
Issue | ISSN | Citations |
267 | 0025-5718 | 15 |
PageRank | References | Authors |
0.99 | 11 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mathieu Dutour Sikiric | 1 | 18 | 4.50 |
Achill Schürmann | 2 | 52 | 9.17 |
Frank Vallentin | 3 | 99 | 12.60 |