Complexity and algorithms for computing Voronoi cells of lattices
From MaRDI portal
Forms over real fields (11E10) Lattice packing and covering (number-theoretic aspects) (11H31) Automorphism groups of lattices (11H56) Number-theoretic algorithms; complexity (11Y16) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
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 #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.
Recommendations
- Computing the Voronoi cell of a lattice: the diamond-cutting algorithm
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- On the Voronoi Regions of Certain Lattices
- Covering radius of two-dimensional lattices
Cites work
- Algebraic Potential Theory on Graphs
- Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
- Approximating CVP to within almost-polynomial factors is NP-hard
- Classification of eight-dimensional perfect forms
- Combinatorial optimization and small polytopes
- Computational approaches to lattice packing and covering problems
- Computing isometries of lattices
- Computing the Voronoi cell of a lattice: the diamond-cutting algorithm
- Convex Analysis
- Crystallographic algorithms and tables.
- Delaunay polytopes of cut lattices
- Exact volume computation for polytopes: A practical study
- Extreme Forms
- Frobenius problem and the covering radius of a lattice
- Generating all vertices of a polyhedron is hard
- Geometry and topology for mesh generation
- Geometry of cuts and metrics
- Hard Enumeration Problems in Geometry and Combinatorics
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 17391 (Why is no real title available?)
- scientific article; zbMATH DE number 467196 (Why is no real title available?)
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- scientific article; zbMATH DE number 1395341 (Why is no real title available?)
- scientific article; zbMATH DE number 3365295 (Why is no real title available?)
- Integration on a convex polytope
- Lattices Which Are Good for (Almost) Everything
- Lectures on Polytopes
- On lattice covering density for \(n = 13\) and \(n = 15\)
- On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
- On the Lattice Isomorphism Problem
- Optimization of lattices for quantization
- Polyhedral representation conversion up to symmetries
- Quantizing using lattice intersections
- Sphere packings, lattices and groups. 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.
- The complexity of the covering radius problem
- The Complexity of Vertex Enumeration Methods
- The density of a lattice covering forn= 11 andn= 14
- The perfect lattices \(\Gamma ({\mathfrak A}^ n)\), and the covering density of \(\Gamma ({\mathfrak A}^ 9)\)
- Voronoi Domains and Dual Cells in the Generalized Kaleidoscope with Applications to Root and Weight Lattices
Cited in
(37)- Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
- The hypermetric cone and polytope on eight vertices and some generalizations
- Inhomogeneous extreme forms
- Combinatorial iterated integrals and the harmonic volume of graphs
- A proof of a conjecture by Haviv, Lyubashevsky and Regev on the second moment of a lattice Voronoi cell
- Covering aspects of the Niemeier lattices
- Delaunay polytopes derived from the Leech lattice
- A generalization of Voronoi's reduction theory and its application
- Computing symmetry groups of polyhedra
- Enumeration of the facets of cut polytopes over some highly symmetric graphs
- Exploiting symmetries in polyhedral computations
- Covering radius of two-dimensional lattices
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- scientific article; zbMATH DE number 4019158 (Why is no real title available?)
- Voronoi cells of lattices with respect to arbitrary norms
- Coloring the Voronoi tessellation of lattices
- scientific article; zbMATH DE number 7499212 (Why is no real title available?)
- Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices
- On the sum of a parallelotope and a zonotope
- Computation of Euclidean minima in totally definite quaternion fields
- Computing the Voronoi cell of a lattice: the diamond-cutting algorithm
- Voronoi polytopes for polyhedral norms on lattices
- On the Voronoi conjecture for combinatorially Voronoi parallelohedra in dimension 5
- scientific article; zbMATH DE number 7302969 (Why is no real title available?)
- A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
- Deciding orthogonality in construction-A lattices
- The contact polytope of the Leech lattice
- Lifts for Voronoi cells of lattices
- The Optimal Lattice Quantizer in Nine Dimensions
- Tropical moments of tropical Jacobians
- The neighborhood of the Voronoi main perfect form from five variables
- Upper bounds on chromatic number of \(\mathbb{E}^n\) in low dimensions
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Deciding whether a lattice has an orthonormal basis is in co-NP
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Relating code equivalence to other isomorphism problems
- Computational approaches to lattice packing and covering problems
This page was built for publication: Complexity and algorithms for computing Voronoi cells of lattices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055167)
