Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Complexity and algorithms for computing Voronoi cells of lattices

Author(s): Mathieu Dutour Sikiric; Achill Schürmann; Frank Vallentin.
Journal: Math. Comp. 78 (2009), 1713-1731.
MSC (2000): Primary 03D15, 11H56, 11H06, 11E10, 52B55, 52B12
Posted: February 6, 2009
Retrieve article in: PDF

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:

[AE98]
E. Agrell, T. Eriksson, Optimization of lattices for quantization, IEEE Trans. Inform. Theory 44 (1998) 1814-1828. MR 1664114 (99h:94003)

[Anz02]
M. M. Anzin, On the density of a lattice covering for $ n=11$ and $ n=14$, Russian Math. Surveys 57 (2002) 407-409, translation from Uspekhi Mat. Nauk 57, (2002) 187-188. MR 1918199 (2003m:11098)

[Anz06]
M. M. Anzin, On the density of the lattice covering for $ n=13$ and $ n=15$, Math. Notes 79 (2006) 721-725, translation from Mat. Zametki 79 (2006) 781-784. MR 2249136 (2007f:11075)

[Avi93]
D. Avis, A C-implementation of the reverse search vertex enumeration algorithm, School of Computer Science, McGill University, Montreal, Canada 1993,

http://www-cgrl.cs.mcgill.ca/~avis/C/lrs.html. MR 1330479

[Bar94]
E. P. Baranovskii, The perfect lattices $ \Gamma(\mathfrak{A} ^n)$, and the covering density of $ \Gamma(\mathfrak{A} ^9)$, European J. Combin. 15 (1994), 317-323. MR 1279070 (95i:11069)

[Big97]
N. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1997), 641-682. MR 1468054 (98m:05120)

[BDS07]
D. Bremner, M. Dutour Sikirić, A. Schürmann, Polyhedral representation conversion up to symmetries, preprint, September 2007, arXiv:math/0702239v2 [math.MG].

[BEF98]
B. Büeler, A. Enge, K. Fukuda, Exact volume computation for polytopes: a practical study, pages 131-154 in Polytopes--combinatorics and computation (Oberwolfach, 1997), Birkhäuser, 2000. MR 1785296 (2001e:52025)

[CL97]
T. Christof, A. Löbel, PORTA: Polyhedron representation transformation algorithm (ver 1.3.1), 1997, http://www.zib.de/Optimization/Software/Porta/.

[CR96]
T. Christof, G. Reinelt, Combinatorial optimization and small polytopes, Top 4 (1996) 1-64. MR 1404262 (97g:90107)

[CS91]
J. H. Conway, N. J. A. Sloane, The cell structures of certain lattices, pages 71-107 in Miscellanea mathematica, Springer, 1991. MR 1131118 (92i:52019)

[CS99]
J. H. Conway, N. J. A. Sloane, Sphere packings, lattices and groups (third edition), Springer, 1999. MR 1662447 (2000b:11077)

[Cox51]
H. S. M. Coxeter, Extreme forms, Canadian J. Math. 3 (1951) 391-441. MR 0044580 (13:443c)

[DG95]
M. Deza, V. Grishukhin, Delaunay polytopes of cut lattices, Linear Algebra Appl. 226/228 (1995) 667-685. MR 1344592 (96f:52021)

[DL97]
M. Deza, M. Laurent, Geometry of cuts and metrics, Springer, 1997. MR 1460488 (98g:52001)

[DKS03]
I. Dinur, G. Kindler, S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, Combinatorica 23 (2003), 205-243. MR 2001908 (2004h:68046)

[Dut08]
M. Dutour Sikirić, Polyhedral, 2008,

http://www.liga.ens.fr/~dutour/polyhedral

[DSV07]
M. Dutour Sikirić, A. Schürmann, F. Vallentin, Classification of eight-dimensional perfect forms, Electron. Res. Announc. Amer. Math. Soc. 13 (2007) 21-32. MR 2300003 (2007m:11089)

[Dy83]
M. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983) 381-402. MR 716120 (85j:68102)

[Ede01]
H. Edelsbrunner, Geometry and topology for mesh generation, Cambridge University Press, 2001. MR 1833977 (2002k:65206)

[EMS03]
P. Engel, L. Michel, M. Sénéchal, Lattice geometry, preprint, 2003.

[ELZ05]
U. Erez, S. Litsyn, R. Zamir, Lattices which are good for (almost) everything, IEEE Trans. Inform. Theory 51-10 (2005) 3401-3416. MR 2236418 (2007a:94129)

[FR05]
L. Fukshansky, S. Robins, Frobenius problem and the covering radius of a lattice, Discrete Comput. Geom. 37 (2007), 471-483. MR 2301530 (2008a:11040)

[Fuk95]
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.

[GG92]
A. Gersho, R. M. Gray, Vector Quantization and Signal Processing, Kluwer Academic Press/Springer, 1992.

[GZ83]
C. Greene, T. 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), 97-126. MR 712251 (84k:05032)

[GMR05]
V. Guruswami, D. Micciancio, O. Regev, The complexity of the covering radius problem, Comput. Complexity 14 (2005) 90-121. MR 2189919 (2006k:68041)

[HR06]
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.

[KBBEG08]
L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, Generating all vertices of a polyhedron is hard, Discrete Comput. Geom. 39 (2008) 174-190. MR 2383757

[KST93]
J. Köbler, U. Schöning, J. Torán, The graph isomorphism problem: its structural complexity, Birkhäuser, 1993. MR 1232421 (95b:05154)

[Las98]
J. B. Lasserre, Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998) 2433-2441. MR 1459132 (98j:65016)

[Lin86]
N. Linial, Hard enumeration problems in geometry and combinatorics, SIAM J. Algebraic Discrete Methods 7 (1986) 331-335. MR 830652 (87e:68029)

[Mar97]
A. Marzetta, pd-C-implementation of the primal dual algorithm, 1997, http://www.cs.unb.ca/profs/bremner/pd/.

[McK06]
B. D. McKay, nauty User's Guide (Version 2.4), 2006,

http://cs.anu. edu.au/people/bdm/nauty/nug-2.4b3.pdf.

[Mic04]
D. Micciancio, Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor, SIAM J. Comput. 34 (2004) 118-169. MR 2114308 (2005h:68049)

[MP95]
R.V. Moody, J. Patera, Voronoi domains and dual cells in the generalized kaleidoscope with applications to root and weight lattices, Canad. J. Math. 47 (1995) 573-605. MR 1346154 (97c:17008)

[OPS98]
J. Opgenorth, W. Plesken, T. Schultz, Crystallographic algorithms and tables, Acta Cryst. Sect. A 54 (1998) 517-531. MR 1645546 (99h:20082)

[Oxl92]
J. G. Oxley, Matroid theory, Oxford University Press, 1992. MR 1207587 (94d:05033)

[PP97]
W. Plesken, B. Souvignier, Computing isometries of lattices, J. Symbolic Comput. 24 (1997) 327-334. MR 1484483 (98i:11047)

[Roc70]
R. T. Rockafellar, Convex analysis, Princeton University Press, 1970. MR 0274683 (43:445)

[Sch86]
A. Schrijver, Theory of linear and integer programming, Wiley, 1986. MR 874114 (88m:90090)

[SV06]
A. Schürmann, F. Vallentin, Computational approaches to lattice packing and covering problems, Discrete Comput. Geom. 35 (2006) 73-116. MR 2183491 (2006k:52048)

[SB03]
N. J. A. Sloane, B. Beferull-Lozano, Quantizing using lattice intersections, Discrete and computational geometry, 799-824, Algorithms Combin., Springer, 2003. MR 2038504 (2005b:52050)

[Tut71]
W. T. Tutte, Introduction to the theory of matroids, American Elsevier Publishing Company, 1971. MR 0276117 (43:1865)

[VB96]
E. Viterbo, E. Biglieri, Computing the Voronoi cell of a lattice: the diamond-cutting algorithm, IEEE Trans. Inform. Theory 42 (1996) 161-171. MR 1375332 (96j:68177)

[Vor08]
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.

[Zie95]
G. M. Ziegler, Lectures on polytopes, Springer, 1995. MR 1311028 (96a:52011)

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 Boskovic 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: 10.1090/S0025-5718-09-02224-8
PII: S 0025-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
Posted: 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.
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google