Complexity and algorithms for computing Voronoi cells of lattices
| dc.creator | Sikiric, Mathieu Dutour | |
| dc.creator | Schuermann, Achill | |
| dc.creator | Vallentin, Frank | |
| dc.date | 2008-03-31 | |
| dc.date | 2008-09-24 | |
| dc.date.accessioned | 2026-07-07T13:10:50Z | |
| dc.date.available | 2026-07-07T13:10:50Z | |
| dc.description | 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. | |
| dc.description | 20 pages, 2 figures, 5 tables | |
| dc.identifier | https://arxiv.org/abs/0804.0036 | |
| dc.identifier | http://arxiv.org/abs/0804.0036 | |
| dc.identifier | Math. Comp. 267 (2009), 1713-1731 | |
| dc.identifier | doi:10.1090/S0025-5718-09-02224-8 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/229110 | |
| dc.subject | Metric Geometry | |
| dc.subject | Computational Geometry | |
| dc.subject | Information Theory | |
| dc.subject | Number Theory | |
| dc.subject | 11H56, 11H06, 11B1, 03D15, 52B55, 52B12 | |
| dc.title | Complexity and algorithms for computing Voronoi cells of lattices | |
| dc.type | text |