Given a polygon, one might want to know how many integral points it contains, and one might want to list them. These are computed by different algorithms (although one can of course list the points and then count them). For point counting we use the methods of Barvinok and Pommersheim ([BP99]), as described in [DLHTY04]. More generally, one might want to know the number of points in integral dilations of a polytope: these numbers are the coefficients of a generating function, the Ehrhart series; this is discussed in a later section.
Returns true if and only if the point v is contained in the cone C or polyhedron P.
Returns true if and only if the point v lies in the strict interior of the cone C or polyhedron P.
Returns true if and only if the point v lies on the (relative) boundary of the cone C or polyhedron P.
Returns true if and only if the polyhedron P contains an integral lattice point.
The integral toric lattice points, the strictly interior lattice points, or the boundary lattice points of the polytope P.
The number of integral toric lattice points, the number of strictly interior lattice points, or the number of boundary lattice points of the polytope P.
The normalised volume and normalised boundary volume of the polytope P.
The rational generating function (Ehr)P(t) of the Ehrhart series for the polytope P. The coefficient cm of tm in the power-series expansion of (Ehr)P(t) is equal to the number of lattice points in mP.
The Ehrhart δ-vector (also known as the h * -vector) for the polytope P. This is a sequence of integers defining the numerator of the Ehrhart generating function (Ehr)P(t) of P. More precisely, if n=(dim)(P) and k∈Z>0 is the smallest dilation of P such that kP is a lattice polytope, then (Ehr)P(t) = (δ0 + δ1t + ... + δk(n + 1) - 1tk(n + 1) - 1) / (1 - tk)n + 1.
A sequence representing the Ehrhart (quasi-)polynomial for the polytope P. That is, a sequence of polynomials [p0, ..., pr - 1] of length r, the quasi-period of the Ehrhart polynomial, so that the number of lattice points of the dilation mP is the value of ps(k), where m=kr + s is the Euclidean division of m by r; in other words, s is the least residue of m modulo r. Note that since Magma indexes sequences from 1, we have that pi = EhrhartPolynomial(P)[i+1].
The first l + 1 coefficients of the Ehrhart series for the polytope P (starting with 0P up to and including lP).
The number of lattice points in the (non-negative, integral) dilation kP of the polytope P.
It is often necessary to determine whether two convex polytopes P and Q, embedded in a lattice Λ, are isomorphic with respect to a lattice automorphism; that is, whether there exists an element of GLn(Z) sending P to Q. For example, in toric geometry lattice polytopes form one of the key constructions of projective toric varieties, and any classification must somehow address the issue of whether there exists an automorphism of the underlying lattice sending P to Q.
In general, any isomorphism problem can be solved in one of two ways: on a case-by-case basis by constructing an explicit isomorphism between the two objects, or by determining a normal form for each isomorphism class. Both approaches are supported.
The first approach -- dynamically constructing a lattice-preserving isomorphism in GLn(Z) between the two polytopes -- has the advantage that it works equally well for rational polytopes and for polytopes of non-zero codimension. The algorithm works by reducing the problem to a graph isomorphism question to which well-developed tools such as Brendan McKay's Nauty software [McK81], [McK] can then be applied.
The second approach -- to compute a normal form (NF)(P) for each isomorphism class -- works only for lattice polytopes of codimension zero. The normal form algorithm used by Magma is based on one developed by Kreuzer and Skarke for their Palp software [KS04]. Briefly, row and column permutations are applied to the vertex--facet pairing matrix of P, placing it in a form that is maximal with respect to a certain ordering. This in turn defines an order in which to list the vertices of P; the choice of basis is fixed by taking the Hermite normal form.
Slightly more generally, one may wish to consider polytopes up to change of basis and translation, i.e. up to affine equivalence. Once again Magma offers two solutions. Affine equivalence between two (possibly rational) polytopes can be determined on a case-by-case basis, or an affine normal form can be calculated. All the algorithms are described in detail in [GK13].
Returns true iff the polytopes P and Q are isomorphic, i.e. if there exists an element in GLn(Z) sending P to Q. If true, also gives an isomorphism from P to Q. The polytopes may be rational, and need not be of maximum dimension in the ambient lattice.
> P:=RandomPolytope(3,3,4) / 2;
> P;
2-dimensional polytope P with 3 generators:
( 0, -2, 1),
( 0, 1/2, -2),
(-1, 3/2, 0)
> Q:=P * RandomGLnZ(3,3,3);
> Q;
2-dimensional polytope Q with 3 generators:
( -2, -3, -1),
(1/2, 5/2, -3/2),
(5/2, 3/2, 5/2)
Now we recover the isomorphism between these two polytopes:
> bool,phi:=IsIsomorphic(P,Q); > bool; true > Image(phi,P) eq Q; trueThe lattice isomorphism can easily be recovered as a matrix in GL3(Z):
> M:=DefiningMatrix(phi); > M; [-1 0 -1] [ 1 1 1] [ 0 -1 1] > P * M eq Q; true
Returns true iff the polytopes P and Q are equivalent, i.e. if there exists an element in GLn(Z) and lattice translation sending P to Q. If true, also gives the map as a lattice map varphi and translation v such that varphi(P) + v = Q.
The Palp normal form of the maximum dimensional lattice polytope P. This is given as a sequence of lattice points equal to the (ordered) vertices of (NF)(P). Also gives the permutation of the vertices of P used to calculate this normal form.
> P:=Polytope([[62,23],[-8,-3],[-27,-10]]);
> NF:=NormalForm(P);
> NF;
[
(1, 0),
(0, 1),
(-2, -1)
]
People familiar with toric geometry will recognise this as the weighted projective space P(1, 1, 2); we can verify this in one line of code by comparing the normal forms:
> NormalForm(PolytopeOfWPS([1,1,2])) eq NF; trueNow we exhibit one way to recover the change of basis that sends P to its normal form (NF)(P). We need to capture the permutation of the vertices, so we redo the calculation and this time we save the second return value:
> NF,perm:=NormalForm(P); > perm; (1, 3)The change of basis in GL2(Z) is now trivial to compute:
> vertsP:=PermuteSequence(Vertices(P),perm);
> VP:=Matrix(vertsP);
> VQ:=Matrix(NF);
> M:=Solution(Transpose(VP),Transpose(VQ));
> M:=Transpose(M);
> M;
[ -3 10]
[ 8 -27]
> P * M;
2-dimensional polytope with 3 vertices:
(-2, -1),
( 0, 1),
( 1, 0)
The affine normal form of the maximum dimensional lattice polytope P. This is given as a sequence of lattice points equal to the (ordered) vertices of (AffNF)(P). Also gives the permutation of the vertices of P used to calculate this affine normal form.
> procedure classify_polygons_recurse(P,~class,allclass)
> for v in Vertices(P) do
> Q:=Polytope(Exclude(Points(P),v));
> if Dimension(Q) eq 2 then
> AffNF:=AffineNormalForm(Q);
> if not AffNF in class and
> not &or[AffNF in subclass : subclass in allclass] then
> Include(~class,AffNF);
> $$(Q,~class,allclass);
> end if;
> end if;
> end for;
> end procedure;
>
> function classify_polygons(N)
> allclass:=[];
> for i in [1..N] do
> B:=Polytope([[0,0],[i,0],[0,i],[i,i]]);
> class:={AffineNormalForm(B)};
> classify_polygons_recurse(B,~class,allclass);
> Append(~allclass,class);
> end for;
> return allclass;
> end function;
>
> classification:=classify_polygons(4);
> [#class : class in classification];
[ 2, 15, 131, 1369 ]
This is the maximal vertex--facet pairing matrix of P constructed as part of the normal form algorithm. For the details of its construction, see [KS04], [GK13].
The subgroup of GL(n, (Z)) (acting on the ambient lattice) which leaves the polyhedron P unchanged.
> P:=CrossPolytope(2);
> P;
2-dimensional polytope P with 4 vertices:
( 1, 0),
( 0, 1),
(-1, 0),
( 0, -1)
> AutomorphismGroup(P);
MatrixGroup(2, Integer Ring)
Generators:
[0 1]
[1 0]
[ 0 1]
[-1 0]
A sequence of polytopes that make a triangulation of the polytope P.
A sequence of polytopes that make a triangulation of the boundary of the polytope P.