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:

• application common
• application graph

uses:

• application group
• application ideal
• application topaz

• 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.
** ''[[.:polytope:QuotientSpace |QuotientSpace]]'':\\  A topological quotient space obtained from a ''[[.:polytope:Polytope |Polytope]]'' by identifying faces. This object will sit inside the polytope.
** ''[[.:polytope:SchlegelDiagram |SchlegelDiagram]]'':\\  A Schlegel diagram of a polytope.
** ''[[.:polytope:SlackIdeal |SlackIdeal]]'':\\ UNDOCUMENTED
** ''[[.:polytope:SymmetrizedCocircuitEquations |SymmetrizedCocircuitEquations]]'':\\ 
** ''[[.:polytope:VectorConfiguration |VectorConfiguration]]'':\\  An object of type VectorConfiguration deals with properties of row vectors, assembled into an n x d matrix called ''[[.:polytope:VectorConfiguration#VECTORS |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.
** ''[[.:polytope:Visual_Cone |Visual::Cone]]'':\\  Visualization of a Cone as a graph (if 1d), or as a solid object (if 2d or 3d)
** ''[[.:polytope:Visual_Gale |Visual::Gale]]'':\\  A gale diagram prepared for drawing.
** ''[[.:polytope:Visual_PointConfiguration |Visual::PointConfiguration]]'':\\  Visualization of the point configuration.
** ''[[.:polytope:Visual_Polytope |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).
** ''[[.:polytope:Visual_PolytopeGraph |Visual::PolytopeGraph]]'':\\  Visualization of the graph of a polyhedron.
** ''[[.:polytope:Visual_PolytopeLattice |Visual::PolytopeLattice]]'':\\  Visualization of the ''[[.:polytope:Polytope#HASSE_DIAGRAM |HASSE_DIAGRAM]]'' of a polyhedron as a multi-layer graph..
** ''[[.:polytope:Visual_SchlegelDiagram |Visual::SchlegelDiagram]]'':\\  Visualization of the Schlegel diagram of a polytope.
** ''[[.:polytope:VoronoiPolyhedron |VoronoiPolyhedron]]'':\\  For a finite set of ''[[.:polytope:VoronoiPolyhedron#SITES |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 [[]].

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

---

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:Polytope |Polytope]]'' ''P1'': the first polytope
  :: ''[[.:polytope: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:
  :: <code perl> > $t = simplex(2);

> $tr = simplex(2,-1); </code>

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,cube(3),verbose => 1);
 Cones/Polytopes do no live in the same ambient space.
 false

 > 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:

 > print included_polyhedra(cube(2),cube(3),verbose=>1);
 Cones/Polytopes do no live in the same ambient space.
 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

---

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>

---

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

---

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>

---

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

---

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

---

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:

bundled:flint

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:

bundled:libnormaliz

---

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}}

---

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

---

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

---

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 R^d.

Parameters:

GeometricSimplicialComplex c

Int facet_index: index of the facet to be lifted

Rational conv_eps: some epsilon > 0

Returns:

Polytope

from extension:

bundled:local

---

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 c^tx , 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>

---

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

---

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}.

---

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

---

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

---

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 R³.

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.

---

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

---

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 P₁×e₁, …, P_k×e_k where e₁, …,e_k are the standard unit vectors in R^k. 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 P₁,…,P_k

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

---

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 R^p to R^q, 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 v₁ and h₁ will have the form “v₁*h₁”.

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 v₁ ⊕ v₂ 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 v₁ ⊕ v₂ will have the form LABEL_1*LABEL_2.

Returns:

Polytope

---