documentation:master:polytope

# Differences

This shows you the differences between two versions of the page.

 documentation:master:polytope [2020/05/21 04:42] documentation:master:polytope [2020/06/02 04:40] (current) Line 1: Line 1: + ====== 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 [[:​external_software#​JavaView|JavaView]] or [[:​external_software#​geomview|geomview]]),​ generating PostScript drawings and povray scene files. + + imports from: + * application [[.:​common|common]] + * application [[.:​graph|graph]] + uses: + * application [[.:​group|group]] + * application [[.:​ideal|ideal]] + * application [[.:​topaz|topaz]] + + ===== Objects ===== + ** ''​[[.:​polytope:​AffineLattice |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 + ** ''​[[.:​polytope:​Cone |Cone]]'':​\\ ​ A polyhedral cone, not necessarily pointed. Note that in contrast to the vertices of a polytope, the ''​[[.:​polytope:​Cone#​RAYS |RAYS]]''​ are given in affine coordinates. + ** ''​[[.:​polytope:​GroebnerBasis |GroebnerBasis]]'':​\\ ​ The Groebner basis of the homogeneous toric ideal associated to the polytope, the term order is given in matrix form. + ** ''​[[.:​polytope:​LinearProgram |LinearProgram]]'':​\\ ​ A linear program specified by a linear or abstract objective function + ** ''​[[.:​polytope:​MixedIntegerLinearProgram |MixedIntegerLinearProgram]]'':​\\ ​ A mixed integer linear program specified by a linear or abstract objective function + ** ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]'':​\\ ​ The ''​[[.:​polytope:​PointConfiguration#​POINTS |POINTS]]''​ of an object of type PointConfiguration encode a not necessarily convex finite point set. The difference to a parent ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ is that the points have homogeneous coordinates,​ i.e. they will be normalized to have first coordinate 1 without warning. + ** ''​[[.:​polytope:​Polytope |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 ''​[[.:​polytope:​Polytope#​VERTICES_IN_FACETS |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 ''​[[.:​polytope:​Cone |Cone]]''​. + ** ''​[[.:​polytope:​PropagatedPolytope |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 [[]]. + + ===== Functions ===== + + ==== Combinatorics ==== + ​Combinatorial functions. + ---- + {{anchor:​circuits2matrix:​}} + ?  **''​circuits2matrix([[.:​common#​Set |Set]]<​[[.:​common#​Pair |Pair]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>,​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%%>​ co)''​** + :: Convert ''​[[.:​polytope:​VectorConfiguration#​CIRCUITS |CIRCUITS]]''​ or ''​[[.:​polytope:​VectorConfiguration#​COCIRCUITS |COCIRCUITS]]''​ to a 0/+1/-1 matrix, with one row for each circuit/​cocircuit, ​ and as many columns as there are VECTORs/​POINTS. + ? Parameters: + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Pair |Pair]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>,​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%%>''​ ''​co'':​ /circuits a set of circuits or cocircuits + ? Returns: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]<​[[.:​common#​Rational |Rational]]>''​ + + + ---- + {{anchor:​cocircuit_equation_of_ridge:​}} + ?  **''​cocircuit_equation_of_ridge([[.:​polytope:​Cone |Cone]] C, [[.:​common#​Set |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​C''​ + :: ''​[[.:​common#​Set |Set]]''​ ''​rho'':​ the interior ridge + ? Returns: + :''​[[.:​common#​HashMap |HashMap]]<​[[.:​common#​Set |Set]],​[[.:​common#​Rational |Rational]]>''​ + + + ---- + {{anchor:​cocircuit_equations:​}} + ?  **''​cocircuit_equations([[.:​polytope:​Cone |Cone]] C, [[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]> interior_ridge_simplices,​ [[.:​common#​Array |Array]]<​[[.:​common#​Set |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​C''​ + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​interior_ridge_simplices'':​ interior codimension 1 simplices + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​interior_simplices'':​ interior simplices of maximal dimension + ? Options: + : + :: ''​[[.:​common#​String |String]]''​ ''​filename'':​ where to write the output (default empty) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​reduce_rows'':​ whether to perform row reduction (default 1) + :: ''​[[.:​common#​Int |Int]]''​ ''​log_frequency'':​ how often to print log messages + ? Returns: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]<​[[.:​common#​Int |Int]]>''​ + + + ---- + {{anchor:​codegree:​}} + ?  **''​codegree<​Scalar>​([[.:​polytope:​Cone |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + ? Example: + :: To find the codegree of the 3-cube, type + :: > print codegree(cube(3));​ + 1 + ​ + ?  **''​codegree<​Scalar>​([[.:​polytope:​PointConfiguration |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: + :: ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]''​ ''​P''​ + + + ---- + {{anchor:​contraction:​}} + ?  **''​contraction([[.:​polytope:​VectorConfiguration |VectorConfiguration]] C, [[.:​common#​Int |Int]] v)''​** + :: Contract a vector configuration //C// along a specified vector //v//. + ? Parameters: + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​C''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​v'':​ index of the vector to contract + + + ---- + {{anchor:​degree:​}} + ?  **''​degree<​Scalar>​([[.:​polytope:​PointConfiguration |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: + :: ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]''​ ''​P'':​ (or Cone or Polytope) + ? Example: + :: To find the degree of the 3-cube, type + :: > print degree(cube(3));​ + 3 + ​ + + + ---- + {{anchor:​deletion:​}} + ?  **''​deletion([[.:​polytope:​VectorConfiguration |VectorConfiguration]] C, [[.:​common#​Int |Int]] v)''​** + :: Delete a specified vector //v// from a vector configuration //C//. + ? Parameters: + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​C''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​v'':​ index of the vector to delete + + + ---- + + ==== Comparing ==== + ​Functions based on graph isomorphisms. + ---- + {{anchor:​congruent:​}} + ?  **''​congruent([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |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: + :: > $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 + ​ + + + ---- + {{anchor:​equal_polyhedra:​}} + ? **''​equal_polyhedra([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1'':​ the first polytope + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2'':​ the second polytope + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ Prints information on the difference between P1 and P2 if they are not equal. + ? Returns: + :''​[[.:​common#​Bool |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 + ​ + + + ---- + {{anchor:​find_facet_vertex_permutations:​}} + ? **''​find_facet_vertex_permutations([[.:​polytope:​Cone |Cone]] P1, [[.:​polytope:​Cone |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P1'':​ the first cone/​polytope + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P2'':​ the second cone/​polytope + ? Returns: + :''​[[.:​common#​Pair |Pair]]<​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]>,​[[.:​common#​Array |Array]]<​[[.:​common#​Int |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 + ​ + + + ---- + {{anchor:​included_polyhedra:​}} + ? **''​included_polyhedra([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1'':​ the first polytope + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2'':​ the second polytope + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ Prints information on the difference between P1 and P2 if none is included in the other. + ? Returns: + :''​[[.:​common#​Bool |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 + ​ + + + ---- + {{anchor:​isomorphic:​}} + ? **''​isomorphic([[.:​polytope:​Cone |Cone]] P1, [[.:​polytope:​Cone |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P1'':​ the first cone/​polytope + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P2'':​ the second cone/​polytope + ? Returns: + :''​[[.:​common#​Bool |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 + ​ + + + ---- + {{anchor:​lattice_isomorphic_smooth_polytopes:​}} + ? **''​lattice_isomorphic_smooth_polytopes([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: Tests whether two smooth lattice polytopes are lattice equivalent by comparing lattice distances between vertices and facets. ​ + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1'':​ the first lattice polytope + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2'':​ the second lattice polytope + ? Returns: + :''​[[.:​common#​Bool |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. + ---- + {{anchor:​check_inc:​}} + ? **''​check_inc([[.:​common#​Matrix |Matrix]] points, [[.:​common#​Matrix |Matrix]] hyperplanes,​ [[.:​common#​String |String]] sign, [[.:​common#​Bool |Bool]] verbose)''​** + :: Check coordinate data. For each pair of vectors from two given matrices their inner product must satisfy the given relation. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​points''​ + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​hyperplanes''​ + :: ''​[[.:​common#​String |String]]''​ ''​sign'':​ composed of one or two characters from [-+0], representing the allowed domain of the vector inner products. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print all products violating the required relation + ? Returns: + :''​[[.:​common#​Bool |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. + + + ---- + {{anchor:​check_poly:​}} + ? **''​check_poly([[.:​common#​IncidenceMatrix |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: + :: ''​[[.:​common#​IncidenceMatrix |IncidenceMatrix]]''​ ''​VIF''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​dual'':​ transposes the incidence matrix + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ prints information about the check. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​validate_moebius_strip:​}} + ? **''​validate_moebius_strip([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Validates the output of the client ''​[[.:​polytope#​edge_orientable |edge_orientable]]'',​ in particular it checks whether the [[.:​polytope:​Polytope#​MOEBIUS_STRIP_EDGES |MOEBIUS_STRIP_EDGES]] form a Moebius strip with parallel opposite edges. Prints a message to stdout. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P'':​ the given polytope + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + {{anchor:​validate_moebius_strip_quads:​}} + ? **''​validate_moebius_strip_quads([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Checks whether the [[.:​polytope:​Polytope#​MOEBIUS_STRIP_QUADS |MOEBIUS_STRIP_QUADS]] form a Moebius strip with parallel opposite edges. Prints a message to stdout and returns the [[.:​polytope:​Polytope#​MOEBIUS_STRIP_EDGES |MOEBIUS_STRIP_EDGES]] if the answer is affirmative. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P'':​ the given polytope + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print details + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]<​[[.:​common#​Int |Int]]>''​ + + + ---- + + ==== Coordinate conversions ==== + The following functions allow for the conversion of the coordinate type of cones and polytopes. + ---- + {{anchor:​affine_float_coords:​}} + ? **''​affine_float_coords([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Dehomogenize the [[.:​polytope:​Polytope#​VERTICES |vertex coordinates]] and convert them to Float + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P'':​ source object + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]<​[[.:​common#​Float |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 + ​ + + + ---- + {{anchor:​convert_to:​}} + ? **''​convert_to<​Coord>​([[.:​polytope:​Cone |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​c'':​ the input cone + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]<​Coord>''​ + ? **''​convert_to<​Coord>​([[.:​polytope:​Polytope |Polytope]] P)''​** + :: provide a Polytope object with desired coordinate type + ? Type Parameters: + :: ''​Coord'':​ target coordinate type + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P'':​ source object + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ---- + {{anchor:​tight_span_envelope:​}} + ? **''​tight_span_envelope([[.:​fan:​SubdivisionOfPoints |SubdivisionOfPoints]] sd)''​** + :: Computes the envelope for a given subdivision of points. + ? Parameters: + :: ''​[[.:​fan:​SubdivisionOfPoints |SubdivisionOfPoints]]''​ ''​sd''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​extended'':​ If True, the envelope of the extended tight span is computed. + ? Returns: + :''​[[.:​polytope:​Polytope |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. + ---- + {{anchor:​all_steiner_points:​}} + ? **''​all_steiner_points([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Compute the Steiner points of all faces of a polyhedron //P// using a randomized approximation of the angles. //P// must be ''​[[.:​polytope:​Polytope#​BOUNDED |BOUNDED]]''​. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Options: + : + :: ''​[[.:​common#​Float |Float]]''​ ''​eps'':​ controls the accuracy of the angles computed + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​ ​fixing a seed number guarantees the same outcome. + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]''​ + + + ---- + {{anchor:​center_distance:​}} + ? **''​center_distance([[.:​polytope:​Polytope |Polytope]] p)''​** + :: Compute the mean or median distance of the ''​[[.:​polytope:​Polytope#​VERTICES |VERTICES]]''​ to the ''​[[.:​polytope:​Polytope#​VERTEX_BARYCENTER |VERTEX_BARYCENTER]]''​. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​p''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​median'':​ use median instead of arithmetic mean + ? Returns: + :''​[[.:​common#​Float |Float]]''​ + + + ---- + {{anchor:​circuit_completions:​}} + ? **''​circuit_completions([[.:​common#​Matrix |Matrix]] L, [[.:​common#​Matrix |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: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​L''​ + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​R''​ + ? Options: + : + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​H''​ + ? Returns: + :''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |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} + ​ + + + ---- + {{anchor:​containing_normal_cone:​}} + ?  **''​containing_normal_cone([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Vector |Vector]] q)''​** + :: Return the vertices of the face of P whose normal cone contains a point //q//. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​q''​ + ? Returns: + :''​[[.:​common#​Set |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} + ​ + + + ---- + {{anchor:​containing_outer_cone:​}} + ?  **''​containing_outer_cone([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Vector |Vector]] q)''​** + :: Return the vertices of the face of P whose outer cone contains a point //q//. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​q''​ + ? Returns: + :''​[[.:​common#​Set |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} + ​ + + + ---- + {{anchor:​dihedral_angle:​}} + ?  **''​dihedral_angle([[.:​common#​Vector |Vector]]<​Scalar>​ H1, [[.:​common#​Vector |Vector]]<​Scalar>​ H2)''​** + :: Compute the dihedral angle between two (oriented) affine or linear hyperplanes. + ? Parameters: + :: ''​[[.:​common#​Vector |Vector]]<​Scalar>''​ ''​H1'':​ : first hyperplane + :: ''​[[.:​common#​Vector |Vector]]<​Scalar>''​ ''​H2'':​ : second hyperplane + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​deg'':​ output in degrees rather than radians, default is false + :: ''​[[.:​common#​Bool |Bool]]''​ ''​cone'':​ hyperplanes seen as linear hyperplanes,​ default is false + ? Returns: + :''​[[.:​common#​Float |Float]]''​ + ? Example: + :: > $H1 = new Vector(1,​5,​5);​ + >$H2 = new Vector(1,​-5,​5);​ + > print dihedral_angle($H1,​$H2,​deg=>​1);​ + 90 + ​ + + + ---- + {{anchor:​induced_lattice_basis:​}} + ?  **''​induced_lattice_basis([[.:​polytope:​Polytope |Polytope]] p)''​** + :: Returns a basis of the affine lattice spanned by the vertices + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​p'':​ the input polytope + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]<​[[.:​common#​Integer |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 + ​ + + + ---- + {{anchor:​integer_points_bbox:​}} + ?  **''​integer_points_bbox([[.:​polytope:​Polytope |Polytope]]<​Scalar>​ P)''​** + :: Enumerate all integer points in the given polytope by searching a bounding box. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]<​Scalar>''​ ''​P''​ + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]<​[[.:​common#​Integer |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 + ​ + + + ---- + {{anchor:​minimal_vertex_angle:​}} + ?  **''​minimal_vertex_angle([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Computes the minimal angle between two vertices of the input polytope //P//. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​common#​Float |Float]]''​ + ? Example: + :: > print minimal_vertex_angle(simplex(3));​ + ​3.14159265358979 + ​ + + + ---- + {{anchor:​normaliz_compute:​}} + ?  **''​normaliz_compute([[.:​polytope:​Cone |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 ''​[[.:​polytope:​Cone#​HOMOGENEOUS |HOMOGENEOUS]]''​ or a ''​[[.:​polytope:​Cone#​MONOID_GRADING |MONOID_GRADING]]''​ is set + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​C''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​from_facets'':​ supply facets instead of rays to normaliz + :: ''​[[.:​common#​Bool |Bool]]''​ ''​degree_one_generators'':​ compute the generators of degree one, i.e. lattice points of the polytope + :: ''​[[.:​common#​Bool |Bool]]''​ ''​hilbert_basis'':​ compute Hilbert basis of the cone C + :: ''​[[.:​common#​Bool |Bool]]''​ ''​h_star_vector'':​ compute Hilbert h-vector of the cone C + :: ''​[[.:​common#​Bool |Bool]]''​ ''​hilbert_series'':​ compute Hilbert series of the monoid + :: ''​[[.:​common#​Bool |Bool]]''​ ''​ehrhart_quasi_polynomial'':​ compute Ehrhart quasi polynomial of a polytope + :: ''​[[.:​common#​Bool |Bool]]''​ ''​facets'':​ compute support hyperplanes (=FACETS,​LINEAR_SPAN) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​rays'':​ compute extreme rays (=RAYS) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​dual_algorithm'':​ use the dual algorithm by Pottier + :: ''​[[.:​common#​Bool |Bool]]''​ ''​skip_long'':​ do not try to use long coordinates first + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ libnormaliz debug output + ? Returns: + :''​[[.:​common#​List |List]]''​ + ? from extension: + : [[:​external_software|bundled:​libnormaliz]] + + + ---- + {{anchor:​occluding_cone:​}} + ?  **''​occluding_cone([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Set |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Set |Set]]''​ ''​F''​ + ? Returns: + :''​[[.:​polytope:​Cone |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 + ​ + + + ---- + {{anchor:​print_face_lattice:​}} + ?  **''​print_face_lattice([[.:​common#​IncidenceMatrix |IncidenceMatrix]] VIF, [[.:​common#​Bool |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: + :: ''​[[.:​common#​IncidenceMatrix |IncidenceMatrix]]''​ ''​VIF''​ + :: ''​[[.:​common#​Bool |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}} + ​ + + + ---- + {{anchor:​separable:​}} + ?  **''​separable([[.:​common#​Vector |Vector]] q, [[.:​polytope:​Cone |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: + :: ''​[[.:​common#​Vector |Vector]]''​ ''​q'':​ the vertex (candidate) which is to be separated from //P// + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P'':​ the polytope/​cone from which //q// is to be separated + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​strong'':​ Test for strong separability. default: true + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + ? Example: + :: > $q = cube(2)->​VERTICES->​row(0);​ + > print separable(cube(2),​$q, strong=>​0);​ + true + ​ + + + ---- + {{anchor:​simple_polytope_vertices_rs:​}} + ?  **''​simple_polytope_vertices_rs([[.:​polytope:​Polytope |Polytope]]<​Scalar>​ P, [[.:​common#​Vector |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 ''​[[.:​polytope:​Polytope#​ONE_VERTEX |ONE_VERTEX]]''​ The input polytope must be ''​[[.:​polytope:​Polytope#​SIMPLE |SIMPLE]]''​ and ''​[[.:​polytope:​Polytope#​POINTED |POINTED]]'',​ these properties are not checked by the algorithm. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]<​Scalar>''​ ''​P''​ + :: ''​[[.:​common#​Vector |Vector]]<​Scalar>''​ ''​min_vertex''​ + ? Returns: + :''​[[.:​common#​List |List]]''​ + + + ---- + {{anchor:​steiner_point:​}} + ?  **''​steiner_point([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Compute the Steiner point of a polyhedron //P// using a randomized approximation of the angles. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Options: + : + :: ''​[[.:​common#​Float |Float]]''​ ''​eps'':​ controls the accuracy of the angles computed + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. + ? Returns: + :''​[[.:​common#​Vector |Vector]]''​ + + + ---- + {{anchor:​violations:​}} + ?  **''​violations([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Vector |Vector]] q)''​** + :: Check which relations, if any, are violated by a point. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​q''​ + ? Options: + : + :: ''​[[.:​common#​String |String]]''​ ''​section'':​ Which section of P to test against q + :: ''​[[.:​common#​Int |Int]]''​ ''​violating_criterion'':​ has the options: +1 (positive values violate; this is the default), 0 (*non*zero values violate), -1 (negative values violate) + ? Returns: + :''​[[.:​common#​Set |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} + ​ + + + ---- + {{anchor:​visible_face_indices:​}} + ?  **''​visible_face_indices([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Vector |Vector]] q)''​** + :: Return the indices (in the HASSE_DIAGRAM) of all faces that are visible from a point //q//. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​q''​ + ? Returns: + :''​[[.:​common#​Set |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} + ​ + + + ---- + {{anchor:​visible_facet_indices:​}} + ?  **''​visible_facet_indices([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Vector |Vector]] q)''​** + :: Return the indices of all facets that are visible from a point //q//. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​q''​ + ? Returns: + :''​[[.:​common#​Set |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} + ​ + + + ---- + {{anchor:​zonotope_tiling_lattice:​}} + ?  **''​zonotope_tiling_lattice([[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​P'':​ the zonotope + ? Options: + : + :: ''​[[.:​common#​Bool |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: + :''​[[.:​polytope:​AffineLattice |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. + ---- + {{anchor:​ball_lifting_lp:​}} + ?  **''​ball_lifting_lp([[.:​topaz:​GeometricSimplicialComplex |GeometricSimplicialComplex]] c, [[.:​common#​Int |Int]] facet_index,​ [[.:​common#​Rational |Rational]] conv_eps)''​** + :: Computes the inequalities and the linear objective for an LP to lift a simplicial //d//-ball embedded starshaped in R<​sup>​d​. + ? Parameters: + :: ''​[[.:​topaz:​GeometricSimplicialComplex |GeometricSimplicialComplex]]''​ ''​c''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​facet_index'':​ index of the facet to be lifted + :: ''​[[.:​common#​Rational |Rational]]''​ ''​conv_eps'':​ some epsilon > 0 + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + ? from extension: + : [[:​external_software|bundled:​local]] + + + ---- + {{anchor:​core_point_algo:​}} + ?  **''​core_point_algo([[.:​polytope:​Polytope |Polytope]] p, [[.:​common#​Rational |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:​Polytope |Polytope]]''​ ''​p''​ + :: ''​[[.:​common#​Rational |Rational]]''​ ''​optLPvalue'':​ optimal value of LP approximation + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose''​ + ? Returns: + :''​[[.:​common#​List |List]]''​ + + + ---- + {{anchor:​core_point_algo_rote:​}} + ?  **''​core_point_algo_Rote([[.:​polytope:​Polytope |Polytope]] p, [[.:​common#​Rational |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:​Polytope |Polytope]]''​ ''​p''​ + :: ''​[[.:​common#​Rational |Rational]]''​ ''​optLPvalue'':​ optimal value of LP approximation + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose''​ + ? Returns: + :''​[[.:​common#​List |List]]''​ + + + ---- + {{anchor:​find_transitive_lp_sol:​}} + ?  **''​find_transitive_lp_sol([[.:​common#​Matrix |Matrix]] Inequalities)''​** + :: Algorithm to solve symmetric linear programs (LP) of the form max c<​sup>​t​x , 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: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​Inequalities'':​ the inequalities describing the feasible region + ? Returns: + :''​[[.:​common#​List |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. + + + ---- + {{anchor:​inner_point:​}} + ? **''​inner_point([[.:​common#​Matrix |Matrix]] points)''​** + :: Compute a true inner point of a convex hull of the given set of //points//. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​points''​ + ? Returns: + :''​[[.:​common#​Vector |Vector]]''​ + ? Example: + :: To print an inner point of the square, do this: + :: > print inner_point(cube(2)->​VERTICES);​ + 1 -1/3 -1/3 + ​ + + + ---- + {{anchor:​lp2poly:​}} + ? **''​lp2poly<​Scalar>​([[.:​common#​String |String]] file, [[.:​common#​Vector |Vector]] testvec, [[.:​common#​String |String]] prefix)''​** + :: Read a linear programming problem given in LP-Format or MILP-Format (as used by cplex & Co.) and convert it to a [[]] object with an added LP property or MILP property + ? Type Parameters: + :: ''​Scalar'':​ coordinate type of the resulting polytope; default is ''​[[.:​common#​Rational |Rational]]''​. + ? Parameters: + :: ''​[[.:​common#​String |String]]''​ ''​file'':​ filename of a linear programming problem in LP-Format + :: ''​[[.:​common#​Vector |Vector]]''​ ''​testvec'':​ If present, after reading in each line of the LP it is checked whether testvec fulfills it + :: ''​[[.:​common#​String |String]]''​ ''​prefix'':​ If testvec is present, all variables in the LP file are assumed to have the form$prefix$i + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​nocheck'':​ Do not automatically compute ''​[[.:​polytope:​Polytope#​FEASIBLE |FEASIBLE]]''​ for the polytope (recommended for very large LPs) + :: ''​[[.:​common#​Bool |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:​Polytope |Polytope]]<​Scalar>''​ + + + ---- + {{anchor:​poly2lp:​}} + ? **''​poly2lp([[.:​polytope:​Polytope |Polytope]] P, [[.:​polytope:​LinearProgram |LinearProgram]] LP, [[.:​common#​Bool |Bool]] maximize, [[.:​common#​String |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. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​polytope:​LinearProgram |LinearProgram]]''​ ''​LP'':​ default value: //​P//​->​LP + :: ''​[[.:​common#​Bool |Bool]]''​ ''​maximize'':​ produces a maximization problem; default value: 0 (minimize) + :: ''​[[.:​common#​String |String]]''​ ''​file'':​ default value: standard output + + + ---- + {{anchor:​poly2porta:​}} + ? **''​poly2porta([[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |Rational]]>​ p, [[.:​common#​String |String]] file)''​** + :: take a rational polytope and write a porta input file (.ieq or .poi) + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |Rational]]>''​ ''​p''​ + :: ''​[[.:​common#​String |String]]''​ ''​file'':​ filename for the porta file (.ieq or .poi) or an open IO handle + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​primal'':​ true if points should be written, false if inequalities should be written (default is true) + + + ---- + {{anchor:​porta2poly:​}} + ? **''​porta2poly([[.:​common#​String |String]] file)''​** + :: Read an .ieq or .poi file (porta input) or .poi.ieq or .ieq.poi (porta output) ​ and convert it to a [[]] object + ? Parameters: + :: ''​[[.:​common#​String |String]]''​ ''​file'':​ filename of a porta file (.ieq or .poi) + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |Rational]]>''​ + + + ---- + {{anchor:​print_constraints:​}} + ? **''​print_constraints([[.:​polytope:​Cone |Cone]]<​Scalar>​ C)''​** + :: Write the ''​[[.:​polytope:​Cone#​FACETS |FACETS]]''​ / ''​[[.:​polytope:​Polytope#​INEQUALITIES |INEQUALITIES]]''​ and the ''​[[.:​polytope:​VectorConfiguration#​LINEAR_SPAN |LINEAR_SPAN]]''​ / ''​[[.:​polytope:​Polytope#​EQUATIONS |EQUATIONS]]''​ (if present) of a polytope //P// or cone //C// in a readable way. ''​[[.:​polytope:​Cone#​COORDINATE_LABELS |COORDINATE_LABELS]]''​ are adopted if present. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]<​Scalar>''​ ''​C'':​ the given polytope or cone + ? Options: + : + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​String |String]]>''​ ''​ineq_labels'':​ changes the labels of the inequality rows + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​String |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 + ​ + + + ---- + {{anchor:​rand_aof:​}} + ? **''​rand_aof([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P'':​ a __simple__ polytope + :: ''​[[.:​common#​Int |Int]]''​ ''​start'':​ the index of the starting vertex; default value: random + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​ ​fixing a seed number guarantees the same outcome. ​ + ? Returns: + :''​[[.:​common#​Vector |Vector]]<​[[.:​common#​Rational |Rational]]>''​ + + + ---- + {{anchor:​random_edge_epl:​}} + ? **''​random_edge_epl([[.:​graph:​Graph |Graph]]<​[[.:​common#​Directed |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:​Graph |Graph]]<​[[.:​common#​Directed |Directed]]>''​ ''​G'':​ a directed graph + ? Returns: + :''​[[.:​common#​Vector |Vector]]<​[[.:​common#​Rational |Rational]]>''​ + + + ---- + {{anchor:​separating_hyperplane:​}} + ? **''​separating_hyperplane([[.:​common#​Vector |Vector]] q, [[.:​common#​Matrix |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: + :: ''​[[.:​common#​Vector |Vector]]''​ ''​q'':​ the vertex (candidate) which is to be separated from //points// + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​points'':​ the points from which //q// is to be separated + ? Returns: + :''​[[.:​common#​Vector |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:​Polytope |Polytope]] p1, [[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​p1'':​ the first polytope, will be on the positive side of the separating hyperplane + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​p2'':​ the second polytope + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​strong'':​ If this is set to true, the resulting hyperplane will be strongly separating, ​ i.e. it wont touch either of the polytopes. If such a plane does not exist, an exception ​ will be thrown. default: true + ? Returns: + :''​[[.:​common#​Vector |Vector]]''​ + + + ---- + {{anchor:​totally_dual_integral:​}} + ? **''​totally_dual_integral([[.:​common#​Matrix |Matrix]] inequalities)''​** + :: Checks weather a given system of inequalities is totally dual integral or not. The inequalities should describe a full dimensional polyhedron + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​inequalities''​ + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + ? Example: + :: > print totally_dual_integral(cube(2)->​FACETS);​ + true + ​ + + + ---- + {{anchor:​vertex_colors:​}} + ? **''​vertex_colors([[.:​polytope:​Polytope |Polytope]] P, [[.:​polytope:​LinearProgram |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​polytope:​LinearProgram |LinearProgram]]''​ ''​LP''​ + ? Options: + : + :: ''​[[.:​common#​RGB |RGB]]''​ ''​min'':​ the minimal RGB value + :: ''​[[.:​common#​RGB |RGB]]''​ ''​max'':​ the maximal RGB value + ? Returns: + :''​[[.:​common#​Array |Array]]<​[[.:​common#​RGB |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);​ + ​ + + + ---- + {{anchor:​write_foldable_max_signature_ilp:​}} + ?  **''​write_foldable_max_signature_ilp([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​String |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​String |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. + + + ---- + {{anchor:​write_simplexity_ilp:​}} + ?  **''​write_simplexity_ilp([[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​P''​ + ? Options: + : + :: ''​[[.:​common#​String |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 + ​ + + + ---- + {{anchor:​write_simplexity_ilp_with_angles:​}} + ?  **''​write_simplexity_ilp_with_angles([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​String |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​String |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 + + ​ + + + ---- + {{anchor:​write_symmetrized_simplexity_ilp:​}} + ?  **''​write_symmetrized_simplexity_ilp([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> isotypic_components,​ [[.:​common#​String |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​isotypic_components'':​ the set of indices of isotypic components to project to; default [0] + :: ''​[[.:​common#​String |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. + ---- + {{anchor:​inner_cone:​}} + ?  **''​inner_cone([[.:​polytope:​Cone |Cone]] p, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> F)''​** + :: Computes the inner cone of //p// at a face //F// (or a vertex //v//). + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​p''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​F'':​ (or Int v) vertex indices which are not contained in the far face + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​outer'':​ Make it point outside the polytope? Default value is 0 (= point inside) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​attach'':​ Attach the cone to //F//? Default 0 (ie, return the cone inside the hyperplane at infinity) + ? Returns: + :''​[[.:​polytope:​Cone |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 + ​ + + + ---- + {{anchor:​normal_cone:​}} + ?  **''​normal_cone([[.:​polytope:​PointConfiguration |PointConfiguration]] p, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> F)''​** + :: Computes the normal cone of //p// at a face //F// (or vertex //v//). By default this is the inner normal cone. + ? Parameters: + :: ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]''​ ''​p''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​F'':​ (or Int v) point indices which are not contained in the far face + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​outer'':​ Calculate outer normal cone?  Default value is 0 (= inner) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​attach'':​ Attach the cone to //F//? Default 0 (ie, return the cone inside the hyperplane at infinity) + ? Returns: + :''​[[.:​polytope:​Cone |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([[.:​polytope:​Cone |Cone]] p, [[.:​common#​Set |Set]]<​[[.:​common#​Int |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​p''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​F'':​ (or Int v) vertex indices which are not contained in the far face + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​outer'':​ Calculate outer normal cone? Default value is 0 (= inner) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​attach'':​ Attach the cone to //F//? Default 0 (ie, return the cone inside the hyperplane at infinity) + ? Returns: + :''​[[.:​polytope:​Cone |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 + ​ + + + ---- + {{anchor:​recession_cone:​}} + ? **''​recession_cone([[.:​polytope:​Polytope |Polytope]]<​Scalar>​ P)''​** + :: retuns the recession cone (tail cone, characteristic cone) of a polytope + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]<​Scalar>''​ ''​P'':​ polytope + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]<​Scalar>''​ + + + ---- + {{anchor:​subcone:​}} + ? **''​subcone([[.:​polytope:​Cone |Cone]] C)''​** + :: Make a subcone from a cone. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​C'':​ the input cone + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not create ''​[[.:​polytope:​Cone#​RAY_LABELS |RAY_LABELS]]''​. default: 0 + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]''​ + + + ---- + + ==== Producing a point configuration ==== + ​Constructing a point configuration,​ either from scratch or from existing objects. + ---- + {{anchor:​minkowski_sum:​}} + ? **''​minkowski_sum([[.:​polytope:​PointConfiguration |PointConfiguration]] P1, [[.:​polytope:​PointConfiguration |PointConfiguration]] P2)''​** + :: Produces the Minkowski sum of //P1// and //P2//. + ? Parameters: + :: ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]''​ ''​P1''​ + :: ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]''​ ''​P2''​ + ? Returns: + :''​[[.:​polytope:​PointConfiguration |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, [[.:​polytope:​PointConfiguration |PointConfiguration]] P1, Scalar mu, [[.:​polytope:​PointConfiguration |PointConfiguration]] P2)''​** + :: Produces the polytope //​lambda//​*//​P1//​+//​mu//​*//​P2//,​ where * and + are scalar multiplication and Minkowski addition, respectively. + ? Parameters: + :: ''​Scalar''​ ''​lambda''​ + :: ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]''​ ''​P1''​ + :: ''​Scalar''​ ''​mu''​ + :: ''​[[.:​polytope:​PointConfiguration |PointConfiguration]]''​ ''​P2''​ + ? Returns: + :''​[[.:​polytope:​PointConfiguration |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. + ---- + {{anchor:​flow_polytope:​}} + ? **''​flow_polytope<​Scalar>​([[.:​common#​GraphAdjacency |GraphAdjacency]]<​[[.:​common#​Directed |Directed]]>​ G, [[.:​common#​EdgeMap |EdgeMap]]<​[[.:​common#​Directed |Directed]],​Scalar>​ Arc_Bounds, [[.:​common#​Int |Int]] source, [[.:​common#​Int |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 + - sum_{e in E going out of v} x_e = 0 + .. ​sum_{e in E going into source} x_e + - sum_{e in E going out of source} x_e <= 0 + .. ​sum_{e in E going into sink} x_e + - 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: + :: ''​[[.:​common#​GraphAdjacency |GraphAdjacency]]<​[[.:​common#​Directed |Directed]]>''​ ''​G''​ + :: ''​[[.:​common#​EdgeMap |EdgeMap]]<​[[.:​common#​Directed |Directed]],​Scalar>''​ ''​Arc_Bounds''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​source''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​sink''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + ? **''​flow_polytope<​Scalar>​([[.:​graph:​Graph |Graph]]<​[[.:​common#​Directed |Directed]]>​ G, [[.:​common#​Array |Array]]<​Scalar>​ Arc_Bounds, [[.:​common#​Int |Int]] source, [[.:​common#​Int |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 + - sum_{e in E going out of v} x_e = 0 + .. ​sum_{e in E going into source} x_e + - sum_{e in E going out of source} x_e <= 0 + .. ​sum_{e in E going into sink} x_e + - 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:​Graph |Graph]]<​[[.:​common#​Directed |Directed]]>''​ ''​G''​ + :: ''​[[.:​common#​Array |Array]]<​Scalar>''​ ''​Arc_Bounds''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​source''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​sink''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​fractional_cut_polytope:​}} + ? **''​fractional_cut_polytope([[.:​graph:​Graph |Graph]] G)''​** + :: Cut polytope of an undirected graph. + ? Parameters: + :: ''​[[.:​graph:​Graph |Graph]]''​ ''​G''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​fractional_matching_polytope:​}} + ? **''​fractional_matching_polytope([[.:​graph:​Graph |Graph]] G)''​** + :: Matching polytope of an undirected graph. + ? Parameters: + :: ''​[[.:​graph:​Graph |Graph]]''​ ''​G''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​tutte_lifting:​}} + ? **''​tutte_lifting([[.:​graph:​Graph |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<​sup>​3​. + ? Parameters: + :: ''​[[.:​graph:​Graph |Graph]]''​ ''​G''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​weighted_digraph_polyhedron:​}} + ? **''​weighted_digraph_polyhedron([[.:​common#​Matrix |Matrix]] encoding)''​** + :: Weighted digraph polyhedron of a directed graph with a weight function. The graph and the weight function are combined into a matrix. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​encoding'':​ weighted digraph + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + + ==== Producing a polytope from other objects ==== + ​Polytope constructions which take other big objects as input. + ---- + {{anchor:​billera_lee:​}} + ? **''​billera_lee([[.:​common#​Vector |Vector]]<​[[.:​common#​Integer |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: + :: ''​[[.:​common#​Vector |Vector]]<​[[.:​common#​Integer |Integer]]>''​ ''​H''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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. + ---- + {{anchor:​bipyramid:​}} + ? **''​bipyramid([[.:​polytope:​Polytope |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:​Polytope |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: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ : don't compute the coordinates,​ purely combinatorial description is produced. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 label the new vertices with "​Apex"​ and "​Apex'"​. + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​blending:​}} + ? **''​blending([[.:​polytope:​Polytope |Polytope]] P1, [[.:​common#​Int |Int]] v1, [[.:​polytope:​Polytope |Polytope]] P2, [[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​v1'':​ the index of the first vertex + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​v2'':​ the index of the second vertex + ? Options: + : + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]>''​ ''​permutation''​ + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytopes. default: 0 + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + ? Example: + :: The following gives the smallest ''​[[.:​polytope:​Cone#​EVEN |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 + ​ + + + ---- + {{anchor:​cayley_embedding:​}} + ? **''​cayley_embedding([[.:​polytope:​Polytope |Polytope]] P_0, [[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​P_0'':​ the first polytope + :: ''​[[.:​polytope:​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: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + ? **''​cayley_embedding([[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |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: + :: ''​[[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |Polytope]]>''​ ''​A'':​ the input polytopes + ? Options: + : + :: ''​[[.:​common#​Array |Array]]<​Scalar>''​ ''​factors'':​ array of scaling factors for the Cayley embedding; defaults to the all-1 vector + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​cayley_polytope:​}} + ? **''​cayley_polytope([[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |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<​sub>​1​Ã—e<​sub>​1,​ ..., P<​sub>​k​Ã—e<​sub>​k​ where e<​sub>​1,​ ...,​e<​sub>​k​ are the standard unit vectors in R<​sup>​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: + :: ''​[[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |Polytope]]>''​ ''​P_Array'':​ an array containing the lattice polytopes P<​sub>​1,​...,​P<​sub>​k​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​proj''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​cell_from_subdivision:​}} + ? **''​cell_from_subdivision([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |Int]] cell)''​** + :: Extract the given //cell// of the subdivision of a polyhedron and write it as a new polyhedron. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​cell''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​cells_from_subdivision:​}} + ? **''​cells_from_subdivision([[.:​polytope:​Polytope |Polytope]]<​Scalar>​ P, [[.:​common#​Set |Set]]<​[[.:​common#​Int |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:​Polytope |Polytope]]<​Scalar>''​ ''​P''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​cells''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​conv:​}} + ? **''​conv([[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |Polytope]]>​ P_Array)''​** + :: Construct a new polyhedron as the convex hull of the polyhedra given in //​P_Array//​. + ? Parameters: + :: ''​[[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |Polytope]]>''​ ''​P_Array''​ + ? Returns: + :''​[[.:​polytope:​PropagatedPolytope |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 + ​ + + + ---- + {{anchor:​dual_linear_program:​}} + ? **''​dual_linear_program([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Bool |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:​Polytope |Polytope]]''​ ''​P'':​ = {x | Ax >= b, Bx = d} + :: ''​[[.:​common#​Bool |Bool]]''​ ''​maximize'':​ tells if the primal lp is a maximization problem. Default value is 0 (= minimize) + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​edge_middle:​}} + ? **''​edge_middle([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Produce the convex hull of all edge middle points of some polytope //P//. The polytope must be ''​[[.:​polytope:​Polytope#​BOUNDED |BOUNDED]]''​. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​face:​}} + ? **''​face([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Set |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Set |Set]]''​ ''​S''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ don't copy the coordinates,​ produce purely combinatorial description. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 + ? Returns: + :''​[[.:​polytope:​Cone |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]);​ + ​ + + + ---- + {{anchor:​facet:​}} + ?  **''​facet([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Int |Int]] facet)''​** + :: Extract the given //facet// of a polyhedron and write it as a new polyhedron. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​facet''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ don't copy the coordinates,​ produce purely combinatorial description. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]''​ + ? Example: + :: To create a cone from the vertices of the zeroth facet of the 3-cube, type this: + :: > $p = facet(cube(3),​0);​ + ​ + + + ---- + {{anchor:​facet_to_infinity:​}} + ? **''​facet_to_infinity([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |Int]] i)''​** + :: Make an affine transformation such that the i-th facet is transformed to infinity + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​i'':​ the facet index + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​free_sum:​}} + ? **''​free_sum([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: Construct a new polyhedron as the free sum of two given bounded ones. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​force_centered'':​ if the input polytopes must be centered. Defaults to true. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ produces a pure combinatorial description. Defaults to false. + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​free_sum_decomposition:​}} + ? **''​free_sum_decomposition([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Decompose a given polytope into the free sum of smaller ones + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |Polytope]]>''​ + + + ---- + {{anchor:​free_sum_decomposition_indices:​}} + ? **''​free_sum_decomposition_indices([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Decompose a given polytope into the free sum of smaller ones, and return the vertex indices of the summands + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |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} + ​ + + + ---- + {{anchor:​gc_closure:​}} + ?  **''​gc_closure([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Produces the gomory-chvatal closure of a full dimensional polyhedron + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​integer_hull:​}} + ?  **''​integer_hull([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Produces the integer hull of a polyhedron + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​intersection:​}} + ?  **''​intersection([[.:​polytope:​Cone |Cone]] C ...)''​** + :: Construct a new polyhedron or cone as the intersection of given polyhedra and/or cones. Works only if all ''​[[.:​polytope:​Cone#​CONE_AMBIENT_DIM |CONE_AMBIENT_DIM]]''​ values are equal. If the input contains both cones and polytopes, the output will be a polytope. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​C ...'':​ polyhedra and cones to be intersected + ? Returns: + :''​[[.:​polytope:​Cone |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 + ​ + + + ---- + {{anchor:​join_polytopes:​}} + ?  **''​join_polytopes([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: Construct a new polyhedron as the join of two given bounded ones. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ produces a pure combinatorial description. + :: ''​[[.:​common#​Bool |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:​Polytope |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 + ​ + + + ---- + {{anchor:​lattice_bipyramid:​}} + ?  **''​lattice_bipyramid([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Vector |Vector]] v, [[.:​common#​Vector |Vector]] v_prime, [[.:​common#​Rational |Rational]] z, [[.:​common#​Rational |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​v'':​ basis point for the first apex + :: ''​[[.:​common#​Vector |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//​. + :: ''​[[.:​common#​Rational |Rational]]''​ ''​z'':​ height for the first apex, default value is 1 + :: ''​[[.:​common#​Rational |Rational]]''​ ''​z_prime'':​ height for the second apex, default value is -//z// + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 label the new vertices with "​Apex"​ and "​Apex'"​. + ? Returns: + :''​[[.:​polytope:​Polytope |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' + ​ + + + ---- + {{anchor:​lattice_pyramid:​}} + ? **''​lattice_pyramid([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Rational |Rational]] z, [[.:​common#​Vector |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Rational |Rational]]''​ ''​z'':​ the height for the apex (//​v//,//​z//​),​ default value is 1. + :: ''​[[.:​common#​Vector |Vector]]''​ ''​v'':​ the lattice point to use as apex, default is the first vertex of //P//. + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 label the new top vertex with "​Apex"​. + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​lawrence:​}} + ?  **''​lawrence([[.:​polytope:​Cone |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P'':​ an input cone or polytope + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]''​ + + + ---- + {{anchor:​make_totally_dual_integral:​}} + ?  **''​make_totally_dual_integral([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Produces a polyhedron with an totally dual integral inequality formulation of a full dimensional polyhedron + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​mapping_polytope:​}} + ?  **''​mapping_polytope([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |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<​sup>​p​ to R<​sup>​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<​sub>​1​ and h<​sub>​1​ will have the form "​v<​sub>​1​*h<​sub>​1"​. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not assign ''​[[.:​polytope:​Polytope#​FACET_LABELS |FACET_LABELS]]''​. default: 0 + ? Returns: + :''​[[.:​polytope:​Polytope |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. + + + ---- + {{anchor:​minkowski_sum:​}} + ?  **''​minkowski_sum([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: Produces the Minkowski sum of //P1// and //P2//. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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:​Polytope |Polytope]] P1, Scalar mu, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: Produces the polytope //​lambda//​*//​P1//​+//​mu//​*//​P2//,​ where * and + are scalar multiplication and Minkowski addition, respectively. + ? Parameters: + :: ''​Scalar''​ ''​lambda''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​Scalar''​ ''​mu''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​minkowski_sum_fukuda:​}} + ?  **''​minkowski_sum_fukuda([[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |Polytope]]>​ summands)''​** + :: Computes the (''​[[.:​polytope:​Polytope#​VERTICES |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: + :: ''​[[.:​common#​Array |Array]]<​[[.:​polytope:​Polytope |Polytope]]>''​ ''​summands''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​mixed_integer_hull:​}} + ?  **''​mixed_integer_hull([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]> int_coords)''​** + :: Produces the mixed integer hull of a polyhedron + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]>''​ ''​int_coords'':​ the coordinates to be integral; + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​pointed_part:​}} + ?  **''​pointed_part([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Produces the pointed part of a polyhedron + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​prism:​}} + ?  **''​prism([[.:​polytope:​Polytope |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:​Polytope |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: + : + :: ''​[[.:​common#​Bool |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 + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ only combinatorial information is handled + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |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:​Polytope |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 + ​ + + + ---- + {{anchor:​product:​}} + ?  **''​product([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ only combinatorial information is handled + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_vertices'':​ do not compute vertices + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_facets'':​ do not compute facets + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytopes, if present. ​  the label of a new vertex corresponding to v<​sub>​1​ âŠ• v<​sub>​2​ will   have the form LABEL_1*LABEL_2. default: 0 + :: ''​[[.:​common#​Bool |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:​Polytope |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);​ + ​ + + + ---- + {{anchor:​project_full:​}} + ? **''​project_full([[.:​polytope:​Cone |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​nofm'':​ suppresses Fourier-Motzkin elimination + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ to the projection. default: 0 + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]''​ + + + ---- + {{anchor:​projection:​}} + ? **''​projection([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Array |Array]]<​[[.:​common#​Int |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]>''​ ''​indices''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​revert'':​ inverts the coordinate list + :: ''​[[.:​common#​Bool |Bool]]''​ ''​nofm'':​ suppresses Fourier-Motzkin elimination + ? Returns: + :''​[[.:​polytope:​Cone |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 + ​ + + + ---- + {{anchor:​projection_preimage:​}} + ? **''​projection_preimage([[.:​common#​Array |Array]]<​[[.:​polytope:​Cone |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: + :: ''​[[.:​common#​Array |Array]]<​[[.:​polytope:​Cone |Cone]]>''​ ''​P_Array''​ + ? Returns: + :''​[[.:​polytope:​Cone |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 + ​ + + + ---- + {{anchor:​pyramid:​}} + ? **''​pyramid([[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​Scalar''​ ''​z'':​ is the distance between the vertex barycenter and //​v//, ​ ​default value is 1. + ? Options: + : + :: ''​[[.:​common#​Bool |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 + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ don't compute new coordinates,​ produce purely combinatorial description. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytope. default: 0 label the new top vertex with "​Apex"​. + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​rand_inner_points:​}} + ? **''​rand_inner_points([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |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. ''​[[.:​polytope#​unirand |unirand]]''​ for this. The polytope must be ''​[[.:​polytope:​Polytope#​BOUNDED |BOUNDED]]''​. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P'':​ the input polytope + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of random points + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​ ​fixing a seed number guarantees the same outcome. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​rand_vert:​}} + ? **''​rand_vert([[.:​common#​Matrix |Matrix]] V, [[.:​common#​Int |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: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​V'':​ the vertices of a polytope + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of random points + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​ ​fixing a seed number guarantees the same outcome. + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]''​ + + + ---- + {{anchor:​spherize:​}} + ? **''​spherize([[.:​polytope:​Polytope |Polytope]] P)''​** + :: Project all vertices of a polyhedron //P// on the unit sphere. //P// must be ''​[[.:​polytope:​Polytope#​CENTERED |CENTERED]]''​ and ''​[[.:​polytope:​Polytope#​BOUNDED |BOUNDED]]''​. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​stack:​}} + ? **''​stack([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Set |Set]]<​[[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |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: + : + :: ''​[[.:​common#​Rational |Rational]]''​ ''​lift'':​ controls the exact coordinates of the new vertices; ​ ​rational number between 0 and 1; default value: 1/2 + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ produces a pure combinatorial description (in contrast to //lift//) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |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:​Polytope |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);​ + ​ + + + ---- + {{anchor:​stellar_all_faces:​}} + ?  **''​stellar_all_faces([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P'':​ , must be bounded + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the lowest dimension of the faces to be divided; ​  ​negative values: treated as the co-dimension;​ default value: 1. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​stellar_indep_faces:​}} + ?  **''​stellar_indep_faces([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P'':​ , must be bounded + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%%''​ ''​in_faces''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​tensor:​}} + ?  **''​tensor([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​truncation:​}} + ?  **''​truncation([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Set |Set]]<​[[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |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 + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ produces a pure combinatorial description (in contrast to //cutoff//) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |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:​Polytope |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 + ​ + + + ---- + {{anchor:​unirand:​}} + ?  **''​unirand([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of random points + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​boundary'':​ forces the points to lie on the boundary of the given polytope + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. + ? Returns: + :''​[[.:​polytope:​Polytope |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);​ + ​ + + + ---- + {{anchor:​vertex_figure:​}} + ?  **''​vertex_figure([[.:​polytope:​Polytope |Polytope]] p, [[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​p''​ + :: ''​[[.:​common#​Int |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. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ skip the coordinates computation,​ producing a pure combinatorial description. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |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:​Polytope |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 + ​ + + + ---- + {{anchor:​wedge:​}} + ?  **''​wedge([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |Int]] facet, [[.:​common#​Rational |Rational]] z, [[.:​common#​Rational |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:​Polytope |Polytope]]''​ ''​P'':​ , must be bounded + :: ''​[[.:​common#​Int |Int]]''​ ''​facet'':​ the `cutting edge'. + :: ''​[[.:​common#​Rational |Rational]]''​ ''​z'':​ default value is 0. + :: ''​[[.:​common#​Rational |Rational]]''​ ''​z_prime'':​ default value is -//z//, or 1 if //z//==0. + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ don't compute coordinates,​ pure combinatorial description is produced. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |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:​Polytope |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 + ​ + + + ---- + {{anchor:​wreath:​}} + ?  **''​wreath([[.:​polytope:​Polytope |Polytope]] P1, [[.:​polytope:​Polytope |Polytope]] P2)''​** + :: Construct a new polytope as the wreath product of two input polytopes //P1//, //P2//. //P1// and //P2// have to be ''​[[.:​polytope:​Polytope#​BOUNDED |BOUNDED]]''​. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P1''​ + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​P2''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​dual'':​ invokes the computation of the dual wreath product + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ from the original polytopes. default: 0   the label of a new vertex corresponding to v<​sub>​1​ âŠ• v<​sub>​2​ will   have the form LABEL_1*LABEL_2. + ? Returns: + :''​[[.:​polytope:​Polytope |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. + ---- + {{anchor:​associahedron:​}} + ?  **''​associahedron([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Options: + : + :: ''​[[.:​common#​Bool |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:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​binary_markov_graph:​}} + ?  **''​binary_markov_graph([[.:​common#​Array |Array]]<​[[.:​common#​Bool |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: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Bool |Bool]]>''​ ''​observation''​ + ? Returns: + :''​[[.:​polytope:​PropagatedPolytope |PropagatedPolytope]]''​ + ?  **''​binary_markov_graph([[.:​common#​String |String]] observation)''​** + :: + ? Parameters: + :: ''​[[.:​common#​String |String]]''​ ''​observation'':​ encoded as a string of "​0"​ and "​1"​. + + + ---- + {{anchor:​birkhoff:​}} + ?  **''​birkhoff([[.:​common#​Int |Int]] n, [[.:​common#​Bool |Bool]] even)''​** + :: Constructs the Birkhoff polytope of dimension //​n//<​sup>​2​. It is the polytope of //n//x//n// stochastic matrices (encoded as //​n//<​sup>​2​ row vectors), thus matrices with non-negative entries whose row and column entries sum up to one. Its vertices are the permutation matrices. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​n''​ + :: ''​[[.:​common#​Bool |Bool]]''​ ''​even'':​ Defaults to '​0'​. Set this to '​1'​ to get vertices only for even permutation matrices. + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group'':​ add the symmetry group induced by the symmetric group to the resulting polytope + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​cyclic:​}} + ?  **''​cyclic([[.:​common#​Int |Int]] d, [[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of points + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​start'':​ defaults to 0 (or to 1 if spherical) + :: ''​[[.:​common#​Bool |Bool]]''​ ''​spherical'':​ defaults to false + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |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 + ​ + + + ---- + {{anchor:​cyclic_caratheodory:​}} + ?  **''​cyclic_caratheodory([[.:​common#​Int |Int]] d, [[.:​common#​Int |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 ''​[[.:​polytope#​cyclic |cyclic]]''​. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension. Required to be even. + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of points + ? Options: + : + :: ''​[[.:​common#​Bool |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:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​delpezzo:​}} + ?  **''​delpezzo([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |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:​Polytope |Polytope]]<​Scalar>''​ + + + ---- + {{anchor:​dwarfed_cube:​}} + ?  **''​dwarfed_cube([[.:​common#​Int |Int]] d)''​** + :: Produce a //​d//​-dimensional dwarfed cube. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​dwarfed_product_polygons:​}} + ?  **''​dwarfed_product_polygons([[.:​common#​Int |Int]] d, [[.:​common#​Int |Int]] s)''​** + :: Produce a //​d//​-dimensional dwarfed product of polygons of size //s//. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​[[.:​common#​Int |Int]]''​ ''​s'':​ the size + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​explicit_zonotope:​}} + ?  **''​explicit_zonotope([[.:​common#​Matrix |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: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​zones'':​ the input vectors + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​rows_are_points'':​ the rows of the input matrix represent affine points(true,​ default) or linear vectors(false) + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​fano_simplex:​}} + ?  **''​fano_simplex([[.:​common#​Int |Int]] d)''​** + :: Produce a Fano //​d//​-simplex. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​fractional_knapsack:​}} + ?  **''​fractional_knapsack([[.:​common#​Vector |Vector]]<​[[.:​common#​Rational |Rational]]>​ b)''​** + :: Produce a knapsack polytope defined by one linear inequality (and non-negativity constraints). + ? Parameters: + :: ''​[[.:​common#​Vector |Vector]]<​[[.:​common#​Rational |Rational]]>''​ ''​b'':​ linear inequality + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​goldfarb:​}} + ?  **''​goldfarb([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​Scalar''​ ''​e''​ + :: ''​Scalar''​ ''​g''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​goldfarb_sit:​}} + ?  **''​goldfarb_sit([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​Scalar''​ ''​eps''​ + :: ''​Scalar''​ ''​delta''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​hypersimplex:​}} + ?  **''​hypersimplex([[.:​common#​Int |Int]] k, [[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​k'':​ number of 1s + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ ambient dimension + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_vertices'':​ do not compute vertices + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_facets'':​ do not compute facets + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_vif'':​ do not compute vertices in facets + ? Returns: + :''​[[.:​polytope:​Polytope |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);​ + ​ + + + ---- + {{anchor:​hypertruncated_cube:​}} + ? **''​hypertruncated_cube<​Scalar>​([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​Scalar''​ ''​k'':​ cutoff parameter + :: ''​Scalar''​ ''​lambda'':​ scaling of extra vertex + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​Scalar>''​ + + + ---- + {{anchor:​k_cyclic:​}} + ? **''​k_cyclic([[.:​common#​Int |Int]] n, [[.:​common#​Vector |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of points + :: ''​[[.:​common#​Vector |Vector]]''​ ''​s'':​ s=(s_1,​...,​s_k) + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + ? Example: + :: To produce a (not exactly) regular pentagon, type this: + :: >$p = k_cyclic(5,​[1]);​ + ​ + + + ---- + {{anchor:​klee_minty_cube:​}} + ?  **''​klee_minty_cube([[.:​common#​Int |Int]] d, Scalar e)''​** + :: Produces a //​d//​-dimensional Klee-Minty-cube if //​e//<​1/​2. Uses the ''​[[.:​polytope#​goldfarb |goldfarb]]''​ client with //g//=0. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​Scalar''​ ''​e''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​lecture_hall_simplex:​}} + ?  **''​lecture_hall_simplex([[.:​common#​Int |Int]] d)''​** + :: Produce a lecture hall //​d//​-simplex. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​long_and_winding:​}} + ?  **''​long_and_winding([[.:​common#​Int |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 ''​[[.:​polytope#​perturbed_long_and_winding |perturbed_long_and_winding]]''​. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​r'':​ defining parameter + ? Options: + : + :: ''​[[.:​common#​Rational |Rational]]''​ ''​eval_ratio'':​ parameter for evaluating the puiseux rational functions + :: ''​[[.:​common#​Int |Int]]''​ ''​eval_exp'':​ to evaluate at eval_ratio^eval_exp,​ default: 1 + :: ''​[[.:​common#​Float |Float]]''​ ''​eval_float'':​ parameter for evaluating the puiseux rational functions + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​PuiseuxFraction |PuiseuxFraction]]<​[[.:​common#​Max |Max]],​[[.:​common#​Rational |Rational]],​[[.:​common#​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);​ + ​ + + + ---- + {{anchor:​max_gc_rank:​}} + ?  **''​max_GC_rank([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​multiplex:​}} + ?  **''​multiplex([[.:​common#​Int |Int]] d, [[.:​common#​Int |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, + .. see also + > 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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​[[.:​common#​Int |Int]]''​ ''​n''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​n_gon:​}} + ?  **''​n_gon([[.:​common#​Int |Int]] n, [[.:​common#​Rational |Rational]] r, [[.:​common#​Rational |Rational]] alpha_0)''​** + :: Produce a regular //n//-gon. All vertices lie on a circle of radius //r//. The radius defaults to 1. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of vertices + :: ''​[[.:​common#​Rational |Rational]]''​ ''​r'':​ the radius (defaults to 1) + :: ''​[[.:​common#​Rational |Rational]]''​ ''​alpha_0'':​ the initial angle divided by pi (defaults to 0) + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​neighborly_cubical:​}} + ? **''​neighborly_cubical([[.:​common#​Int |Int]] d, [[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ dimension of the polytope + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ dimension of the equivalent cube + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​newton:​}} + ? **''​newton([[.:​common#​Polynomial |Polynomial]] p)''​** + :: Produce the Newton polytope of a polynomial //p//. + ? Parameters: + :: ''​[[.:​common#​Polynomial |Polynomial]]''​ ''​p''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |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 + ​ + + + ---- + {{anchor:​perles_irrational_8_polytope:​}} + ? **''​perles_irrational_8_polytope()''​** + :: Create an 8-dimensional polytope without rational realizations due to Perles + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​permutahedron:​}} + ? **''​permutahedron([[.:​common#​Int |Int]] d)''​** + :: Produce a //​d//​-dimensional permutahedron. The vertices correspond to the elements of the symmetric group of degree //d//+1. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​perturbed_long_and_winding:​}} + ? **''​perturbed_long_and_winding([[.:​common#​Int |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 ''​[[.:​polytope#​long_and_winding |long_and_winding]]'',​ which yields simple polytopes. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​r'':​ defining parameter + ? Options: + : + :: ''​[[.:​common#​Rational |Rational]]''​ ''​eval_ratio'':​ parameter for evaluating the puiseux rational functions + :: ''​[[.:​common#​Int |Int]]''​ ''​eval_exp'':​ to evaluate at eval_ratio^eval_exp,​ default: 1 + :: ''​[[.:​common#​Float |Float]]''​ ''​eval_float'':​ parameter for evaluating the puiseux rational functions + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​PuiseuxFraction |PuiseuxFraction]]<​[[.:​common#​Max |Max]],​[[.:​common#​Rational |Rational]],​[[.:​common#​Rational |Rational]]%%>>​%%''​ + ? Example: + :: This yields a simple 4-polytope over the field of Puiseux fractions. + :: >$p = perturbed_long_and_winding(2);​ + ​ + + + ---- + {{anchor:​pile:​}} + ?  **''​pile([[.:​common#​Vector |Vector]]<​[[.:​common#​Int |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: + :: ''​[[.:​common#​Vector |Vector]]<​[[.:​common#​Int |Int]]>''​ ''​sizes'':​ a vector (s<​sub>​1,​...,​s<​sub>​d, ​  where s<​sub>​i​ specifies the number of boxes in the i-th dimension. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​pseudo_delpezzo:​}} + ?  **''​pseudo_delpezzo([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |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:​Polytope |Polytope]]<​Scalar>''​ + + + ---- + {{anchor:​rand01:​}} + ?  **''​rand01([[.:​common#​Int |Int]] d, [[.:​common#​Int |Int]] n)''​** + :: Produce a //​d//​-dimensional 0/​1-polytope with //n// random vertices. Uniform distribution. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of random vertices + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. ​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​rand_box:​}} + ?  **''​rand_box([[.:​common#​Int |Int]] d, [[.:​common#​Int |Int]] n, [[.:​common#​Int |Int]] b)''​** + :: Computes the convex hull of //n// points sampled uniformly at random from the integer points in the cube [0,//​b//​]<​sup>//​d//​. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension of the box + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of random points + :: ''​[[.:​common#​Int |Int]]''​ ''​b'':​ the size of the box + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​rand_cyclic:​}} + ?  **''​rand_cyclic([[.:​common#​Int |Int]] d, [[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of vertices + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​rand_metric:​}} + ?  **''​rand_metric<​Scalar>​([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​n''​ + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. ​ + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]''​ + + + ---- + {{anchor:​rand_metric_int:​}} + ?  **''​rand_metric_int<​Scalar>​([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​n''​ + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. ​ + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]''​ + + + ---- + {{anchor:​rand_normal:​}} + ?  **''​rand_normal([[.:​common#​Int |Int]] d, [[.:​common#​Int |Int]] n)''​** + :: Produce a rational //​d//​-dimensional polytope from //n// random points approximately normally distributed in the unit ball. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension of ball + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of random points + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. ​ + :: ''​[[.:​common#​Int |Int]]''​ ''​precision'':​ Number of bits for MPFR sphere approximation + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |Rational]]>''​ + + + ---- + {{anchor:​rand_sphere:​}} + ?  **''​rand_sphere<​Num>​([[.:​common#​Int |Int]] d, [[.:​common#​Int |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 ''​[[.:​common#​AccurateFloat |AccurateFloat]]''​ the distribution should be closer to uniform, but the vertices will not exactly be on the sphere. With ''​[[.:​common#​Rational |Rational]]''​ the vertices are guaranteed to be on the unit sphere, at the expense of both uniformity and log-height of points. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension of sphere + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of random vertices + ? Options: + : + :: ''​[[.:​common#​Int |Int]]''​ ''​seed'':​ controls the outcome of the random number generator; ​  ​fixing a seed number guarantees the same outcome. ​ + :: ''​[[.:​common#​Int |Int]]''​ ''​precision'':​ Number of bits for MPFR sphere approximation + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |Rational]]>''​ + + + ---- + {{anchor:​rss_associahedron:​}} + ?  **''​rss_associahedron([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​l'':​ ambient dimension + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​signed_permutahedron:​}} + ?  **''​signed_permutahedron([[.:​common#​Int |Int]] d)''​** + :: Produce a //​d//​-dimensional signed permutahedron. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​simplex:​}} + ?  **''​simplex([[.:​common#​Int |Int]] d, Scalar scale)''​** + :: Produce the standard //​d//​-simplex. Combinatorially equivalent to a regular polytope corresponding to the Coxeter group of type A<​sub>//​d//​-1​. Optionally, the simplex can be scaled by the parameter //scale//. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​Scalar''​ ''​scale'':​ default value: 1 + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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);​ + ​ + + + ---- + {{anchor:​stable_set:​}} + ?  **''​stable_set([[.:​graph:​Graph |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:​Graph |Graph]]''​ ''​G''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​transportation:​}} + ?  **''​transportation([[.:​common#​Vector |Vector]] r, [[.:​common#​Vector |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: + :: ''​[[.:​common#​Vector |Vector]]''​ ''​r''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​c''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​upper_bound_theorem:​}} + ?  **''​upper_bound_theorem([[.:​common#​Int |Int]] d, [[.:​common#​Int |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 ''​[[.:​polytope:​Polytope#​H_VECTOR |H_VECTOR]]''​ and the ''​[[.:​polytope:​Polytope#​F_VECTOR |F_VECTOR]]''​. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of points + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​zonotope:​}} + ?  **''​zonotope([[.:​common#​Matrix |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 ''​[[.:​polytope:​Polytope#​ZONOTOPE_INPUT_POINTS |ZONOTOPE_INPUT_POINTS]]''​. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]<​Scalar>''​ ''​M'':​ input points or vectors + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​rows_are_points'':​ true if M are points instead of vectors; default true + :: ''​[[.:​common#​Bool |Bool]]''​ ''​centered'':​ true if output should be centered; default true + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​zonotope_vertices_fukuda:​}} + ?  **''​zonotope_vertices_fukuda([[.:​common#​Matrix |Matrix]] M)''​** + :: Create the vertices of a zonotope from a matrix whose rows are input points or vectors. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​M''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​centered_zonotope'':​ default 1 + ? Returns: + :''​[[.:​common#​Matrix |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. + ---- + {{anchor:​free_sum:​}} + ?  **''​free_sum([[.:​polytope:​VectorConfiguration |VectorConfiguration]] P1, [[.:​polytope:​VectorConfiguration |VectorConfiguration]] P2)''​** + :: Construct the free sum of two vector configurations. + ? Parameters: + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​P1''​ + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​P2''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​force_centered'':​ if the input polytopes must be centered. Defaults to true. + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_coordinates'':​ produces a pure combinatorial description. Defaults to false. + ? Returns: + :''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ + + + ---- + {{anchor:​project_full:​}} + ?  **''​project_full<​Scalar>​([[.:​polytope:​VectorConfiguration |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: + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​P''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​no_labels'':​ Do not copy ''​[[.:​polytope:​Polytope#​VERTEX_LABELS |VERTEX_LABELS]]''​ to the projection. default: 0 + ? Returns: + :''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ + + + ---- + {{anchor:​project_out:​}} + ?  **''​project_out<​Scalar>​([[.:​polytope:​VectorConfiguration |VectorConfiguration]] V, [[.:​common#​Matrix |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: + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​V''​ + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​B'':​ a matrix whose rows contain the basis of the space to be projected out + ? Returns: + :''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ + ?  **''​project_out<​Scalar>​([[.:​polytope:​Cone |Cone]] C, [[.:​common#​Matrix |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​C''​ + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​B'':​ a matrix whose rows contain the basis of the space to be projected out + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]''​ + + + ---- + {{anchor:​project_to:​}} + ?  **''​project_to<​Scalar>​([[.:​polytope:​VectorConfiguration |VectorConfiguration]] V, [[.:​common#​Matrix |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: + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​V''​ + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​B'':​ a matrix whose rows contain the basis of the image space + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​make_affine'':​ . If undef (default), apply the above reasoning. If 1 (0), unconditionally (don'​t) add leading 1's. + ? Returns: + :''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ + ?  **''​project_to<​Scalar>​([[.:​polytope:​Cone |Cone]] C, [[.:​common#​Matrix |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: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​C''​ + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​B'':​ a matrix whose rows contain the basis of the image space + ? Returns: + :''​[[.:​polytope:​Cone |Cone]]''​ + + + ---- + {{anchor:​projection:​}} + ?  **''​projection<​Scalar>​([[.:​polytope:​VectorConfiguration |VectorConfiguration]] P, [[.:​common#​Array |Array]]<​[[.:​common#​Int |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: + :: ''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ ''​P''​ + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]>''​ ''​indices''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​revert'':​ inverts the coordinate list + ? Returns: + :''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ + + + ---- + {{anchor:​projection_preimage:​}} + ?  **''​projection_preimage<​Scalar>​([[.:​common#​Array |Array]]<​[[.:​polytope:​VectorConfiguration |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: + :: ''​[[.:​common#​Array |Array]]<​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]>''​ ''​P_Array''​ + ? Returns: + :''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ + + + ---- + + ==== Producing other objects ==== + ​Functions producing big objects which are not contained in application polytope. + ---- + {{anchor:​coxeter_group:​}} + ?  **''​coxeter_group([[.:​common#​String |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 [[/​polytope/​functions/​Producing regular polytopes and their generalizations/​simple_roots_type_A|simple_roots_type_*]]. + ? Parameters: + :: ''​[[.:​common#​String |String]]''​ ''​type'':​ the type of the Coxeter group + ? Returns: + :''​[[.:​group:​Group |Group]]''​ + + + ---- + {{anchor:​crosscut_complex:​}} + ?  **''​crosscut_complex([[.:​polytope:​Polytope |Polytope]] p)''​** + :: Produce the __crosscut complex__ of the boundary of a polytope. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​p''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​geometric_realization'':​ create a ''​[[.:​topaz:​GeometricSimplicialComplex |GeometricSimplicialComplex]]'';​ default is true + ? Returns: + :''​[[.:​topaz:​SimplicialComplex |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. + ---- + {{anchor:​archimedean_solid:​}} + ?  **''​archimedean_solid([[.:​common#​String |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: + :: ''​[[.:​common#​String |String]]''​ ''​s'':​ the name of the desired Archimedean solid + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + ? Example: + :: To show the mirror image of the snub cube use: + :: > scale(archimedean_solid('​snub_cube'​),​-1)->​VISUAL;​ + ​ + + + ---- + {{anchor:​catalan_solid:​}} + ?  **''​catalan_solid([[.:​common#​String |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: + :: ''​[[.:​common#​String |String]]''​ ''​s'':​ the name of the desired Catalan solid + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​cross:​}} + ?  **''​cross<​Scalar>​([[.:​common#​Int |Int]] d, Scalar scale)''​** + :: Produce a //​d//​-dimensional cross polytope. Regular polytope corresponding to the Coxeter group of type B<​sub>//​d//​-1​ = C<​sub>//​d//​-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: + :: ''​[[.:​common#​Int |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: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group'':​ add a symmetry group description to the resulting polytope + :: ''​[[.:​common#​Bool |Bool]]''​ ''​character_table'':​ add the character table to the symmetry group description,​ if 0<​d<​7;​ default 1 + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​cube:​}} + ?  **''​cube<​Scalar>​([[.:​common#​Int |Int]] d, Scalar x_up, Scalar x_low)''​** + :: Produce a //​d//​-dimensional cube. Regular polytope corresponding to the Coxeter group of type B<​sub>//​d//​-1​ = C<​sub>//​d//​-1​. The bounding hyperplanes are x<​sub>​i​ <= //x_up// and x<​sub>​i​ >= //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: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + :: ''​Scalar''​ ''​x_up'':​ upper bound in each dimension + :: ''​Scalar''​ ''​x_low'':​ lower bound in each dimension + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group'':​ add a symmetry group description to the resulting polytope + :: ''​[[.:​common#​Bool |Bool]]''​ ''​character_table'':​ add the character table to the symmetry group description,​ if 0<​d<​7;​ default 1 + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​cuboctahedron:​}} + ?  **''​cuboctahedron()''​** + :: Create cuboctahedron. ​ An Archimedean solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​dodecahedron:​}} + ?  **''​dodecahedron()''​** + :: Create exact regular dodecahedron in Q(sqrt{5}). ​ A Platonic solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​icosahedron:​}} + ?  **''​icosahedron()''​** + :: Create exact regular icosahedron in Q(sqrt{5}). ​ A Platonic solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​icosidodecahedron:​}} + ?  **''​icosidodecahedron()''​** + :: Create exact icosidodecahedron in Q(sqrt{5}). ​ An Archimedean solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​johnson_solid:​}} + ?  **''​johnson_solid([[.:​common#​Int |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 ''​[[.:​polytope:​Polytope#​VERTICES_IN_FACETS |VERTICES_IN_FACETS]]''​ is correct in all cases. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the index of the desired Johnson polytope + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + ?  **''​johnson_solid([[.:​common#​String |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 ''​[[.:​polytope:​Polytope#​VERTICES_IN_FACETS |VERTICES_IN_FACETS]]''​ is correct in all cases. + ? Parameters: + :: ''​[[.:​common#​String |String]]''​ ''​s'':​ the name of the desired Johnson polytope + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​octahedron:​}} + ?  **''​octahedron()''​** + :: Produce a regular octahedron, which is the same as the 3-dimensional cross polytope. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​platonic_solid:​}} + ?  **''​platonic_solid([[.:​common#​String |String]] s)''​** + :: Create Platonic solid of the given name. + ? Parameters: + :: ''​[[.:​common#​String |String]]''​ ''​s'':​ the name of the desired Platonic solid + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​reduced:​}} + ?  **''​reduced([[.:​common#​Rational |Rational]] t, [[.:​common#​Rational |Rational]] x, [[.:​common#​Rational |Rational]] s, [[.:​common#​Rational |Rational]] h, [[.:​common#​Rational |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: + :: ''​[[.:​common#​Rational |Rational]]''​ ''​t''​ + :: ''​[[.:​common#​Rational |Rational]]''​ ''​x''​ + :: ''​[[.:​common#​Rational |Rational]]''​ ''​s''​ + :: ''​[[.:​common#​Rational |Rational]]''​ ''​h''​ + :: ''​[[.:​common#​Rational |Rational]]''​ ''​r''​ + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]<​[[.:​common#​Rational |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);​ + ​ + + + ---- + {{anchor:​regular_120_cell:​}} + ? **''​regular_120_cell()''​** + :: Create exact regular 120-cell in Q(sqrt{5}). + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​regular_24_cell:​}} + ? **''​regular_24_cell()''​** + :: Create regular 24-cell. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​regular_600_cell:​}} + ? **''​regular_600_cell()''​** + :: Create exact regular 600-cell in Q(sqrt{5}). + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​regular_simplex:​}} + ? **''​regular_simplex([[.:​common#​Int |Int]] d)''​** + :: Produce a regular //​d//​-simplex embedded in R^d with edge length sqrt(2). + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​d'':​ the dimension + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​group''​ + ? Returns: + :''​[[.:​polytope:​Polytope |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(c) 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 + ​ + + + ---- + {{anchor:​rhombicosidodecahedron:​}} + ?  **''​rhombicosidodecahedron()''​** + :: Create exact rhombicosidodecahedron in Q(sqrt{5}). ​ An Archimedean solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​rhombicuboctahedron:​}} + ?  **''​rhombicuboctahedron()''​** + :: Create rhombicuboctahedron. ​ An Archimedean solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​root_system:​}} + ?  **''​root_system([[.:​common#​String |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: + :: ''​[[.:​common#​String |String]]''​ ''​type'':​ the type of the Coxeter arrangement,​ for example A4 or E8 + ? Returns: + :''​[[.:​polytope:​VectorConfiguration |VectorConfiguration]]''​ + + + ---- + {{anchor:​simple_roots_type_a:​}} + ?  **''​simple_roots_type_A([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​index'':​ of the arrangement (3, 4, etc) + ? Returns: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_b:​}} + ?  **''​simple_roots_type_B([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​index'':​ of the arrangement (3, 4, etc) + ? Returns: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_c:​}} + ?  **''​simple_roots_type_C([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​index'':​ of the arrangement (3, 4, etc) + ? Returns: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_d:​}} + ?  **''​simple_roots_type_D([[.:​common#​Int |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: + :: ''​[[.:​common#​Int |Int]]''​ ''​index'':​ of the arrangement (3, 4, etc) + ? Returns: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_e6:​}} + ?  **''​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: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_e7:​}} + ?  **''​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: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_e8:​}} + ?  **''​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: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_f4:​}} + ?  **''​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: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_g2:​}} + ?  **''​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: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_h3:​}} + ?  **''​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: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​simple_roots_type_h4:​}} + ?  **''​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: + :''​[[.:​common#​SparseMatrix |SparseMatrix]]''​ + + + ---- + {{anchor:​tetrahedron:​}} + ?  **''​tetrahedron()''​** + :: Create regular tetrahedron. ​ A Platonic solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​truncated_cube:​}} + ?  **''​truncated_cube()''​** + :: Create truncated cube.  An Archimedean solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​truncated_cuboctahedron:​}} + ?  **''​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:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​truncated_dodecahedron:​}} + ?  **''​truncated_dodecahedron()''​** + :: Create exact truncated dodecahedron in Q(sqrt{5}). ​ An Archimedean solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​truncated_icosahedron:​}} + ?  **''​truncated_icosahedron()''​** + :: Create exact truncated icosahedron in Q(sqrt{5}). ​ An Archimedean solid. Also known as the soccer ball. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​truncated_icosidodecahedron:​}} + ?  **''​truncated_icosidodecahedron()''​** + :: Create exact truncated icosidodecahedron in Q(sqrt{5}). ​ An Archimedean solid. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​truncated_octahedron:​}} + ?  **''​truncated_octahedron()''​** + :: Create truncated octahedron. ​ An Archimedean solid. Also known as the 3-permutahedron. + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​wythoff:​}} + ?  **''​wythoff([[.:​common#​String |String]] type, [[.:​common#​Set |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: + :: ''​[[.:​common#​String |String]]''​ ''​type'':​ single letter followed by rank representing the type of the arrangement + :: ''​[[.:​common#​Set |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: + : + :: ''​[[.:​common#​Bool |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:​Polytope |Polytope]]''​ + + + ---- + + ==== Quotient spaces ==== + ​Topologic cell complexes defined as quotients over polytopes modulo a discrete group. + ---- + {{anchor:​cs_quotient:​}} + ?  **''​cs_quotient([[.:​polytope:​Polytope |Polytope]] P)''​** + :: For a centrally symmetric polytope, divide out the central symmetry, i.e, identify diametrically opposite faces. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |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. + + + ---- + {{anchor:​cylinder_2:​}} + ? **''​cylinder_2()''​** + :: Return a 2-dimensional __cylinder__ obtained by identifying two opposite sides of a square. + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​davis_manifold:​}} + ?  **''​davis_manifold()''​** + :: Return the 4-dimensional hyperbolic manifold obtained by Michael Davis + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​quarter_turn_manifold:​}} + ? **''​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:​Polytope |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 + ​ + + + ---- + {{anchor:​write_quotient_space_simplexity_ilp:​}} + ?  **''​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. + ---- + {{anchor:​cocircuit_equations_support_reps:​}} + ?  **''​cocircuit_equations_support_reps([[.:​common#​Matrix |Matrix]]<​Scalar>​ points, [[.:​common#​Array |Array]]<​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]%%>>​%% gens, [[.:​common#​Array |Array]]<​SetType>​ rirs, [[.:​common#​Array |Array]]<​SetType>​ rmis)''​** + :: write the indices of the representatives of the support of the cocircuit equations to a file + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]<​Scalar>''​ ''​points''​ + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]%%>>​%%''​ ''​gens'':​ the generators of the action of the symmetry group + :: ''​[[.:​common#​Array |Array]]<​SetType>''​ ''​rirs'':​ representatives of interior ridge simplices + :: ''​[[.:​common#​Array |Array]]<​SetType>''​ ''​rmis'':​ representatives of maximal interior simplices + ? Options: + : + :: ''​[[.:​common#​String |String]]''​ ''​filename'':​ where large output should go to. '​filename=>"​-"'​ writes to stdout. + ? Returns: + :''​[[.:​common#​Int |Int]]''​ + + + ---- + {{anchor:​combinatorial_symmetries:​}} + ?  **''​combinatorial_symmetries([[.:​polytope:​Polytope |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:​Polytope |Polytope]]''​ ''​p''​ + ? Returns: + :''​[[.:​group:​PermutationAction |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 + ​ + + + ---- + {{anchor:​combinatorial_symmetrized_cocircuit_equations:​}} + ?  **''​combinatorial_symmetrized_cocircuit_equations([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> comps)''​** + :: calculate a sparse representation of the cocircuit equations corresponding to a direct sum of isotypic components + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |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([[.:​polytope:​Cone |Cone]] P, [[.:​common#​Array |Array]]<​SetType>​ rirs, [[.:​common#​Array |Array]]<​SetType>​ rmis, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> comps)''​** + :: calculate the projection of the cocircuit equations to a direct sum of isotypic components and represent it combinatorially + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​P''​ + :: ''​[[.:​common#​Array |Array]]<​SetType>''​ ''​rirs'':​ representatives of interior ridge simplices + :: ''​[[.:​common#​Array |Array]]<​SetType>''​ ''​rmis'':​ representatives of maximal interior simplices + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |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: + : + :: ''​[[.:​common#​String |String]]''​ ''​filename'':​ where large output should go to. '​filename=>"​-"'​ writes to stdout. + ? Returns: + :''​[[.:​common#​Array |Array]]<​[[.:​common#​Pair |Pair]]<​SetType,​[[.:​common#​HashMap |HashMap]]<​SetType,​[[.:​common#​Rational |Rational]]%%>>​%%>''​ + + + ---- + {{anchor:​isotypic_configuration:​}} + ?  **''​isotypic_configuration([[.:​polytope:​Polytope |Polytope]] P, [[.:​common#​Int |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:​Polytope |Polytope]]''​ ''​P'':​ a polytope with a matrix action, or a group::​Group g with a permutation action + :: ''​[[.:​common#​Int |Int]]''​ ''​i'':​ the index of the desired isotypic component + ? Returns: + :''​[[.:​polytope:​PointConfiguration |PointConfiguration]]<​[[.:​common#​Float |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. + + + ---- + {{anchor:​lattice_automorphisms_smooth_polytope:​}} + ?  **''​lattice_automorphisms_smooth_polytope([[.:​polytope:​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:​Polytope |Polytope]]''​ ''​P'':​ the given polytope + ? Returns: + :''​[[.:​common#​Array |Array]]<​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]%%>>​%%''​ + ? Example: + :: > print lattice_automorphisms_smooth_polytope(cube(2));​ + 2 3 0 1 + 1 0 3 2 + 0 2 1 3 + ​ + + + ---- + {{anchor:​linear_symmetries:​}} + ?  **''​linear_symmetries''​** + :: wrapper function to store the symmetry group in the parent object + ? from extension: + : [[:​external_software|bundled:​sympol]] + ?  **''​linear_symmetries([[.:​common#​Matrix |Matrix]] m)''​** + :: Use sympol to compute the linear symmetries of + - the rows of a rational matrix //m//, or + - the RAYS|VERTICES,​ FACETS, or POINTS of a rational cone or polytope //C// (whatever is available, in this order), or + - the VECTORS|POINTS of a rational vector or point configuration //P//. + .. Except for matrices, 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: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​m'':​ | Cone //C// | VectorConfiguration //P// + ? Returns: + :''​[[.:​group:​Group |Group]]''​ + ? from extension: + : [[:​external_software|bundled:​sympol]] + ? Example: + :: > $ls = linear_symmetries(cube(2)->​VERTICES);​ + > print$ls->​PERMUTATION_ACTION->​GENERATORS;​ + 0 2 1 3 + 3 1 2 0 + 2 3 0 1 + ​ + :: > print linear_symmetries(cube(3)->​VERTICES)->​PERMUTATION_ACTION->​GENERATORS;​ + 0 4 2 6 1 5 3 7 + 0 1 4 5 2 3 6 7 + 7 6 5 4 3 2 1 0 + 2 6 0 4 3 7 1 5 + ​ + :: > 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 + ​ + + + ---- + {{anchor:​nestedopgraph:​}} + ?  **''​nestedOPGraph([[.:​common#​Vector |Vector]] gen_point, [[.:​common#​Matrix |Matrix]] points, [[.:​common#​Matrix |Matrix]] lattice_points,​ [[.:​group:​Group |Group]] group, [[.:​common#​Bool |Bool]] verbose)''​** + :: Constructs the NOP-graph of an orbit polytope. It is used by the rule for the ''​[[.:​polytope:​Polytope#​NOP_GRAPH |NOP_GRAPH]]''​. + ? Parameters: + :: ''​[[.:​common#​Vector |Vector]]''​ ''​gen_point'':​ the generating point + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​points'':​ the vertices of the orbit polytope + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​lattice_points'':​ the lattice points of the orbit polytope + :: ''​[[.:​group:​Group |Group]]''​ ''​group'':​ the generating group + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print out additional information + ? Returns: + :''​ARRAY''​ + + + ---- + {{anchor:​orbit_polytope:​}} + ?  **''​orbit_polytope([[.:​common#​Vector |Vector]] input_point,​ [[.:​group:​PermutationAction |PermutationAction]] a)''​** + :: Constructs the orbit polytope of a given point //​input_point//​ with respect to a given group action //a//. + ? Parameters: + :: ''​[[.:​common#​Vector |Vector]]''​ ''​input_point'':​ the basis point of the orbit polytope + :: ''​[[.:​group:​PermutationAction |PermutationAction]]''​ ''​a'':​ the action of a permutation group on the coordinates of the ambient space + ? Returns: + :''​[[.:​polytope:​Polytope |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([[.:​common#​Matrix |Matrix]] input_points,​ [[.:​group:​PermutationAction |PermutationAction]] a)''​** + :: Constructs the orbit polytope of a given set of points //​input_points//​ with respect to a given group action //a//. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​input_points'':​ the basis points of the orbit polytope + :: ''​[[.:​group:​PermutationAction |PermutationAction]]''​ ''​a'':​ the action of a permutation group on the coordinates of the ambient space + ? Returns: + :''​[[.:​polytope:​Polytope |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([[.:​common#​Vector |Vector]] input_point,​ [[.:​group:​Group |Group]] g)''​** + :: Constructs the orbit polytope of a given point //​input_point//​ with respect to a given group action //a//. + ? Parameters: + :: ''​[[.:​common#​Vector |Vector]]''​ ''​input_point'':​ the basis point of the orbit polytope + :: ''​[[.:​group:​Group |Group]]''​ ''​g'':​ a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient space + ? Returns: + :''​[[.:​polytope:​Polytope |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([[.:​common#​Matrix |Matrix]] input_points,​ [[.:​group:​Group |Group]] g)''​** + :: Constructs the orbit polytope of a given set of points //​input_points//​ with respect to a given group action //a//. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​input_points'':​ the basis points of the orbit polytope + :: ''​[[.:​group:​Group |Group]]''​ ''​g'':​ a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient space + ? Returns: + :''​[[.:​polytope:​Polytope |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([[.:​common#​Matrix |Matrix]] input_points,​ [[.:​common#​Array |Array]]<​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]%%>>​%% gens)''​** + :: Constructs the orbit polytope of a given set of points //​input_points//​ with respect to a given set of generators //gens//. + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​input_points'':​ the basis point of the orbit polytope + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]%%>>​%%''​ ''​gens'':​ the generators of a permutation group that acts on the coordinates of the ambient space + ? Returns: + :''​[[.:​polytope:​Polytope |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>​([[.:​common#​Vector |Vector]] input_point,​ [[.:​group:​MatrixActionOnVectors |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: + :: ''​[[.:​common#​Vector |Vector]]''​ ''​input_point'':​ the generating point of the orbit polytope + :: ''​[[.:​group:​MatrixActionOnVectors |MatrixActionOnVectors]]''​ ''​a'':​ the action of a matrix group on the coordinates of the ambient space + ? Returns: + :''​[[.:​polytope:​Polytope |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>​([[.:​common#​Matrix |Matrix]]<​Scalar>​ input_points,​ [[.:​group:​MatrixActionOnVectors |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: + :: ''​[[.:​common#​Matrix |Matrix]]<​Scalar>''​ ''​input_points'':​ the generating points of the orbit polytope + :: ''​[[.:​group:​MatrixActionOnVectors |MatrixActionOnVectors]]<​Scalar>''​ ''​a'':​ the action of a matrix group on the coordinates of the ambient space + ? Returns: + :''​[[.:​polytope:​Polytope |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 + ​ + + + ---- + {{anchor:​ortho_project:​}} + ?  **''​ortho_project([[.:​polytope:​Polytope |Polytope]] p)''​** + :: Projects a symmetric polytope in R<​sup>​4​ cap H<​sub>​1,​k​ to R<​sup>​3​. (See also the polymake extension '​tropmat'​ by S. Horn.) + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​p'':​ the symmetric polytope to be projected + ? Returns: + :''​[[.:​polytope:​Polytope |Polytope]]''​ + + + ---- + {{anchor:​representation_conversion_up_to_symmetry:​}} + ?  **''​representation_conversion_up_to_symmetry([[.:​polytope:​Cone |Cone]] c)''​** + :: Computes the dual description of a polytope up to its linear symmetry group. + ? Parameters: + :: ''​[[.:​polytope:​Cone |Cone]]''​ ''​c'':​ the cone (or polytope) whose dual description is to be computed, equipped with a GROUP + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​v_to_h'':​ 1 (default) if converting V to H, false if converting H to V