Polytopes, Cones, and Polyhedra
A (rational) polytope (in a lattice \(L={\mathbb{Q}}^n\)) is the convex hull of finitely many points in \(L\). (The points do not need to be integral points.)
A cone \(C\) (in a lattice \(L\)) is the convex hull of finitely many rays (or zero). Precisely, a ray is a half line emanating from the origin, but, as is common, we treat rays synonymously with the first integral lattice point on the ray outside the origin—thus, for example, an intrinsic that returns a ray will actually return an primitive integral 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 \({\bf Z}\)-module \({\mathbb{Z}}^n\subset L\)) by its extreme rays (in other words, by the integral vectors on its extreme rays).
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.
Polytopes
- Polytope(Q): SeqEnum -> TorPol
The polytope defined by taking the convex hull of the sequence of points \(Q\), where the points can be specified as sequences of integers of rational numbers (of some fixed length) or as points of a common lattice.
- PolyhedronWithInequalities(A, c): SeqEnum, [RngIntElt] -> TorPol
- PolyhedronWithInequalities(A, c): [TorLatElt], [RngIntElt] -> TorPol
The polyhedron defined by the system of inequalities \(A_iv\geq c_i\) for each vector \(A_i\) and integer \(c_i\).
- RandomPolytope(L, n, k): TorLat, RngIntElt, RngIntElt -> TorPol
- 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 integral points with coefficients of modulus at most the non-negative integer \(k\).
- BoundingBox(P): TorPol -> TorPol, TorLatElt, TorLatElt
The smallest box \(Q\) containing the polytope \(P\). Also gives the bottom-left and top-right corners of \(Q\).
- Polar(P): TorPol -> TorPol
The polar dual polyhedron to the polyhedron \(P\), namely
\[P^{\star} = \left\{ u \in L^{\vee} \ | \ u\cdot v \ge -1 \ \forall v \in P \right\}.\]
- CrossPolytope(L): TorLat -> TorPol
- CrossPolytope(d): RngIntElt -> TorPol
The maximum dimensional cross-polytope in the lattice \(L\), or of dimension \(d\) for an integer \(d\).
- StandardSimplex(L): TorLat -> TorPol
- StandardSimplex(d): RngIntElt -> TorPol
The simplex given by the standard basis and the origin of the lattice \(L\), or the \(d\)-dimensional simplex given by the standard basis and the origin for an integer \(d\).
- CyclicPolytope(L, n): TorLat, RngIntElt -> TorPol
- CyclicPolytope(d, n): RngIntElt, RngIntElt -> TorPol
The cyclic polytope generated by \(n\) points in the lattice \(L\), or by \(n\) points in \(d\)-dimensional space for an integer \(d\).
Cones
Cones in lattices are of type TorCon.
- Cone(A): Seq -> TorCon
The cone in a lattice generated by a sequence \(A\) of its elements (or simply of sequences of integer or rational coefficients).
- Cone(v): TorLatElt -> TorCon
The cone in a lattice generated by a single element \(v\) of that lattice; namely the single ray \({\mathbb{Q}}^+v\).
- ConeWithInequalities(B): Set -> TorCon
The cone in a lattice \(L\) defined by the set \(B\) of elements of the dual lattice \(L^{\vee}\) (or simply by a set of sequences of integer or rational coefficients). The cone is the intersection of half-spaces \(v\cdot u \ge 0\) as \(v\) runs through \(B\):
\[\bigcap_{v \in B} \left\{ u \in L \mid v\cdot u \ge 0 \right\}.\]
- FullCone(L): TorLat -> TorCon
- FullCone(n): RngIntElt -> TorCon
The cone which is the entire lattice \(L\), or the lattice of dimension \(n\) for a positive integer \(n\).
- PositiveQuadrant(L): TorLat -> TorCon
- PositiveQuadrant(n): RngIntElt -> TorCon
The cone in the lattice \(L\) generated by the standard basis vectors of \(L\), or that of the lattice of dimension \(n\) for a positive integer \(n\).
- ZeroCone(L): TorLat -> TorCon
- ZeroCone(n): RngIntElt -> TorCon
The cone which consists of only the origin of the lattice \(L\), or of the lattice of dimension \(n\) for a positive integer \(n\).
- RandomCone(d, n, k): RngIntElt, RngIntElt, RngIntElt -> TorCon
- RandomCone(L, n, k): TorLat, RngIntElt, RngIntElt -> TorCon
A random cone in a \(d\)-dimensional toric lattice – or in the toric lattice \(L\) – generated by \(n\) points whose coefficients lies between \(-k\) and \(k\).
- RandomPositiveCone(d, n, k): RngIntElt, RngIntElt, RngIntElt -> TorCon
- RandomPositiveCone(L, n, k): TorLat, RngIntElt, RngIntElt -> TorCon
A random cone in a \(d\)-dimensional toric lattice – or in the toric lattice \(L\) – generated by \(n\) points whose coefficients lies between \(0\) and \(k\).
- Dual(C): TorCon -> TorCon
The dual cone to the cone \(C\), namely
\[C^\vee = \left\{ u \in L^\vee \mid v\cdot u \ge 0 \hbox{ for all }v \in C \right\}.\]where \(C\) lies in the lattice \(L\).
- NormalisedCone(P): TorPol -> TorCon
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\).
- ConeInSublattice(C): TorCon -> TorCon, Map
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.
- ConeQuotientByLinearSubspace(C): TorCon -> TorCon, Map, Map
The strictly convex cone given by the quotient of the cone \(C\) by its maximal linear subspace. Also gives the quotient map.
Polyhedra
Polytopes and polyhedra in lattices are of type TorPol.
- Polyhedron(C, H, h): TorCon, TorLatElt, FldRatElt -> TorPol
- Polyhedron(C, H, h): TorCon, TorLatElt, RngIntElt -> TorPol
The polyhedron constructed as the slice of the cone \(C\) by the hyperplane determined by the primitive dual vector \(H\) at height given by the integer or rational number \(h\).
- Polyhedron(C): TorCon -> TorPol
level: RngIntElt Default: 1
The polyhedron arising as the intersection of the cone \(C\) with the hyperplane at height one (can be changed via ‘level’).
- HalfspaceToPolyhedron(v, h): TorLatElt, FldRatElt -> TorPol
- HalfspaceToPolyhedron(Q, h): [FldRatElt], FldRatElt -> TorPol
The halfspace \(\{ u | v\cdot u \ge 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\in{\mathbb{Q}}\).
- HyperplaneToPolyhedron(v, h): TorLatElt, FldRatElt -> TorPol
- HyperplaneToPolyhedron(Q, h): [FldRatElt], FldRatElt -> TorPol
The hyperplane \(\{ u | v\cdot 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\in{\mathbb{Q}}\).
- Polyhedron(C, f, v): TorCon, Map, TorLatElt -> TorPol
The polyhedron arising as the preimage of the cone \(C\) under the affine map \(f + v\).
- PolyhedronInSublattice(P): TorPol -> TorPol, Map, TorLatElt
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.
- FixedSubspaceToPolyhedron(G): GrpMat -> TorPol
- FixedSubspaceToPolyhedron(L, G): TorLat, GrpMat -> TorPol
The subspace (realised as a polyhedron) fixed by the action of the matrix group \(G\) on the toric lattice \(L\). \(G\) should be a subgroup of either \(GL(n,\bf{Z})\) or of \(SL(n,\bf{Z})\), where \(n\) is the dimension of \(L\).
- Example: Polyhedra as Slices of a Quadrant (ex-d6dc93)
Run in calculator (opens in a new tab)
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], 1); > IsPolytope(P); true > Q := Polyhedron(C, M ! [1,-2,3], 1 ); > 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], -5); > R; Empty polyhedron
Arithmetic Operations on Polyhedra
- C eq D: TorCon, TorCon -> BoolElt
Return
trueif and only if the cones \(C\) and \(D\) are equal, that is, they lie in the same toric lattice and have identical supports.
- P eq Q: TorPol, TorPol -> BoolElt
Return
trueif and only if the polyhedra \(P\) and \(Q\) are equal, that is, they lie in the same toric lattice and have identical supports.
- C meet D: TorCon, TorCon -> TorCon
The intersection of the cones \(C\) and \(D\); the cones must lie in the same toric lattice otherwise an error is reported.
- P meet Q: TorPol, TorPol -> TorPol
The intersection of the polyhedra \(P\) and \(Q\); the polyhedra must lie in the same toric lattice otherwise an error is reported.
- P subset Q: TorPol, TorPol -> BoolElt
Return
trueif and only if the support of the polyhedron \(P\) is contained in that of the polyhedron \(Q\); the polyhedra must lie in the same toric lattice otherwise an error is reported.
- C + D: TorCon, TorCon -> TorCon
- P + Q: TorPol, TorPol -> TorPol
The Minkowski sum of the cones \(C\) and \(D\) or of the polyhedra \(P\) and \(Q\).
- P + C: TorPol, TorCon -> TorPol
- C + P: TorCon, TorPol -> TorPol
The polyhedron constructed as the Minkowski sum of the polytope \(P\) and the cone \(C\).
- P * Q: TorPol, TorPol -> TorPol
The convex hull of the Cartesian product of the polyhedra \(P\) and \(Q\).