×

Complexity and algorithms for computing Voronoi cells of lattices. (English) Zbl 1215.11067

Let \(L=B\mathbb Z^m\subseteq\mathbb R^n\) be a lattice of rank \(m\) in Euclidean space given by a matrix \(B\in \mathbb R^{n\times m}\) of rank \(m\). By lin \(L\) we denote the linear subspace spanned by the elements of \(L\). The Voronoi cell of \(L\) is \[ V(L)=\{x\in \text{\;lin\;} L:\;\|x\|\leq \|x-v\| \text{\;for all\;} v\in L\}. \] Recall that the Voronoi cell of a lattice is a centrally symmetric convex polytope and that the polytopes \(V(L)+v\) for \(v\in L\) tile lin \(L\). The determinant det \(L\) equals the volume \(V(L)\), the covering radius \(\mu(L)\) equals the circumradius of \(V(L)\) and the quantizer constant \(G(L)\) is \[ G(L)=(\det L)^{-(1+2/n)}\int_{V(L}\|x\|^2 \,dx. \] For a lattice \(L\subseteq \mathbb R^n\) of full rank \(n\), a point \(x\in \mathbb R^n\) defines a Delone cell \(D(x)\) by \[ D(x):= conv\{v\in L:\|x-v\|=\min_{w\in L}\|x-w\|\}. \]
The main aim of this article is to find the vertices of the Voronoi cell of an Euclidean lattice. Given a basis of a lattice, the authors prove that computing the number of vertices is a #P-hard problem. On the other hand, they describe an algorithm for this problem especially suited for low-dimensional (dimensions at most \(12\)) and highly-symmetric lattices. They use their implementation of the algorithm (outperforming those of current computer algebra systems) to find the vertices of Voronoi cells and quantizer constants of some prominent lattices.
The structure of the paper is as follows. In section 2 the authors discuss the computational complexity of the covering radius problem and prove that the related problem of counting vertices of a Voronoi cell is #P-hard. As a consequence they prove that the lattice isomorphism problem is at least as difficult as the graph isomorphism problem. In section 3, they turn to practical algorithms for the covering radius problem and they describe an algorithm which computes the vertices of the Voronoi cell of a lattice. In fact the algorithm computes all full-dimensional Delone cells and the adjacencies between them up to equivalence using Gram matrices instead of lattice basis. They compare also their algorithm with [E. Viterbo and E. Biglieri, “Computing the Voronoi cell of a lattice: The diamond-cutting algorithm”, IEEE Trans. Inf. Theory 42, No. 1, 161–171 (1996; Zbl 0853.68166)]. In section 4 they gives an algorithm for computing the quantizer constant. In section 5 they report the numerical results obtained and observe that they determine the exact covering radius and quantizer constants of many prominent lattices which were not known before (Coxeter lattices, laminated lattices, shorter Leech lattices and cut lattices).

MSC:

11H31 Lattice packing and covering (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
11E10 Forms over real fields
11H56 Automorphism groups of lattices
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52B55 Computational aspects related to convexity
68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Citations:

Zbl 0853.68166

Software:

cdd; PORTA; CARAT; Polyhedral; pd; nauty
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Erik Agrell and Thomas Eriksson, Optimization of lattices for quantization, IEEE Trans. Inform. Theory 44 (1998), no. 5, 1814 – 1828. · Zbl 0964.94014 · doi:10.1109/18.705561
[2] M. M. Anzin, On the density of a lattice covering for \?=11 and \?=14, Uspekhi Mat. Nauk 57 (2002), no. 2(344), 187 – 188 (Russian); English transl., Russian Math. Surveys 57 (2002), no. 2, 407 – 409. · Zbl 1114.11304 · doi:10.1070/RM2002v057n02ABEH000501
[3] M. M. Anzin, On the density of the lattice covering for \?=13 and \?=15, Mat. Zametki 79 (2006), no. 5, 781 – 784 (Russian); English transl., Math. Notes 79 (2006), no. 5-6, 721 – 725. · Zbl 1136.11045 · doi:10.1007/s11006-006-0082-y
[4] David Avis, A C implementation of the reverse search vertex enumeration algorithm, Sūrikaisekikenkyūsho Kōkyūroku 872 (1994), 16 – 29. Computational geometry and discrete geometry (Japanese) (Kyoto, 1993). · Zbl 0939.68883
[5] E. P. Baranovskiĭ, The perfect lattices \Gamma (\?\(^{n}\)), and the covering density of \Gamma (\?\(^{9}\)), European J. Combin. 15 (1994), no. 4, 317 – 323. · Zbl 0805.52010 · doi:10.1006/eujc.1994.1036
[6] Norman Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1997), no. 6, 641 – 682. · Zbl 0892.05033 · doi:10.1112/S0024609397003305
[7] D. Bremner, M. Dutour Sikirić, A. Schürmann, Polyhedral representation conversion up to symmetries, preprint, September 2007, arXiv:math/0702239v2 [math.MG]. · Zbl 1170.68621
[8] 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. · Zbl 0960.68162
[9] T. Christof, A. Löbel, PORTA: Polyhedron representation transformation algorithm (ver 1.3.1), 1997, http://www.zib.de/Optimization/Software/Porta/.
[10] T. Christof and G. Reinelt, Combinatorial optimization and small polytopes, Top 4 (1996), no. 1, 1 – 64. With discussion. · Zbl 0858.90107 · doi:10.1007/BF02568602
[11] John H. Conway and Neil J. A. Sloane, The cell structures of certain lattices, Miscellanea mathematica, Springer, Berlin, 1991, pp. 71 – 107. · Zbl 0738.52014
[12] 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. · Zbl 0915.52003
[13] H. S. M. Coxeter, Extreme forms, Canadian J. Math. 3 (1951), 391 – 441. · Zbl 0044.04201
[14] Michel Deza and Viatcheslav Grishukhin, Delaunay polytopes of cut lattices, Linear Algebra Appl. 226/228 (1995), 667 – 685. · Zbl 0831.52006 · doi:10.1016/0024-3795(95)00240-R
[15] Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. · Zbl 0885.52001
[16] 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. · Zbl 1049.68072 · doi:10.1007/s00493-003-0019-y
[17] M. Dutour Sikirić, Polyhedral, 2008, http://www.liga.ens.fr/ dutour/polyhedral
[18] 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. · Zbl 1186.11039
[19] M. E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983), no. 3, 381 – 402. · Zbl 0531.90064 · doi:10.1287/moor.8.3.381
[20] Herbert Edelsbrunner, Geometry and topology for mesh generation, Cambridge Monographs on Applied and Computational Mathematics, vol. 7, Cambridge University Press, Cambridge, 2001. · Zbl 0981.65028
[21] P. Engel, L. Michel, M. Sénéchal, Lattice geometry, preprint, 2003.
[22] Uri Erez, Simon Litsyn, and Ram Zamir, Lattices which are good for (almost) everything, IEEE Trans. Inform. Theory 51 (2005), no. 10, 3401 – 3416. · Zbl 1293.94040 · doi:10.1109/TIT.2005.855591
[23] Lenny Fukshansky and Sinai Robins, Frobenius problem and the covering radius of a lattice, Discrete Comput. Geom. 37 (2007), no. 3, 471 – 483. · Zbl 1136.11307 · doi:10.1007/s00454-006-1295-2
[24] 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.
[25] A. Gersho, R. M. Gray, Vector Quantization and Signal Processing, Kluwer Academic Press/Springer, 1992. · Zbl 0782.94001
[26] 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. · Zbl 0539.05024
[27] Venkatesan Guruswami, Daniele Micciancio, and Oded Regev, The complexity of the covering radius problem, Comput. Complexity 14 (2005), no. 2, 90 – 121. · Zbl 1085.68063 · doi:10.1007/s00037-005-0193-y
[28] 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. · Zbl 1286.68192
[29] 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. · Zbl 1147.05040 · doi:10.1007/s00454-008-9050-5
[30] 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. · Zbl 0813.68103
[31] Jean B. Lasserre, Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), no. 8, 2433 – 2441. · Zbl 0901.65012
[32] Nathan Linial, Hard enumeration problems in geometry and combinatorics, SIAM J. Algebraic Discrete Methods 7 (1986), no. 2, 331 – 335. · Zbl 0596.68041 · doi:10.1137/0607036
[33] A. Marzetta, pd-C-implementation of the primal dual algorithm, 1997, http://www.cs.unb.ca/profs/bremner/pd/.
[34] B. D. McKay, nauty User’s Guide (Version 2.4), 2006, http://cs.anu. edu.au/people/bdm/nauty/nug-2.4b3.pdf.
[35] 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. · Zbl 1112.68067 · doi:10.1137/S0097539703433511
[36] 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. · Zbl 0838.52019 · doi:10.4153/CJM-1995-031-2
[37] J. Opgenorth, W. Plesken, and T. Schulz, Crystallographic algorithms and tables, Acta Cryst. Sect. A 54 (1998), no. 5, 517 – 531. · Zbl 1176.20051 · doi:10.1107/S010876739701547X
[38] James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. · Zbl 0784.05002
[39] 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). · Zbl 0882.11042 · doi:10.1006/jsco.1996.0130
[40] R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. · Zbl 0193.18401
[41] Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. · Zbl 0665.90063
[42] Achill Schürmann and Frank Vallentin, Computational approaches to lattice packing and covering problems, Discrete Comput. Geom. 35 (2006), no. 1, 73 – 116. · Zbl 1091.52009 · doi:10.1007/s00454-005-1202-2
[43] 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. · Zbl 1077.52508 · doi:10.1007/978-3-642-55566-4_38
[44] 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. · Zbl 0231.05027
[45] 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. · Zbl 0853.68166 · doi:10.1109/18.481786
[46] 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.
[47] Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.