Basic Combinatorics of Polytopes and Polyhedra#

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\). Definitions for polytopes and polyhedra are similar.

Vertices and Inequalities#

Vertices(P): TorPol -> SeqEnum[TorLatElt]#: A sequence containing the vertices of the polyhedron \(P\).

NumberOfVertices(P): TorPol -> RngIntElt#: The number of vertices of the polyhedron \(P\).

Rays(C): TorCon -> SeqEnum#: The sequence of generators of the rays of the cone \(C\) (returned as primitive lattice points). If \(C\) is strictly convex, this is the same as the minimal \({\bf R}\)-generators.

Ray(C, i): TorCon, RngIntElt -> TorLatElt#: The \(i\)th ray of the of the cone \(C\) (in the order returned by Rays(C)).

LinearSpanEquations(C): TorCon -> SeqEnum#
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(C): TorCon -> SeqEnum#
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\)).

LinearSubspaceGenerators(C): TorCon -> SeqEnum#: A basis of the maximal linear subspace contained in the cone \(C\).

Inequalities(C): TorCon -> SeqEnum#
Inequalities(P): TorPol -> SeqEnum, RngIntElt#
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. If the argument is a polyhedron, then an integer \(k\) is returned as a second return value, so that the first \(k\) inequalities correspond to the facets of \(P\) while the remaining cut out the subspace containing \(P\).

MatrixOfInequalities(R, C): Rng, TorCon -> ModMatRngElt#
MatrixOfInequalities(C): TorCon -> ModMatRngElt#: The inequalities of \(C\) arranged in a matrix, with each row representing an inequality.

Example: Toric Polytope Inequalities Example (ex-b4cdf2)#

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

Run in calculator

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)

Run in calculator

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

Run in calculator

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.

NormalCone(P, F): TorPol, TorPol -> TorCon#: The (outer) normal cone of the face \(F\) of the polyhedron \(P\).

NormalEdgeCones(P): TorPol -> [TorCon]#: The (outer) normal cones of the edges of the polyhedron \(P\). The cones are presented in the same order as the edges of \(P\); i.e. the \(i\)-th cone in the resulting sequence is the normal cone to the \(i\)-th edge returned by Edges(P) or EdgeIndices(P).

InnerNormal(C): TorCon -> TorLatElt#
OuterNormal(C): TorCon -> TorLatElt#: For a Gorenstein cone \(C\), i.e. a cone such that the primitive generators \(\rho_i\) of the rays of \(C\) lie in a common hyperplane, gives an element \(u\) in the dual lattice such that \(u(\rho_i) = -1\) (inner normal) or \(u(\rho_i) = 1\) (outer normal).

Basic Combinatorics of Polytopes and Polyhedra#

Vertices and Inequalities#

Facets and Faces#