Complexity and algorithms for computing Voronoi cells of lattices

Dutour Sikirić, Mathieu; Schürmann, Achill; Vallentin, Frank

doi:10.1090/S0025-5718-09-02224-8

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;

Math. Comp. 78 (2009), 1713-1731

DOI: https://doi.org/10.1090/S0025-5718-09-02224-8

Published electronically: February 6, 2009

PDF | 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

Erik Agrell and Thomas Eriksson, Optimization of lattices for quantization, IEEE Trans. Inform. Theory 44 (1998), no. 5, 1814–1828. MR 1664114, DOI 10.1109/18.705561
M. M. Anzin, On the density of a lattice covering for $n=11$ and $n=14$, Uspekhi Mat. Nauk 57 (2002), no. 2(344), 187–188 (Russian); English transl., Russian Math. Surveys 57 (2002), no. 2, 407–409. MR 1918199, DOI 10.1070/RM2002v057n02ABEH000501
M. M. Anzin, On the density of the lattice covering for $n=13$ and $n=15$, Mat. Zametki 79 (2006), no. 5, 781–784 (Russian); English transl., Math. Notes 79 (2006), no. 5-6, 721–725. MR 2249136, DOI 10.1007/s11006-006-0082-y
David Avis, A C implementation of the reverse search vertex enumeration algorithm, Sūrikaisekikenkyūsho K\B{o}kyūroku 872 (1994), 16–29. Computational geometry and discrete geometry (Japanese) (Kyoto, 1993). MR 1330479
E. P. Baranovskiĭ, The perfect lattices $\Gamma (\mathfrak {A}^n)$, and the covering density of $\Gamma (\mathfrak {A}^9)$, European J. Combin. 15 (1994), no. 4, 317–323. MR 1279070, DOI 10.1006/eujc.1994.1036
Norman Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1997), no. 6, 641–682. MR 1468054, DOI 10.1112/S0024609397003305
D. Bremner, M. Dutour Sikirić, A. Schürmann, Polyhedral representation conversion up to symmetries, preprint, September 2007, arXiv:math/0702239v2 [math.MG].
Benno Büeler, Andreas Enge, and Komei Fukuda, Exact volume computation for polytopes: a practical study, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 131–154. MR 1785296
T. Christof, A. Löbel, PORTA: Polyhedron representation transformation algorithm (ver 1.3.1), 1997, http://www.zib.de/Optimization/Software/Porta/.
T. Christof and G. Reinelt, Combinatorial optimization and small polytopes, Top 4 (1996), no. 1, 1–64. With discussion. MR 1404262, DOI 10.1007/BF02568602
John H. Conway and Neil J. A. Sloane, The cell structures of certain lattices, Miscellanea mathematica, Springer, Berlin, 1991, pp. 71–107. MR 1131118
J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups, 3rd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, Springer-Verlag, New York, 1999. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. MR 1662447, DOI 10.1007/978-1-4757-6568-7
H. S. M. Coxeter, Extreme forms, Canad. J. Math. 3 (1951), 391–441. MR 44580, DOI 10.4153/cjm-1951-045-8
Michel Deza and Viatcheslav Grishukhin, Delaunay polytopes of cut lattices, Linear Algebra Appl. 226/228 (1995), 667–685. MR 1344592, DOI 10.1016/0024-3795(95)00240-R
Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR 1460488, DOI 10.1007/978-3-642-04295-9
I. Dinur, G. Kindler, R. Raz, and S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, Combinatorica 23 (2003), no. 2, 205–243. MR 2001908, DOI 10.1007/s00493-003-0019-y
M. Dutour Sikirić, Polyhedral, 2008, http://www.liga.ens.fr/~dutour/polyhedral
Mathieu Dutour Sikirić, Achill Schürmann, and Frank Vallentin, Classification of eight-dimensional perfect forms, Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 21–32. MR 2300003, DOI 10.1090/S1079-6762-07-00171-0
M. E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983), no. 3, 381–402. MR 716120, DOI 10.1287/moor.8.3.381
Herbert Edelsbrunner, Geometry and topology for mesh generation, Cambridge Monographs on Applied and Computational Mathematics, vol. 7, Cambridge University Press, Cambridge, 2001. MR 1833977, DOI 10.1017/CBO9780511530067
P. Engel, L. Michel, M. Sénéchal, Lattice geometry, preprint, 2003.
Uri Erez, Simon Litsyn, and Ram Zamir, Lattices which are good for (almost) everything, IEEE Trans. Inform. Theory 51 (2005), no. 10, 3401–3416. MR 2236418, DOI 10.1109/TIT.2005.855591
Lenny Fukshansky and Sinai Robins, Frobenius problem and the covering radius of a lattice, Discrete Comput. Geom. 37 (2007), no. 3, 471–483. MR 2301530, DOI 10.1007/s00454-006-1295-2
K. Fukuda, cdd+ reference manual, Institute for operations research, Swiss Federal Institute of Technology, Zurich, Switzerland, 1995, http://www. ifor. math. ethz. ch/ ~fukuda/ cdd_home/cdd.html.
A. Gersho, R. M. Gray, Vector Quantization and Signal Processing, Kluwer Academic Press/Springer, 1992.
Curtis Greene and Thomas Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Amer. Math. Soc. 280 (1983), no. 1, 97–126. MR 712251, DOI 10.1090/S0002-9947-1983-0712251-1
Venkatesan Guruswami, Daniele Micciancio, and Oded Regev, The complexity of the covering radius problem, Comput. Complexity 14 (2005), no. 2, 90–121. MR 2189919, DOI 10.1007/s00037-005-0193-y
I. Haviv, O. Regev, Hardness of the covering radius problem on lattices, pages 145–158 in Proc. of 21st IEEE Annual Conference on Computational Complexity (CCC), 2006.
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich, Generating all vertices of a polyhedron is hard, Discrete Comput. Geom. 39 (2008), no. 1-3, 174–190. MR 2383757, DOI 10.1007/s00454-008-9050-5
Johannes Köbler, Uwe Schöning, and Jacobo Torán, The graph isomorphism problem: its structural complexity, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1993. MR 1232421, DOI 10.1007/978-1-4612-0333-9
Jean B. Lasserre, Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), no. 8, 2433–2441. MR 1459132, DOI 10.1090/S0002-9939-98-04454-2
Nathan Linial, Hard enumeration problems in geometry and combinatorics, SIAM J. Algebraic Discrete Methods 7 (1986), no. 2, 331–335. MR 830652, DOI 10.1137/0607036
A. Marzetta, pd-C-implementation of the primal dual algorithm, 1997, http:// www. cs.unb.ca/profs/bremner/pd/.
B. D. McKay, nauty User’s Guide (Version 2.4), 2006, http:// cs. anu. edu. au/ people/bdm/nauty/nug-2.4b3.pdf.
Daniele Micciancio, Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor, SIAM J. Comput. 34 (2004), no. 1, 118–169. MR 2114308, DOI 10.1137/S0097539703433511
R. V. Moody and J. Patera, Voronoĭ domains and dual cells in the generalized kaleidoscope with applications to root and weight lattices, Canad. J. Math. 47 (1995), no. 3, 573–605. MR 1346154, DOI 10.4153/CJM-1995-031-2
J. Opgenorth, W. Plesken, and T. Schulz, Crystallographic algorithms and tables, Acta Cryst. Sect. A 54 (1998), no. 5, 517–531. MR 1645546, DOI 10.1107/S010876739701547X
James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
W. Plesken and B. Souvignier, Computing isometries of lattices, J. Symbolic Comput. 24 (1997), no. 3-4, 327–334. Computational algebra and number theory (London, 1993). MR 1484483, DOI 10.1006/jsco.1996.0130
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970. MR 274683
Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
Achill Schürmann and Frank Vallentin, Computational approaches to lattice packing and covering problems, Discrete Comput. Geom. 35 (2006), no. 1, 73–116. MR 2183491, DOI 10.1007/s00454-005-1202-2
N. J. A. Sloane and B. Beferull-Lozano, Quantizing using lattice intersections, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 799–824. MR 2038504, DOI 10.1007/978-3-642-55566-4_{3}8
W. T. Tutte, Introduction to the theory of matroids, Modern Analytic and Computational Methods in Science and Mathematics, No. 37, American Elsevier Publishing Co., Inc., New York, 1971. MR 276117
Emanuele Viterbo and Ezio Biglieri, Computing the Voronoĭ cell of a lattice: the diamond-cutting algorithm, IEEE Trans. Inform. Theory 42 (1996), no. 1, 161–171. MR 1375332, DOI 10.1109/18.481786
G. F. Voronoi, Nouvelles applications des paramètres continus à là théorie des formes quadratiques, Deuxième Mémoire, Recherches sur les parallélloedres primitifs, J. Reine Angew. Math. 134 (1908) 198–287 and 136 (1909) 67–181.
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1