Complexity and algorithms for computing Voronoi cells of lattices - Mathematics > Metric GeometryReportar como inadecuado




Complexity and algorithms for computing Voronoi cells of lattices - Mathematics > Metric Geometry - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In this paper we are concerned with finding the vertices of the Voronoi cellof a Euclidean lattice. Given a basis of a lattice, we prove that computing thenumber of vertices is a #P-hard problem. On the other hand we describe analgorithm for this problem which is especially suited for low dimensional saydimensions at most 12 and for highly-symmetric lattices. We use ourimplementation, which drastically outperforms those of current computer algebrasystems, to find the vertices of Voronoi cells and quantizer constants of someprominent lattices.



Autor: Mathieu Dutour Sikiric, Achill Schuermann, Frank Vallentin

Fuente: https://arxiv.org/







Documentos relacionados