{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:59:18Z","timestamp":1776790758437,"version":"3.51.2"},"reference-count":47,"publisher":"American Mathematical Society (AMS)","issue":"267","license":[{"start":{"date-parts":[[2010,2,6]],"date-time":"2010-02-06T00:00:00Z","timestamp":1265414400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    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\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"number-sign normal upper P\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi mathvariant=\"normal\">\n                              #\n                              \n                            <\/mml:mi>\n                            <mml:mi mathvariant=\"normal\">P<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\#\\operatorname {P}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -hard problem. On the other hand, we describe an algorithm for this problem which is especially suited for low-dimensional (say dimensions at most\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"12\">\n                        <mml:semantics>\n                          <mml:mn>12<\/mml:mn>\n                          <mml:annotation encoding=\"application\/x-tex\">12<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    ) 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.\n                  <\/p>","DOI":"10.1090\/s0025-5718-09-02224-8","type":"journal-article","created":{"date-parts":[[2009,4,27]],"date-time":"2009-04-27T13:47:33Z","timestamp":1240840053000},"page":"1713-1731","source":"Crossref","is-referenced-by-count":42,"title":["Complexity and algorithms for computing Voronoi cells of lattices"],"prefix":"10.1090","volume":"78","author":[{"given":"Mathieu","family":"Dutour Sikiri\u0107","sequence":"first","affiliation":[]},{"given":"Achill","family":"Sch\u00fcrmann","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Vallentin","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2009,2,6]]},"reference":[{"issue":"5","key":"1","doi-asserted-by":"publisher","first-page":"1814","DOI":"10.1109\/18.705561","article-title":"Optimization of lattices for quantization","volume":"44","author":"Agrell, Erik","year":"1998","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1070\/RM2002v057n02ABEH000501","article-title":"On the density of a lattice covering for \ud835\udc5b=11 and \ud835\udc5b=14","volume":"57","author":"Anzin, M. M.","year":"2002","journal-title":"Uspekhi Mat. Nauk","ISSN":"https:\/\/id.crossref.org\/issn\/0042-1316","issn-type":"print"},{"issue":"5","key":"3","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/s11006-006-0082-y","article-title":"On the density of the lattice covering for \ud835\udc5b=13 and \ud835\udc5b=15","volume":"79","author":"Anzin, M. M.","year":"2006","journal-title":"Mat. Zametki","ISSN":"https:\/\/id.crossref.org\/issn\/0025-567X","issn-type":"print"},{"issue":"872","key":"4","first-page":"16","article-title":"A C implementation of the reverse search vertex enumeration algorithm","author":"Avis, David","year":"1994","journal-title":"S\\={u}rikaisekikenky\\={u}sho K\\B{o}ky\\={u}roku"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/eujc.1994.1036","article-title":"The perfect lattices \u0393(\ud835\udd04\u207f), and the covering density of \u0393(\ud835\udd04\u2079)","volume":"15","author":"Baranovski\u012d, E. P.","year":"1994","journal-title":"European J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0195-6698","issn-type":"print"},{"issue":"6","key":"6","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1112\/S0024609397003305","article-title":"Algebraic potential theory on graphs","volume":"29","author":"Biggs, Norman","year":"1997","journal-title":"Bull. London Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6093","issn-type":"print"},{"key":"7","unstructured":"[BDS07] D. Bremner, M. Dutour Sikiri\u0107, A. Sch\u00fcrmann, Polyhedral representation conversion up to symmetries, preprint, September 2007, arXiv:math\/0702239v2 [math.MG]."},{"key":"8","isbn-type":"print","first-page":"131","article-title":"Exact volume computation for polytopes: a practical study","author":"B\u00fceler, Benno","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3764363517"},{"key":"9","unstructured":"[CL97] T. Christof, A. L\u00f6bel, PORTA: Polyhedron representation transformation algorithm (ver 1.3.1), 1997, http:\/\/www.zib.de\/Optimization\/Software\/Porta\/."},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02568602","article-title":"Combinatorial optimization and small polytopes","volume":"4","author":"Christof, T.","year":"1996","journal-title":"Top","ISSN":"https:\/\/id.crossref.org\/issn\/1134-5764","issn-type":"print"},{"key":"11","isbn-type":"print","first-page":"71","article-title":"The cell structures of certain lattices","author":"Conway, John H.","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/3540541748"},{"key":"12","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6568-7","volume-title":"Sphere packings, lattices and groups","volume":"290","author":"Conway, J. H.","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0387985859","edition":"3"},{"key":"13","doi-asserted-by":"publisher","first-page":"391","DOI":"10.4153\/cjm-1951-045-8","article-title":"Extreme forms","volume":"3","author":"Coxeter, H. S. M.","year":"1951","journal-title":"Canad. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-414X","issn-type":"print"},{"key":"14","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1016\/0024-3795(95)00240-R","article-title":"Delaunay polytopes of cut lattices","volume":"226\/228","author":"Deza, Michel","year":"1995","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"15","series-title":"Algorithms and Combinatorics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of cuts and metrics","volume":"15","author":"Deza, Michel Marie","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/354061611X"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00493-003-0019-y","article-title":"Approximating CVP to within almost-polynomial factors is NP-hard","volume":"23","author":"Dinur, I.","year":"2003","journal-title":"Combinatorica","ISSN":"https:\/\/id.crossref.org\/issn\/0209-9683","issn-type":"print"},{"key":"17","unstructured":"[Dut08] M. Dutour Sikiri\u0107, Polyhedral, 2008, http:\/\/www.liga.ens.fr\/~dutour\/polyhedral"},{"key":"18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S1079-6762-07-00171-0","article-title":"Classification of eight-dimensional perfect forms","volume":"13","author":"Sikiri\u0107, Mathieu Dutour","year":"2007","journal-title":"Electron. Res. Announc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/1079-6762","issn-type":"print"},{"issue":"3","key":"19","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1287\/moor.8.3.381","article-title":"The complexity of vertex enumeration methods","volume":"8","author":"Dyer, M. E.","year":"1983","journal-title":"Math. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0364-765X","issn-type":"print"},{"key":"20","series-title":"Cambridge Monographs on Applied and Computational Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511530067","volume-title":"Geometry and topology for mesh generation","volume":"7","author":"Edelsbrunner, Herbert","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0521793092"},{"key":"21","unstructured":"[EMS03] P. Engel, L. Michel, M. S\u00e9n\u00e9chal, Lattice geometry, preprint, 2003."},{"issue":"10","key":"22","doi-asserted-by":"publisher","first-page":"3401","DOI":"10.1109\/TIT.2005.855591","article-title":"Lattices which are good for (almost) everything","volume":"51","author":"Erez, Uri","year":"2005","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"3","key":"23","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00454-006-1295-2","article-title":"Frobenius problem and the covering radius of a lattice","volume":"37","author":"Fukshansky, Lenny","year":"2007","journal-title":"Discrete Comput. Geom.","ISSN":"https:\/\/id.crossref.org\/issn\/0179-5376","issn-type":"print"},{"key":"24","unstructured":"[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."},{"key":"25","doi-asserted-by":"crossref","unstructured":"[GG92] A. Gersho, R. M. Gray, Vector Quantization and Signal Processing, Kluwer Academic Press\/Springer, 1992.","DOI":"10.1007\/978-1-4615-3626-0"},{"issue":"1","key":"26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.2307\/1999604","article-title":"On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs","volume":"280","author":"Greene, Curtis","year":"1983","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"2","key":"27","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s00037-005-0193-y","article-title":"The complexity of the covering radius problem","volume":"14","author":"Guruswami, Venkatesan","year":"2005","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[HR06] I. Haviv, O. Regev, Hardness of the covering radius problem on lattices, pages 145\u2013158 in \\textsl{Proc. of 21st IEEE Annual Conference on Computational Complexity (CCC)}, 2006.","DOI":"10.1109\/CCC.2006.23"},{"issue":"1-3","key":"29","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/s00454-008-9050-5","article-title":"Generating all vertices of a polyhedron is hard","volume":"39","author":"Khachiyan, Leonid","year":"2008","journal-title":"Discrete Comput. Geom.","ISSN":"https:\/\/id.crossref.org\/issn\/0179-5376","issn-type":"print"},{"key":"30","series-title":"Progress in Theoretical Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The graph isomorphism problem: its structural complexity","author":"K\u00f6bler, Johannes","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0817636803"},{"issue":"8","key":"31","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1090\/S0002-9939-98-04454-2","article-title":"Integration on a convex polytope","volume":"126","author":"Lasserre, Jean B.","year":"1998","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"2","key":"32","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/0607036","article-title":"Hard enumeration problems in geometry and combinatorics","volume":"7","author":"Linial, Nathan","year":"1986","journal-title":"SIAM J. Algebraic Discrete Methods","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5212","issn-type":"print"},{"key":"33","unstructured":"[Mar97] A. Marzetta, pd-C-implementation of the primal dual algorithm, 1997, http:\/\/ www. cs.unb.ca\/profs\/bremner\/pd\/."},{"key":"34","unstructured":"[McK06] B. D. McKay, nauty User\u2019s Guide (Version 2.4), 2006, http:\/\/ cs. anu. edu. au\/ people\/bdm\/nauty\/nug-2.4b3.pdf."},{"issue":"1","key":"35","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1137\/S0097539703433511","article-title":"Almost perfect lattices, the covering radius problem, and applications to Ajtai\u2019s connection factor","volume":"34","author":"Micciancio, Daniele","year":"2004","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"3","key":"36","doi-asserted-by":"publisher","first-page":"573","DOI":"10.4153\/CJM-1995-031-2","article-title":"Vorono\u012d domains and dual cells in the generalized kaleidoscope with applications to root and weight lattices","volume":"47","author":"Moody, R. V.","year":"1995","journal-title":"Canad. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-414X","issn-type":"print"},{"issue":"5","key":"37","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1107\/S010876739701547X","article-title":"Crystallographic algorithms and tables","volume":"54","author":"Opgenorth, J.","year":"1998","journal-title":"Acta Cryst. Sect. A","ISSN":"https:\/\/id.crossref.org\/issn\/0108-7673","issn-type":"print"},{"key":"38","series-title":"Oxford Science Publications","isbn-type":"print","volume-title":"Matroid theory","author":"Oxley, James G.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0198535635"},{"issue":"3-4","key":"39","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1006\/jsco.1996.0130","article-title":"Computing isometries of lattices","volume":"24","author":"Plesken, W.","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"40","series-title":"Princeton Mathematical Series, No. 28","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex analysis","author":"Rockafellar, R. Tyrrell","year":"1970"},{"key":"41","series-title":"Wiley-Interscience Series in Discrete Mathematics","isbn-type":"print","volume-title":"Theory of linear and integer programming","author":"Schrijver, Alexander","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0471908541"},{"issue":"1","key":"42","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00454-005-1202-2","article-title":"Computational approaches to lattice packing and covering problems","volume":"35","author":"Sch\u00fcrmann, Achill","year":"2006","journal-title":"Discrete Comput. Geom.","ISSN":"https:\/\/id.crossref.org\/issn\/0179-5376","issn-type":"print"},{"key":"43","isbn-type":"print","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1007\/978-3-642-55566-4_38","article-title":"Quantizing using lattice intersections","author":"Sloane, N. J. A.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3540003711"},{"key":"44","series-title":"Modern Analytic and Computational Methods in Science and Mathematics, No. 37","volume-title":"Introduction to the theory of matroids","author":"Tutte, W. T.","year":"1971"},{"issue":"1","key":"45","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1109\/18.481786","article-title":"Computing the Vorono\u012d cell of a lattice: the diamond-cutting algorithm","volume":"42","author":"Viterbo, Emanuele","year":"1996","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"46","doi-asserted-by":"crossref","unstructured":"[Vor08] G. F. Voronoi, Nouvelles applications des param\u00e8tres continus \u00e0 l\u00e0 th\u00e9orie des formes quadratiques, Deuxi\u00e8me M\u00e9moire, Recherches sur les parall\u00e9lloedres primitifs, J. Reine Angew. Math. 134 (1908) 198\u2013287 and 136 (1909) 67\u2013181.","DOI":"10.1515\/crll.1908.134.198"},{"key":"47","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1","volume-title":"Lectures on polytopes","volume":"152","author":"Ziegler, G\u00fcnter M.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/038794365X"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2009-78-267\/S0025-5718-09-02224-8\/S0025-5718-09-02224-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-267\/S0025-5718-09-02224-8\/S0025-5718-09-02224-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:09:30Z","timestamp":1776787770000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-267\/S0025-5718-09-02224-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,6]]},"references-count":47,"journal-issue":{"issue":"267","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["S0025-5718-09-02224-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-09-02224-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2009,2,6]]}}}