Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Complexity and algorithms for computing Voronoi cells of lattices


Authors: Mathieu Dutour Sikiric, Achill Schürmann and Frank Vallentin
Journal: Math. Comp. 78 (2009), 1713-1731
MSC (2000): Primary 03D15, 11H56, 11H06, 11E10, 52B55, 52B12
DOI: https://doi.org/10.1090/S0025-5718-09-02224-8
Published electronically: February 6, 2009
MathSciNet review: 2501071
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 $ \char93 \operatorname{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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 03D15, 11H56, 11H06, 11E10, 52B55, 52B12

Retrieve articles in all journals with MSC (2000): 03D15, 11H56, 11H06, 11E10, 52B55, 52B12


Additional Information

Mathieu Dutour Sikiric
Affiliation: Rudjer Bosković Institute, Bijenicka 54, 10000 Zagreb, Croatia
Email: mdsikir@irb.hr

Achill Schürmann
Affiliation: Mathematics Department, University of Magdeburg, 39106 Magdeburg, Germany
Email: achill@math.uni-magdeburg.de

Frank Vallentin
Affiliation: Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
Email: f.vallentin@cwi.nl

DOI: https://doi.org/10.1090/S0025-5718-09-02224-8
Keywords: Lattice, Voronoi cell, Delone cell, covering radius, quantizer constant, lattice isomorphism problem, zonotope
Received by editor(s): April 7, 2008
Received by editor(s) in revised form: August 19, 2008
Published electronically: February 6, 2009
Additional Notes: The work of the first author was supported by the Croatian Ministry of Science, Education and Sport under contract 098-0982705-2707
The second and third authors were supported by the Deutsche Forschungsgemeinschaft (DFG) under grant SCHU 1503/4-2.
The third author was also supported by the Netherlands Organization for Scientific Research under grant NWO 639.032.203. \indent All three authors thank the Hausdorff Research Institute for Mathematics for its hospitality and support.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.