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
- 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 1224949 (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 1538124 (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?)
- scientific article; zbMATH DE number 2209745 (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
- 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)
