Voronoi Cells of Lattices with Respect to Arbitrary Norms

  title={Voronoi Cells of Lattices with Respect to Arbitrary Norms},
  author={Johannes Bl{\"o}mer and Kathl{\'e}n Kohn},
We study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms. On the positive side, we show for strictly convex and smooth norms that the geometry of Voronoi cells of lattices in any dimension is similar to the Euclidean case, i.e., the Voronoi cells are defined by the so-called Voronoi-relevant vectors and the facets of a Voronoi cell are in one-to-one correspondence with these vectors. On the negative side, we show that Voronoi cells are combinatorially… Expand
Note on minimal number of skewed unit cells for periodic distance calculation
This paper describes how to obtain all primitive cells of a lattice that realise the smallest number of copies needed and give them explicitly in 2D and 3D. Expand
Star-shaped metrics for mechanical metamaterial design
A method for designing mechanical metamaterials based on the novel concept of Voronoi diagrams induced by star-shaped metrics, which supports interpolation between arbitrary metrics opens up a rich space of structures with interesting aesthetics and a wide range of mechanical properties. Expand


Complexity and algorithms for computing Voronoi cells of lattices
This paper uses its implementation, which drastically outperforms those of current computer algebra systems, to find the vertices of Voronoi cells and quantizer constants of some prominent lattices. Expand
Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
A novel algorithm for enumerating lattice points in any convex body known as the M-ellipsoid is given, and an expected O(f*(n))^n-time algorithm for Integer Programming, where f*( n) denotes the optimal bound in the so-calledflatnesstheorem, which is conjectured to be f* (n) = O(n). Expand
Voronoi polytopes for polyhedral norms on lattices
The algorithms, that are proposed, use the symmetries effectively in order to compute a decomposition of the space into convex polytopes named VN-spaces and the Voronoi polytope and other geometrical information are easily obtained. Expand
Voronoi diagrams—a survey of a fundamental geometric data structure
Computational geometry is concerned with the design and analysis of algorithms for geometrical problems. In addition, other more practically oriented, areas of computer science— such as computerExpand
A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
A new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function is given. Expand
Closest point search in lattices
An efficient closest point search algorithm, based on the Schnorr-Euchner (1995) variation of the Pohst (1981) method, is implemented and is shown to be substantially faster than other known methods. Expand
Lattice Sparsification and the Approximate Closest Vector Problem
A method for "spar-sifying" any input lattice while approximately maintaining its metric structure is employed, which employs the idea of random sublattice restrictions, which was first employed by Khot for proving hardness for Shortest Vector Problem (SVP) under lp norms. Expand
On Bisectors in Minkowski Normed Spaces
We discuss the concept of the bisector of a segment in a Minkowski normed n-space, and prove that if the unit ball K of the space is strictly convex then all bisectors are topological images of aExpand
The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)
  • M. Ajtai
  • Computer Science, Mathematics
  • STOC '98
  • 1998
There is a prob-abilistic Turing-machine which in polynomial time reduces any problem in NP to instances of the shortest vector problem, provided that it can use an oracle which returns the solution of the longest vector problem if an instance of it is presented (by giving a basis of the corresponding lattice). Expand
Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima
A probabilistic single exponential time algorithm for Sap for arbitrary lP norms for the l2 norm to arbitrary lp norms is described and the result generalize and extend previous results of Ajtai, Kumar and Sivakumar. Expand