[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Voronoi Cells, Holes and Covering Radius

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 is therefore the use of these functions is restricted to small dimensions (up to about 10). See [J.H. Conway, N.J.A. Sloane, op. cit.] 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 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:
VoronoiGraph(L) : Lat -> GrphUnd
Return a graph having the vertices and edges of the Voronoi cell of L as vertices and edges, respectively.
Holes(L) : Lat -> [ ModTupFldElt ]
Return a sequence of vectors which are the holes of 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 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 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.

Example Lat_Voronoi (H45E12)

We compute the Voronoi cell of a perfect lattice of dimension 6.

> 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: 26.609
> #Holes(L), #DeepHoles(L), CoveringRadius(L);
782 28 5/2
The Voronoi cell has 782 vertices, but only 28 of these are of maximal norm 5/2 and therefore deep holes. We now compute the norms and cardinalities for the shallow holes.

> 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 ]
So there are 126 holes of norm 17/9, 16 holes of norm 2, etc. We now investigate the Voronoi cell as a polyhedron.

> #V, #E, #P;
782 4074 104
> { Norm(L!p) : p in P };
{ 4, 6 }
> #ShortVectors(L, 6);
52
The polyhedron which is the convex closure of the holes has 782 vertices, 4074 edges and 104 faces. The faces are defined by vectors of length up to 6 and all such vectors are relevant (since there are only 104). We finally look at the graph defined by the vertices and edges of the Voronoi cell.

> 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
The graph is (of course) connected, its diameter is 8 and the vertices of maximal degree 20 are exactly the deep holes.
[Next] [Prev] [Right] [Left] [Up] [Index] [Root]