documentation:latest:polytope

Available versions of this document: latest release, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, release 3.5, nightly master

Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2

# application polytope

This is the historically first application, and the largest one. It deals with convex pointed polyhedra. It allows to define a polyhedron either as a convex hull of a point set, an intersection of halfspaces, or as an incidence matrix without any embedding. Then you can ask for a plenty of its (especially combinatorial) properties, construct new polyhedra by modifying it, or study the behavior of the objective functions. There is a wide range of visualization methods for polyhedra, even for dimensions > 4 and purely combinatorial descriptions, including interfaces to interactive geometry viewers (such as JavaView or geomview), generating PostScript drawings and povray scene files.

imports from:

uses:

## Objects

• AffineLattice:
a lattice that is displaced from the origin, i.e., a set of the form x + L, where x is a non-zero vector and L a (linear) lattice

• Cone:
A polyhedral cone, not necessarily pointed. Note that in contrast to the vertices of a polytope, the RAYS are given in affine coordinates.

• LinearProgram:
A linear program specified by a linear or abstract objective function

• MixedIntegerLinearProgram:
A mixed integer linear program specified by a linear or abstract objective function

• PointConfiguration:
The POINTS of an object of type PointConfiguration encode a not necessarily convex finite point set. The difference to a parent VectorConfiguration is that the points have homogeneous coordinates, i.e. they will be normalized to have first coordinate 1 without warning.

• Polytope:
Not necessarily bounded convex polyhedron, i.e., the feasible region of a linear program. Nonetheless, the name “Polytope” is used for two reasons: Firstly, as far as the combinatorics is concerned we always deal with polytopes; see the description of VERTICES_IN_FACETS for details. Note that a pointed polyhedron is projectively equivalent to a polytope. The second reason is historical. We use homogeneous coordinates, which is why Polytope is derived from Cone.

• PropagatedPolytope:
Polytope propagation means to define a polytope inductively by assigning vectors to arcs of a directed graph. At each node of such a graph a polytope arises as the joint convex hull of the polytopes at the translated sources of the inward pointing arcs. For details see

Joswig: Polytope Propagation on Graphs.
Chapter 6 in Pachter/Sturmfels: Algebraic Statistics for Computational Biology, Cambridge 2005.
• QuotientSpace:
A topological quotient space obtained from a Polytope by identifying faces. This object will sit inside the polytope.

• SchlegelDiagram:
A Schlegel diagram of a polytope.

• SlackIdeal:
UNDOCUMENTED

• SymmetrizedCocircuitEquations:

• VectorConfiguration:
An object of type VectorConfiguration deals with properties of row vectors, assembled into an n x d matrix called VECTORS. The entries of these row vectors are interpreted as non-homogeneous coordinates. In particular, the coordinates of a VECTOR will *NOT* be normalized to have a leading 1.

• Visual::Cone:
Visualization of a Cone as a graph (if 1d), or as a solid object (if 2d or 3d)

• Visual::Gale:
A gale diagram prepared for drawing.

• Visual::PointConfiguration:
Visualization of the point configuration.

• Visual::Polytope:
Visualization of a polytope as a graph (if 1d), or as a solid object (if 2d or 3d), or as a Schlegel diagram (4d).

• Visual::PolytopeGraph:
Visualization of the graph of a polyhedron.

• Visual::PolytopeLattice:
Visualization of the HASSE_DIAGRAM of a polyhedron as a multi-layer graph..

• Visual::SchlegelDiagram:
Visualization of the Schlegel diagram of a polytope.

• VoronoiPolyhedron:
For a finite set of SITES S the Voronoi region of each site is the set of points closest (with respect to Euclidean distance) to the given site. All Voronoi regions (and their faces) form a polyhedral complex which is a vertical projection of the boundary complex of an unbounded polyhedron P(S). This way VoronoiPolyhedron becomes a derived class from polytope.

## Functions

### Combinatorics

Combinatorial functions.

circuits2matrix(Set<Pair<Set<Int>,Set<Int>>> co)

Convert CIRCUITS or COCIRCUITS to a 0/+1/-1 matrix, with one row for each circuit/cocircuit, and as many columns as there are VECTORs/POINTS.

Parameters:

Set<Pair<Set<Int>,Set<Int>>> co: /circuits a set of circuits or cocircuits

Returns:
SparseMatrix<Rational>

cocircuit_equation_of_ridge(Cone C, Set rho)

The cocircuit equations of a cone C corresponding to some interior ridge rho with respect to a list of interior simplices symmetries of the cone are NOT taken into account

Parameters:

Cone C

Set rho: the interior ridge

Returns:
HashMap<Set,Rational>

cocircuit_equations(Cone C, Array<Set> interior_ridge_simplices, Array<Set> interior_simplices)

A matrix whose rows contain the cocircuit equations of a cone C with respect to a list of interior ridge simplices symmetries of the cone are NOT taken into account

Parameters:

Cone C

Array<Set> interior_ridge_simplices: interior codimension 1 simplices

Array<Set> interior_simplices: interior simplices of maximal dimension

Options:

String filename: where to write the output (default empty)

Bool reduce_rows: whether to perform row reduction (default 1)

Int log_frequency: how often to print log messages

Returns:
SparseMatrix<Int>

codegree<Scalar>(Cone P)

Calculate the codegree of a cone or polytope P. This is the maximal positive integer c such that every subset of size < c lies in a common facet of conv P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.

Type Parameters:

Scalar: the underlying number type,

Parameters:

Cone P

Example:

To find the codegree of the 3-cube, type

 > print codegree(cube(3));
1
codegree<Scalar>(PointConfiguration P)

Calculate the codegree of a point configuration P. This is the maximal positive integer c such that every subset of size < c lies in a common facet of conv P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.

Type Parameters:

Scalar: the underlying number type,

Parameters:

PointConfiguration P

contraction(VectorConfiguration C, Int v)

Contract a vector configuration C along a specified vector v.

Parameters:

VectorConfiguration C

Int v: index of the vector to contract

degree<Scalar>(PointConfiguration P)

Calculate the degree of a cone, polytope or point configuration P. This is the maximal dimension of an interior face of P, where an interior face is a subset of the points of P whose convex hull does not lie on the boundary of P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.

Type Parameters:

Scalar: the underlying number type,

Parameters:

PointConfiguration P: (or Cone or Polytope)

Example:

To find the degree of the 3-cube, type

 > print degree(cube(3));
3

deletion(VectorConfiguration C, Int v)

Delete a specified vector v from a vector configuration C.

Parameters:

VectorConfiguration C

Int v: index of the vector to delete

describe(Polytope P)

Provide a basic combinatorial description (unless there exists one already). Only the options extended and matchthenet (for 3-polytopes) can trigger any computation.

Parameters:

Polytope P: source object

Options:

Bool extended

Bool matchthenet

String language

Returns:
String
Example:

 > print describe(cube(3));
cube of dimension 3
 > $P = new Polytope(POINTS=>cube(3)->VERTICES); print describe($P);
polytope with POINTS, CONE_AMBIENT_DIM
 > $P = new Polytope(POINTS=>cube(3)->VERTICES); print describe($P, extended=>1, language=>"de");
einfaches 3-Polytop im 3-Raum mit f-Vektor 8 12 6
 > $P = new Polytope(POINTS=>cube(3)->VERTICES); print describe($P, matchthenet=>1);
{ "en": "A simple polytope with 8 vertices, 12 edges and 6 facets.", "de": "Ein einfaches Polytop mit 8 Ecken, 12 Kanten und 6 Seiten."}

### Comparing

Functions based on graph isomorphisms.

congruent(Polytope P1, Polytope P2)

Check whether two given polytopes P1 and P2 are congruent, i.e. whether there is an affine isomorphism between them that is induced by a (possibly scaled) orthogonal matrix. Returns the scale factor, or 0 if the polytopes are not congruent. We are using the reduction of the congruence problem (for arbitrary point sets) to the graph isomorphism problem due to:

Akutsu, T.: On determining the congruence of point sets in d dimensions.
Comput. Geom. Theory Appl. 9, 247–256 (1998), no. 4
Parameters:

Polytope P1: the first polytope

Polytope P2: the second polytope

Returns:
Scalar
Example:

Let's first consider an isosceles triangle and its image of the reflection in the origin:

 > $t = simplex(2); >$tr = simplex(2,-1);

Those two are congruent:

 > print congruent($t,$tr);
1

If we scale one of them, we get a factor:

 > print congruent(scale($t,2),$tr);
4

But if we instead take a triangle that is not isosceles, we get a negative result.

 > $tn = new Polytope(VERTICES => [[1,0,0],[1,2,0],[1,0,1]]); > print congruent($t,$tn); 0 equal_polyhedra(Polytope P1, Polytope P2) Parameters: Polytope P1: the first polytope Polytope P2: the second polytope Options: Bool verbose: Prints information on the difference between P1 and P2 if they are not equal. Returns: Bool Example:  >$p = new Polytope(VERTICES => [[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]);
> print equal_polyhedra($p,cube(2)); true To see why two polytopes are unequal, try this:  > print equal_polyhedra($p,simplex(2),verbose => 1);
Inequality 1 -1 -1 not satisfied by point 1 1 1.
false

find_facet_vertex_permutations(Cone P1, Cone P2)

Find the permutations of facets and vertices which maps the cone or polyhedron P1 to P2. The facet permutation is the first component, the vertex permutation is the second component of the return value. Only the combinatorial isomorphism is considered.

Parameters:

Cone P1: the first cone/polytope

Cone P2: the second cone/polytope

Returns:
Pair<Array<Int>,Array<Int>>
Example:

To print the vertex permutation that maps the 3-simplex to its mirror image, type this:

 > $p = find_facet_vertex_permutations(simplex(3),scale(simplex(3),-1)); > print$p->first;
1 2 3 0

included_polyhedra(Polytope P1, Polytope P2)
Parameters:

Polytope P1: the first polytope

Polytope P2: the second polytope

Options:

Bool verbose: Prints information on the difference between P1 and P2 if none is included in the other.

Returns:
Bool
Example:

 > print included_polyhedra(simplex(3),cube(3));
true

To see in what way the two polytopes differ, try this:

 > $p = new Polytope(VERTICES => [[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]); > print included_polyhedra($p,simplex(2),verbose => 1);
Inequality 0 1 0 not satisfied by point 1 -1 -1.
false

isomorphic(Cone P1, Cone P2)

Check whether the face lattices of two cones or polytopes are isomorphic. The problem is reduced to graph isomorphism of the vertex-facet incidence graphs.

Parameters:

Cone P1: the first cone/polytope

Cone P2: the second cone/polytope

Returns:
Bool
Example:

The following compares the standard 2-cube with a polygon generated as the convex hull of five points. The return value is true since both polygons are quadrangles.

 > $p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]); > print isomorphic(cube(2),$p);
true

lattice_isomorphic_smooth_polytopes(Polytope P1, Polytope P2)

Tests whether two smooth lattice polytopes are lattice equivalent by comparing lattice distances between vertices and facets.

Parameters:

Polytope P1: the first lattice polytope

Polytope P2: the second lattice polytope

Returns:
Bool
Example:

 > $t = new Vector(2,2); > print lattice_isomorphic_smooth_polytopes(cube(2),translate(cube(2),$t));
true

### Consistency check

These functions are for checking the consistency of some properties.

check_inc(Matrix points, Matrix hyperplanes, String sign, Bool verbose)

Check coordinate data. For each pair of vectors from two given matrices their inner product must satisfy the given relation.

Parameters:

Matrix points

Matrix hyperplanes

String sign: composed of one or two characters from [-+0], representing the allowed domain of the vector inner products.

Bool verbose: print all products violating the required relation

Returns:
Bool
Example:

Let's check which vertices of the square lie in its zeroth facet:

 > $H = cube(2)->FACETS->minor([0],All); > print check_inc(cube(2)->VERTICES,$H,'0',1);
<1,0>   ( 1 1 -1 ) * [ 1 1 0 ] == 2
<3,0>   ( 1 1 1 ) * [ 1 1 0 ] == 2
#points==4, #hyperplanes==1, -:0, 0:2, +:2, total:4
false

Thus, the first and third vertex don't lie on the hyperplane defined by the facet but on the positive side of it, and the remaining two lie on the hyperplane.

check_poly(IncidenceMatrix VIF)

Try to check whether a given vertex-facet incidence matrix VIF defines a polytope. Note that a successful certification by check_poly is not sufficient to determine whether an incidence matrix actually defines a polytope. Think of it as a plausibility check.

Parameters:

IncidenceMatrix VIF

Options:

Bool dual: transposes the incidence matrix

Bool verbose: prints information about the check.

Returns:
Polytope

validate_moebius_strip(Polytope P)

Validates the output of the client edge_orientable, in particular it checks whether the MOEBIUS_STRIP_EDGES form a Moebius strip with parallel opposite edges. Prints a message to stdout.

Parameters:

Polytope P: the given polytope

Returns:
Bool

validate_moebius_strip_quads(Polytope P)

Checks whether the MOEBIUS_STRIP_QUADS form a Moebius strip with parallel opposite edges. Prints a message to stdout and returns the MOEBIUS_STRIP_EDGES if the answer is affirmative.

Parameters:

Polytope P: the given polytope

Options:

Bool verbose: print details

Returns:
Matrix<Int>

### Coordinate conversions

The following functions allow for the conversion of the coordinate type of cones and polytopes.

affine_float_coords(Polytope P)

Dehomogenize the vertex coordinates and convert them to Float

Parameters:

Polytope P: source object

Returns:
Matrix<Float>
Example:

 > print cube(2,1/2)->VERTICES;
1 -1/2 -1/2
1 1/2 -1/2
1 -1/2 1/2
1 1/2 1/2
 > print affine_float_coords(cube(2,1/2));
-0.5 -0.5
0.5 -0.5
-0.5 0.5
0.5 0.5

building_set_ycoord_2_zcoord(Map<Set<Int>,Scalar> The)

Convert the y-coordinate representation of a generalized permutahedron given via a building set into the z-coordinate representation. See 6, 7, 8 of Postnikov, A. (2009) “Permutohedra, Associahedra, and Beyond,” International Mathematics Research Notices, Vol. 2009, No. 6, pp. 1026–1106 Advance Access publication January 7, 2009 doi:10.1093/imrn/rnn153# @tparam Scalar

Parameters:

Map<Set<Int>,Scalar> The: y-coordinates of the building set

Returns:
Map<Set<Int>,Scalar>

convert_to<Coord>(Cone c)

Creates a new Cone object with different coordinate type target coordinate type Coord must be specified in angle brackets e.g. $new_cone = convert_to<Coord>($cone)

Type Parameters:

Coord: target coordinate type

Parameters:

Cone c: the input cone

Returns:
Cone<Coord>
convert_to<Coord>(Polytope P)

provide a Polytope object with desired coordinate type

Type Parameters:

Coord: target coordinate type

Parameters:

Polytope P: source object

Returns:
Polytope<Coord>
Example:

 > print cube(2)->type->full_name;
Polytope<Rational>
 > $pf = convert_to<Float>(cube(2)); > print$pf->type->full_name;
Polytope<Float>

### Finite metric spaces

Tight spans and their connections to polyhedral geometry

tight_span_envelope(SubdivisionOfPoints sd)

Computes the envelope for a given subdivision of points.

Parameters:

SubdivisionOfPoints sd

Options:

Bool extended: If True, the envelope of the extended tight span is computed.

Returns:
Polytope

### Geometry

These functions capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.

all_steiner_points(Polytope P)

Compute the Steiner points of all faces of a polyhedron P using a randomized approximation of the angles. P must be BOUNDED.

Parameters:

Polytope P

Options:

Float eps: controls the accuracy of the angles computed

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Matrix

center_distance(Polytope p)

Compute the mean or median distance of the VERTICES to the VERTEX_BARYCENTER.

Parameters:

Polytope p

Options:

Bool median: use median instead of arithmetic mean

Returns:
Float

circuit_completions(Matrix L, Matrix R)

Given two matrices L (n x d) and R (m x d) such that (L/R) has rank r, select all (r+1-n)-subsets C of rows of R such that (L,S) or (S,L) is a circuit. Optionally, if d > r, a basis H for the orthogonal span of the affine hull of (L/R) may be given.

Parameters:

Matrix L

Matrix R

Options:

Matrix H

Returns:
Array<Set>
Example:

Divide the vertex set of the 3-cube into a body diagonal L and six remaining vertices R. To find the subsets of R that complete L to a circuit, type

 > $c = cube(3); >$L = $c->VERTICES->minor([0,7],All); >$R = $c->VERTICES->minor([1,2,3,4,5,6],All); > print circuit_completions($L,$R); {0 1 3} {2 4 5} containing_normal_cone(Cone P, Vector q) Return the vertices of the face of P whose normal cone contains a point q. Parameters: Cone P Vector q Returns: Set Example: To find the face whose normal cone contains a given point, type  >$p = new Polytope(VERTICES=>[[1,-1,0],[1,0,-1],[1,0,1],[1,100,0]]);
> print containing_normal_cone($p, new Vector([1,1,2])); {2 3} containing_outer_cone(Polytope P, Vector q) Return the vertices of the face of P whose outer cone contains a point q. Parameters: Polytope P Vector q Returns: Set Example: To find the face whose outer cone contains a given point, type  > print containing_outer_cone(cube(3), new Vector([1,2,2,2])); {7} dihedral_angle(Vector<Scalar> H1, Vector<Scalar> H2) Compute the dihedral angle between two (oriented) affine or linear hyperplanes. Parameters: Vector<Scalar> H1: : first hyperplane Vector<Scalar> H2: : second hyperplane Options: Bool deg: output in degrees rather than radians, default is false Bool cone: hyperplanes seen as linear hyperplanes, default is false Returns: Float Example:  >$H1 = new Vector(1,5,5);
> $H2 = new Vector(1,-5,5); > print dihedral_angle($H1,$H2,deg=>1); 90 gelfand_tsetlin_counting<Scalar>(Vector<Scalar> lambda) Compute the volume of the Gelfand-Tsetlin polytope associated to the vector lambda. See Postnikov: Permutohedra, associahedra, and beyond, IMRN (2009); doi:10.1093/imrn/rnn153 Theorem 15.1. Note that this volume is the volume of the polytope in its embedding space, in case that all entries of lambda are different. Type Parameters: Scalar Parameters: Vector<Scalar> lambda: Vector encoding a descending sequence of numbers. Options: Bool lattice: The same formula may be used to count lattice points, default=false Returns: Scalar Example: Illustrating the differences between the volumes for the sequence (6,4,2,1)  >$lambda = new Vector(6,4,2,1);
> $pgt = gelfand_tsetlin($lambda,projected=>1);
> $gt = gelfand_tsetlin($lambda,projected=>0);
> print $gt->VOLUME; 0  > print$gt->FULL_DIM;
false
 > print $pgt->VOLUME; 20  > print$pgt->FULL_DIM;
true
 > print gelfand_tsetlin_counting($lambda); 20  > print$gt->N_LATTICE_POINTS;
360
 > print gelfand_tsetlin_counting($lambda, lattice_points=>1); 360 gelfand_tsetlin_diagrams<Scalar>(Vector<Scalar> lambda) Turn points from a Gelfand-Tsetlin polytope into triangular arrays. See Postnikov: Permutohedra, associahedra, and beyond, IMRN (2009); doi:10.1093/imrn/rnn153 Theorem 15.1. Note that we assume the points to come with a homogenizing coordinate. Type Parameters: Scalar Parameters: Vector<Scalar> lambda: Vector encoding a descending sequence of numbers. Returns: Array<Matrix<Scalar>> Example: Small example with tree lattice points  >$lambda = new Vector(3,2,2);
> $gt = gelfand_tsetlin($lambda,projected=>0);
> print $gt->N_LATTICE_POINTS; 3  > print$gt->LATTICE_POINTS;
1 3 2 2 2 2 2
1 3 2 2 3 2 2
1 3 2 2 3 2 3
 > print gelfand_tsetlin_diagrams($gt->LATTICE_POINTS); <3 2 2 2 2 0 2 0 0 > <3 2 2 3 2 0 2 0 0 > <3 2 2 3 2 0 3 0 0 > induced_lattice_basis(Polytope p) Returns a basis of the affine lattice spanned by the vertices Parameters: Polytope p: the input polytope Returns: Matrix<Integer> Example: The vertices of the 2-simplex span all of Z^2…  > print induced_lattice_basis(simplex(2)); 0 1 0 0 0 1 …but if we scale it with 2, we get only every second lattice point.  > print induced_lattice_basis(scale(simplex(2),2)); 0 2 0 0 0 2 integer_points_bbox(Polytope<Scalar> P) Enumerate all integer points in the given polytope by searching a bounding box. Parameters: Polytope<Scalar> P Returns: Matrix<Integer> Example:  >$p = new Polytope(VERTICES=>[[1,13/10,1/2],[1,1/5,6/5],[1,1/10,-3/2],[1,-7/5,1/5]]);
> print integer_points_bbox($p); 1 0 -1 1 -1 0 1 0 0 1 1 0 1 0 1 maximal_ball(Polytope<Rational> P) Finds for a given rational Polytope P the maximal ball B(r,c) which is contained in P. Here r is the radius of the maximal ball and c is it center. Since is can happen, that r is not a rational number or c is not a rational, does this function only work for polytopes for which in the norm of each can be written as QuadraticExtension to the same root. Parameters: Polytope<Rational> P: input polytope with rational coordinates Returns: Pair <QuadraticExtension<Rational>> from extension: Example:  >$S = simplex(2);
> print maximal_ball($S); 1-1/2r2 <1 1-1/2r2 1-1/2r2> minimal_vertex_angle(Polytope P) Computes the minimal angle between two vertices of the input polytope P. Parameters: Polytope P Returns: Float Example:  > print minimal_vertex_angle(simplex(3)); 3.14159265358979 normaliz_compute(Cone C) Compute degree one elements, Hilbert basis or Hilbert series of a cone C with libnormaliz Hilbert series and Hilbert h-vector depend on the given grading and will not work unless C is HOMOGENEOUS or a MONOID_GRADING is set Parameters: Cone C Options: Bool from_facets: supply facets instead of rays to normaliz Bool degree_one_generators: compute the generators of degree one, i.e. lattice points of the polytope Bool hilbert_basis: compute Hilbert basis of the cone C Bool h_star_vector: compute Hilbert h-vector of the cone C Bool hilbert_series: compute Hilbert series of the monoid Bool ehrhart_quasi_polynomial: compute Ehrhart quasi polynomial of a polytope Bool facets: compute support hyperplanes (=FACETS,LINEAR_SPAN) Bool rays: compute extreme rays (=RAYS) Bool dual_algorithm: use the dual algorithm by Pottier Bool skip_long: do not try to use long coordinates first Bool verbose: libnormaliz debug output Returns: List from extension: occluding_cone(Cone P, Set F) For a face F of a cone or polytope P, return the polyhedral cone C such that taking the convex hull of P and any point in C destroys the face F Parameters: Cone P Set F Returns: Cone Example: To find the occluding cone of an edge of the 3-cube, type  >$c=occluding_cone(cube(3), [0,1]);
> print $c->FACETS; -1 0 -1 0 -1 0 0 -1 optimal_contains(Polytope P_in, Polytope P_out) Finds for a given inner Polytope P_in and a given outer Polytope P_out a maximal a scalar s and a vector t, such that P_in scaled with s and shifted by t is a subset of P_out. Parameters: Polytope P_in: the inner Polytope Polytope P_out: the outer Polytope Returns: Pair <Scalar,Vector<Scalar>> Example:  >$P_in = new Polytope(POINTS=>[[1,0],[1,1]]);
> $P_out = new Polytope(POINTS=>[[1,2],[1,4]]); > print optimal_contains($P_in,$P_out); 2 <1 2> print_face_lattice(IncidenceMatrix VIF, Bool dual) Write the face lattice of a vertex-facet incidence matrix VIF to stdout. If dual is set true the face lattice of the dual is printed. Parameters: IncidenceMatrix VIF Bool dual Example: To get a nice representation of the squares face lattice, do this:  > print_face_lattice(cube(2)->VERTICES_IN_FACETS); FACE_LATTICE [ -1 : 4 ] {{0 1} {0 2} {1 3} {2 3}} [ -2 : 4 ] {{0} {1} {2} {3}} separable(Vector q, Cone P) Checks whether there exists a hyperplane separating a given point q from a polytope/cone P by solving a suitable LP. If true, q is a vertex of the polytope defined by q and the vertices of P. To get the separating hyperplane, use separating_hyperplane. Works without knowing the facets of P! Parameters: Vector q: the vertex (candidate) which is to be separated from P Cone P: the polytope/cone from which q is to be separated Options: Bool strong: Test for strong separability. default: true Returns: Bool Example:  >$q = cube(2)->VERTICES->row(0);
> print separable(cube(2), $q, strong=>0); true simple_polytope_vertices_rs(Polytope<Scalar> P, Vector<Scalar> min_vertex) Use reverse search method to find the vertices of a polyhedron. While applying this method, also collect the directed graph of cost optimization with respect to a (optionally) provided objective. If no objective is provided, one will be selected that cuts of ONE_VERTEX The input polytope must be SIMPLE and POINTED, these properties are not checked by the algorithm. Parameters: Polytope<Scalar> P Vector<Scalar> min_vertex Returns: List steiner_point(Polytope P) Compute the Steiner point of a polyhedron P using a randomized approximation of the angles. Parameters: Polytope P Options: Float eps: controls the accuracy of the angles computed Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome. Returns: Vector violations(Cone P, Vector q) Check which relations, if any, are violated by a point. Parameters: Cone P Vector q Options: String section: Which section of P to test against q Int violating_criterion: has the options: +1 (positive values violate; this is the default), 0 (*non*zero values violate), -1 (negative values violate) Returns: Set Example: This calculates and prints the violated equations defining a square with the origin as its center and side length 2 with respect to a certain point:  >$p = cube(2);
> $v = new Vector([1,2,2]); >$S = violations($p,$v);
> print $S; {1 3} visible_face_indices(Cone P, Vector q) Return the indices (in the HASSE_DIAGRAM) of all faces that are visible from a point q. Parameters: Cone P Vector q Returns: Set Example: This prints the faces of a square with the origin as its center and side length 2 that are visible from a certain point:  >$p = cube(2);
> $v = new Vector([1,2,2]); > map { print$p->HASSE_DIAGRAM->FACES->[$_], "\n" } @{visible_face_indices($p,$v)}; {} {1} {2} {3} {1 3} {2 3} visible_facet_indices(Cone P, Vector q) Return the indices of all facets that are visible from a point q. Parameters: Cone P Vector q Returns: Set Example: This prints the facets of a square with the origin as its center and side length 2 that are visible from a certain point:  >$p = cube(2);
> $v = new Vector([1,2,2]); > map { print$p->VERTICES_IN_FACETS->[$_], "\n" } @{visible_facet_indices($p,$v)}; {1 3} {2 3} zonotope_tiling_lattice(Polytope P) Calculates a generating set for a tiling lattice for P, i.e., a lattice L such that P + L tiles the affine span of P. Parameters: Polytope P: the zonotope Options: Bool lattice_origin_is_vertex: true if the origin of the tiling lattice should be a vertex of P; default false, ie, the origin will be the barycenter of P Returns: AffineLattice Example: This determines a tiling lattice for a parallelogram with the origin as its vertex barycenter and prints it base vectors:  >$M = new Matrix([[1,1,0],[1,1,1]]);
> $p = zonotope($M);
> $A = zonotope_tiling_lattice($p);
> print $A->BASIS; 0 -1 -1 0 0 1 ### Optimization These functions provide tools from linear, integer and dicrete optimization. In particular, linear programs are defined here. ball_lifting_lp(GeometricSimplicialComplex c, Int facet_index, Rational conv_eps) Computes the inequalities and the linear objective for an LP to lift a simplicial d-ball embedded starshaped in Rd. Parameters: GeometricSimplicialComplex c Int facet_index: index of the facet to be lifted Rational conv_eps: some epsilon > 0 Returns: Polytope from extension: core_point_algo(Polytope p, Rational optLPvalue) Algorithm to solve highly symmetric integer linear programs (ILP). It is required that the group of the ILP induces the alternating or symmetric group on the set of coordinate directions. The linear objective function is the vector (0,1,1,..,1). Parameters: Polytope p Rational optLPvalue: optimal value of LP approximation Options: Bool verbose Returns: List core_point_algo_Rote(Polytope p, Rational optLPvalue) Version of core_point_algo with improved running time (according to a suggestion by G. Rote). The core_point_algo is an algorithm to solve highly symmetric integer linear programs (ILP). It is required that the group of the ILP induces the alternating or symmetric group on the set of coordinate directions. The linear objective function is the vector (0,1,1,..,1). Parameters: Polytope p Rational optLPvalue: optimal value of LP approximation Options: Bool verbose Returns: List find_transitive_lp_sol(Matrix Inequalities) Algorithm to solve symmetric linear programs (LP) of the form max ctx , c=(0,1,1,..,1) subject to the inequality system given by Inequalities. It is required that the symmetry group of the LP acts transitively on the coordinate directions. Parameters: Matrix Inequalities: the inequalities describing the feasible region Returns: List Example: Consider the LP described by the facets of the 3-cube:  > @sol=find_transitive_lp_sol(cube(3)->FACETS); > print$_, "\n" for @sol;
1 1 1 1
3
true
true

The optimal solution is [1,1,1,1], its value under c is 3, and the LP is feasible and bounded in direction of c.

inner_point(Matrix points)

Compute a true inner point of a convex hull of the given set of points.

Parameters:

Matrix points

Returns:
Vector
Example:

To print an inner point of the square, do this:

 > print inner_point(cube(2)->VERTICES);
1 -1/3 -1/3

lp2poly<Scalar>(String file, Vector testvec, String prefix)

Read a linear programming problem given in LP-Format or MILP-Format (as used by cplex & Co.) and convert it to a polytope object with an added LP property or MILP property

Type Parameters:

Scalar: coordinate type of the resulting polytope; default is Rational.

Parameters:

String file: filename of a linear programming problem in LP-Format

Vector testvec: If present, after reading in each line of the LP it is checked whether testvec fulfills it

String prefix: If testvec is present, all variables in the LP file are assumed to have the form $prefix$i

Options:

Bool nocheck: Do not automatically compute FEASIBLE for the polytope (recommended for very large LPs)

Bool create_lp: Create an LP property regardless of the format of the given file. If the file has MILP-Format, the created LP property will have an attachment INTEGER_VARIABLES

Returns:
Polytope<Scalar>

mps2poly<Scalar>(String file, String prefix, Bool use_lazy)

Read a linear problem or mixed integer problem from in MPS-Format (as used by Gurobi and other linear problem solvers) and convert it to a polytope object with one or multiple added LP property or MILP property. This interface has some limitations since the MPS-Format offer a wide range of functionalities, which are not all compatible with polymake right now.

Type Parameters:

Scalar: coordinate type of the resulting polytope; default is rational

Parameters:

String file: filename of a linear programming problem in MPS-Format

String prefix: If prefix is present, all variables in the LP file are assumed to have the form $prefix$i

Bool use_lazy: Also use the lazy constrains if they are given to build the polytope.

poly2lp(Polytope P, LinearProgram LP, Bool maximize, String file)

Convert a polymake description of a polyhedron to LP format (as used by CPLEX and other linear problem solvers) and write it to standard output or to a file. If LP comes with an attachment 'INTEGER_VARIABLES' (of type Array<Bool>), the output will contain an additional section 'GENERAL', allowing for IP computations in CPLEX. If the polytope is not FEASIBLE, the function will throw a runtime error. Alternatively one can also provide a MILP, instead of a LP with 'INTEGER_VARIABLES' attachment.

Parameters:

Polytope P

LinearProgram LP: default value: P→LP

Bool maximize: produces a maximization problem; default value: 0 (minimize)

String file: default value: standard output

poly2mps(Polytope P, LinearProgram LP, Set<Int> br, String file)

Convert a polymake description of a polyhedron to MPS format (as used by Gurobi and other linear problem solvers) and write it to standard output or to a file. If LP comes with an attachment 'INTEGER_VARIABLES' (of type Array<Bool>), the output will contain markers for them. You can give the indices rows, which are just variable bounds (x_i>=b_i or x_i⇐b_i), as a Set. If you do so, the will be in this way. If the polytope is not FEASIBLE, the function will throw a runtime error. Alternatively one can also provide a MILP, instead of a LP with 'INTEGER_VARIABLES' attachment.

Parameters:

Polytope P

LinearProgram LP: default value: P→LP

Set<Int> br: the possible empty set of inequalities of the form x_i ⇐/>= b_i, that should be handelt as variable bounds

String file: default value: standard output

poly2porta(Polytope<Rational> p, String file)

take a rational polytope and write a porta input file (.ieq or .poi)

Parameters:

Polytope<Rational> p

String file: filename for the porta file (.ieq or .poi) or an open IO handle

Options:

Bool primal: true if points should be written, false if inequalities should be written (default is true)

porta2poly(String file)

Read an .ieq or .poi file (porta input) or .poi.ieq or .ieq.poi (porta output) and convert it to a polytope object

Parameters:

String file: filename of a porta file (.ieq or .poi)

Returns:
Polytope<Rational>

print_constraints(Cone<Scalar> C)

Write the FACETS / INEQUALITIES and the LINEAR_SPAN / EQUATIONS (if present) of a polytope P or cone C in a readable way. COORDINATE_LABELS are adopted if present.

Parameters:

Cone<Scalar> C: the given polytope or cone

Options:

Array<String> ineq_labels: changes the labels of the inequality rows

Array<String> eq_labels: changes the labels of the equation rows

Example:

The following prints the facet inequalities of the square, changing the labels.

 > print_constraints(cube(2),ineq_labels=>['zero','one','two','three']);
Facets:
zero: x1 >= -1
one: -x1 >= -1
two: x2 >= -1
three: -x2 >= -1

rand_aof(Polytope P, Int start)

Produce a random abstract objective function on a given simple polytope P. It is assumed that the boundary complex of the dual polytope is extendibly shellable. If, during the computation, it turns out that a certain partial shelling cannot be extended, then this is given instead of an abstract objective function. It is possible (but not required) to specify the index of the starting vertex start.

Parameters:

Polytope P: a simple polytope

Int start: the index of the starting vertex; default value: random

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Vector<Rational>

random_edge_epl(Graph<Directed> G)

Computes a vector containing the expected path length to the maximum for each vertex of a directed graph G. The random edge pivot rule is applied.

Parameters:

Graph<Directed> G: a directed graph

Returns:
Vector<Rational>

separating_hyperplane(Vector q, Matrix points)

Computes (the normal vector of) a hyperplane which separates a given point q from points via solving a suitable LP. The scalar product of the normal vector of the separating hyperplane and a point in points is greater or equal than 0 (same behavior as for facets!). If q is not a vertex of P=conv(points,q), the function throws an infeasible exception. Works without knowing the facets of P!

Parameters:

Vector q: the vertex (candidate) which is to be separated from points

Matrix points: the points from which q is to be separated

Returns:
Vector
Example:

The following stores the result in the List @r and then prints the answer and a description of the hyperplane separating the zeroth vertex of the square from the others.

 > $q = cube(2)->VERTICES->row(0); >$points = cube(2)->VERTICES->minor(sequence(1,3),All);
> print separating_hyperplane($q,$points);
0 1/2 1/2
separating_hyperplane(Polytope p1, Polytope p2)

Computes (the normal vector of) a hyperplane which separates two given polytopes p1 and p2 if possible. Works by solving a linear program, not by facet enumeration.

Parameters:

Polytope p1: the first polytope, will be on the positive side of the separating hyperplane

Polytope p2: the second polytope

Options:

Bool strong: If this is set to true, the resulting hyperplane will be strongly separating, i.e. it won't touch either of the polytopes. If such a plane does not exist, an exception will be thrown. default: true

Returns:
Vector

totally_dual_integral(Matrix inequalities)

Checks weather a given system of inequalities is totally dual integral or not. The inequalities should describe a full dimensional polyhedron

Parameters:

Matrix inequalities

Returns:
Bool
Example:

 > print totally_dual_integral(cube(2)->FACETS);
true

vertex_colors(Polytope P, LinearProgram LP)

Calculate RGB-color-values for each vertex depending on a linear or abstract objective function. Maximal and minimal affine vertices are colored as specified. Far vertices (= rays) orthogonal to the linear function normal vector are white. The colors for other affine vertices are linearly interpolated in the HSV color model. If the objective function is linear and the corresponding LP problem is unbounded, then the affine vertices that would become optimal after the removal of the rays are painted pale.

Parameters:

Polytope P

LinearProgram LP

Options:

RGB min: the minimal RGB value

RGB max: the maximal RGB value

Returns:
Array<RGB>
Example:

This calculates a vertex coloring with respect to a linear program. For a better visualization, we also set the vertex thickness to 2.

 > $p = cube(3); >$p->LP(LINEAR_OBJECTIVE=>[0,1,2,3]);
> $v = vertex_colors($p,$p->LP); >$p->VISUAL(VertexColor=>$v,VertexThickness=>2); write_foldable_max_signature_ilp(Polytope P, String outfile_name) construct a linear program whose optimal value is an upper bound for the algebraic signature of a triangulation of P. This is the absolute value of the difference of normalized volumes of black minus white simplices (counting only those with odd normalized volume) in a triangulation of P whose dual graph is bipartite. If P has a GROUP, it will be used to construct the linear program. Parameters: Polytope P String outfile_name Example: For the 0/1 2-cube without a GROUP, the foldable max signature lp is computed as follows:  > write_foldable_max_signature_ilp(cube(2,0)); MINIMIZE obj: +1 x1 -1 x2 +1 x3 -1 x4 +1 x5 -1 x6 +1 x7 -1 x8 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 ie4: +1 x5 >= 0 ie5: +1 x6 >= 0 ie6: +1 x7 >= 0 ie7: +1 x8 >= 0 ie8: -1 x1 -1 x2 >= -1 ie9: -1 x3 -1 x4 >= -1 ie10: -1 x5 -1 x6 >= -1 ie11: -1 x7 -1 x8 >= -1 eq0: -1 x4 +1 x5 = 0 eq1: +1 x3 -1 x6 = 0 eq2: -1 x2 +1 x7 = 0 eq3: +1 x1 -1 x8 = 0 eq4: +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 = 2 BOUNDS x1 free x2 free x3 free x4 free x5 free x6 free x7 free x8 free GENERAL x1 x2 x3 x4 x5 x6 x7 x8 END There are eight variables, one for each possible black or white maximal interior simplex. The optimal value of this LP is zero, because any triangulation has exactly one black and one white simplex of odd normalized volume. Notice that the objective function becomes empty for cube(2), because in the +1/-1 cube, each simplex has even volume. Example: For the 0/1 3-cube, we use a GROUP property:  > write_foldable_max_signature_ilp(cube(3,0,group=>1)); MINIMIZE obj: +1 x1 -1 x2 +1 x3 -1 x4 +1 x5 -1 x6 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 ie4: +1 x5 >= 0 ie5: +1 x6 >= 0 ie6: +1 x7 >= 0 ie7: +1 x8 >= 0 ie8: -1 x1 -1 x2 >= -8 ie9: -1 x3 -1 x4 >= -24 ie10: -1 x5 -1 x6 >= -24 ie11: -1 x7 -1 x8 >= -2 eq0: +2 x3 -2 x4 +2 x5 -2 x6 = 0 eq1: -2 x3 +2 x4 -2 x5 +2 x6 = 0 eq2: -6 x2 +6 x5 +24 x7 = 0 eq3: -6 x1 +6 x6 +24 x8 = 0 eq4: +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +2 x7 +2 x8 = 6 BOUNDS x1 free x2 free x3 free x4 free x5 free x6 free x7 free x8 free GENERAL x1 x2 x3 x4 x5 x6 x7 x8 END There are again 8 variables, but now they correspond to the black and white representatives of the four symmetry classes of maximal interior simplices. The optimal value of this linear program is 4, because the most imbalanced triangulation is the one with 5 simplices, in which the volume of the big interior simplex is even and doesn't get counted in the objective function. write_simplexity_ilp(Polytope P) construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P. Parameters: Polytope P Options: String outfile_name: . If the string is '-' (as is the default), the linear program is printed to STDOUT. Example: To print the linear program for the 2-dimensional cube, write  > write_simplexity_ilp(cube(2)); MINIMIZE obj: +1 x1 +1 x2 +1 x3 +1 x4 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 eq0: +4 x1 +4 x2 +4 x3 +4 x4 = 8 eq1: -1 x2 +1 x3 = 0 eq2: -1 x1 +1 x4 = 0 BOUNDS x1 free x2 free x3 free x4 free GENERAL x1 x2 x3 x4 END write_simplexity_ilp_with_angles(Polytope P, String outfile_name) construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P, and that takes into account the angle constraint around codimension 2 faces. The first set of variables correspond to possible maximal internal simplices, the second set to the simplices of codimension 2. See the source file polytope/src/symmetrized_codim_2_angle_sums.cc for details. Parameters: Polytope P String outfile_name Example: To print the linear program for the 2-dimensional cube, write  > write_simplexity_ilp_with_angles(cube(2)); MINIMIZE obj: +1 x1 +1 x2 +1 x3 +1 x4 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 ie4: +1 x5 >= 0 ie5: +1 x6 >= 0 ie6: +1 x7 >= 0 ie7: +1 x8 >= 0 eq0: -1 x2 +1 x3 = 0 eq1: -1 x1 +1 x4 = 0 eq2: +0.5 x1 +0.25 x2 +0.2500000000000001 x3 -0.5 x5 = 0 eq3: +0.25 x1 +0.5 x3 +0.2500000000000001 x4 -0.5 x6 = 0 eq4: +0.25 x1 +0.5 x2 +0.2500000000000001 x4 -0.5 x7 = 0 eq5: +0.25 x2 +0.2500000000000001 x3 +0.5 x4 -0.5 x8 = 0 eq6: +1 x5 = 1 eq7: +1 x6 = 1 eq8: +1 x7 = 1 eq9: +1 x8 = 1 eq10: +4 x1 +4 x2 +4 x3 +4 x4 = 8 BOUNDS x1 free x2 free x3 free x4 free x5 free x6 free x7 free x8 free GENERAL x1 x2 x3 x4 x5 x6 x7 x8 END  write_symmetrized_simplexity_ilp(Polytope P, Set<Int> isotypic_components, String outfile_name) construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P. The symmetry group of P is taken into account, in that the variables in the linear program are projections of the indicator variables of the maximal interior simplices to a given direct sum of isotypic components of the symmetry group of P acting on these simplices. Parameters: Polytope P Set<Int> isotypic_components: the set of indices of isotypic components to project to; default [0] String outfile_name: . Setting this to '-' (as is the default) prints the LP to stdout. Example: For the 3-cube, the symmetrized LP for isotypic component 0 reads as follows:  > write_symmetrized_simplexity_ilp(cube(3,group=>1)); MINIMIZE obj: +1 x1 +1 x2 +1 x3 +1 x4 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 eq0: +8 x1 +8 x2 +8 x3 +16 x4 = 48 eq1: -6 x1 +6 x3 +24 x4 = 0 BOUNDS x1 free x2 free x3 free x4 free GENERAL x1 x2 x3 x4 END The interpretation is as follows: The variables x1,…,x4 correspond to the representatives of interior simplices:  > print cube(3,group=>1)->GROUP->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES; {0 1 2 4} {0 1 2 5} {0 1 2 7} {0 3 5 6} The solution (x1,x2,x3,x4) = (4,0,0,1) of the LP says that in a minimal triangulation of the 3-cube, there are 4 simplices in the same symmetry class as {0,1,2,4}, and one in the class of {0,3,5,6}. ### Producing a cone Various constructions of cones. inner_cone(Cone p, Set<Int> F) Computes the inner cone of p at a face F (or a vertex v). Parameters: Cone p Set<Int> F: (or Int v) vertex indices which are not contained in the far face Options: Bool outer: Make it point outside the polytope? Default value is 0 (= point inside) Bool attach: Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity) Returns: Cone Example: To compute the inner cone at a vertex of the 3-cube, do this:  >$c = inner_cone(cube(3), 1);
> print $c->RAYS; -1 0 0 0 1 0 0 0 1 Example: To compute the inner cone along an edge of the 3-cube, and make it point outside the polytope, do this:  > print inner_cone(cube(3), [0,1], outer=>1)->RAYS; 0 0 -1 0 -1 0 Example: If you want to attach the cone to the polytope, specify the corresponding option:  > print normal_cone(cube(3), [0,1], attach=>1)->RAYS; 1 -1 -1 -1 1 1 -1 -1 0 0 1 0 0 0 0 1 normal_cone(PointConfiguration p, Set<Int> F) Computes the normal cone of p at a face F (or vertex v). By default this is the inner normal cone. Parameters: PointConfiguration p Set<Int> F: (or Int v) point indices which are not contained in the far face Options: Bool outer: Calculate outer normal cone? Default value is 0 (= inner) Bool attach: Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity) Returns: Cone Example: To compute the outer normal cone of a doubled 2-cube, do this:  >$v = cube(2)->VERTICES;
> $p = new PointConfiguration(POINTS=>($v/$v)); > print normal_cone($p, 4, outer=>1)->RAYS;
0 -1
-1 0
normal_cone(Cone p, Set<Int> F)

Computes the normal cone of p at a face F (or a vertex v). By default this is the inner normal cone.

Parameters:

Cone p

Set<Int> F: (or Int v) vertex indices which are not contained in the far face

Options:

Bool outer: Calculate outer normal cone? Default value is 0 (= inner)

Bool attach: Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity)

Returns:
Cone
Example:

To compute the outer normal cone at a vertex of the 3-cube, do this:

 > $c = normal_cone(cube(3), 0, outer=>1); > print$c->RAYS;
-1 0 0
0 -1 0
0 0 -1
Example:

To compute the outer normal cone along an edge of the 3-cube, do this:

 > print normal_cone(cube(3), [0,1], outer=>1)->RAYS;
0 -1 0
0 0 -1
Example:

If you want to attach the cone to the polytope, specify the corresponding option:

 > print normal_cone(cube(3), [0,1], outer=>1, attach=>1)->RAYS;
1 -1 -1 -1
1 1 -1 -1
0 0 -1 0
0 0 0 -1

recession_cone(Polytope<Scalar> P)

retuns the recession cone (tail cone, characteristic cone) of a polytope

Parameters:

Polytope<Scalar> P: polytope

Returns:
Cone<Scalar>

subcone(Cone C)

Make a subcone from a cone.

Parameters:

Cone C: the input cone

Options:

Bool no_labels: Do not create RAY_LABELS. default: 0

Returns:
Cone

### Producing a point configuration

Constructing a point configuration, either from scratch or from existing objects.

minkowski_sum(PointConfiguration P1, PointConfiguration P2)

Produces the Minkowski sum of P1 and P2.

Parameters:

PointConfiguration P1

PointConfiguration P2

Returns:
PointConfiguration
Example:

 > $P1 = new PointConfiguration(POINTS=>simplex(2)->VERTICES); >$P2 = new PointConfiguration(POINTS=>[[1,1,1],[1,-1,1],[1,1,-1],[1,-1,-1],[1,0,0]]);
> $m = minkowski_sum($P1,$P2); > print$m->POINTS;
1 1 1
1 -1 1
1 1 -1
1 -1 -1
1 0 0
1 2 1
1 0 1
1 2 -1
1 0 -1
1 1 0
1 1 2
1 -1 2
1 1 0
1 -1 0
1 0 1
minkowski_sum(Scalar lambda, PointConfiguration P1, Scalar mu, PointConfiguration P2)

Produces the polytope lambda*P1+mu*P2, where * and + are scalar multiplication and Minkowski addition, respectively.

Parameters:

Scalar lambda

PointConfiguration P1

Scalar mu

PointConfiguration P2

Returns:
PointConfiguration
Example:
 > $P1 = new PointConfiguration(POINTS=>simplex(2)->VERTICES); >$P2 = new PointConfiguration(POINTS=>[[1,1,1],[1,-1,1],[1,1,-1],[1,-1,-1],[1,0,0]]);
> $m = minkowski_sum(1,$P1,3,$P2); > print$m->POINTS;
1 3 3
1 -3 3
1 3 -3
1 -3 -3
1 0 0
1 4 3
1 -2 3
1 4 -3
1 -2 -3
1 1 0
1 3 4
1 -3 4
1 3 -2
1 -3 -2
1 0 1

### Producing a polytope from graphs

Polytope constructions which take graphs as input.

flow_polytope<Scalar>(GraphAdjacency<Directed> G, EdgeMap<Directed,Scalar> Arc_Bounds, Int source, Int sink)

Produces the flow polytope of a directed Graph G=(V,E) with a given source and sink. The flow polytope has the following outer description: forall v in V-{source, sink}: sum_{e in E going into v} x_e

1. sum_{e in E going out of v} x_e = 0

sum_{e in E going into source} x_e

1. sum_{e in E going out of source} x_e ⇐ 0

sum_{e in E going into sink} x_e

1. sum_{e in E going out of sink} x_e >= 0

forall e in E: x_e ⇐ given bound on edge e

Type Parameters:

Scalar

Parameters:

GraphAdjacency<Directed> G

EdgeMap<Directed,Scalar> Arc_Bounds

Int source

Int sink

Returns:
Polytope
flow_polytope<Scalar>(Graph<Directed> G, Array<Scalar> Arc_Bounds, Int source, Int sink)

Produces the flow polytope of a directed Graph G=(V,E) with a given source and sink. The flow polytope has the following outer description: forall v in V-{source, sink}: sum_{e in E going into v} x_e

1. sum_{e in E going out of v} x_e = 0

sum_{e in E going into source} x_e

1. sum_{e in E going out of source} x_e ⇐ 0

sum_{e in E going into sink} x_e

1. sum_{e in E going out of sink} x_e >= 0

forall e in E: x_e ⇐ given bound on edge e

Type Parameters:

Scalar

Parameters:

Graph<Directed> G

Array<Scalar> Arc_Bounds

Int source

Int sink

Returns:
Polytope

fractional_cut_polytope(Graph G)

Cut polytope of an undirected graph.

Parameters:

Graph G

Returns:
Polytope

fractional_matching_polytope(Graph G)

Matching polytope of an undirected graph.

Parameters:

Graph G

Returns:
Polytope

tutte_lifting(Graph G)

Let G be a 3-connected planar graph. If the corresponding polytope contains a triangular facet (ie. the graph contains a non- separating cycle of length 3), the client produces a realization in R3.

Parameters:

Graph G

Returns:
Polytope

weighted_digraph_polyhedron(Matrix encoding)

Weighted digraph polyhedron of a directed graph with a weight function as studied in Joswig, Loho: Weighted digraph polyhedra and tropical cones, LAA (2016). The graph and the weight function are combined into a matrix.

Parameters:

Matrix encoding: weighted digraph

Returns:
Polytope
Example:

This digraph has two nodes and a single arc (with weight 2).

 > $enc = new Matrix([[0,2],["inf",0]]); >$Q = weighted_digraph_polyhedron($enc); > print$Q->FACETS;
2 -1 1
1 0 0

These are the one defining inequality and the trivial inequality, which contains the far face.

### Producing a polytope from other objects

Polytope constructions which take other big objects as input.

billera_lee(Vector<Integer> H)

Produces a simplicial polytope whose H-vector is the given input vector. The G-vector coming from the given vector must be an M-sequence. This is an implementation of the algorithm described in the paper “A Proof of the Sufficiency of McMullen’s Conditions of Simplicial Convex Polytopes” by Louis Billera and Carl Lee, DOI: 10.1016/0097-3165(81)90058-3

Parameters:

Vector<Integer> H

Returns:
Polytope
Example:

 > $p = billera_lee([1,5,15,15,5,1]); > print$p->H_VECTOR;
1 5 15 15 5 1

### Producing a polytope from polytopes

An important way of constructing polytopes is to modify an already existing polytope. Actually, these functions don't alter the input polytope (it is forbidden in polymake), but create a new polytope object. Many functions can at your choice either calculate the vertex or facet coordinates, or constrain themselves on the purely combinatorial description of the resulting polytope.

bipyramid(Polytope P, Scalar z, Scalar z_prime)

Make a bipyramid over a pointed polyhedron. The bipyramid is the convex hull of the input polyhedron P and two points (v, z), (v, z_prime) on both sides of the affine span of P. For bounded polyhedra, the apex projections v to the affine span of P coincide with the vertex barycenter of P.

Parameters:

Polytope P

Scalar z: distance between the vertex barycenter and the first apex, default value is 1.

Scalar z_prime: distance between the vertex barycenter and the second apex, default value is -z.

Options:

Bool no_coordinates: : don't compute the coordinates, purely combinatorial description is produced.

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new vertices with “Apex” and “Apex'”.

Returns:
Polytope
Example:

Here's a way to construct the 3-dimensional cross polytope:

 > $p = bipyramid(bipyramid(cube(1))); > print equal_polyhedra($p,cross(3));
true

blending(Polytope P1, Int v1, Polytope P2, Int v2)

Compute the blending of two polyhedra at simple vertices. This is a slightly less standard construction. A vertex is simple if its vertex figure is a simplex. Moving a vertex v of a bounded polytope to infinity yields an unbounded polyhedron with all edges through v becoming mutually parallel rays. Do this to both input polytopes P1 and P2 at simple vertices v1 and v2, respectively. Up to an affine transformation one can assume that the orthogonal projections of P1 and P2 in direction v1 and v2, respectively, are mutually congruent. Any bijection b from the set of edges through v1 to the edges through v2 uniquely defines a way of glueing the unbounded polyhedra to obtain a new bounded polytope, the blending with respect to b. The bijection is specified as a permutation of indices 0 1 2 etc. The default permutation is the identity. The number of vertices of the blending is the sum of the numbers of vertices of the input polytopes minus 2. The number of facets is the sum of the numbers of facets of the input polytopes minus the dimension. The resulting polytope is described only combinatorially.

Parameters:

Polytope P1

Int v1: the index of the first vertex

Polytope P2

Int v2: the index of the second vertex

Options:

Array<Int> permutation

Bool no_labels: Do not copy VERTEX_LABELS from the original polytopes. default: 0

Returns:
Polytope
Example:

The following gives the smallest EVEN 3-polytope which is not a zonotope.

 > $c = cube(3);$bc = blending($c,0,$c,0);
> print $bc->EVEN true  > print$bc->F_VECTOR
14 21 9

cayley_embedding(Polytope P_0, Polytope P_1, Scalar t_0, Scalar t_1)

Create a Cayley embedding of two polytopes (one of them must be pointed). The vertices of the first polytope P_0 get embedded to (t_0,0) and the vertices of the second polytope P_1 to (0,t_1). Default values are t_0=t_1=1.

Parameters:

Polytope P_0: the first polytope

Polytope P_1: the second polytope

Scalar t_0: the extra coordinate for the vertices of P_0

Scalar t_1: the extra coordinate for the vertices of P_1

Options:

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0

Returns:
Polytope
cayley_embedding(Array<Polytope> A)

Create a Cayley embedding of an array (P1,…,Pm) of polytopes. All polytopes must have the same dimension, at least one of them must be pointed, and all must be defined over the same number type. Each vertex v of the i-th polytope is embedded to v|t_i e_i, where t_i is the i-th entry of the optional array t.

Parameters:

Array<Polytope> A: the input polytopes

Options:

Array<Scalar> factors: array of scaling factors for the Cayley embedding; defaults to the all-1 vector

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0

Returns:
Polytope

cayley_polytope(Array<Polytope> P_Array)

Construct the cayley polytope of a set of pointed lattice polytopes contained in P_Array which is the convex hull of P1×e1, …, Pk×ek where e1, …,ek are the standard unit vectors in Rk. In this representation the last k coordinates always add up to 1. The option proj projects onto the complement of the last coordinate.

Parameters:

Array<Polytope> P_Array: an array containing the lattice polytopes P1,…,Pk

Options:

Bool proj

Returns:
Polytope

cell_from_subdivision(Polytope P, Int cell)

Extract the given cell of the subdivision of a polyhedron and write it as a new polyhedron.

Parameters:

Polytope P

Int cell

Options:

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0

Returns:
Polytope
Example:

First we create a nice subdivision for our favourite 2-polytope, the square:

 > $p = cube(2); >$p->POLYTOPAL_SUBDIVISION(MAXIMAL_CELLS=>[[0,1,3],[1,2,3]]);

Then we extract the [1,2,3]-cell, copying the vertex labels.

 > $c = cell_from_subdivision($p,1);
> print $c->VERTICES; 1 1 -1 1 -1 1 1 1 1  > print$c->VERTEX_LABELS;
1 2 3

cells_from_subdivision(Polytope<Scalar> P, Set<Int> cells)

Extract the given cells of the subdivision of a polyhedron and create a new polyhedron that has as vertices the vertices of the cells.

Parameters:

Polytope<Scalar> P

Set<Int> cells

Options:

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0

Returns:
Polytope<Scalar>
Example:

First we create a nice subdivision for a small polytope:

 > $p = new Polytope(VERTICES=>[[1,0,0],[1,0,1],[1,1,0],[1,1,1],[1,3/2,1/2]]); >$p->POLYTOPAL_SUBDIVISION(MAXIMAL_CELLS=>[[0,1,3],[1,2,3],[2,3,4]]);

Then we create the polytope that has as vertices the vertices from cell 1 and 2, while keeping their labels.

 > $c = cells_from_subdivision($p,[1,2]);
> print $c->VERTICES; 1 0 1 1 1 0 1 1 1 1 3/2 1/2  > print$c->VERTEX_LABELS;
1 2 3 4

conv(Array<Polytope> P_Array)

Construct a new polyhedron as the convex hull of the polyhedra given in P_Array.

Parameters:

Array<Polytope> P_Array

Returns:
PropagatedPolytope
Example:

 > $p = conv([cube(2,1,0),cube(2,6,5)]); > print$p->VERTICES;
1 0 0
1 1 0
1 0 1
1 6 5
1 5 6
1 6 6

conway(Polytope P, String operations)

Applies a sequence of Conway operations to the polytope P (from left to right)

Parameters:

Polytope P

String operations: 'd': conway operation dual 'a': conway operation ambo 'k': conway operation kis 's': conway operation snub 'g': conway operation gyro 'n': conway operation needle 'z': conway operation zip 'j': conway operation join 't': conway operation truncate 'e': conway operation expand 'o': conway operation ortho 'm': conway operation meta 'b': conway operation bevel

Returns:
Polytope
Example:

 > $s = simplex(3); >$as = conway($s, "a"); > print isomorphic(octahedron(),$as);
true
 > $ss = conway($s, "s");
> print isomorphic(icosahedron(),$ss); true   >$mjzkab_s = conway($s, "mjzkab"); > print$mjzkab_s->F_VECTOR;
5184 7776 2594

conway_ambo(Polytope P)

Produces Ambo of a 3-polytope (Conway notation 'a')

Parameters:

Polytope P

Returns:
Polytope
Example:

 >$c = cube(3); >$ac = conway_ambo($c); > print$ac->F_VECTOR;
12 24 14

conway_dual(Polytope P)

Produces dual of a 3-polytope (Conway notation 'd')

Parameters:

Polytope P

Returns:
Polytope

conway_gyro(Polytope P)

Produces Gyro of a 3-polytope (Conway notation 'g')

Parameters:

Polytope P

Returns:
Polytope

conway_kis(Polytope P)

Produces Kis of a 3-polytope (Conway notation 'k')

Parameters:

Polytope P

Returns:
Polytope

conway_needle(Polytope P)

Produces Needle of a 3-polytope (Conway notation 'n')

Parameters:

Polytope P

Returns:
Polytope

conway_propeller(Polytope P)

Produces Propeller of a 3-polytope (Conway notation 'p')

Parameters:

Polytope P

Returns:
Polytope

conway_seed()

Produces Conway Seed (3-cube) (Conway notation 'S')

Returns:
Polytope

conway_snub(Polytope P)

Produces Snub of a 3-polytope (Conway notation 's')

Parameters:

Polytope P

Returns:
Polytope
Example:

 > $c = cube(3); >$sc = conway_snub($c); > print$sc->F_VECTOR;
24 60 38

dual_linear_program(Polytope P, Bool maximize)

Produces the dual linear program for a given linear program of the form min {cx | Ax >= b, Bx = d}. Here (A,b) are given by the FACETS (or the INEQAULITIES), and (B,d) are given by the AFFINE_HULL (or by the EQUATIONS) of the polytope P, while the objective function c comes from an LP subobject.

Parameters:

Polytope P: = {x | Ax >= b, Bx = d}

Bool maximize: tells if the primal lp is a maximization problem. Default value is 0 (= minimize)

Returns:
Polytope

edge_middle(Polytope P)

Produce the convex hull of all edge middle points of some polytope P. The polytope must be BOUNDED.

Parameters:

Polytope P

Returns:
Polytope

face(Cone P, Set S)

For a given set S of rays compute the smallest face F of a cone P containing them all; see also face_pair.

Parameters:

Cone P

Set S

Options:

Bool no_coordinates: don't copy the coordinates, produce purely combinatorial description.

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0

Returns:
Cone
Example:

To create a cone from the vertices of the zeroth facet of the 3-cube, type this:

 > $p = face(cube(3),[0,1]); facet(Cone P, Int facet) Extract the given facet of a polyhedron and write it as a new polyhedron. Parameters: Cone P Int facet Options: Bool no_coordinates: don't copy the coordinates, produce purely combinatorial description. Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 Returns: Cone Example: To create a cone from the vertices of the zeroth facet of the 3-cube, type this:  >$p = facet(cube(3),0);

facet_to_infinity(Polytope P, Int i)

Make an affine transformation such that the i-th facet is transformed to infinity

Parameters:

Polytope P

Int i: the facet index

Returns:
Polytope
Example:

This generates the polytope that is the positive quadrant in 2-space:

 > $q = new Polytope(VERTICES=>[[1,-1,-1],[1,0,1],[1,1,0]]); >$pf = facet_to_infinity($q,2); > print$pf->VERTICES;
0 -1 -1
0 0 1
1 0 1

free_sum(Polytope P1, Polytope P2)

Construct a new polyhedron as the free sum of two given bounded ones.

Parameters:

Polytope P1

Polytope P2

Options:

Bool force_centered: if the input polytopes must be centered. Defaults to true.

Bool no_coordinates: produces a pure combinatorial description. Defaults to false.

Returns:
Polytope
Example:

 > $p = free_sum(cube(2),cube(2)); > print$p->VERTICES;
1 -1 -1 0 0
1 1 -1 0 0
1 -1 1 0 0
1 1 1 0 0
1 0 0 -1 -1
1 0 0 1 -1
1 0 0 -1 1
1 0 0 1 1

free_sum_decomposition(Polytope P)

Decompose a given polytope into the free sum of smaller ones

Parameters:

Polytope P

Returns:
Array<Polytope>

free_sum_decomposition_indices(Polytope P)

Decompose a given polytope into the free sum of smaller ones, and return the vertex indices of the summands

Parameters:

Polytope P

Returns:
Array<Set>
Example:

 > $p = free_sum(cube(1),cube(1)); > print$p->VERTICES;
1 -1 0
1 1 0
1 0 -1
1 0 1
 > print free_sum_decomposition_indices($p); {0 1} {2 3} gc_closure(Polytope P) Produces the gomory-chvatal closure of a full dimensional polyhedron Parameters: Polytope P Returns: Polytope integer_hull(Polytope P) Produces the integer hull of a polyhedron Parameters: Polytope P Returns: Polytope Example:  >$p = new Polytope(VERTICES=>[[1,13/10,1/2],[1,1/5,6/5],[1,1/10,-3/2],[1,-7/5,1/5]]);
> $ih = integer_hull($p);
> print $ih->VERTICES; 1 -1 0 1 0 -1 1 0 1 1 1 0 intersection(Cone C …) Construct a new polyhedron or cone as the intersection of given polyhedra and/or cones. Works only if all CONE_AMBIENT_DIM values are equal. If the input contains both cones and polytopes, the output will be a polytope. Parameters: Cone C …: polyhedra and cones to be intersected Returns: Cone Example:  >$p = intersection(cube(2), cross(2,3/2));
> print $p->VERTICES; 1 -1/2 1 1 -1 1/2 1 1/2 1 1 1 1/2 1 1/2 -1 1 1 -1/2 1 -1/2 -1 1 -1 -1/2 join_polytopes(Polytope P1, Polytope P2) Construct a new polyhedron as the join of two given bounded ones. Parameters: Polytope P1 Polytope P2 Options: Bool no_coordinates: produces a pure combinatorial description. Bool group: Compute the canonical group induced by the groups on P1 and P2 Throws an exception if the GROUPs of the input polytopes are not provided. default 0 Returns: Polytope Example: To join two squares, use this:  >$p = join_polytopes(cube(2),cube(2));
> print $p->VERTICES; 1 -1 -1 -1 0 0 1 1 -1 -1 0 0 1 -1 1 -1 0 0 1 1 1 -1 0 0 1 0 0 1 -1 -1 1 0 0 1 1 -1 1 0 0 1 -1 1 1 0 0 1 1 1 lattice_bipyramid(Polytope P, Vector v, Vector v_prime, Rational z, Rational z_prime) Make a lattice bipyramid over a polyhedron. The bipyramid is the convex hull of the input polyhedron P and two points (v, z), (v_prime, z_prime) on both sides of the affine span of P. Parameters: Polytope P Vector v: basis point for the first apex Vector v_prime: basis for the second apex If v_prime is omitted, v will be used for both apices. If both v and v_prime are omitted, it tries to find two vertices which don't lie in a common facet. If no such vertices can be found or P is a simplex, it uses an interior lattice point as both v and v_prime. Rational z: height for the first apex, default value is 1 Rational z_prime: height for the second apex, default value is -z Options: Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new vertices with “Apex” and “Apex'”. Returns: Polytope Example: To create the bipyramid over a square and keep the vertex labels, do this:  >$p = lattice_bipyramid(cube(2),new Vector(1,0,0));
> print $p->VERTICES; 1 -1 -1 0 1 1 -1 0 1 -1 1 0 1 1 1 0 1 0 0 1 1 0 0 -1  > print$p->VERTEX_LABELS;
0 1 2 3 Apex Apex'

lattice_pyramid(Polytope P, Rational z, Vector v)

Make a lattice pyramid over a polyhedron. The pyramid is the convex hull of the input polyhedron P and a point v outside the affine span of P.

Parameters:

Polytope P

Rational z: the height for the apex (v,z), default value is 1.

Vector v: the lattice point to use as apex, default is the first vertex of P.

Options:

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new top vertex with “Apex”.

Returns:
Polytope
Example:

To create the pyramid of height 5 over a square and keep the vertex labels, do this:

 > $p = lattice_pyramid(cube(2),5,new Vector(1,0,0)); > print$p->VERTICES;
1 -1 -1 0
1 1 -1 0
1 -1 1 0
1 1 1 0
1 0 0 5
 > print $p->VERTEX_LABELS; 0 1 2 3 Apex lawrence(Cone P) Create the Lawrence polytope$ Lambda(P) $corresponding to P.$ Lambda(P) $has the property that$ Gale( Lambda(P) ) = Gale(P) union -Gale(P) $. Parameters: Cone P: an input cone or polytope Returns: Cone make_totally_dual_integral(Polytope P) Produces a polyhedron with an totally dual integral inequality formulation of a full dimensional polyhedron Parameters: Polytope P Returns: Polytope mapping_polytope(Polytope P1, Polytope P2) Construct a new polytope as the mapping polytope of two polytopes P1 and P2. The mapping polytope is the set of all affine maps from Rp to Rq, that map P1 into P2. Mapping polytopes are also called Hom-polytopes; cf. Bogart, Contois & Gubeladze, doi:10.1007/s00209-012-1053-5. The label of a new facet corresponding to v1 and h1 will have the form “v1*h1”. Parameters: Polytope P1 Polytope P2 Options: Bool no_labels: Do not assign FACET_LABELS. default: 0 Returns: Polytope Example: Let us look at the mapping polytope of the unit interval and the standard unimodular triangle.  >$I=simplex(1); $T=simplex(2);$Hom_IT=mapping_polytope($I,$T);

The dimension equals (dim I + 1) * dim T.

 > print $Hom_IT->DIM 4  > print rows_labeled($Hom_IT->FACETS,$Hom_IT->FACET_LABELS); v0*F0:1 -1 0 -1 0 v0*F1:0 1 0 0 0 v0*F2:0 0 0 1 0 v1*F0:1 -1 -1 -1 -1 v1*F1:0 1 1 0 0 v1*F2:0 0 0 1 1  > print$Hom_IT->N_VERTICES;
9

This is how to turn, e.g., the first vertex into a linear map.

 > $v=$Hom_IT->VERTICES->[0];
> $M=new Matrix([$v->slice([1..2]),$v->slice([3..4])]); > print$I->VERTICES * transpose($M); 0 0 0 1 The above are coordinates in R^2, without the homogenization commonly used in polymake. minkowski_sum(Polytope P1, Polytope P2) Produces the Minkowski sum of P1 and P2. Parameters: Polytope P1 Polytope P2 Returns: Polytope Example: The following stores the minkowski sum of a square and a triangle in the variable$p and then prints its vertices.

 > $p = minkowski_sum(cube(2),simplex(2)); > print$p->VERTICES;
1 -1 -1
1 2 -1
1 -1 2
1 2 1
1 1 2
minkowski_sum(Scalar lambda, Polytope P1, Scalar mu, Polytope P2)

Produces the polytope lambda*P1+mu*P2, where * and + are scalar multiplication and Minkowski addition, respectively.

Parameters:

Scalar lambda

Polytope P1

Scalar mu

Polytope P2

Returns:
Polytope
Example:

The following stores the minkowski sum of a scaled square and a triangle in the variable $p and then prints its vertices.  >$p = minkowski_sum(2,cube(2),1,simplex(2));
> print $p->VERTICES; 1 -2 -2 1 3 -2 1 -2 3 1 3 2 1 2 3 minkowski_sum_fukuda(Array<Polytope> summands) Computes the (VERTICES of the) Minkowski sum of a list of polytopes using the algorithm by Fukuda described in Komei Fukuda, From the zonotope construction to the Minkowski addition of convex polytopes, J. Symbolic Comput., 38(4):1261-1272, 2004. Parameters: Array<Polytope> summands Returns: Polytope Example:  >$p = minkowski_sum_fukuda([cube(2),simplex(2),cross(2)]);
> print $p->VERTICES; 1 3 -1 1 3 1 1 -1 -2 1 1 3 1 -1 3 1 2 -2 1 -2 2 1 -2 -1 mixed_integer_hull(Polytope P, Array<Int> int_coords) Produces the mixed integer hull of a polyhedron Parameters: Polytope P Array<Int> int_coords: the coordinates to be integral; Returns: Polytope pointed_part(Polytope P) Produces the pointed part of a polyhedron Parameters: Polytope P Returns: Polytope Example:  >$p = new Polytope(POINTS=>[[1,0,0],[1,0,1],[1,1,0],[1,1,1],[0,1,0],[0,0,1]]);
> $pp = pointed_part($p);
> print $pp->VERTICES; 1 0 0 0 1 0 0 0 1 prism(Polytope P, Scalar z1, Scalar z2) Make a prism over a pointed polyhedron. The prism is the product of the input polytope P and the interval [z1, z2]. Parameters: Polytope P: the input polytope Scalar z1: the left endpoint of the interval; default value: -1 Scalar z2: the right endpoint of the interval; default value: -z1 Options: Bool group: Compute the canonical group induced by the group on P with an extra generator swapping the upper and lower copy. throws an exception if GROUP of P is not provided. default 0 Bool no_coordinates: only combinatorial information is handled Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 the bottom facet vertices get the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended. Returns: Polytope Example: The following saves the prism over the square and the interval [-2,2] to the variable$p, and then prints a nice representation of its vertices.

 > $p = prism(cube(2),-2); > print rows_labeled($p->VERTICES,$p->VERTEX_LABELS); 0:1 -1 -1 -2 1:1 1 -1 -2 2:1 -1 1 -2 3:1 1 1 -2 0':1 -1 -1 2 1':1 1 -1 2 2':1 -1 1 2 3':1 1 1 2 product(Polytope P1, Polytope P2) Construct a new polytope as the product of two given polytopes P1 and P2. As little additional properties of the input polytopes as possible are computed. You can control this behaviour using the option flags. Parameters: Polytope P1 Polytope P2 Options: Bool no_coordinates: only combinatorial information is handled Bool no_vertices: do not compute vertices Bool no_facets: do not compute facets Bool no_labels: Do not copy VERTEX_LABELS from the original polytopes, if present. the label of a new vertex corresponding to v1 ⊕ v2 will have the form LABEL_1*LABEL_2. default: 0 Bool group: Compute the canonical group of the product, as induced by the groups on FACETS of VERTICES of P1 and P2. If neither FACETS_ACTION nor VERTICES_ACTION of the GROUPs of the input polytopes are provided, an exception is thrown. default 0 Returns: Polytope Example: The following builds the product of a square and an interval, without computing vertices of neither the input nor the output polytopes.  >$p = product(cube(2),cube(1), no_vertices=>1);

project_full(Cone P)

Orthogonally project a polyhedron to a coordinate subspace such that redundant columns are omitted, i.e., the projection becomes full-dimensional without changing the combinatorial type. The client scans for all coordinate sections and produces proper output from each. If a description in terms of inequalities is found, the client performs Fourier-Motzkin elimination unless the nofm option is set. Setting the nofm option is useful if the corank of the projection is large; in this case the number of inequalities produced grows quickly.

Parameters:

Cone P

Options:

Bool nofm: suppresses Fourier-Motzkin elimination

Bool no_labels: Do not copy VERTEX_LABELS to the projection. default: 0

Returns:
Cone

projection(Cone P, Array<Int> indices)

Orthogonally project a pointed polyhedron to a coordinate subspace. The subspace the polyhedron P is projected on is given by indices in the set indices. The option revert inverts the coordinate list. The client scans for all coordinate sections and produces proper output from each. If a description in terms of inequalities is found, the client performs Fourier-Motzkin elimination unless the nofm option is set. Setting the nofm option is useful if the corank of the projection is large; in this case the number of inequalities produced grows quickly.

Parameters:

Cone P

Array<Int> indices

Options:

Bool revert: inverts the coordinate list

Bool nofm: suppresses Fourier-Motzkin elimination

Returns:
Cone
Example:

project the 3-cube along the first coordinate, i.e. to the subspace spanned by the second and third coordinate:

 > $p = projection(cube(3),[1],revert=>1); > print$p->VERTICES;
1 1 -1
1 1 1
1 -1 1
1 -1 -1

projection_preimage(Array<Cone> P_Array)

Construct a new polyhedron that projects to a given array of polyhedra. If the n polyhedra are d_1, d_2, …, d_n-dimensional and all have m vertices, the resulting polyhedron is (d_1+…+d_n)-dimensional, has m vertices, and the projection to the i-th d_i coordinates gives the i-th input polyhedron.

Parameters:

Array<Cone> P_Array

Returns:
Cone
Example:

 > $p = projection_preimage(cube(2),cube(2)); > print$p->VERTICES;
1 -1 -1 -1 -1
1 1 -1 1 -1
1 -1 1 -1 1
1 1 1 1 1

pyramid(Polytope P, Scalar z)

Make a pyramid over a polyhedron. The pyramid is the convex hull of the input polyhedron P and a point v outside the affine span of P. For bounded polyhedra, the projection of v to the affine span of P coincides with the vertex barycenter of P.

Parameters:

Polytope P

Scalar z: is the distance between the vertex barycenter and v, default value is 1.

Options:

Bool group: compute the group induced by the GROUP of P and leaving the apex fixed. throws an exception if GROUP of P is not provided. default 0

Bool no_coordinates: don't compute new coordinates, produce purely combinatorial description.

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new top vertex with “Apex”.

Returns:
Polytope
Example:

The following saves the pyramid of height 2 over the square to the variable $p. The vertices are relabeled.  >$p = pyramid(cube(2),2);

To print the vertices and vertex labels of the newly generated pyramid, do this:

 > print $p->VERTICES; 1 -1 -1 0 1 1 -1 0 1 -1 1 0 1 1 1 0 1 0 0 2  > print$p->VERTEX_LABELS;
0 1 2 3 Apex

rand_inner_points(Polytope P, Int n)

Produce a polytope with n random points from the input polytope P. Each generated point is a convex linear combination of the input vertices with uniformly distributed random coefficients. Thus, the output points can't in general be expected to be distributed uniformly within the input polytope; cf. unirand for this. The polytope must be BOUNDED.

Parameters:

Polytope P: the input polytope

Int n: the number of random points

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Polytope

rand_vert(Matrix V, Int n)

Selects n random vertices from the set of vertices V. This can be used to produce random polytopes which are neither simple nor simplicial as follows: First produce a simple polytope (for instance at random, by using rand_sphere, rand, or unirand). Then use this client to choose among the vertices at random. Generalizes random 0/1-polytopes.

Parameters:

Matrix V: the vertices of a polytope

Int n: the number of random points

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Matrix

spherize(Polytope P)

Project all vertices of a polyhedron P on the unit sphere. P must be CENTERED and BOUNDED.

Parameters:

Polytope P

Returns:
Polytope
Example:

The following scales the 2-dimensional cross polytope by 23 and then projects it back onto the unit circle.

 > $p = scale(cross(2),23); >$s = spherize($p); > print$s->VERTICES;
1 1 0
1 -1 0
1 0 1
1 0 -1

stack(Polytope P, Set<Int> stack_facets)

Stack a (simplicial or cubical) polytope over one or more of its facets. For each facet of the polytope P specified in stack_facets, the barycenter of its vertices is lifted along the normal vector of the facet. In the simplicial case, this point is directly added to the vertex set, thus building a pyramid over the facet. In the cubical case, this pyramid is truncated by a hyperplane parallel to the original facet at its half height. This way, the property of being simplicial or cubical is preserved in both cases. The option lift controls the exact coordinates of the new vertices. It should be a rational number between 0 and 1, which expresses the ratio of the distance between the new vertex and the stacked facet, to the maximal possible distance. When lift=0, the new vertex would lie on the original facet. lift=1 corresponds to the opposite extremal case, where the new vertex hit the hyperplane of some neighbor facet. As an additional restriction, the new vertex can't lie further from the facet as the vertex barycenter of the whole polytope. Alternatively, the option noc (no coordinates) can be specified to produce a pure combinatorial description of the resulting polytope.

Parameters:

Polytope P

Set<Int> stack_facets: the facets to be stacked; A single facet to be stacked is specified by its number. Several facets can be passed in a Set or in an anonymous array of indices: [n1,n2,…] Special keyword All means that all factes are to be stacked.

Options:

Rational lift: controls the exact coordinates of the new vertices; rational number between 0 and 1; default value: 1/2

Bool no_coordinates: produces a pure combinatorial description (in contrast to lift)

Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 New vertices get labels 'f(FACET_LABEL)' in the simplicial case, and 'f(FACET_LABEL)-NEIGHBOR_VERTEX_LABEL' in the cubical case.

Returns:
Polytope
Example:

To generate a cubical polytope by stacking all facets of the 3-cube to height 1/4, do this:

 > $p = stack(cube(3),All,lift=>1/4); stellar_all_faces(Polytope P, Int d) Perform a stellar subdivision of all proper faces, starting with the facets. Parameter d specifies the lowest dimension of the faces to be divided. It can also be negative, then treated as the co-dimension. Default is 1, that is, the edges of the polytope. Parameters: Polytope P: , must be bounded Int d: the lowest dimension of the faces to be divided; negative values: treated as the co-dimension; default value: 1. Returns: Polytope stellar_indep_faces(Polytope P, Array<Set<Int>> in_faces) Perform a stellar subdivision of the faces in_faces of a polyhedron P. The faces must have the following property: The open vertex stars of any pair of faces must be disjoint. Parameters: Polytope P: , must be bounded Array<Set<Int>> in_faces Returns: Polytope tensor(Polytope P1, Polytope P2) Construct a new polytope as the convex hull of the tensor products of the vertices of two polytopes P1 and P2. Unbounded polyhedra are not allowed. Does depend on the vertex coordinates of the input. Parameters: Polytope P1 Polytope P2 Returns: Polytope Example: The following creates the tensor product polytope of two squares and then prints its vertices.  >$p = tensor(cube(2),cube(2));
> print $p->VERTICES; 1 1 1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 truncation(Polytope P, Set<Int> trunc_vertices) Cut off one or more vertices of a polyhedron. The exact location of the cutting hyperplane(s) can be controlled by the option cutoff, a rational number between 0 and 1. When cutoff=0, the hyperplane would go through the chosen vertex, thus cutting off nothing. When cutoff=1, the hyperplane touches the nearest neighbor vertex of a polyhedron. Alternatively, the option no_coordinates can be specified to produce a pure combinatorial description of the resulting polytope, which corresponds to the cutoff factor 1/2. Parameters: Polytope P Set<Int> trunc_vertices: the vertex/vertices to be cut off; A single vertex to be cut off is specified by its number. Several vertices can be passed in a Set or in an anonymous array of indices: [n1,n2,…] Special keyword All means that all vertices are to be cut off. Options: Scalar cutoff: controls the exact location of the cutting hyperplane(s); rational number between 0 and 1; default value: 1/2 Bool no_coordinates: produces a pure combinatorial description (in contrast to cutoff) Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 New vertices get labels of the form 'LABEL1-LABEL2', where LABEL1 is the original label of the truncated vertex, and LABEL2 is the original label of its neighbor. Returns: Polytope Example: To truncate the second vertex of the square at 1/4, try this:  >$p = truncation(cube(2),2,cutoff=>1/4);
> print $p->VERTICES; 1 -1 -1 1 1 -1 1 1 1 1 -1 1/2 1 -1/2 1 unirand(Polytope P, Int n) Produce a polytope with n random points that are uniformly distributed within the given polytope P. P must be bounded and full-dimensional. Parameters: Polytope P Int n: the number of random points Options: Bool boundary: forces the points to lie on the boundary of the given polytope Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome. Returns: Polytope Example: This produces a polytope as the convex hull of 5 random points in the square with the origin as its center and side length 2:  >$p = unirand(cube(2),5);
Example:

This produces a polytope as the convex hull of 5 random points on the boundary of the square with the origin as its center and side length 2:

 > $p = unirand(cube(2),5,boundary=>1); vertex_figure(Polytope p, Int n) Construct the vertex figure of the vertex n of a polyhedron. The vertex figure is dual to a facet of the dual polytope. Parameters: Polytope p Int n: number of the chosen vertex Options: Scalar cutoff: controls the exact location of the cutting hyperplane. It should lie between 0 and 1. Value 0 would let the hyperplane go through the chosen vertex, thus degenerating the vertex figure to a single point. Value 1 would let the hyperplane touch the nearest neighbor vertex of a polyhedron. Default value is 1/2. Bool no_coordinates: skip the coordinates computation, producing a pure combinatorial description. Bool no_labels: Do not copy VERTEX_LABELS from the original polytope. default: 0 by default, the labels are produced from the corresponding neighbor vertices of the original polytope. Returns: Polytope Example: This produces a vertex figure of one vertex of a 3-dimensional cube with the origin as its center and side length 2. The result is a 2-simplex.  >$p = vertex_figure(cube(3),5);
> print $p->VERTICES; 1 1 -1 0 1 0 -1 1 1 1 0 1 wedge(Polytope P, Int facet, Rational z, Rational z_prime) Make a wedge from a polytope over the given facet. The polytope must be bounded. The inclination of the bottom and top side facet is controlled by z and z_prime, which are heights of the projection of the old vertex barycenter on the bottom and top side facet respectively. Parameters: Polytope P: , must be bounded Int facet: the cutting edge'. Rational z: default value is 0. Rational z_prime: default value is -z, or 1 if z==0. Options: Bool no_coordinates: don't compute coordinates, pure combinatorial description is produced. Bool no_labels: Do not copy VERTEX_LABELS from the original polytopes. default: 0 By default, the vertices get labelled as follows: The bottom facet vertices obtain the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended. Returns: Polytope Example: This produces the wedge from a square (over the facet 0), which yields a prism over a triangle:  >$p = wedge(cube(2),0);
> print $p->VERTICES; 1 -1 -1 0 1 1 -1 0 1 -1 1 0 1 1 1 0 1 1 -1 2 1 1 1 2 wreath(Polytope P1, Polytope P2) Construct a new polytope as the wreath product of two input polytopes P1, P2. P1 and P2 have to be BOUNDED. Parameters: Polytope P1 Polytope P2 Options: Bool dual: invokes the computation of the dual wreath product Bool no_labels: Do not copy VERTEX_LABELS from the original polytopes. default: 0 the label of a new vertex corresponding to v1 ⊕ v2 will have the form LABEL_1*LABEL_2. Returns: Polytope ### Producing a polytope from scratch With these clients you can create polytopes belonging to various parameterized families which occur frequently in polytope theory, as well as several kinds of random polytopes. Regular polytopes and their friends are listed separately. SIM_body<Scalar>(Vector<Scalar> alpha) Produce an n-dimensional SIM-body as generalized permutahedron in (n+1)-space. SIM-bodies are defined in the article “Duality and Optimality of Auctions for Uniform Distributions” by Yiannis Giannakopoulos and Elias Koutsoupias, but the input needs to be descending instead of ascending, as used in “Generalized Permutahedra and Optimal Auctions” by Michael Joswig, Max Klimm and Sylvain Spitz. Type Parameters: Scalar Parameters: Vector<Scalar> alpha: Vector with the parameters (a1,…,an) s.t. a1 >= … >= an >= 0. Returns: Polytope Example: To produce a 2-dimensional SIM-body, use for example the following code. Note that the polytope lives in 3-space, so we project it down to 2-space by eliminating the last coordinate.  >$p = SIM_body(new Vector(sequence(3,1)));
> $s = new Polytope(POINTS=>$p->VERTICES->minor(All,~[$p->CONE_DIM])); associahedron(Int d) Produce a d-dimensional associahedron (or Stasheff polytope). We use the facet description given in Ziegler's book on polytopes, section 9.2. Parameters: Int d: the dimension Options: Bool group: Compute the combinatorial symmetry group of the polytope. It has two generators, as it is induced by the symmetry group of an d+3-gon, the dihedral group of degree d+3. See arXiv 1109.5544v2 for details. Returns: Polytope binary_markov_graph(Array<Bool> observation) Defines a very simple graph for a polytope propagation related to a Hidden Markov Model. The propagated polytope is always a polygon. For a detailed description see M. Joswig: Polytope propagation, in: Algebraic statistics and computational biology by L. Pachter and B. Sturmfels (eds.), Cambridge, 2005. Parameters: Array<Bool> observation Returns: PropagatedPolytope binary_markov_graph(String observation) Parameters: String observation: encoded as a string of “0” and “1”. birkhoff(Int n, Bool even) Constructs the Birkhoff polytope of dimension n2. It is the polytope of nxn stochastic matrices (encoded as n2 row vectors), thus matrices with non-negative entries whose row and column entries sum up to one. Its vertices are the permutation matrices. Parameters: Int n Bool even: Defaults to '0'. Set this to '1' to get vertices only for even permutation matrices. Options: Bool group: add the symmetry group induced by the symmetric group to the resulting polytope Returns: Polytope cyclic(Int d, Int n) Produce a d-dimensional cyclic polytope with n points. Prototypical example of a neighborly polytope. Combinatorics completely known due to Gale's evenness criterion. Coordinates are chosen on the (spherical) moment curve at integer steps from start, or 0 if unspecified. If spherical is true the vertices lie on the sphere with center (1/2,0,…,0) and radius 1/2. In this case (the necessarily positive) parameter start defaults to 1. Parameters: Int d: the dimension Int n: the number of points Options: Int start: defaults to 0 (or to 1 if spherical) Bool spherical: defaults to false Returns: Polytope<Rational> Example: To create the 2-dimensional cyclic polytope with 6 points on the sphere, starting at 3:  >$p = cyclic(2,6,start=>3,spherical=>1);
> print $p->VERTICES; 1 1/10 3/10 1 1/17 4/17 1 1/26 5/26 1 1/37 6/37 1 1/50 7/50 1 1/65 8/65 cyclic_caratheodory(Int d, Int n) Produce a d-dimensional cyclic polytope with n points. Prototypical example of a neighborly polytope. Combinatorics completely known due to Gale's evenness criterion. Coordinates are chosen on the trigonometric moment curve. For cyclic polytopes from other curves, see cyclic. Parameters: Int d: the dimension. Required to be even. Int n: the number of points Options: Bool group: add a symmetry group description. If 0 (default), the return type is Polytope<Rational>, else Polytope<Float> so that the matrices corresponding to the symmetry action may be approximated Returns: Polytope delpezzo(Int d, Scalar scale) Produce a d-dimensional del-Pezzo polytope, which is the convex hull of the cross polytope together with the all-ones and minus all-ones vector. All coordinates are +/- scale or 0. Parameters: Int d: the dimension Scalar scale: the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1. Returns: Polytope<Scalar> dwarfed_cube(Int d) Produce a d-dimensional dwarfed cube. Parameters: Int d: the dimension Returns: Polytope dwarfed_product_polygons(Int d, Int s) Produce a d-dimensional dwarfed product of polygons of size s. Parameters: Int d: the dimension Int s: the size Returns: Polytope explicit_zonotope(Matrix zones) Produce the POINTS of a zonotope as the iterated Minkowski sum of all intervals [-x,x], where x ranges over the rows of the input matrix zones. Parameters: Matrix zones: the input vectors Options: Bool rows_are_points: the rows of the input matrix represent affine points(true, default) or linear vectors(false) Returns: Polytope Example:  >$M = new Matrix([1,1],[1,-1]);
> $p = explicit_zonotope($M,rows_are_points=>0);
> print $p->VERTICES; 1 2 0 1 0 -2 1 0 2 1 -2 0 fano_simplex(Int d) Produce a Fano d-simplex. Parameters: Int d: the dimension Options: Bool group Returns: Polytope Example: To create the 2-dimensional fano simplex and compute its symmetry group, type this: and print ints generators, do this:  >$p = fano_simplex(2,group=>1);
> print $p->GROUP->RAYS_ACTION->GENERATORS; 1 0 2 2 0 1 fractional_knapsack(Vector<Rational> b) Produce a knapsack polytope defined by one linear inequality (and non-negativity constraints). Parameters: Vector<Rational> b: linear inequality Returns: Polytope gelfand_tsetlin<Scalar>(Vector<Scalar> lambda) Produce a Gelfand-Tsetlin polytope for a given sequence. See Postnikov: Permutohedra, associahedra, and beyond, IMRN (2009); doi:10.1093/imrn/rnn153 Theorem 15.1. Type Parameters: Scalar Parameters: Vector<Scalar> lambda: Vector encoding a descending sequence of numbers. Options: Bool projected: Omit the redundant first row of equations to reduce dimension, default=false Returns: Polytope Example: Create the Gelfand-Tsetlin polytope for the sequence (6,4,2,1)  >$lambda = new Vector(6,4,2,1);
> $pgt = gelfand_tsetlin($lambda,projected=>1);
> $gt = gelfand_tsetlin($lambda,projected=>0);
> print $gt->LATTICE_VOLUME; 14400  > print$pgt->LATTICE_VOLUME;
14400

generalized_permutahedron<Scalar>(Int d, Map<Set<Int>,Scalar> z)

Produce a generalized permutahedron via zI height function. See Postnikov: Permutohedra, associahedra, and beyond, IMRN (2009); doi:10.1093/imrn/rnn153 Note that opposed to Postnikov's paper, polymake starts counting at zero.

Type Parameters:

Scalar

Parameters:

Int d: The dimension

Map<Set<Int>,Scalar> z: Values of the height functions for the different 0/1-directions, i.e. for h = height({1,2,4}) we have the inequality x1 + x2 + x4 >= h. The height value for the set containing all coordinates from 0 to d-1 is interpreted as equality. If any value is missing, it will be skipped. Also it is not checked, if the values are consistent for a height function.

Returns:
Polytope
Example:

To create a generalized permutahedron in 3-space use

 > $m = new Map<Set,Rational>; >$m->{new Set(0)} = 0;
> $m->{new Set(1)} = 0; >$m->{new Set(2)} = 0;
> $m->{new Set(0,1)} = 1/4; >$m->{new Set(0,2)} = 1/4;
> $m->{new Set(1,2)} = 1/4; >$m->{new Set(0,1,2)} = 1;
> $p = generalized_permutahedron(3,$m);

goldfarb(Int d, Scalar e, Scalar g)

Produces a d-dimensional Goldfarb cube if e<1/2 and g⇐e/4. The Goldfarb cube is a combinatorial cube and yields a bad example for the Simplex Algorithm using the Shadow Vertex Pivoting Strategy. Here we use the description as a deformed product due to Amenta and Ziegler. For e<1/2 and g=0 we obtain the Klee-Minty cubes.

Parameters:

Int d: the dimension

Scalar e

Scalar g

Returns:
Polytope

goldfarb_sit(Int d, Scalar eps, Scalar delta)

Produces a d-dimensional variation of the Klee-Minty cube if eps<1/2 and delta⇐1/2. This Klee-Minty cube is scaled in direction x_(d-i) by (eps*delta)^i. This cube is a combinatorial cube and yields a bad example for the Simplex Algorithm using the 'steepest edge' Pivoting Strategy. Here we use a scaled description of the construction of Goldfarb and Sit.

Parameters:

Int d: the dimension

Scalar eps

Scalar delta

Returns:
Polytope

hypersimplex(Int k, Int d)

Produce the hypersimplex $Δ(k,d)$, that is the the convex hull of all 0/1-vector in $R^d$ with exactly k 1s. Note that the output is never full-dimensional.

Parameters:

Int k: number of 1s

Int d: ambient dimension

Options:

Bool group

Bool no_vertices: do not compute vertices

Bool no_facets: do not compute facets

Bool no_vif: do not compute vertices in facets

Returns:
Polytope
Example:

This creates the hypersimplex in dimension 4 with vertices with exactly two 1-entries and computes its symmetry group:

 > $h = hypersimplex(2,4,group=>1); hypertruncated_cube<Scalar>(Int d, Scalar k, Scalar lambda) Produce a d-dimensional hypertruncated cube. With symmetric linear objective function (0,1,1,…,1). Type Parameters: Scalar: Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational. Parameters: Int d: the dimension Scalar k: cutoff parameter Scalar lambda: scaling of extra vertex Returns: Polytope<Scalar> k_cyclic(Int n, Vector s) Produce a (rounded) 2*k-dimensional k-cyclic polytope with n points, where k is the length of the input vector s. Special cases are the bicyclic (k=2) and tricyclic (k=3) polytopes. Only possible in even dimensions. The parameters s_i can be specified as integer, floating-point, or rational numbers. The coordinates of the i-th point are taken as follows: cos(s_1 * 2πi/n), sin(s_1 * 2πi/n), cos(s_k * 2πi/n), sin(s_k * 2πi/n) Warning: Some of the k-cyclic polytopes are not simplicial. Since the components are rounded, this function might output a polytope which is not a k-cyclic polytope! More information can be found in the following references: P. Schuchert: “Matroid-Polytope und Einbettungen kombinatorischer Mannigfaltigkeiten”, PhD thesis, TU Darmstadt, 1995. Z. Smilansky: “Bi-cyclic 4-polytopes”, Isr. J. Math. 70, 1990, 82-92 Parameters: Int n: the number of points Vector s: s=(s_1,…,s_k) Returns: Polytope Example: To produce a (not exactly) regular pentagon, type this:  >$p = k_cyclic(5,[1]);

klee_minty_cube(Int d, Scalar e)

Produces a d-dimensional Klee-Minty-cube if e<1/2. Uses the goldfarb client with g=0.

Parameters:

Int d: the dimension

Scalar e

Returns:
Polytope

lecture_hall_simplex(Int d)

Produce a lecture hall d-simplex.

Parameters:

Int d: the dimension

Options:

Bool group

Returns:
Polytope
Example:

To create the 2-dimensional lecture hall simplex and compute its symmetry group, type this:

 > $p = lecture_hall_simplex(2, group=>1); > print$p->GROUP->RAYS_ACTION->GENERATORS;
1 0 2
2 0 1

long_and_winding(Int r)

Produce polytope in dimension 2r with 3r+2 facets such that the total curvature of the central path is at least Omega(2^r); see Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. Appl. Algebra Geom. (2018). See also perturbed_long_and_winding.

Parameters:

Int r: defining parameter

Options:

Rational eval_ratio: parameter for evaluating the puiseux rational functions

Int eval_exp: to evaluate at eval_ratio^eval_exp, default: 1

Float eval_float: parameter for evaluating the puiseux rational functions

Returns:
Polytope<PuiseuxFraction<Max,Rational,Rational>>
Example:

This yields a 4-polytope over the field of Puiseux fractions.

 > $p = long_and_winding(2); Example: This yields a rational 4-polytope with the same combinatorics.  >$p = long_and_winding(2,eval_ratio=>2);

max_GC_rank(Int d)

Produce a d-dimensional polytope of maximal Gomory-Chvatal rank $Omega( d/log(d) )$ , integrally infeasible. With symmetric linear objective function (0,1,1..,1). Construction due to Pokutta and Schulz.

Parameters:

Int d: the dimension

Returns:
Polytope

multiplex(Int d, Int n)

Produce a combinatorial description of a multiplex with parameters d and n. This yields a self-dual d-dimensional polytope with n+1 vertices. They are introduced by

T. Bisztriczky,
On a class of generalized simplices, Mathematika 43:27-285, 1996,

M.M. Bayer, A.M. Bruening, and J.D. Stewart,
A combinatorial study of multiplexes and ordinary polytopes,
Discrete Comput. Geom. 27(1):49–63, 2002.
Parameters:

Int d: the dimension

Int n

Returns:
Polytope

n_gon(Int n, Rational r, Rational alpha_0)

Produce a regular n-gon. All vertices lie on a circle of radius r. The radius defaults to 1.

Parameters:

Int n: the number of vertices

Rational r: the radius (defaults to 1)

Rational alpha_0: the initial angle divided by pi (defaults to 0)

Options:

Bool group

Returns:
Polytope
Example:

To store the regular pentagon in the variable $p and calculate its symmetry group, do this:  >$p = n_gon(5,group=>1);
> print $p->GROUP->RAYS_ACTION->GENERATORS; 0 4 3 2 1 1 2 3 4 0 neighborly_cubical(Int d, Int n) Produce the combinatorial description of a neighborly cubical polytope. The facets are labelled in oriented matroid notation as in the cubical Gale evenness criterion. See Joswig and Ziegler, Discr. Comput. Geom. 24:315-344 (2000). Parameters: Int d: dimension of the polytope Int n: dimension of the equivalent cube Returns: Polytope newton(Polynomial p) Produce the Newton polytope of a polynomial p. Parameters: Polynomial p Returns: Polytope<Rational> Example: Create the newton polytope of 1+x^2+y like so:  > local_var_names<Polynomial>(qw(x y));$p=new Polynomial('1+x^2+y');
> $n = newton($p);
> print $n->VERTICES; 1 0 0 1 0 1 1 2 0 perles_irrational_8_polytope() Create an 8-dimensional polytope without rational realizations due to Perles Returns: Polytope permutahedron(Int d) Produce a d-dimensional permutahedron. The vertices correspond to the elements of the symmetric group of degree d+1. Parameters: Int d: the dimension Options: Bool group Returns: Polytope Example: To create the 3-permutahedron and also compute its symmetry group, do this:  >$p = permutahedron(3,group=>1);
> print $p->GROUP->COORDINATE_ACTION->GENERATORS; 1 0 2 3 3 0 1 2 perturbed_long_and_winding(Int r) Produce polytope in dimension 2r with 3r+2 facets such that the total curvature of the central path is at least Omega(2^r). This is a perturbed version of long_and_winding, which yields simple polytopes. Parameters: Int r: defining parameter Options: Rational eval_ratio: parameter for evaluating the puiseux rational functions Int eval_exp: to evaluate at eval_ratio^eval_exp, default: 1 Float eval_float: parameter for evaluating the puiseux rational functions Returns: Polytope<PuiseuxFraction<Max,Rational,Rational>> Example: This yields a simple 4-polytope over the field of Puiseux fractions.  >$p = perturbed_long_and_winding(2);

pile(Vector<Int> sizes)

Produce a (d+1)-dimensional polytope from a pile of cubes. Start with a d-dimensional pile of cubes. Take a generic convex function to lift this polytopal complex to the boundary of a (d+1)-polytope.

Parameters:

Vector<Int> sizes: a vector (s1,…,sd, where si specifies the number of boxes in the i-th dimension.

Returns:
Polytope

pitman_stanley<Scalar>(Vector<Scalar> y)

Produce a Pitman-Stanley polytope of dimension n-1. See Pitman and Stanley, Discrete Comput Geom 27 (2002); doi:10.1007/s00454-002-2776-6

Type Parameters:

Scalar

Parameters:

Vector<Scalar> y: Vector of n positive parameters.

Returns:
Polytope
Example:

Pitman-Stanley polytopes are combinatorial cubes:

 > $p = pitman_stanley(new Vector([1,1,2,3])); > print$p->F_VECTOR;
8 12 6

pseudo_delpezzo(Int d, Scalar scale)

Produce a d-dimensional del-Pezzo polytope, which is the convex hull of the cross polytope together with the all-ones vector. All coordinates are +/- scale or 0.

Parameters:

Int d: the dimension

Scalar scale: the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.

Returns:
Polytope<Scalar>

rand01(Int d, Int n)

Produce a d-dimensional 0/1-polytope with n random vertices. Uniform distribution.

Parameters:

Int d: the dimension

Int n: the number of random vertices

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Polytope

rand_box(Int d, Int n, Int b)

Computes the convex hull of n points sampled uniformly at random from the integer points in the cube [0,b]d.

Parameters:

Int d: the dimension of the box

Int n: the number of random points

Int b: the size of the box

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Polytope

rand_cyclic(Int d, Int n)

Computes a random instance of a cyclic polytope of dimension d on n vertices by randomly generating a Gale diagram whose cocircuits have alternating signs.

Parameters:

Int d: the dimension

Int n: the number of vertices

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Polytope

rand_metric<Scalar>(Int n)

Produce an n-point metric with random distances. The values are uniformily distributed in [1,2].

Type Parameters:

Scalar: element type of the result matrix

Parameters:

Int n

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Matrix

rand_metric_int<Scalar>(Int n)

Produce an n-point metric with random distances. The values are uniformily distributed in [1,2].

Type Parameters:

Scalar: element type of the result matrix

Parameters:

Int n

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Returns:
Matrix

rand_normal(Int d, Int n)

Produce a rational d-dimensional polytope from n random points approximately normally distributed in the unit ball.

Parameters:

Int d: the dimension of ball

Int n: the number of random points

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Int precision: Number of bits for MPFR sphere approximation

Returns:
Polytope<Rational>

rand_sphere<Num>(Int d, Int n)

Produce a rational d-dimensional polytope with n random vertices approximately uniformly distributed on the unit sphere.

Type Parameters:

Num: can be AccurateFloat (the default) or Rational With AccurateFloat the distribution should be closer to uniform, but the vertices will not exactly be on the sphere. With Rational the vertices are guaranteed to be on the unit sphere, at the expense of both uniformity and log-height of points.

Parameters:

Int d: the dimension of sphere

Int n: the number of random vertices

Options:

Int seed: controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.

Int precision: Number of bits for MPFR sphere approximation

Returns:
Polytope<Rational>

rss_associahedron(Int l)

Produce a polytope of constrained expansions in dimension l according to

Rote, Santos, and Streinu: Expansive motions and the polytope of pointed pseudo-triangulations.
Discrete and computational geometry, 699–736, Algorithms Combin., 25, Springer, Berlin, 2003.
Parameters:

Int l: ambient dimension

Returns:
Polytope

signed_permutahedron(Int d)

Produce a d-dimensional signed permutahedron.

Parameters:

Int d: the dimension

Options:

Bool group

Returns:
Polytope

simplex(Int d, Scalar scale)

Produce the standard d-simplex. Combinatorially equivalent to a regular polytope corresponding to the Coxeter group of type Ad-1. Optionally, the simplex can be scaled by the parameter scale.

Parameters:

Int d: the dimension

Scalar scale: default value: 1

Options:

Bool group

Returns:
Polytope
Example:

To print the vertices (in homogeneous coordinates) of the standard 2-simplex, i.e. a right-angled isoceles triangle, type this:

 > print simplex(2)->VERTICES;
(3) (0 1)
1 1 0
1 0 1

The first row vector is sparse and encodes the origin.

Example:

To create a 3-simplex and also calculate its symmetry group, type this:

 > simplex(3, group=>1);

stable_set(Graph G)

Produces the stable set polytope from an undirected graph G=(V,E). The stable set Polytope has the following inequalities: x_i + x_j ⇐ 1 forall {i,j} in E x_i >= 0 forall i in V x_i ⇐ 1 forall i in V with deg(i)=0

Parameters:

Graph G

Returns:
Polytope

transportation(Vector r, Vector c)

Produce the transportation polytope from two vectors r of length m and c of length n, i.e. all positive m×n Matrizes with row sums equal to r and column sums equal to c.

Parameters:

Vector r

Vector c

Returns:
Polytope

upper_bound_theorem(Int d, Int n)

Produce combinatorial data common to all simplicial d-polytopes with n vertices with the maximal number of facets as given by McMullen's Upper-Bound-Theorem. Essentially this lets you read off all possible entries of the H_VECTOR and the F_VECTOR.

Parameters:

Int d: the dimension

Int n: the number of points

Returns:
Polytope
Example:

This produces the combinatorial data as mentioned above for 5 points in dimension 3 and prints the h-vector:

 > $p = upper_bound_theorem(3,5); > print$p->H_VECTOR;
1 2 2 1

zonotope(Matrix<Scalar> M)

Create a zonotope from a matrix whose rows are input points or vectors. This method merely defines a Polytope object with the property ZONOTOPE_INPUT_POINTS.

Parameters:

Matrix<Scalar> M: input points or vectors

Options:

Bool rows_are_points: true if M are points instead of vectors; default true

Bool centered: true if output should be centered; default true

Returns:
Polytope<Scalar>
Example:

The following produces a parallelogram with the origin as its vertex barycenter:

 > $M = new Matrix([[1,1,0],[1,1,1]]); >$p = zonotope($M); > print$p->VERTICES;
1 0 -1/2
1 0 1/2
1 -1 -1/2
1 1 1/2
Example:

The following produces a parallelogram with the origin being a vertex (not centered case):

 > $M = new Matrix([[1,1,0],[1,1,1]]); >$p = zonotope($M,centered=>0); > print$p->VERTICES;
1 1 0
1 0 0
1 1 1
1 2 1

zonotope_vertices_fukuda(Matrix M)

Create the vertices of a zonotope from a matrix whose rows are input points or vectors.

Parameters:

Matrix M

Options:

Bool centered_zonotope: default 1

Returns:
Matrix
Example:

The following stores the vertices of a parallelogram with the origin as its vertex barycenter and prints them:

 > $M = new Matrix([[1,1,0],[1,1,1]]); > print zonotope_vertices_fukuda($M);
1 0 -1/2
1 0 1/2
1 -1 -1/2
1 1 1/2

### Producing a vector configuration

A way of constructing vector configurations is to modify an already existing vector configuration.

free_sum(VectorConfiguration P1, VectorConfiguration P2)

Construct the free sum of two vector configurations.

Parameters:

VectorConfiguration P1

VectorConfiguration P2

Options:

Bool force_centered: if the input polytopes must be centered. Defaults to true.

Bool no_coordinates: produces a pure combinatorial description. Defaults to false.

Returns:
VectorConfiguration

project_full<Scalar>(VectorConfiguration P)

Orthogonally project a vector configuration to a coordinate subspace such that redundant columns are omitted, i.e., the projection becomes full-dimensional without changing the combinatorial type.

Type Parameters:

Scalar: coordinate type

Parameters:

VectorConfiguration P

Options:

Bool no_labels: Do not copy VERTEX_LABELS to the projection. default: 0

Returns:
VectorConfiguration

project_out<Scalar>(VectorConfiguration V, Matrix B)

Project a vector configuration V along the subspace with the given basis B. The result is still expressed in the original ambient basis. If V is a PointConfiguration and the first column of B is zero, the result is a PointConfiguration, else a VectorConfiguration.

Type Parameters:

Scalar: coordinate type

Parameters:

VectorConfiguration V

Matrix B: a matrix whose rows contain the basis of the space to be projected out

Returns:
VectorConfiguration
project_out<Scalar>(Cone C, Matrix B)

Project a Cone C along the subspace with the given basis B The result is still expressed in the original ambient basis. If V is a Polytope and the first column of B is zero, the result is a Polytope, else a Cone.

Type Parameters:

Scalar: coordinate type

Parameters:

Cone C

Matrix B: a matrix whose rows contain the basis of the space to be projected out

Returns:
Cone

project_to<Scalar>(VectorConfiguration V, Matrix B)

Project a vector configuration V to the subspace with a given basis B and express the result in that basis. A boolean flag make_affine (by default undef) determines whether the resulting coordinates acquire an extra leading '1'. The return type is a VectorConfiguration, unless (i) P is a PointConfiguration, (ii) the first column of B is zero, (iii) make_affine is not 0, in which case it is a PointConfiguration. The return type depends on the input: (1) If V is a VectorConfiguration, the result is also a VectorConfiguration. (2a) If V is a PointConfiguration and all rows in B start with a 0, the result is a PointConfiguration. If, furthermore, make_affine is undef, it is set to 1. (2b) If V is a PointConfiguration and some row of B has a non-zero first entry, the result is a VectorConfiguration. The reasoning here is that B having a zero first column or not influences the hyperplane at infinity.

Type Parameters:

Scalar: coordinate type

Parameters:

VectorConfiguration V

Matrix B: a matrix whose rows contain the basis of the image space

Options:

Bool make_affine: . If undef (default), apply the above reasoning. If 1 (0), unconditionally (don't) add leading 1's.

Returns:
VectorConfiguration
project_to<Scalar>(Cone C, Matrix B)

Project a Polytope or Cone to the subspace with a given basis, and express the result in that basis A boolean flag make_affine (by default undef) determines whether the resulting coordinates acquire an extra leading '1'. The return type is a Cone, unless (i) P is a Polytope, (ii) the first column of B is zero, (iii) make_affine is not 0, in which case it is a Polytope. If make_affine is undef and (ii) is true, make_affine is set to 1. The reasoning here is that B having a zero first column or not influences the hyperplane at infinity.

Type Parameters:

Scalar: coordinate type

Parameters:

Cone C

Matrix B: a matrix whose rows contain the basis of the image space

Returns:
Cone

projection<Scalar>(VectorConfiguration P, Array<Int> indices)

Orthogonally project a vector configuration to a coordinate subspace. The subspace the VectorConfiguration P is projected on is given by indices in the set indices. The option revert inverts the coordinate list.

Type Parameters:

Scalar: coordinate type

Parameters:

VectorConfiguration P

Array<Int> indices

Options:

Bool revert: inverts the coordinate list

Returns:
VectorConfiguration

projection_preimage<Scalar>(Array<VectorConfiguration> P_Array)

Construct a new vector configuration that projects to a given array of vector configurations If the n vector configurations are d_1, d_2, …, d_n-dimensional and all have m vectors, the resulting vector configuration is (d_1+…+d_n)-dimensional, has m vectors, and the projection to the i-th d_i coordinates gives the i-th input vector configuration.

Type Parameters:

Scalar: coordinate type

Parameters:

Array<VectorConfiguration> P_Array

Returns:
VectorConfiguration

### Producing other objects

Functions producing big objects which are not contained in application polytope.

coxeter_group(String type)

Produces the Coxeter group of type type. The Dynkin diagrams of the different types can be found in the description of the clients simple_roots_type_*.

Parameters:

String type: the type of the Coxeter group

Returns:
Group

crosscut_complex(Polytope p)

Produce the crosscut complex of the boundary of a polytope.

Parameters:

Polytope p

Options:

Bool geometric_realization: create a GeometricSimplicialComplex; default is true

Returns:
SimplicialComplex

### Producing regular polytopes and their generalizations

This includes the Platonic solids and their generalizations into two directions. In dimension 3 there are the Archimedean, Catalan and Johnson solids. In higher dimensions there are the simplices, the cubes, the cross polytopes and three other regular 4-polytopes.

archimedean_solid(String s)

Create Archimedean solid of the given name. Some polytopes are realized with floating point numbers and thus not exact; Vertex-facet-incidences are correct in all cases.

Parameters:

String s: the name of the desired Archimedean solid

Returns:
Polytope
Example:

To show the mirror image of the snub cube use:

 > scale(archimedean_solid('snub_cube'),-1)->VISUAL;

catalan_solid(String s)

Create Catalan solid of the given name. Some polytopes are realized with floating point numbers and thus not exact; Vertex-facet-incidences are correct in all cases.

Parameters:

String s: the name of the desired Catalan solid

Returns:
Polytope

cross<Scalar>(Int d, Scalar scale)

Produce a d-dimensional cross polytope. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1. All coordinates are +/- scale or 0.

Type Parameters:

Scalar: Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.

Parameters:

Int d: the dimension

Scalar scale: the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.

Options:

Bool group: add a symmetry group description to the resulting polytope

Bool character_table: add the character table to the symmetry group description, if 0<d<7; default 1

Returns:
Polytope<Scalar>
Example:

To create the 3-dimensional cross polytope, type

 > $p = cross(3); Check out it's vertices and volume:  > print$p->VERTICES;
1 1 0 0
1 -1 0 0
1 0 1 0
1 0 -1 0
1 0 0 1
1 0 0 -1
 > print cross(3)->VOLUME;
4/3

If you rather had a bigger one, type

 > $p_scaled = cross(3,2); > print$p_scaled->VOLUME;
32/3

To also calculate the symmetry group, do this:

 > $p = cross(3,group=>1); You can then print the generators of this group like this:  > print$p->GROUP->RAYS_ACTION->GENERATORS;
1 0 2 3 4 5
2 3 0 1 4 5
0 1 4 5 2 3

cube<Scalar>(Int d, Scalar x_up, Scalar x_low)

Produce a d-dimensional cube. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1. The bounding hyperplanes are xix_up and xi >= x_low.

Type Parameters:

Scalar: Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.

Parameters:

Int d: the dimension

Scalar x_up: upper bound in each dimension

Scalar x_low: lower bound in each dimension

Options:

Bool group: add a symmetry group description to the resulting polytope

Bool character_table: add the character table to the symmetry group description, if 0<d<7; default 1

Returns:
Polytope<Scalar>
Example:

This yields a +/-1 cube of dimension 3 and stores it in the variable $c.  >$c = cube(3);
Example:

This stores a standard unit cube of dimension 3 in the variable $c.  >$c = cube(3,0);
Example:

This prints the area of a square with side length 4 translated to have its vertex barycenter at [5,5]:

 > print cube(2,7,3)->VOLUME;
16

cuboctahedron()

Create cuboctahedron. An Archimedean solid.

Returns:
Polytope

dodecahedron()

Create exact regular dodecahedron in Q(sqrt{5}). A Platonic solid.

Returns:
Polytope

icosahedron()

Create exact regular icosahedron in Q(sqrt{5}). A Platonic solid.

Returns:
Polytope

icosidodecahedron()

Create exact icosidodecahedron in Q(sqrt{5}). An Archimedean solid.

Returns:
Polytope

johnson_solid(Int n)

Create Johnson solid number n, where 1 ⇐ n ⇐ 92. A Johnson solid is a 3-polytope all of whose facets are regular polygons. Some are realized with floating point numbers and thus not exact; yet VERTICES_IN_FACETS is correct in all cases.

Parameters:

Int n: the index of the desired Johnson polytope

Returns:
Polytope
johnson_solid(String s)

Create Johnson solid with the given name. A Johnson solid is a 3-polytope all of whose facets are regular polygons. Some are realized with floating point numbers and thus not exact; yet VERTICES_IN_FACETS is correct in all cases.

Parameters:

String s: the name of the desired Johnson polytope

Returns:
Polytope

octahedron()

Produce a regular octahedron, which is the same as the 3-dimensional cross polytope.

Returns:
Polytope

platonic_solid(String s)

Create Platonic solid of the given name.

Parameters:

String s: the name of the desired Platonic solid

Returns:
Polytope

reduced(Rational t, Rational x, Rational s, Rational h, Rational r)

Produce a 3-dimensional reduced polytope (for suitably chosen parameters). That is, a polytope of constant width which does not properly contain a subpolytope of the same width. Construction due to Bernardo González Merino, Thomas Jahn, Alexandr Polyanskii and Gerd Wachsmuth, arXiv:1701.08629

Parameters:

Rational t

Rational x

Rational s

Rational h

Rational r

Returns:
Polytope<Rational>
Example:

These values yield a reduced 3-polytope (approximately). The width equals 1.

 > $r = reduced(0.55, 0.6176490959800, 0.1351384931026, 0.0984300252409, 0.3547183586709); regular_120_cell() Create exact regular 120-cell in Q(sqrt{5}). Returns: Polytope regular_24_cell() Create regular 24-cell. Returns: Polytope regular_600_cell() Create exact regular 600-cell in Q(sqrt{5}). Returns: Polytope regular_simplex(Int d) Produce a regular d-simplex embedded in R^d with edge length sqrt(2). Parameters: Int d: the dimension Options: Bool group Returns: Polytope Example: To print the vertices (in homogeneous coordinates) of the regular 2-simplex, i.e. an equilateral triangle, type this:  > print regular_simplex(2)->VERTICES; 1 1 0 1 0 1 1 1/2-1/2r3 1/2-1/2r3 The polytopes cordinate type is QuadraticExtension<Rational>, thus numbers that can be represented as a + b*sqrt© with Rational numbers a, b and c. The last row vectors entries thus represent the number$ 1/2 * ( 1 - sqrt(3) ) $. Example: To store a regular 3-simplex in the variable$s and also calculate its symmetry group, type this:

 > $s = regular_simplex(3, group=>1); You can then print the groups generators like so:  > print$s->GROUP->RAYS_ACTION->GENERATORS;
1 0 2 3
3 0 1 2

rhombicosidodecahedron()

Create exact rhombicosidodecahedron in Q(sqrt{5}). An Archimedean solid.

Returns:
Polytope

rhombicuboctahedron()

Create rhombicuboctahedron. An Archimedean solid.

Returns:
Polytope

root_system(String type)

Produce the root systems of the Coxeter arrangement of a given type The roots lie at infinity to facilitate reflecting in them.

Parameters:

String type: the type of the Coxeter arrangement, for example A4 or E8

Returns:
VectorConfiguration

simple_roots_type_A(Int index)

Produce the simple roots of the Coxeter arrangement of type A Indices are taken w.r.t. the Dynkin diagram 0 —- 1 —- … —- n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.

Parameters:

Int index: of the arrangement (3, 4, etc)

Returns:
SparseMatrix

simple_roots_type_B(Int index)

Produce the simple roots of the Coxeter arrangement of type B Indices are taken w.r.t. the Dynkin diagram 0 —- 1 —- … —- n-2 –(4)–> n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.

Parameters:

Int index: of the arrangement (3, 4, etc)

Returns:
SparseMatrix

simple_roots_type_C(Int index)

Produce the simple roots of the Coxeter arrangement of type C Indices are taken w.r.t. the Dynkin diagram 0 —- 1 —- … —- n-2 ←-(4)– n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.

Parameters:

Int index: of the arrangement (3, 4, etc)

Returns:
SparseMatrix

simple_roots_type_D(Int index)

Produce the simple roots of the Coxeter arrangement of type D Indices are taken w.r.t. the Dynkin diagram n-2 / 0 - 1 - … - n-3 # n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.

Parameters:

Int index: of the arrangement (3, 4, etc)

Returns:
SparseMatrix

simple_roots_type_E6()

Produce the simple roots of the Coxeter arrangement of type E6 Indices are taken w.r.t. the Dynkin diagram 3 | | 0 —- 1 —- 2 —- 4 —- 5 Note that the roots lie at infinity to facilitate reflecting in them.

Returns:
SparseMatrix

simple_roots_type_E7()

Produce the simple roots of the Coxeter arrangement of type E7 Indices are taken w.r.t. the Dynkin diagram 4 | | 0 —- 1 —- 2 —- 3 —- 5 —- 6 Note that the roots lie at infinity to facilitate reflecting in them.

Returns:
SparseMatrix

simple_roots_type_E8()

Produce the simple roots of the Coxeter arrangement of type E8 Indices are taken w.r.t. the Dynkin diagram 5 | | 0 —- 1 —- 2 —- 3 —- 4 —- 6 —- 7 Note that the roots lie at infinity to facilitate reflecting in them.

Returns:
SparseMatrix

simple_roots_type_F4()

Produce the simple roots of the Coxeter arrangement of type F4 Indices are taken w.r.t. the Dynkin diagram 0 —- 1 –(4)–> 2 —- 3

Returns:
SparseMatrix

simple_roots_type_G2()

Produce the simple roots of the Coxeter arrangement of type G2 Indices are taken w.r.t. the Dynkin diagram 0 ←-(6)– 1

Returns:
SparseMatrix

simple_roots_type_H3()

Produce the simple roots of the Coxeter arrangement of type H3 Indices are taken w.r.t. the Dynkin diagram 0 –(5)– 1 —- 2 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length 2

Returns:
SparseMatrix

simple_roots_type_H4()

Produce the simple roots of the Coxeter arrangement of type H4 Indices are taken w.r.t. the Dynkin diagram 0 –(5)– 1 —- 2 —- 3 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}

Returns:
SparseMatrix

tetrahedron()

Create regular tetrahedron. A Platonic solid.

Returns:
Polytope

truncated_cube()

Create truncated cube. An Archimedean solid.

Returns:
Polytope

truncated_cuboctahedron()

Create truncated cuboctahedron. An Archimedean solid. This is actually a misnomer. The actual truncation of a cuboctahedron is normally equivalent to this construction, but has two different edge lengths. This construction has regular 2-faces.

Returns:
Polytope

truncated_dodecahedron()

Create exact truncated dodecahedron in Q(sqrt{5}). An Archimedean solid.

Returns:
Polytope

truncated_icosahedron()

Create exact truncated icosahedron in Q(sqrt{5}). An Archimedean solid. Also known as the soccer ball.

Returns:
Polytope

truncated_icosidodecahedron()

Create exact truncated icosidodecahedron in Q(sqrt{5}). An Archimedean solid.

Returns:
Polytope

truncated_octahedron()

Create truncated octahedron. An Archimedean solid. Also known as the 3-permutahedron.

Returns:
Polytope

wythoff(String type, Set rings)

Produce the orbit polytope of a point under a Coxeter arrangement with exact coordinates, possibly in a qudratic extension field of the rationals

Parameters:

String type: single letter followed by rank representing the type of the arrangement

Set rings: indices of the hyperplanes corresponding to simple roots of the arrangement that the initial point should NOT lie on. You may specify just an integer or a perl array ref like [0,1] or [0..2].

Options:

Bool lattice: Should the vertices of the orbit polytope be chosen to lie on the corresponding root lattice? default 0, which means that the vertices will instead be chosen to lie as symmetrically as possible.

Returns:
Polytope

### Quotient spaces

Topologic cell complexes defined as quotients over polytopes modulo a discrete group.

cs_quotient(Polytope P)

For a centrally symmetric polytope, divide out the central symmetry, i.e, identify diametrically opposite faces.

Parameters:

Polytope P: , centrally symmetric

Example:

 > $P = cube(3); > cs_quotient($P);
> print $P->CS_PERMUTATION; 7 6 5 4 3 2 1 0 The zeroth vertex gets identified with the seventh, the first with the sixth etc. cylinder_2() Return a 2-dimensional cylinder obtained by identifying two opposite sides of a square. Returns: Polytope Example: To obtain a topological space homeomorphic to a cylinder, type  >$p = cylinder_2();
> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS; 2 3 0 1  > print$p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS;
{0 2}
{1 3}

Thus, vertices 0,2 and vertices 1,3 are identified.

 > print $p->QUOTIENT_SPACE->FACES; {{0} {1}} {{0 1} {0 2} {1 3}} {{0 1 2 3}} Thus, after identification two vertices, three edges, and one two-dimensional face remain:  > print$p->QUOTIENT_SPACE->F_VECTOR;
2 3 1

davis_manifold()

Return the 4-dimensional hyperbolic manifold obtained by Michael Davis

Returns:
Polytope
Example:

The Davis manifold is the centrally symmetric quotient of the regular 210-cell:

 > $d = davis_manifold(); > print$d->F_VECTOR;
600 1200 720 120
 > print $d->QUOTIENT_SPACE->F_VECTOR; 300 600 360 60 1 quarter_turn_manifold() Return the 3-dimensional Euclidean manifold obtained by identifying opposite faces of a 3-dimensional cube by a quarter turn. After identification, two classes of vertices remain. Returns: Polytope Example: To obtain a topological space homeomorphic to the quarter turn manifold, type  >$p = quarter_turn_manifold();
> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS; 5 7 4 6 2 0 3 1 6 2 1 5 7 3 0 4 To see which vertices are identified, type  > print$p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS;
{0 3 5 6}
{1 2 4 7}

Thus, two classes of vertices remain, with 0 and 1 being representatives. To see the faces remaining after identification, type

 > print $p->QUOTIENT_SPACE->FACES; {{0} {1}} {{0 1} {0 2} {0 4} {0 7}} {{0 1 2 3} {0 1 4 5} {0 1 6 7}} {{0 1 2 3 4 5 6 7}}  > print$p->QUOTIENT_SPACE->F_VECTOR;
2 4 3 1

write_quotient_space_simplexity_ilp

outputs a linear program whose optimal value is a lower bound for the number of simplices necessary to triangulate the polytope in such a way that its symmetries respect the triangulation of the boundary.

### Symmetry

These functions capture information of the object that is concerned with the action of permutation groups.

cocircuit_equations_support_reps(Matrix<Scalar> points, Array<Array<Int>> gens, Array<SetType> rirs, Array<SetType> rmis)

write the indices of the representatives of the support of the cocircuit equations to a file

Parameters:

Matrix<Scalar> points

Array<Array<Int>> gens: the generators of the action of the symmetry group

Array<SetType> rirs: representatives of interior ridge simplices

Array<SetType> rmis: representatives of maximal interior simplices

Options:

String filename: where large output should go to. 'filename⇒“-”' writes to stdout.

Returns:
Int

combinatorial_symmetries(Polytope p)

Compute the combinatorial symmetries (i.e., automorphisms of the face lattice) of a given polytope p. They are stored in terms of a GROUP.VERTICES_ACTION and a GROUP.FACETS_ACTION property in p, and the GROUP.VERTICES_ACTION is also returned.

Parameters:

Polytope p

Returns:
PermutationAction
Example:

To get the vertex symmetry group of the square and print its generators, type the following:

 > print combinatorial_symmetries(cube(2))->GENERATORS;
2 3 0 1
1 0 2 3
 > $p = cube(2); combinatorial_symmetries($p);
> print $p->GROUP->VERTICES_ACTION->GENERATORS; 0 2 1 3 1 0 3 2  > print$p->GROUP->FACETS_ACTION->GENERATORS;
2 3 0 1
1 0 2 3

combinatorial_symmetrized_cocircuit_equations(Cone P, Set<Int> comps)

calculate a sparse representation of the cocircuit equations corresponding to a direct sum of isotypic components

Parameters:

Cone P

Set<Int> comps: the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge.

combinatorial_symmetrized_cocircuit_equations(Cone P, Array<SetType> rirs, Array<SetType> rmis, Set<Int> comps)

calculate the projection of the cocircuit equations to a direct sum of isotypic components and represent it combinatorially

Parameters:

Cone P

Array<SetType> rirs: representatives of interior ridge simplices

Array<SetType> rmis: representatives of maximal interior simplices

Set<Int> comps: the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge.

Options:

String filename: where large output should go to. 'filename⇒“-”' writes to stdout.

Returns:
Array<Pair<SetType,HashMap<SetType,Rational>>>

isotypic_configuration(Polytope P, Int i)

Given a polytope that has a matrix group acting on it, return the projections of the vertices to the i-th isotypic component C_i. If the input is a group with a permutation action a, regard a as acting on the unit basis vectors of the ambient space and return the projection of the unit basis vectors to the i-th isotypic component.

Parameters:

Polytope P: a polytope with a matrix action, or a group::Group g with a permutation action

Int i: the index of the desired isotypic component

Returns:
PointConfiguration<Float>
Example:

Consider the symmetry group of the cyclic polytope c(4,10) in the Carathéodory realization.

 > $p = cyclic_caratheodory(4,10,group=>1); For i=4, we obtain a 10-gon:  > print isotypic_configuration($p,4)->POINTS;
1 1 0
1 0.8090169944 0.5877852523
1 0.3090169944 0.9510565163
1 -0.3090169944 0.9510565163
1 -0.8090169944 0.5877852523
1 -1 0
1 -0.8090169944 -0.5877852523
1 -0.3090169944 -0.9510565163
1 0.3090169944 -0.9510565163
1 0.8090169944 -0.5877852523

Similarly, for i=5 we get two copies of a pentagon.

lattice_automorphisms_smooth_polytope(Polytope P)

Returns a generating set for the lattice automorphism group of a smooth polytope P by comparing lattice distances between vertices and facets.

Parameters:

Polytope P: the given polytope

Returns:
Array<Array<Int>>
Example:

 > print lattice_automorphisms_smooth_polytope(cube(2));
2 3 0 1
1 0 3 2
0 2 1 3

linear_symmetries(Matrix M)

Compute the linear symmetries of the rows of a rational matrix M. This is an implementation of the algorithm described in the paper “Computing symmetry groups of polyhedra” LMS J. Comput. Math. 17 (1) (2004) by By David Bremner, Mathieu Dutour Sikiri'{c}, Dmitrii V. Pasechnik, Thomas Rehn and Achill Sch“{u}rmann.

Parameters:

Matrix M

Returns:
Array<Array<Int>>
Example:

 > $ls = linear_symmetries(cube(2)->VERTICES); > print$ls->PERMUTATION_ACTION->GENERATORS;
0 2 1 3
1 0 3 2
 > print linear_symmetries(cube(3)->VERTICES)->PERMUTATION_ACTION->GENERATORS;
0 1 4 5 2 3 6 7
0 2 1 3 4 6 5 7
1 0 3 2 5 4 7 6
linear_symmetries(Cone C)

CREDIT sympol\n\n Use sympol to compute the linear symmetries of

1. the RAYS|VERTICES, FACETS, or POINTS of a rational cone or polytope C (whatever is available, in this order), or
2. the VECTORS|POINTS of a rational vector or point configuration P.

The action of the symmetry group is stored inside the parent object. In the case of cones, sympol might compute only a subset of the linear symmetry group. Sympol, and therefore this function, can only handle rational objects.

Parameters:

Cone C: | VectorConfiguration P

Returns:
Group
from extension:
Example:
 > print linear_symmetries(cube(3))->FACETS_ACTION->GENERATORS;
1 0 2 3 4 5
0 1 3 2 4 5
2 3 0 1 4 5
0 1 2 3 5 4
0 1 4 5 2 3

nestedOPGraph(Vector gen_point, Matrix points, Matrix lattice_points, Group group, Bool verbose)

Constructs the NOP-graph of an orbit polytope. It is used by the rule for the NOP_GRAPH.

Parameters:

Vector gen_point: the generating point

Matrix points: the vertices of the orbit polytope

Matrix lattice_points: the lattice points of the orbit polytope

Group group: the generating group

Bool verbose: print out additional information

Returns:
ARRAY

orbit_polytope(Vector input_point, PermutationAction a)

Constructs the orbit polytope of a given point input_point with respect to a given group action a.

Parameters:

Vector input_point: the basis point of the orbit polytope

PermutationAction a: the action of a permutation group on the coordinates of the ambient space

Returns:
Polytope
Example:

The orbit polytope of a set of points A in affine d-space is the convex hull of the images of A under the action of a group G on the affine space. polymake implements several variations of this concept. The most basic one is the convex hull of the orbit of a single point under a set of coordinate permutations. For example, consider the cyclic group C_6 that acts on 6-dimensional space by cyclically permuting the coordinates. This action is represented in polymake by group::cyclic_group(6)→PERMUTATION_ACTION. To compute the convex hull of cyclic shifts of the vector v = [1,6,0,5,-5,0,-5] in homogeneous coordinates, type

 > $p = orbit_polytope(new Vector([1,6,0,5,-5,0,-5]), group::cyclic_group(6)->PERMUTATION_ACTION); After this assignment, the orbit polytope is still in implicit form, and the only properties that are defined reside in GROUP→COORDINATE_ACTION:  > print$p->GROUP->COORDINATE_ACTION->properties();
type: PermutationAction<Int, Rational> as Polytope<Rational>::GROUP::COORDINATE_ACTION

GENERATORS
1 2 3 4 5 0

INPUT_RAYS_GENERATORS
1 6 0 5 -5 0 -5

To calculate the vertices of the orbit polytope explicitly, say

 > print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5 orbit_polytope(Matrix input_points, PermutationAction a) Constructs the orbit polytope of a given set of points input_points with respect to a given group action a. Parameters: Matrix input_points: the basis points of the orbit polytope PermutationAction a: the action of a permutation group on the coordinates of the ambient space Returns: Polytope Example: To find the orbit of more than one point under a PermutationAction on the coordinates, say  >$p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), new group::PermutationAction(GENERATORS=>[ [1,2,3,4,5,0] ]));
> print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5 1 1 2 3 4 5 6 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 1 2 3 1 5 6 1 2 3 4 1 6 1 2 3 4 5 orbit_polytope(Vector input_point, Group g) Constructs the orbit polytope of a given point input_point with respect to a given group action a. Parameters: Vector input_point: the basis point of the orbit polytope Group g: a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient space Returns: Polytope Example: As a convenience function, you can also directly specify a group::Group that contains a PERMUTATION_ACTION:  >$p = orbit_polytope(new Vector([1,6,0,5,-5,0,-5]), group::cyclic_group(6));

Up to now, the orbit polytope is still in implicit form. To calculate the vertices explicitly, say

 > print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5 orbit_polytope(Matrix input_points, Group g) Constructs the orbit polytope of a given set of points input_points with respect to a given group action a. Parameters: Matrix input_points: the basis points of the orbit polytope Group g: a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient space Returns: Polytope Example: As a convenience function, you can also directly specify a group::Group that contains a PERMUTATION_ACTION:  >$p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), group::cyclic_group(6));
> print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5 1 1 2 3 4 5 6 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 1 2 3 1 5 6 1 2 3 4 1 6 1 2 3 4 5 orbit_polytope(Matrix input_points, Array<Array<Int>> gens) Constructs the orbit polytope of a given set of points input_points with respect to a given set of generators gens. Parameters: Matrix input_points: the basis point of the orbit polytope Array<Array<Int>> gens: the generators of a permutation group that acts on the coordinates of the ambient space Returns: Polytope Example: This is a variation where several points are given as the row of a matrix, and the permutation action on coordinates is given by explicitly listing the generators. In this example, the matrix has just one row, and there is just one generator.  > print orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5] ]), [ [1,2,3,4,5,0] ])->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5 orbit_polytope<Scalar>(Vector input_point, MatrixActionOnVectors a) Constructs the orbit polytope of a given point input_point with respect to a given matrix group action a. Type Parameters: Scalar: S the underlying number type Parameters: Vector input_point: the generating point of the orbit polytope MatrixActionOnVectors a: the action of a matrix group on the coordinates of the ambient space Returns: Polytope Example: polymake also supports orbit polytopes under the action of a group by matrices. To find the orbit of a point in the plane under the symmetry group of the square, say  >$p = orbit_polytope(new Vector([1,2,1]), cube(2, group=>1)->GROUP->MATRIX_ACTION);
> print $p->VERTICES; 1 -2 -1 1 -2 1 1 -1 -2 1 -1 2 1 1 -2 1 1 2 1 2 -1 1 2 1 orbit_polytope<Scalar>(Matrix<Scalar> input_points, MatrixActionOnVectors<Scalar> a) Constructs the orbit polytope of a given set of points input_points with respect to a given matrix group action a. Type Parameters: Scalar: S the underlying number type Parameters: Matrix<Scalar> input_points: the generating points of the orbit polytope MatrixActionOnVectors<Scalar> a: the action of a matrix group on the coordinates of the ambient space Returns: Polytope Example: To find the orbit of more than one point in the plane under the symmetry group of the square, say  >$p = orbit_polytope(new Matrix([ [1,2,1], [1,5/2,0] ]), cube(2, group=>1)->GROUP->MATRIX_ACTION);
> print $p->VERTICES; 1 -2 -1 1 -2 1 1 -1 -2 1 -1 2 1 1 -2 1 1 2 1 2 -1 1 2 1 1 -5/2 0 1 0 -5/2 1 0 5/2 1 5/2 0 ortho_project(Polytope p) Projects a symmetric polytope in R4 cap H1,k to R3. (See also the polymake extension 'tropmat' by S. Horn.) Parameters: Polytope p: the symmetric polytope to be projected Returns: Polytope projective_symmetries(Cone C) Find the group of projective automorphisms of a Cone C. This is a group of all permutations on the rays of the cone (not necessarily there representatives), such that there is a invertible matrix A with A*Ray = Ray_sigma for all rays of the cone. This is an implementation of the algorithm described in the paper “Computing symmetry groups of polyhedra” LMS J. Comput. Math. 17 (1) (2004) by By David Bremner, Mathieu Dutour Sikiri'{c}, Dmitrii V. Pasechnik, Thomas Rehn and Achill Sch”{u}rmann. Parameters: Cone C Returns: Array<Array<Int>> Example:  >$C = cube(2);
> print projective_symmetries($C); 0 1 2 3 0 2 1 3 1 0 3 2 1 3 0 2 2 0 3 1 2 3 0 1 3 1 2 0 3 2 1 0 representation_conversion_up_to_symmetry(Cone c) Computes the dual description of a polytope up to its linear symmetry group. Parameters: Cone c: the cone (or polytope) whose dual description is to be computed, equipped with a GROUP Options: Bool v_to_h: 1 (default) if converting V to H, false if converting H to V String method: specifies sympol's method of ray computation via 'lrs' (default), 'cdd', 'beneath_beyond', 'ppl' Returns: Pair from extension: symmetrized_cocircuit_equations<Scalar>(Cone P, Set<Int> comps) calculate the projection of the cocircuit equations to a direct sum of isotypic components Type Parameters: Scalar: the underlying data type Parameters: Cone P: or PointConfiguration Set<Int> comps: the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge. Options: Bool reduce_rows: Should we return only linearly independent equations? default: 1 truncated_orbit_polytope(Polytope P, Scalar eps) Gives an implicit representation of the all-vertex truncation of an orbit polytope P, in which all vertices are cut off by hyperplanes at distance eps. The input polytope P must have a GROUP.COORDINATE_ACTION. The output is a polytope with a GROUP.COORDINATE_ACTION equipped with INEQUALITIES_GENERATORS. Parameters: Polytope P: the input polytope Scalar eps: scaled distance by which the vertices of the orbit polytope are to be cut off Returns: Polytope ### Transformations These functions take a realized polytope and produce a new one by applying a suitable affine or projective transformation in order to obtain some special coordinate description but preserve the combinatorial type. For example, before you can polarize an arbitrary polyhedron, it must be transformed to a combinatorially equivalent bounded polytope with the origin as a relatively interior point. It is achieved with the sequence orthantify - bound - center - polarize. ambient_lattice_normalization(Polytope p) Transform to a full-dimensional polytope while preserving the ambient lattice Z^n Parameters: Polytope p: the input polytope, Options: Bool store_transform: store the reverse transformation as an attachement Returns: Polytope Example: Consider a line segment embedded in 2-space containing three lattice points:  >$p = new Polytope(VERTICES=>[[1,0,0],[1,2,2]]);
> print ambient_lattice_normalization($p)->VERTICES; 1 0 1 2 The ambient lattice of the projection equals the intersection of the affine hull of$p with Z^2.

Example:

Another line segment containing only two lattice points:

 > $p = new Polytope(VERTICES=>[[1,0,0],[1,1,2]]); >$P = ambient_lattice_normalization($p,store_transform=>1); > print$P->VERTICES;
1 0
1 1

To get the transformation, do the following:

 > $M =$P->get_attachment('REVERSE_LATTICE_PROJECTION');
> print $M; 1 0 0 0 1 2  > print$P->VERTICES * $M; 1 0 0 1 1 2 bound(Polytope P) Make a positive polyhedron bounded. Apply a projective linear transformation to a polyhedron mapping the far hyperplane to the hyperplane spanned by the unit vectors. The origin (1,0,…,0) is fixed. The input polyhedron should be POSITIVE; i.e. no negative coordinates. Parameters: Polytope P: a positive polyhedron Returns: Polytope Example: Observe the transformation of a simple unbounded 2-polyhedron:  >$P = new Polytope(VERTICES=>[[1,0,0],[0,1,1],[0,0,1]]);
> print bound($P)->VERTICES; 1 0 0 1 1/2 1/2 1 0 1 As you can see, the far points are mapped to the hyperplane spanned by (1,1,0) and (1,0,1). center(Polytope P) Make a polyhedron centered. Apply a linear transformation to a polyhedron P such that a relatively interior point (preferably the vertex barycenter) is moved to the origin (1,0,…,0). Parameters: Polytope P Returns: Polytope Example: Consider this triangle not containing the origin:  >$P = new Polytope(VERTICES => [[1,1,1],[1,2,1],[1,1,2]]);
> $origin = new Vector([1,0,0]); > print$P->contains_in_interior($origin); false To create a translate that contains the origin, do this:  >$PC = center($P); > print$PC->contains_in_interior($origin); true This is what happened to the vertices:  > print$PC->VERTICES;
1 -1/3 -1/3
1 2/3 -1/3
1 -1/3 2/3

There also exists a property to check whether a polytope is centered:

 > print $PC->CENTERED; true orthantify(Polytope P, Int v) Make a polyhedron POSITIVE. Apply an affine transformation to a polyhedron such that the vertex v is mapped to the origin (1,0,…,0) and as many facets through this vertex as possible are mapped to the bounding facets of the first orthant. Parameters: Polytope P Int v: vertex to be moved to the origin. By default it is the first affine vertex of the polyhedron. Returns: Polytope Example: To orthantify the square, moving its first vertex to the origin, do this:  >$p = orthantify(cube(2),1);
> print $p->VERTICES; 1 2 0 1 0 0 1 2 2 1 0 2 orthonormal_col_basis(Matrix M) Return an orthonormal column basis of the input matrix. Parameters: Matrix M: the input matrix Returns: Matrix<Float> orthonormal_row_basis(Matrix M) Return an orthonormal row basis of the input matrix. Parameters: Matrix M: the input matrix Returns: Matrix<Float> polarize(Cone C) This method takes either a polytope (1.) or a cone (2.) as input. 1. Given a bounded, centered, not necessarily full-dimensional polytope P, produce its polar with respect to the standard Euclidean scalar product. 2. Given a cone C produce its dual with respect to the standard Euclidean scalar product, i.e. all the vectors that evaluate positively on C. Note that the definition of the polar has changed after version 2.10: the polar is reflected in the origin to conform with cone polarization If P is not full-dimensional, the output will contain lineality orthogonal to the affine span of P. In particular, polarize() of a pointed polytope will always produce a full-dimensional polytope. If you want to compute the polar inside the affine hull you may use the pointed_part client afterwards. Parameters: Cone C Options: Bool no_coordinates: only combinatorial information is handled Returns: Cone Example: To save the polar of the square in the variable$p and then print its vertices, do this:

 > $p = polarize(cube(2)); > print$p->VERTICES;
1 1 0
1 -1 0
1 0 1
1 0 -1
Example:

To dualize the cone over a hexagon and print its rays, do this:

 > $c = new Cone(INPUT_RAYS=>[[1,0,0],[1,1,0],[1,2,1],[1,2,2],[1,1,2],[1,0,1]]); >$cd = polarize($c); > print$cd->RAYS;
1 -1 1
0 0 1
0 1 0
1 1 -1
1 0 -1/2
1 -1/2 0

porta_dual

Dual transformation via porta. Computes vertices and lineality space from inequalities and equations.

porta_primal

Primal transformation via porta. Computes facets and affine hull from vertices or points.

revert(Polytope P)

Apply a reverse transformation to a given polyhedron P. All transformation clients keep track of the polytope's history. They write or update the attachment REVERSE_TRANSFORMATION. Applying revert to the transformed polytope reconstructs the original polytope.

Parameters:

Polytope P: a (transformed) polytope

Returns:
Polytope
Example:

The following translates the square and then reverts the transformation:

 > $v = new Vector(1,2); >$p = translate(cube(2),$v); > print$p->VERTICES;
1 0 1
1 2 1
1 0 3
1 2 3
 > $q = revert($p);
> print $q->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1 scale(Polytope P, Scalar factor, Bool store) Scale a polyhedron P by a given scaling parameter factor. Parameters: Polytope P: the polyhedron to be scaled Scalar factor: the scaling factor Bool store: stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1. Returns: Polytope Example: To scale the square by 23, do this:  >$p = scale(cube(2),23);
> print $p->VERTICES; 1 -23 -23 1 23 -23 1 -23 23 1 23 23 The transformation matrix is stored in an attachment:  > print$p->get_attachment('REVERSE_TRANSFORMATION');
1 0 0
0 1/23 0
0 0 1/23

To reverse the transformation, you can use the revert function.

 > $q = revert($p);
> print $q->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1 transform(Polytope P, Matrix trans, Bool store) Transform a polyhedron P according to the linear transformation trans. Parameters: Polytope P: the polyhedron to be transformed Matrix trans: the transformation matrix Bool store: stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1. Returns: Polytope Example: This translates the square by (23,23) and stores the transformation:  >$M = new Matrix([1,23,23],[0,1,0],[0,0,1]);
> $p = transform(cube(2),$M,1);
> print $p->VERTICES; 1 22 22 1 24 22 1 22 24 1 24 24 To retrieve the attached transformation, use this:  > print$p->get_attachment('REVERSE_TRANSFORMATION');
1 -23 -23
0 1 0
0 0 1

Check out the revert function to learn how to undo the transformation. It might be more comfortable to use the translate function to achieve the same result.

translate(Polytope P, Vector trans, Bool store)

Translate a polyhedron P by a given translation vector trans.

Parameters:

Polytope P: the polyhedron to be translated

Vector trans: the translation vector

Bool store: stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.

Returns:
Polytope
Example:

This translates the square by (23,23) and stores the transformation:

 > $t = new Vector(23,23); >$p = translate(cube(2),$t); > print$p->VERTICES;
1 22 22
1 24 22
1 22 24
1 24 24

To retrieve the attached transformation, use this:

 > print $p->get_attachment('REVERSE_TRANSFORMATION'); 1 -23 -23 0 1 0 0 0 1 Check out the revert function to learn how to undo the transformation. vertex_lattice_normalization(Polytope p) Transform to a full-dimensional polytope while preserving the lattice spanned by vertices induced lattice of new vertices = Z^dim Parameters: Polytope p: the input polytope, Options: Bool store_transform: store the reverse transformation as an attachement Returns: Polytope ### Triangulations, subdivisions and volume These functions collect information about triangulations and other subdivisions of the object and properties usually computed from such, as the volume. barycentric_subdivision(Cone c) Create a simplicial complex as a barycentric subdivision of a given cone or polytope. Each vertex in the new complex corresponds to a face in the old complex. Parameters: Cone c: input cone or polytope Options: Bool no_labels: Do not generate VERTEX_LABELS from the faces of the original cone. default: 0 Bool geometric_realization: create a GeometricSimplicialComplex; default is true Returns: SimplicialComplex chirotope(Matrix M) Compute the chirotope of a point configuration given as the rows of a matrix. Parameters: Matrix M: The rows are the points Returns: String coherency_index(Polytope p1, Polytope p2, Matrix points, Vector w1, Vector w2) DOC_FIXME: Incomprehensible description! Computes the coherency index of w1 w.r.t. w2 Parameters: Polytope p1 Polytope p2 Matrix points Vector w1 Vector w2 from extension: coherency_index(Matrix points, Vector w1, Vector w2) DOC_FIXME: Incomprehensible description! Computes the coherency index of w1 w.r.t. w2 Parameters: Matrix points Vector w1 Vector w2 from extension: coherency_index(Polytope p1, Polytope p2) DOC_FIXME: Erroneous description! w1 is not a parameter here! Computes the coherency index of p1 w.r.t. p2 Parameters: Polytope p1 Polytope p2 from extension: common_refinement(Matrix points, IncidenceMatrix sub1, IncidenceMatrix sub2, Int dim) Computes the common refinement of two subdivisions of points. It is assumed that there exists a common refinement of the two subdivisions. Parameters: Matrix points IncidenceMatrix sub1: first subdivision IncidenceMatrix sub2: second subdivision Int dim: dimension of the point configuration Returns: IncidenceMatrix Example: A simple 2-dimensional set of points:  >$points = new Matrix<Rational>([[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,2,1]]);

Two different subdivisions…

 > $sub1 = new IncidenceMatrix([[0,1,2],[1,2,3,4]]); >$sub2 = new IncidenceMatrix([[1,3,4],[0,1,2,3]]);

…and their common refinement:

 > print common_refinement($points,$sub1,$sub2,2); {0 1 2} {1 3 4} {1 2 3} common_refinement(Polytope p1, Polytope p2) Computes the common refinement of two subdivisions of the same polytope p1, p2. It is assumed that there exists a common refinement of the two subdivisions. It is not checked if p1 and p2 are indeed the same! Parameters: Polytope p1 Polytope p2 Returns: Polytope delaunay_triangulation(VoronoiPolyhedron V) Compute the Delaunay triangulation of the given SITES of a VoronoiPolyhedron V. If the sites are not in general position, the non-triangular facets of the Delaunay subdivision are triangulated (by applying the beneath-beyond algorithm). Parameters: VoronoiPolyhedron V Returns: Array<Set<Int>> Example:  >$VD = new VoronoiPolyhedron(SITES=>[[1,1,1],[1,0,1],[1,-1,1],[1,1,-1],[1,0,-1],[1,-1,-1]]);
> $D = delaunay_triangulation($VD);
> print $D; {0 1 3} {1 3 4} {1 2 4} {2 4 5} fiber_polytope(PointConfiguration pc, PointConfiguration pc) Computes the fiber polytope of a projection of point configurations P→Q via the GKZ secondary configuration. Parameters: PointConfiguration pc: (or Polytope) source point configuration or polytope PointConfiguration pc: target point configuration Returns: PointConfiguration fiber_polytope(PointConfiguration pc, Polytope pc) Computes the fiber polytope of a projection of point configurations P→Q via the GKZ secondary configuration. Parameters: PointConfiguration pc: (or Polytope) source point configuration or polytope Polytope pc: target polytope Returns: PointConfiguration fiber_polytope(PointConfiguration P, Matrix pi) Computes the fiber polytope of a projection of point configurations P -pi→ Q via the GKZ secondary configuration. Parameters: PointConfiguration P: (or Polytope) source point configuration or polytope Matrix pi: the projection acting on P Returns: PointConfiguration foldable_max_signature_ilp(Int d, Matrix points, Rational volume, SparseMatrix cocircuit_equations) Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold Parameters: Int d: the dimension of the input polytope, point configuration or quotient manifold Matrix points: the input points or vertices Rational volume: the volume of the convex hull SparseMatrix cocircuit_equations: the matrix of cocircuit equations Returns: LinearProgram<Rational> foldable_max_signature_upper_bound(Int d, Matrix points, Rational volume, SparseMatrix cocircuit_equations) Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold Parameters: Int d: the dimension of the input polytope, point configuration or quotient manifold Matrix points: the input points or vertices Rational volume: the volume of the convex hull SparseMatrix cocircuit_equations: the matrix of cocircuit equations Returns: Integer interior_and_boundary_ridges(Polytope P) Find the (d-1)-dimensional simplices in the interior and in the boundary of a d-dimensional polytope or cone Parameters: Polytope P: the input polytope or cone Returns: Pair<Array<Set>,Array<Set>> Example:  > print interior_and_boundary_ridges(cube(2)); <{0 3} {1 2} > <{0 1} {0 2} {1 3} {2 3} > is_regular(Matrix points, Array<Set<Int>> subdiv) For a given subdivision subdiv of points tests if the subdivision is regular and if yes computes a weight vector inducing this subdivsion. The output is a pair of Bool and the weight vector. Options can be used to ensure properties of the resulting vector. The default is having 0 on all vertices of the first face of subdiv. Parameters: Matrix points: in homogeneous coordinates Array<Set<Int>> subdiv Options: Matrix<Scalar> equations: system of linear equation the cone is cut with. Set<Int> lift_to_zero: gives only lifting functions lifting the designated vertices to 0 Int lift_face_to_zero: gives only lifting functions lifting all vertices of the designated face to 0 Returns: Pair<Bool,Vector> Example: A regular subdivision of the square, with the first cell lifted to zero:  >$points = cube(2)->VERTICES;
> print is_regular($points,[[0,1,3],[1,2,3]],lift_to_zero=>[0,1,3]); 1 <0 0 1 0> is_subdivision(Matrix points, Array<Set<Int>> faces) Parameters: Matrix points Array<Set<Int>> faces Options: Set<Int> interior_points Example: Two potential subdivisions of the square without inner points:  >$points = cube(2)->VERTICES;
> print is_subdivision($points,[[0,1,3],[1,2,3]],interior_points=>[ ]); true  > print is_subdivision($points,[[0,1,2],[1,2]],interior_points=>[ ]);
false
Example:

Three points in RR^1

 > $points = new Matrix([[1,0],[1,1],[1,2]]); > print is_subdivision($points, [[0,2]]);
true
 > print is_subdivision($points, [[0,1]]); false iterated_barycentric_subdivision(Cone c, Int n) Create a simplicial complex as an iterated barycentric subdivision of a given cone or polytope. Parameters: Cone c: input cone or polytope Int n: how many times to subdivide Options: Bool no_labels: Do not generate VERTEX_LABELS from the faces of the original cone. default: 0 Bool geometric_realization: create a GeometricSimplicialComplex; default is false Returns: SimplicialComplex max_interior_simplices(Polytope P) Find the maximal interior simplices of a polytope P. Symmetries of P are NOT taken into account. Parameters: Polytope P: the input polytope Returns: Array<Set> Example:  > print max_interior_simplices(cube(2)); {0 1 2} {0 1 3} {0 2 3} {1 2 3} max_interior_simplices(PointConfiguration P) find the maximal interior simplices of a point configuration Symmetries of the configuration are NOT taken into account. Parameters: PointConfiguration P: the input point configuration Returns: Array<Set> Example: To calculate the maximal interior simplices of a point configuration, type  >$p=new PointConfiguration(POINTS=>[[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,1/2,1/2]]);
> print max_interior_simplices($p); {0 1 2} {0 1 3} {0 1 4} {0 2 3} {0 2 4} {1 2 3} {1 3 4} {2 3 4} mixed_volume(Polytope<Scalar> P1, Polytope<Scalar> P2, Polytope<Scalar> Pn) Produces the normalized mixed volume of polytopes P1,P2,…,Pn. It does so by producing a (pseudo-)random lift function. If by bad luck the function is not generic, an error message might be displayed. Parameters: Polytope<Scalar> P1: first polytope Polytope<Scalar> P2: second polytope Polytope<Scalar> Pn: last polytope Returns: Scalar Example:  > print mixed_volume(cube(2),simplex(2)); 4 n_fine_triangulations(Matrix M, Bool optimization) Calculates the number of fine triangulations of a planar point configuration. This can be space intensive. Victor Alvarez, Raimund Seidel: A Simple Aggregative Algorithm for Counting Triangulations of Planar Point Sets and Related Problems. In Proc. of the 29th Symposium on Computational Geometry (SoCG '13), pages 1-8, Rio de Janeiro, Brazil, 2013 Parameters: Matrix M: in the plane (homogeneous coordinates) Bool optimization: defaults to 1, where 1 includes optimization and 0 excludes it Returns: Integer Example: To print the number of possible fine triangulations of a square, do this:  > print n_fine_triangulations(cube(2)->VERTICES); 2 placing_triangulation(Matrix Points) Compute the placing triangulation of the given point set using the beneath-beyond algorithm. Parameters: Matrix Points: the given point set Options: Bool non_redundant: whether it's already known that Points are non-redundant Array<Int> permutation: placing order of Points, must be a valid permutation of (0..Points.rows()-1) Returns: Array<Set<Int>> Example: To compute the placing triangulation of the square (of whose vertices we know that they're non-redundant), do this:  >$t = placing_triangulation(cube(2)->VERTICES, non_redundant=>1);
> print $t; {0 1 2} {1 2 3} points2metric(Matrix points) Define a metric by restricting the Euclidean distance function to a given set of points. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-norm is used instead (with exact computation). Parameters: Matrix points Options: Bool max: triggers the usage of the max-norm (exact computation) Bool l1: triggers the usage of the l1-norm (exact computation) Returns: Matrix Example:  > print points2metric(cube(2)->VERTICES, max=>1); 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 poly2metric(Polytope P) Define a metric by restricting the Euclidean distance function to the vertex set of a given polytope P. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-norm is used instead (with exact computation). Parameters: Polytope P Options: Bool max: triggers the usage of the max-norm (exact computation) Returns: Matrix Example:  > print poly2metric(cube(2), max=>1); 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 positive_circuits(Polytope or, Set<Int> S) returns all sets of points that form a circuit with the given list of points Parameters: Polytope or: PointConfiguration P Set<Int> S: subset of point indices Returns: Set<Set<Int>> quotient_space_simplexity_ilp(Int d, Matrix V, Scalar volume, SparseMatrix cocircuit_equations) Set up an LP whose MINIMAL_VALUE is a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold Parameters: Int d: the dimension of the input polytope, point configuration or quotient manifold Matrix V: the input points or vertices Scalar volume: the volume of the convex hull SparseMatrix cocircuit_equations: the matrix of cocircuit equations Options: String filename: a name for a file in .lp format to store the linear program Returns: LinearProgram quotient_space_simplexity_lower_bound(Int d, Matrix V, Scalar volume, SparseMatrix cocircuit_equations) Calculate a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold Parameters: Int d: the dimension of the input polytope, point configuration or quotient manifold Matrix V: the input points or vertices Scalar volume: the volume of the convex hull SparseMatrix cocircuit_equations: the matrix of cocircuit equations Returns: Integer regular_subdivision(Matrix points, Vector weights) Compute a regular subdivision of the polytope obtained by lifting points to weights and taking the lower complex of the resulting polytope. If the weight is generic the output is a triangulation. Parameters: Matrix points Vector weights Returns: Array<Set<Int>> Example: The following generates a regular subdivision of the square.  >$w = new Vector(2,23,2,2);
> $r = regular_subdivision(cube(2)->VERTICES,$w);
> print $r; {0 2 3} {0 1 3} regularity_lp(Matrix points, Array<Set<Int>> subdiv) For a given subdivision subdiv of points determines a LinearProgram to decide whether the subdivision is regular. The output a Polytope with an attached LP. Options can be used to ensure properties of the resulting LP. The default is having 0 on all vertices of the first face of subdiv. Parameters: Matrix points: in homogeneous coordinates Array<Set<Int>> subdiv Options: Matrix<Scalar> equations: system of linear equation the cone is cut with. Set<Int> lift_to_zero: gives only lifting functions lifting the designated vertices to 0 Int lift_face_to_zero: gives only lifting functions lifting all vertices of the designated face to 0 Scalar epsilon: minimum distance from all inequalities Returns: Polytope<Scalar> secondary_configuration(PointConfiguration pc) Computes the point configuration of GKZ vectors of a point configuration via its chirotope using topcom or mptopcom. Parameters: PointConfiguration pc: input point configuration Returns: PointConfiguration Example: The following PointConfiguration is called the “mother of all examples (moae)”. It has two non-regular triangulations, which can be seen when comparing the number of points of the output configuration with the number of vertices of the convex hull of the output configuration.  >$moae = new PointConfiguration(POINTS=>[[1,4,0,0],[1,0,4,0],[1,0,0,4],[1,2,1,1],[1,1,2,1],[1,1,1,2]]);
> $moae = project_full($moae);
> $SC_moae = secondary_configuration($moae);
> print $SC_moae -> N_POINTS; 18  > print$SC_moae -> CONVEX_HULL -> N_VERTICES;
16
secondary_configuration(Polytope pc)

Computes the point configuration of GKZ vectors of a point configuration via its chirotope using topcom or mptopcom.

Parameters:

Polytope pc: input polytope

Returns:
PointConfiguration
Example:

The square only has two triangulations using its vertices.

 > $square = cube(2,1,0); >$SC_square = secondary_configuration($square); > print$SC_square -> POINTS;
1 1 2 2 1
1 2 1 1 2

secondary_polytope(PointConfiguration pc)

Computes the GKZ secondary polytope of a point configuration via its using topcom or mptopcom.

Parameters:

PointConfiguration pc: input point configuration

Returns:
Polytope
Example:

The following PointConfiguration is called the “mother of all examples (moae)”. It has two non-regular triangulations, which can be seen when comparing the number of points in the secondary configuration with the number of vertices of the secondary polytope.

 > $moae = new PointConfiguration(POINTS => [[1,4,0,0],[1,0,4,0],[1,0,0,4],[1,2,1,1],[1,1,2,1],[1,1,1,2]]); >$moae = project_full($moae); >$SC_moae = secondary_configuration($moae); >$SP_moae = secondary_polytope($moae); > print$SC_moae -> N_POINTS;
18
 > print $SP_moae -> N_VERTICES; 16 secondary_polytope(Polytope pc) Computes the GKZ secondary polytope of a point configuration via its using topcom or mptopcom. Parameters: Polytope pc: input polytope Returns: Polytope Example: The square only has two triangulations using its vertices.  >$square = cube(2,1,0);
> $SP_square = secondary_polytope($square);
> print $SP_square -> VERTICES; 1 1 2 2 1 1 2 1 1 2 simplexity_ilp(Int d, Matrix points, Array<Set> MIS, Scalar volume, SparseMatrix cocircuit_equations) Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold Parameters: Int d: the dimension of the input polytope, point configuration or quotient manifold Matrix points: the input points or vertices Array<Set> MIS: the representatives of maximal interior simplices Scalar volume: the volume of the convex hull SparseMatrix cocircuit_equations: the matrix of cocircuit equations Returns: LinearProgram simplexity_ilp_with_angles(Int d, Matrix V, Matrix F, IncidenceMatrix VIF, IncidenceMatrix VIR, Array<Array<Int>> gens, Array<Set> MIS, Scalar volume, SparseMatrix cocircuit_equations) Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold Parameters: Int d: the dimension of the input polytope, point configuration or quotient manifold Matrix V: the input points or vertices Matrix F: the facets of the input polytope IncidenceMatrix VIF: the vertices-in-facets incidence matrix IncidenceMatrix VIR: the vertices-in-ridges incidence matrix Array<Array<Int>> gens: the generators of the symmetry group Array<Set> MIS: the (representative) maximal interior simplices Scalar volume: the volume of the convex hull SparseMatrix cocircuit_equations: the matrix of cocircuit equations Returns: LinearProgram simplexity_lower_bound(Int d, Matrix points, Scalar volume, SparseMatrix cocircuit_equations) Calculate the LP relaxation lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold Parameters: Int d: the dimension of the input polytope, point configuration or quotient manifold Matrix points: the input points or vertices Scalar volume: the volume of the convex hull SparseMatrix cocircuit_equations: the matrix of cocircuit equations Returns: Integer split_compatibility_graph(Matrix splits, Polytope P) DOC_FIXME: Incomprehensible description! Computes the compatibility graph among the splits of a polytope P. Parameters: Matrix splits: the splits given by split equations Polytope P: the input polytope Returns: Graph split_polyhedron(Polytope P) Computes the split polyhedron of a full-dimensional polyhdron P. Parameters: Polytope P Returns: Polytope splits(Matrix V, Graph G, Matrix F, Int dimension) Computes the SPLITS of a polytope. The splits are normalized by dividing by the first non-zero entry. If the polytope is not fulldimensional the first entries are set to zero unless coords are specified. Parameters: Matrix V: vertices of the polytope Graph G: graph of the polytope Matrix F: facets of the polytope Int dimension: of the polytope Options: Set<Int> coords: entries that should be set to zero Returns: Matrix splits_in_subdivision(Matrix vertices, Array<Set<Int>> subdivision, Matrix splits) Tests which of the splits of a polyhedron are coarsenings of the given subdivision. Parameters: Matrix vertices: the vertices of the polyhedron Array<Set<Int>> subdivision: a subdivision of the polyhedron Matrix splits: the splits of the polyhedron Returns: Set<Int> staircase_weight(Int k, Int l) Gives a weight vector for the staircase triangulation of the product of a k-1- and an l-1-dimensional simplex. Parameters: Int k: the number of vertices of the first simplex Int l: the number of vertices of the second simplex Returns: Vector<Rational> Example: The following creates the staircase triangulation of the product of the 2- and the 1-simplex.  >$w = staircase_weight(3,2);
> $p = product(simplex(2),simplex(1)); >$p->POLYTOPAL_SUBDIVISION(WEIGHTS=>$w); > print$p->POLYTOPAL_SUBDIVISION->MAXIMAL_CELLS;
{0 2 4 5}
{0 2 3 5}
{0 1 3 5}

symmetrized_foldable_max_signature_ilp(Int d, Matrix points, Rational volume, Array<Array<Int>> generators, SparseMatrix symmetrized_foldable_cocircuit_equations)

Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold

Parameters:

Int d: the dimension of the input polytope, point configuration or quotient manifold

Matrix points: the input points or vertices

Rational volume: the volume of the convex hull

Array<Array<Int>> generators: the generators of the symmetry group

SparseMatrix symmetrized_foldable_cocircuit_equations: the matrix of symmetrized cocircuit equations

Returns:
LinearProgram<Rational>

symmetrized_foldable_max_signature_upper_bound(Int d, Matrix points, Rational volume, SparseMatrix cocircuit_equations)

Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold

Parameters:

Int d: the dimension of the input polytope, point configuration or quotient manifold

Matrix points: the input points or vertices

Rational volume: the volume of the convex hull

SparseMatrix cocircuit_equations: the matrix of cocircuit equations

Returns:
Integer

topcom_all_triangulations(PointConfiguration pc)

Computes all triangulations of a point configuration via its chirotope.

Parameters:

PointConfiguration pc: input point configuration

Returns:
Array<Array<Set<Int>>>

topcom_fine_and_connected_triangulations(PointConfiguration pc)

Computes all fine triangulations of a point configuration that are connected by bistellar flips to a fine seed triangulation. The triangulations are computed via the chirotope. If the input point configuration or polytope has a symmetry group, only fine triangulations up to symmetry will be computed.

Parameters:

PointConfiguration pc: or Polytope p input point configuration or polytope

Returns:
Array<Array<Set<Int>>>

topcom_input_format(Cone P)

This converts a polytope, cone or point configuration into a format that topcom understands

Parameters:

Cone P: (or PointConfiguration)

Returns:
String
Example:

To convert a 2-cube without symmetries into topcom format, type

 > print topcom_input_format(cube(2));
[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]
[]

If you also want the symmetry group, you can type

 > print topcom_input_format(cube(2,group=>1));
[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]
[[1,0,3,2],[0,2,1,3]]

topcom_regular_and_connected_triangulations(PointConfiguration pc)

Computes all triangulations of a point configuration that are connected by bistellar flips to the regular triangulations. The triangulations are computed via the chirotope. If the input point configuration or polytope has a symmetry group, only triangulations up to symmetry will be computed.

Parameters:

PointConfiguration pc: or Polytope p input point configuration or polytope

Returns:
Array<Array<Set<Int>>>

topcom_regular_triangulations(PointConfiguration pc)

Computes all regular triangulations of a point configuration.

Parameters:

PointConfiguration pc: or Polytope p input point configuration or polytope

Returns:
Array<Array<Set<Int>>>

universal_polytope<Scalar>(PointConfiguration<Scalar> PC)

Calculate the universal polytope of a point configuration A. It is a 0/1 polytope with one vertex for every triangulation of A. Each coordinate of the ambient space corresponds to a simplex in the configuration.

Type Parameters:

Scalar: the underlying number type

Parameters:

PointConfiguration<Scalar> PC: the point configuration

Returns:
Polytope
Example:

To calculate the universal polytope of a point configuration, type

 > $p=new PointConfiguration(POINTS=>[[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,1/2,1/2]]); > print universal_polytope($p)->VERTICES;
1 0 1 0 1 0 0 0 0
1 1 0 0 0 0 1 0 0
1 0 0 1 0 1 0 1 1

Notice how the first vertex corresponds to the triangulation using all points, and the other ones to the triangulations that don't use the inner point.

universal_polytope(Polytope P)

Calculate the universal polytope U(P) of an input polytope P. If P has n vertices and dimension d, then U(P) is a 0/1-polytope in dimension binomial(n,d+1) whose vertices correspond to the full triangulations of P. Each coordinate of a particular vertex v indicates the presence or absence of a particular simplex in the triangulation corresponding to v, and the order of the simplices (and hence the interpretation of each coordinate of v) is the one given by the property MAX_INTERIOR_SIMPLICES. Because the number of triangulations of P is typically very large, the polytope U(P) is not constructed by enumerating triangulations, but instead in the inequality description afforded by the cocircuit equations, a volume equality, and non-negativity constraints for the coordinates.

Parameters:

Polytope P: the input polytope

Returns:
Polytope
Example:

Since the 2-dimensional cube (i.e., the square) has just two triangulations, its universal polytope is a segment embedded in dimension binomial(4,3) = 4. The cocircuit equations read as follows:

 > print universal_polytope(cube(2))->EQUATIONS;
-8 4 4 4 4
(5) (2 -1) (3 1)
(5) (1 -1) (4 1)
universal_polytope(Polytope P, Array<Set> reps, SparseMatrix cocircuit_equations)

Calculate the universal polytope of a polytope, point configuration or quotient manifold

Parameters:

Polytope P: the input polytope

Array<Set> reps: the representatives of maximal interior simplices

SparseMatrix cocircuit_equations: the matrix of cocircuit equations

Returns:
Polytope

### Visualization

These functions are for visualization.

bounding_box_facets(Matrix V)

Produces boundary facets describing a box shaped polytope that contains all bounded vertices in V.

Parameters:

Matrix V: vertices that should be in the box

Options:

Scalar offset: the minimum offset between a bounding box facet and its nearest bounded vertex

Scalar surplus_k: size of the bounding box relative to the box spanned by V (added to offset)

Bool fulldim: keeps the bounding box full dimensional even if the bounded vertices do not span the whole space and offset is zero. Useful for visualizations of Voronoi diagrams that do not have enough vertices. Default value is 0.

Bool make_cube

Returns:
Matrix

bounding_facets(Matrix H, Matrix V)

A function that turns a giving H-description into one that can be used as bounding facets for a given set of vertices.

Parameters:

Matrix H: H-description of some bounded polytope P

Matrix V: vertices of which the bounded ones will be contained in P

Options:

Scalar offset: the minimum euclidean distance between a hyperplane and a bounded vertex. Default is 0

Scalar surplus_k: factor multiplied with $max(<f,v> | v in V) - min(<f,v> | v in V)$ to describe the minimum offset relative to the extents of V in f direction (added to offset)

Bool transform: instead of simply shifting the facets. For P simplicial/(and simple?) this should produce the same as the LP and can be turned off. Default is true

Bool fulldim: keep P full dimensional. Default is false

Bool return_nonredundant: (shifted) hyperplanes only. If transform is true there will be no check. Regardless of this variable. Default is true

Returns:
Matrix

vlabels(Matrix vertices, Bool wo_zero)

Creates vertex labels for visualization from the vertices of the polytope. The parameter wo_zero decides whether the entry at position 0 (homogenizing coordinate) is omitted (1) or included (0) in the label string.“

Parameters:

Matrix vertices: the vertices of the polytope

Bool wo_zero: includes (0) or omits (1) the entry at position 0

Returns:
ARRAY
Example:

This prints the vertex labels for the square with the origin as its center and side length 2, where we omit the leading 1:

 > $l = vlabels(cube(2)->VERTICES,1); > print join(', ', @{$l});
(-1,-1), (1,-1), (-1,1), (1,1)

### Other

Special purpose functions.

edge_orientable(Polytope P)

Checks whether a 2-cubical polytope P is edge-orientable (in the sense of Hetyei), that means that there exits an orientation of the edges such that for each 2-face the opposite edges point in the same direction. It produces the certificates EDGE_ORIENTATION if the polytope is edge-orientable, or MOEBIUS_STRIP_EDGES otherwise. In the latter case, the output can be checked with the client validate_moebius_strip.

Parameters:

Polytope P: the given 2-cubical polytope

face_pair(Cone P, Set S)

For a given set S of rays compute the smallest face F of a cone P containing them all; see also face.

Parameters:

Cone P

Set S

Returns:
Pair<Set,Set>
Example:

computes the dimension of the face of the 3-cube which is spanned by the vertices 0 and 1

 > $c=cube(3); > print rank($c->VERTICES->minor(face_pair($c,[0,1])->first(),All))-1; 1 lawrence_matrix(Matrix M) Parameters: Matrix M: Create the Lawrence matrix$ Lambda(M) \$ corresponding to M. If M has n rows and d columns, then Lambda(M) equals ( M I_n ) ( 0_{n,d} I_n ).

Returns:
Matrix

m_sequence(Vector<Int> h)

Test if the given vector is an M-sequence.

Parameters:

Vector<Int> h

Returns:
Bool
Example:

The h-vector of a simplicial or simple polytope is an M-sequence.

 > print m_sequence(cyclic(7,23)->H_VECTOR);
true

matroid_indices_of_hypersimplex_vertices()

For a given matroid return the bases as a subset of the vertices of the hypersimplex

Options:

Matroid m: the matroid

Returns:
Set<Int>

pseudopower(Integer l, Int i)

Compute the i-th pseudopower of l, commonly denoted l^<i>. See “A Proof of the Sufficiency of McMullen’s Conditions of Simplicial Convex Polytopes” by Louis Billera and Carl Lee, DOI: 10.1016/0097-3165(81)90058-3, for the definition.

Parameters:

Integer l

Int i

Returns:
Integer

wronski_center_ideal(Matrix<Int> L, Vector<Int> lambda)

Returns a system of polynomials which is necessary to check if degeneration avoids center of projection: compute eliminant e(s); this must not have a zero in (0,1)

Parameters:

Matrix<Int> L: lattice points

Vector<Int> lambda: height function on lattice points

wronski_polynomial(Matrix<Int> M, Vector<Int> lambda, Array<Rational> coeff, Rational s)

Returns a Wronski polynomial of a FOLDABLE triangulation of a lattice polytope

Parameters:

Matrix<Int> M: points (in homogeneous coordinates); affinely span the space

Vector<Int> lambda: height function on lattice points

Array<Rational> coeff: coefficients

Rational s: additional Parameter in the polynomial

Options:

SimplicialComplex triangulation: The triangulation of the pointset corresponding to the lifting function

wronski_system(Matrix<Int> M, Vector<Int> lambda, Array<Array<Rational>> coeff_array, Rational s)

Returns a Wronski system of a FOLDABLE triangulation of a lattice polytope

Parameters:

Matrix<Int> M: points (in homogeneous coordinates); affinely span the space

Vector<Int> lambda: height function on lattice points

Array<Array<Rational>> coeff_array: coefficients

Rational s: additional Parameter in the polynomial

Options:

SimplicialComplex triangulation`: The triangulation of the pointset corresponding to the lifting function

• documentation/latest/polytope.txt