Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Complexity and algorithms for computing Voronoi cells of lattices
HTML articles powered by AMS MathViewer

by Mathieu Dutour Sikirić, Achill Schürmann and Frank Vallentin PDF
Math. Comp. 78 (2009), 1713-1731 Request permission

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 $\#\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
Similar Articles
Additional Information
  • Mathieu Dutour Sikirić
  • 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
  • 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. All three authors thank the Hausdorff Research Institute for Mathematics for its hospitality and support.
  • © Copyright 2009 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • 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
  • MathSciNet review: 2501071