Complexity and algorithms for computing Voronoi cells of lattices

Details Complexity and algorithms for computing Voronoi cells of lattices Complexity and algorithms for computing Voronoi cells of lattices

2008-03-31

arxiv.org/abs/0804.0036v4

Math. Comp. 267 (2009), 1713-1731

Mathematics

Metric Geometry

20 pages, 2 figures, 5 tables

Scientific paper

10.1090/S0025-5718-09-02224-8

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.

Affiliated with

Also associated with

No associations

Rating

Complexity and algorithms for computing Voronoi cells of lattices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity and algorithms for computing Voronoi cells of lattices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity and algorithms for computing Voronoi cells of lattices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216245