Voronoi Cells, Holes and Covering Radius

The functions in this section compute the Voronoi cell of a lattice around the origin and associated information. Note that the computation of the Voronoi cell is of truly exponential complexity, and therefore the use of these functions is restricted to small dimensions (up to about 10). See [JC98] for the relevant definitions.

A lattice to which any of these functions are applied must be an exact lattice (over Z or Q).

VoronoiCell(L) : Lat -> [ ModTupFldElt ], SetEnum , [ ModTupFldElt ]

Return the Voronoi cell of the lattice L around the origin which is the convex polytope consisting of all the points closer to the origin than to any other lattice point of L. This function returns three values:

(a)

A sequence V of vectors which are the vertices of the Voronoi cell.

(b)

A set E of pairs, where each pair {i, j} represents an edge connecting V[i] and V[j].

(c)

A sequence P of vectors defining the relevant hyperplanes. A vector p corresponds to the hyperplane given by (x, p) = (Norm)(p)/2.

VoronoiGraph(L) : Lat -> GrphUnd

Return a graph having the vertices and edges of the Voronoi cell of the lattice L as vertices and edges, respectively.

Holes(L) : Lat -> [ ModTupFldElt ]

Return a sequence of vectors which are the holes of the lattice L. The holes are defined to be the vertices of the Voronoi cell around the origin. Note that this involves computing the Voronoi cell of L around the origin.

DeepHoles(L) : Lat -> [ ModTupFldElt ]

Return a sequence of vectors which are the deep holes of the lattice L. The deep holes are defined to be the holes of maximum norm and are points of maximum distance to all lattice points. Note that this involves computing the Voronoi cell of L around the origin.

CoveringRadius(L) : Lat -> FldRatElt

Return the squared covering radius of the lattice L, which is the norm of the deep holes of L. Note that this involves computing the Voronoi cell of L around the origin.

VoronoiRelevantVectors(L) : Lat -> [ ModTupFldElt ]

Return the Voronoi relevant hyperplanes (as a set of vectors) of the Voronoi cell of L around the origin. Note that this is the same as the third return value of the VoronoiCell intrinsic. However, it is usually much faster since it does not compute the Voronoi cell of L. The algorithm employed is [AEVZ02, Section C].

> L := LatticeWithGram(6, [4, 1,4, 2,2,4, 2,2,1,4, 2,2,1,1,4, 2,2,2,2,2,4]);
> L;
Standard Lattice of rank 6 and degree 6
Inner Product Matrix:
[4 1 2 2 2 2]
[1 4 2 2 2 2]
[2 2 4 1 1 2]
[2 2 1 4 1 2]
[2 2 1 1 4 2]
[2 2 2 2 2 4]
> time V, E, P := VoronoiCell(L);
Time: 1.740
> #Holes(L), #DeepHoles(L), CoveringRadius(L);
782 28 5/2

> M := MatrixRing(Rationals(), 6) ! InnerProductMatrix(L);
> N := [ (v*M, v) : v in V ];                                 
> norms := Sort(Setseq(Set(N))); norms;                       
[ 17/9, 2, 37/18, 20/9, 7/3, 5/2 ]
> card := [ #[ x : x in N | x eq n ] : n in norms ]; card;    
[ 126, 16, 288, 180, 144, 28 ]

> #V, #E, #P;
782 4074 104
> { Norm(L!p) : p in P };
{ 4, 6 }
> #ShortVectors(L, 6);
52

> G := VoronoiGraph(L);
> IsConnected(G);
true
> Diameter(G);
8
> Maxdeg(G);
20 ( -1   0 1/2 1/2 1/2   0)
> v := RSpace(Rationals(), 6) ! [ -1, 0, 1/2, 1/2, 1/2, 0 ]; (v*M, v);
5/2