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).
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.
Return a graph having the vertices and edges of the Voronoi cell of the lattice L as vertices and edges, respectively.
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.
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.
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.
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/2The 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/2The graph is (of course) connected, its diameter is 8 and the vertices of maximal degree 20 are exactly the deep holes.