Complexity and algorithms for computing Voronoi cells of lattices

DOI10.1090/S0025-5718-09-02224-8zbMath1215.11067arXiv0804.0036OpenAlexW3105421475WikidataQ110628961 ScholiaQ110628961MaRDI QIDQ3055167

Frank Vallentin, Mathieu Dutour Sikirić, Achill Schürmann

Publication date: 7 November 2010

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0804.0036

zbMATH Keywords

covering radiusVoronoi cellDelone celllattice isomorphism problemquantizer constant

Mathematics Subject Classification ID

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

Related Items (23)

Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ The contact polytope of the Leech lattice ⋮ The Optimal Lattice Quantizer in Nine Dimensions ⋮ On the sum of a parallelotope and a zonotope ⋮ Tropical moments of tropical Jacobians ⋮ The neighborhood of the Voronoi main perfect form from five variables ⋮ Inhomogeneous extreme forms ⋮ Unnamed Item ⋮ Computation of Euclidean minima in totally definite quaternion fields ⋮ On the Voronoi Conjecture for Combinatorially Voronoi Parallelohedra in Dimension 5 ⋮ Delaunay polytopes derived from the Leech lattice ⋮ Voronoi polytopes for polyhedral norms on lattices ⋮ The hypermetric cone and polytope on eight vertices and some generalizations ⋮ A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices ⋮ A generalization of Voronoi's reduction theory and its application ⋮ Combinatorial iterated integrals and the harmonic volume of graphs ⋮ Coloring the Voronoi tessellation of lattices ⋮ Covering aspects of the Niemeier lattices ⋮ Computing symmetry groups of polyhedra ⋮ Enumeration of the facets of cut polytopes over some highly symmetric graphs ⋮ Unnamed Item ⋮ Exploiting Symmetries in Polyhedral Computations ⋮ Deciding Orthogonality in Construction-A Lattices

Uses Software

• cdd
• nauty
• CARAT
• PORTA
• pd
• Polyhedral

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of the covering radius problem
• Computational approaches to lattice packing and covering problems
• Frobenius problem and the covering radius of a lattice
• The perfect lattices \(\Gamma ({\mathfrak A}^ n)\), and the covering density of \(\Gamma ({\mathfrak A}^ 9)\)
• Computing isometries of lattices
• Combinatorial optimization and small polytopes
• Approximating CVP to within almost-polynomial factors is NP-hard
• Delaunay polytopes of cut lattices
• On lattice covering density for \(n = 13\) and \(n = 15\)
• Geometry and Topology for Mesh Generation
• The Complexity of Vertex Enumeration Methods
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Classification of eight-dimensional perfect forms
• Lattices Which Are Good for (Almost) Everything
• Crystallographic Algorithms and Tables
• Hard Enumeration Problems in Geometry and Combinatorics
• Lectures on Polytopes
• Algebraic Potential Theory on Graphs
• Integration on a convex polytope
• The density of a lattice covering forn= 11 andn= 14
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
• Optimization of lattices for quantization
• Voronoi Domains and Dual Cells in the Generalized Kaleidoscope with Applications to Root and Weight Lattices
• Computing the Voronoi cell of a lattice: the diamond-cutting algorithm
• On the Lattice Isomorphism Problem
• Convex Analysis
• Extreme Forms
• Geometry of cuts and metrics
• Generating all vertices of a polyhedron is hard

This page was built for publication: Complexity and algorithms for computing Voronoi cells of lattices