|
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.
v in P : TorLatElt,TorPol -> BoolElt
Returns true if and only if the point v is contained in the cone C or polyhedron P.
IsInInterior(v,P) : TorLatElt,TorPol -> BoolElt
Returns true if and only if the point v lies in the strict interior of the cone C or polyhedron P.
IsOnBoundary(v,P) : TorLatElt,TorPol -> BoolElt
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.
InteriorPoints(P) : TorPol -> SeqEnum[TorLatElt]
BoundaryPoints(P) : TorPol -> SeqEnum[TorLatElt]
The integral toric lattice points, the strictly interior
lattice points, or the boundary lattice points
of the polytope P.
NumberOfInteriorPoints(P) : TorPol -> RngIntElt
NumberOfBoundaryPoints(P) : TorPol -> RngIntElt
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.
VolumeOfBoundary(P) : TorPol -> FldRatElt
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.
We begin by creating a random rational 2-dimensional polytope in a 3-dimensional lattice. We shall then apply a random change of basis to P to generate an isomorphic polytope Q.
> 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;
true
The lattice isomorphism can easily be recovered as a matrix in GL 3(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.
PALPNormalForm(P) : TorPol -> SeqEnum, GrpPermElt
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.
We start by computing the normal form of a lattice polytope.
> 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;
true
Now 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 GL 2(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.
We wish to classify all polygons in an [0, N] x [0, N] box but not contained in a smaller [0, N - 1] x [0, N - 1] box, up to change of basis and translation. To do this we make use of the affine normal form. We will perform the classification for N≤4.
> 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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|