|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
A cone C (in a toric lattice L) is the convex hull of finitely
many rays (or zero). Mathematically, ray is a half line emanating
from the origin, but, as is common, we treat rays synonymously with
the first lattice point on the ray outside the origin---thus, for
example, an intrinsic that returns a ray will actually return a
point of the ambient lattice.
Rays that are the intersection of a linear hyperplane with C are
called extreme rays of C---these are the corner edges of C.
A cone is regular if it is generated (as a semigroup in the
( Z)-module L) by its extreme rays (in other words, by
the primitive vectors on its extreme rays).
A (rational) polytope (in a toric lattice L)
is the convex hull of finitely many points in L.
(The points do not need to be integral points.)
Combining all concepts so far,
a (rational) polyhedron is the Minkowski sum of a polytope
and a cone---the latter is the tail cone and is unique; the
smallest possible polytope is unique but seems not to be used
in the theory.
We also use the expressions compact part and infinite part
to indicate the polytope and the cone used to define a polyhedron.
Subsections
Cones in toric lattices are of type TorCon.
The cone in a toric lattice generated by a sequence A of its elements
(or sequences of integer or rational coefficients).
The cone in a toric lattice generated by a single element v of
that lattice.
The cone in a toric lattice L defined by the set B of elements of
the dual lattice L^(check( )) (or simply by a set of sequences of integer
or rational coefficients): the cone is the intersection of half-spaces
b ≥0 as b runs through B.
The Minkowski sum of the toric cones C and D.
FullCone(n): RngIntElt -> TorCon
The cone which is the entire toric lattice L, or the toric lattice
of dimension n for a positive integer n.
PositiveQuadrant(n) : RngIntElt -> TorCon
The cone in the toric lattice L generated by the
standard basis vectors of L,
or that of the toric lattice of dimension n for a positive integer n.
ZeroCone(n): RngIntElt -> TorCon
The cone which consists of only the origin of the toric lattice L,
or of the toric lattice of dimension n for a positive integer n.
The dual cone to the cone C.
Polytopes and polyhedra in toric lattices are of type TorPol.
Polyhedron(C) : TorCon -> TorPol
level: RngIntElt Default: 1
The polyhedron constructed as the slice of the toric cone C
by the hyperplane determined by the primitive dual vector v
at height 1.
The height can be changed using the parameter level.
If the form v is not specified, then a default form
will be used; typically this will be (1, 0, ..., 0), but
cannot be assumed since it will depend on how C was created.
The polyhedron arising as the preimage of the cone C under the affine
map f + v.
We construct some polyhedra by taking slices of the positive
quadrant in 3-space.
> C := PositiveQuadrant(3);
> C;
3-dimensional simplicial cone C with 3 minimal generators:
(1, 0, 0),
(0, 1, 0),
(0, 0, 1)
We slice using dual vectors, so we recover the dual lattice M
to the ambient lattice of C.
Some slices are compact, some are not.
> M := Dual(Ambient(C));
> P := Polyhedron(C, M ! [1,2,3]);
> IsPolytope(P);
true
> Q := Polyhedron(C, M ! [1,-2,3] );
> IsPolytope(Q);
false
> Q;
2-dimensional polyhedron Q with 1-dimensional finite part with 2 vertices:
( 1, -1),
( 0, -1/3)
and 2-dimensional infinite part given by a cone with 2 minimal generators:
( 2, -1),
( 0, 1)
We can change the level, or height, at which the slice is taken.
> R := Polyhedron(C, M ! [1,2,3] : level := -5);
> R;
Empty polyhedron
HalfspaceToPolyhedron(Q,h) : [FldRatElt],FldRatElt -> TorPol
The halfspace { u | v.u ≥h } as a polyhedron,
where v is a point of a toric lattice (or a sequence of
integral or rational numbers that are its coefficients)
and h∈Q.
HyperplaneToPolyhedron(Q,h) : [FldRatElt],FldRatElt -> TorPol
The hyperplane { u | v.u = h } as a polyhedron,
where v is a point of a toric lattice (or a sequence of
integral or rational numbers that are its coefficients)
and h∈Q.
C + P : TorCon,TorPol -> TorPol
The polyhedron constructed as the Minkowski sum of the
polytope P and the cone C.
The empty polyhedron in the toric lattice L.
RandomPolytope(d,n,k) : RngIntElt,RngIntElt,RngIntElt -> TorPol
A polytope in the toric lattice L (or a toric lattice of
dimension d) generated by n random points
with coefficients of modulus at most the non-negative integer k.
If P is a polytope of maximum dimension containing the origin in its
strict interior, then this is the corresponding polar polytope.
The polar dual polyhedron to the polyhedron P, namely
P^(check( )) =
{ u ∈L^(check( )) | u.v ≥ - 1 forall v ∈P }.
The cone C as a polyhedron.
The d-dimensional cross-polytope.
The maximum dimensional cross-polytope in the toric lattice L.
The d-dimensional simplex given by the standard basis and the origin.
The simplex given by the standard basis and the origin of the
toric lattice L.
The cyclic polytope generated by n points in d-dimensional space.
The cyclic polytope generated by n points in the toric lattice L.
IntegralPart(P) : TorPol -> TorPol
The polytope defined by taking the convex hull of the vertices of the
polyhedron P. This is the smallest polytope which can occur
as a factor in an expression of P as the Minkowski sum of a
polytope and a cone.
The tail cone of the polyhedron P.
A cone C such that the polyhedron P is the intersection of C
with a hyperplane at height one, together with the embedding of the
ambient lattice of P into the ambient lattice of C.
IsEmpty(P) : TorPol -> BoolElt
True if and only if the polyhedron P contains no lattice points
(either in its interior or on its boundary).
One can build a polytope as the convex hull of a finite sequence
of points---these may be elements of a toric lattice or simply
sequences of integer or rational coefficients.
> P := Polytope([[-4,2,1],[0,3,4],[3,1,-3],[3,0,0],[2,-1,1]]);
The polar polyhedron comprises dual vectors that evaluate
to at least -1 on P. It is compact if and only if the
origin lies in the interior of P.
> D := Polar(P);
> D;
3-dimensional polyhedron D with 3-dimensional finite part with 5 vertices:
(1/67, -37/67, 11/67),
( 1/2, 1, -1),
(-1/3, -3/13, -1/13),
(-1/3, 1/2, 1/6),
(-1/3, 1/21, -2/7)
and 3-dimensional infinite part given by a cone with 3 minimal generators:
( 7, 9, 10),
( 1, 2, 0),
( 2, 9, 5)
Since D is infinite, the is no intrinsic to list its integral
points, but one can determine whether it contains integral points
at all.
> ContainsIntegralPoint(D);
true
The compact and infinite parts of D can be recovered: the infinite
part is uniquely defined, but the compact part is not.
> cD := CompactPart(D);
> cD;
3-dimensional polytope cD with 5 vertices:
(1/67, -37/67, 11/67),
( 1/2, 1, -1),
(-1/3, -3/13, -1/13),
(-1/3, 1/2, 1/6),
(-1/3, 1/21, -2/7)
> iD := InfinitePart(D);
> iD;
3-dimensional cone iD with 3 minimal generators:
(7, 9, 10),
(1, 2, 0),
(2, 9, 5)
Polytopes are special cases of polyhedra (those whose infinite tail
cone is the zero cone, or equivalently those that are compact),
and the distinction can be determined.
> IsPolytope(cD);
true
> IsPolytope(iD);
false
> C:=Cone([[0,1,0],[0,1,1],[1,1,2],[1,1,4]]);
> P:=Polyhedron(C);
> P;
2-dimensional polyhedron P with 1-dimensional finite part with 2
vertices:
(1, 2),
(1, 4)
and 2-dimensional infinite part given by a cone with 2 minimal
generators:
(1, 0),
(1, 1)
> CC:=Cone([[1,0],[1,1]]);
> QQ:=Polytope([[1,2],[1,4]]);
> PP:=CC + QQ;
> PP;
2-dimensional polyhedron PP with 1-dimensional finite part with 2
vertices:
(1, 2),
(1, 4)
and 2-dimensional infinite part given by a cone with 2 minimal
generators:
(1, 0),
(1, 1)
But there's a potential catch.
> PP eq P;
false
> Ambient(PP);
2-dimensional toric lattice Z^2
> Ambient(P);
2-dimensional toric lattice ker <1, 0, 0>
> P:=ChangeAmbient(P,Ambient(PP));
> PP eq P;
true
The ambients are different simply because of the
method of construction of the two polyhedra, but they
can be forced into the same space.
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.
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.
The number of integral toric lattice points of the polytope P.
The rational generating function of the Ehrhart series for the polytope P.
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 nP is
the value of ps(k)
where n=kr + s is the Euclidean division of n by r;
in other words, s is the least residue of n 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.
Cones, polytopes and polyhedra have similar combinatorial
features: they are composed of faces of various dimensions
that meet in faces of lower dimensions.
Some functions apply to all of these geometrical objects, some do not.
A face of a cone C is the intersection of C with an
affine hyperplane whose defining equation is non-negative on C.
A facet of a cone C is a codimension 1 face of C.
Defintions for polytopes and polyhedra are similar.
A sequence containing the vertices of the polyhedron P.
The number of vertices of the polyhedron P.
The sequence of generators of the rays of the cone C.
If C is strictly convex, this is the same as the minimal RGenerators.
The ith ray of the of the cone C (in the order returned by Rays(C).
Facets(P) : TorPol -> SeqEnum
A sequence containing all facets of the toric cone C or polyhedron P.
The number of facets of the polyhedron P.
Faces(C,i) : TorCon,RngIntElt -> SeqEnum
A sequence containing all face cones of the toric cone C,
or only those of dimension i if an integer i is also specified.
The face of the toric cone C supported by the toric lattice element
H in the dual lattice to the one containing C
(so H is a linear form on the ambient lattice of C).
LinearSpanEquations(Q) : [TorLatElt] -> SeqEnum
A sequence of equations defining the minimal linear subspace containing the
cone C (or the sequence of toric lattice points Q).
LinearSpanGenerators(Q) : [TorLatElt] -> SeqEnum
A sequence of generators of the minimal linear subspace containing the
cone C (or the sequence of toric lattice points Q).
A basis of the maximal linear subspace contained in the cone C.
If C lies in a toric lattice L, then return
a finite sequence of elements of L that generate C
as a monoid.
If specified, the parameter 'level' restricts the search for generators
to that given level; this assumes that C is graded.
MinimalRGenerators(C) : TorCon -> SeqEnum
If C lies in a toric lattice L, then return
a finite sequence of elements of L that generate C
over Q_ +.
The list is forced to be minimal for MinimalRGenerators,
but might not be otherwise.
Inequalities(P) : TorPol -> SeqEnum
MinimalInequalities(C) : TorCon -> SeqEnum
If the cone C or polyhedron P lies in a toric lattice L, then return
a finite sequence of vectors in the dual lattice check(L)
which define supporting hyperplanes of C or P.
The list is forced to be minimal for MinimalInequalities,
but might not be otherwise.
Build a polytope and recover the inequalities that define it: the
second return value, 3, says that all three inequalities define
facets of P---we see an example below where this is not the case.
> P := Polytope([[1,0],[0,1],[-1,-1]]);
> Inequalities(P);
[
<(2, -1), -1>,
<(-1, -1), -1>,
<(-1, 2), -1>
]
3
For each inequality use HalfspaceToPolyhedron(m,h) to define
the corresponding halfspace, and then intersect them all to
recover P---and finally recover the vertices we started with.
> PP := &meet [HalfspaceToPolyhedron(H[1],H[2]) : H in Inequalities(P)];
> PP eq P;
true
> PP;
2-dimensional polytope PP with 3 vertices:
( 0, 1),
(-1, -1),
( 1, 0)
It can happen that a polytope does not span the ambient
toric lattice in which it lies and that some of the inequalities
are used to cut out the affine subspace that it does span.
> Q := Polytope([[1,0,2],[0,1,2],[-1,0,2],[0,-1,2]]);
> Inequalities(Q);
[
<(1, -1, 0), -1>,
<(-1, -1, 0), -1>,
<(-1, 1, 0), -1>,
<(1, 1, 0), -1>,
<(0, 0, 1), 2>,
<(0, 0, -1), -2>
]
4
In this case the final two inequalities are opposites
of one another and cut out the affine hyperplane z=2.
The second return value 4 indicates that the first 4
inequalities are cutting out facets of the polytope while
the remaining inequalities are cutting out the affine
hyperplane.
Here we find the generators of a cone in the
sublattice spanned by its defining lattice points.
First build some points in a toric lattice and
make the cone they generate.
> L := ToricLattice(4);
> B := [ L | [1,2,3,-3], [-1,0,1,0], [1,2,1,-2], [2,0,0,-1], [0,0,2,-1] ];
> L1,f := Sublattice(B);
> Dimension(L1);
3
> C := Cone(B);
> IsNonsingular(C);
false
> ZGenerators(C);
[
(-1, 0, 1, 0),
(0, 1, 1, -1),
(1, 2, 1, -2),
(2, 0, 0, -1)
]
Using the embedding map f, pull the cone back to the lattice span of C.
> C1 := C @@ f;
In the smaller lattice, this cone is nonsingular.
> IsNonsingular(C1);
true
We can find out which points generate the cone in the smaller
lattice and compare them with the generators of the original cone.
> B1 := ZGenerators(C1);
> B1;
[
(-1 0 1),
(1 1 0),
( 2 0 -1)
]
> [ Index(B,f@b) : b in B1 ];
[ 2, 3, 4 ]
Ambient(P) : TorPol -> TorLat
The ambient toric lattice of the toric cone C or polyhedron P.
ChangeAmbient(P,L) : TorPol,TorLat -> TorPol
Make a cone or polyhedron identical to the toric cone C or
polyhedron P but lying in the toric lattice L; the identification
of the existing ambient toric lattice with L is simply
by identification of the two standard bases.
Dimension(P) : TorPol -> RngIntElt
The dimension of the toric cone C or polyhedron P.
The index of the sublattice generatated by the minimal
( R)-generators of the cone C in its linear span.
IsMaximalDimension(P) : TorPol -> BoolElt
True if and only if the cone C of polyhedron P has dimension
equal to that of its ambient lattice.
IsSimplicial(C) : TorCon -> BoolElt
IsSimplicial(P) : TorPol -> BoolElt
True if and only if the cone C or the polyhedron P is simplicial.
True if and only if the polyhedron P is a simplex.
True if and only if the polyhedron P is simple.
True if and only if the cone C is supported at the origin of
its ambient toric lattice.
True if and only if the rays of the cone C
are a Z-basis of its ambient toric lattice.
True if and only if the cone C has (the primitive points on its)
rays contained in an affine hyperplane that is defined by
an integral equation.
True if and only if the cone C has (the primitive points on its)
rays contained in an affine hyperplane.
The Gorenstein index of the affine variety corresponding to the
cone C together with the dual vector determining the equation
of the hyperplane. (It is an error if C is not Q-Gorenstein.)
True if and only if the cone C is simplicial.
True if and only if the singularity of the affine variety associated
to the cone C is (at worst) terminal.
True if and only if the singularity of the affine variety associated
to the cone C is (at worst) canonical.
We make the cone corresponding to the (affine) terminal quotient
singularity C3/(Z/5) where Z/5 acts as the 5th roots
of unity in the diagonal representation ( diag)(1, 2, 3).
> L := ToricLattice(3);
> v := L ! [1/5,2/5,3/5];
> LL,emb := AddVectorToLattice(v);
> C := PositiveQuadrant(L);
> CC := emb @ C;
> CC;
Cone CC with 3 generators:
(1, 0, 0),
(0, 1, 0),
(3, 1, 5)
We can check that this really is terminal and compute its Gorenstein
index, the least positive multiple of the canonical class that
is Cartier.
> IsTerminal(CC);
true
> GorensteinIndex(CC);
5 (1, 1, -3/5)
We can compute a resolution of singularities of this cone,
the analogue of a simplicial subdivision for cones,
although we must treat it as a fan to do so.
> F := Fan(CC);
> F;
Fan F with 3 rays:
(0, 1, 0),
(1, 0, 0),
(3, 1, 5)
and one cone with indices:
[ 1, 2, 3 ]
> Resolution(F);
Fan with 8 rays:
(0, 1, 0),
(1, 0, 0),
(3, 1, 5),
(2, 1, 2),
(1, 1, 1),
(3, 1, 3),
(3, 1, 4),
(2, 1, 3)
and 11 cones
Note that this is not a minimal resolution: such a resolution
would only need to subdivide at the four additional rays
at the (original) lattice points 1/5(1, 2, 3), 1/5(2, 4, 1),
1/5(3, 1, 4) and 1/5(4, 3, 2).
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.
True if and only if the cones C and D are equal, that is,
they lie in the same toric lattice and have identical supports.
True if and only if the polyhedra P and Q are equal, that is,
they lie in the same toric lattice and have identical supports.
The intersection of the cones C and D; the cones must
lie in the same toric lattice otherwise an error is reported.
The intersection of the polyhedra P and Q; the polyhedra must
lie in the same toric lattice otherwise an error is reported.
The Minkowski sum of the cones C and D.
P + C : TorPol,TorCon -> TorPol
The Minkowski sum of the polyhedron P and cone C.
The Minkowski sum of the polyhedra P and Q.
The convex hull of the Cartesian product of the polyhedra P and Q.
The cone of maximal dimension given by the intersection of the cone C
with its linear span. Also gives the embedding of the sublattice in the
ambient toric lattice.
The polyhedron of maximal dimension given by the intersection of the
toric lattice containing the polyhedron P with an affine sublattice
of dimension equal to the dimension of P.
Also gives the affine embedding as a lattice embedding and translation.
The stricly convex cone given by the quotient of the cone C by its
maximal linear subspace. Also gives the quotient map.
The face of the cone C supported by the hyperplane defined by H
(that is, H is an element of the toric lattice dual to the
ambient lattice of C).
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
