application: polytope

This is the historically first application, and the largest one.

It deals with convex pointed polyhedra. It allows to define a polyhedron either as a convex hull of a point set, an intersection of halfspaces, or as an incidence matrix without any embedding. Then you can ask for a plenty of its (especially combinatorial) properties, construct new polyhedra by modifying it, or study the behavior of the objective functions.

There is a wide range of visualization methods for polyhedra, even for dimensions > 4 and purely combinatorial descriptions, including interfaces to interactive geometry viewers (such as JavaView or geomview), generating PostScript drawings and povray scene files.

imports from: common, graph
uses: group, ideal, topaz

Objects

User Functions

  •  
    normaliz_compute (C) → perl::ListReturn

    Compute degree one elements, Hilbert basis or Hilbert series of a cone C with libnormaliz Hilbert series and Hilbert h-vector depend on the given grading and will not work unless C is HOMOGENEOUS or a MONOID_GRADING is set

    Parameters
    ConeC
    Options
    Boolfrom_facets
    supply facets instead of rays to normaliz
    Booldegree_one_generators
    compute the generators of degree one, i.e. lattice points of the polytope
    Boolhilbert_basis
    compute Hilbert basis of the cone C
    Boolh_star_vector
    compute Hilbert h-vector of the cone C
    Boolhilbert_series
    compute Hilbert series of the monoid
    Booldual_algorithm
    use the dual algorithm by Pottier
    Boolskip_long
    do not try to use long coordinates first
    Boolverbose
    libnormaliz debug output
    Returns
    perl::ListReturn
    (degree one generators, Hilbert basis, Hilbert h-vector, Hilbert series) (if they are requested)
  •  
    write_foldable_max_signature_ilp ()

    UNDOCUMENTED

    Contained in extension bundled:group.
  •  
    write_quotient_space_simplexity_ilp ()

    UNDOCUMENTED

    Contained in extension bundled:group.
  •  
    write_simplexity_ilp ()

    UNDOCUMENTED

    Contained in extension bundled:group.
  •  
    UNDOCUMENTED
    •  
      violations (P, q) → Set

      Check which relations, if any, are violated by a point.

      Parameters
      PolytopeP
      Vectorq
      Options
      Stringsection
      Which section of P to test against q
      Intviolating_criterion
      has the options: +1 (positive values violate; this is the default), 0 (*non*zero values violate), -1 (negative values violate)
      Returns
      Set
  •  
    UNDOCUMENTED
    •  
      edge_orientable (P)

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

      Parameters
      PolytopeP
  •  
    UNDOCUMENTED
    •  
      congruent (P1, 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
      PolytopeP1
      PolytopeP2
    •  
      equal_polyhedra (P1, P2)

      Tests if the two polyhedra P1 and P2 are equal.

      Parameters
      PolytopeP1
      PolytopeP2
    •  
      find_facet_vertex_permutations (P1, P2) → Pair<Array<Int>, Array<Int>>

      Find the permutations of facets and vertices which maps the cone or polyhedron P1 to P2. The facet permutation is the first component of the return value.

      Only the combinatorial isomorphism is considered. If the polytopes are not isomorphic, an exception is thrown.

    •  
      included_polyhedra (P1, P2)

      Tests if polyhedron P1 is included in polyhedron P2.

      Parameters
      PolytopeP1
      PolytopeP2
    •  
      isomorphic (P1, 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
      ConeP1
      ConeP2
    •  
      lattice_isomorphic_smooth_polytopes (P1, P2)

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

  •  
    UNDOCUMENTED
    •  
      check_inc (points, hyperplanes, sign, verbose)

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

      Parameters
      Matrixpoints
      Matrixhyperplanes
      Stringsign
      composed of one or two characters from [-+0], representing the allowed domain of the vector inner products.
      Boolverbose
      print all products violating the required relation
    •  
      check_poly (VIF) → Polytope

      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
      IncidenceMatrixVIF
      Options
      Booldual
      transposes the incidence matrix
      Boolverbose
      prints information about the check.
      Returns
      Polytope
    •  
      validate_moebius_strip (P) → Bool

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

      Parameters
      PolytopeP
      Returns
      Bool
    •  
      validate_moebius_strip_quads (P) → Matrix<int>

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

      Parameters
      PolytopeP
      Options
      Boolverbose
      Returns
      Matrix<int>
  •  
    UNDOCUMENTED
    •  
      affine_float_coords (P) → Matrix<Float>

      dehomogenize the vertex coordinates and convert them to Float

      Parameters
      PolytopeP
      source object
      Returns
      Matrix<Float>
    •  
      convert_to <Coord> (c) → Cone<Coord>

      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
      Conec
      the input cone
      Returns
      Cone<Coord>
      a new cone object or C itself it has the requested type
    •  
      convert_to <Coord> (P) → Polytope<Coord>

      provide a Polytope object with desired coordinate type

      Type Parameters
      Coord
      target coordinate type
      Parameters
      PolytopeP
      source object
      Returns
      Polytope<Coord>
      P if it already has the requested type, a new object otherwise
  •  
    UNDOCUMENTED
    •  
      all_steiner_points (P) → Matrix

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

      Parameters
      PolytopeP
      Options
      epscontrols
      the accuracy of the angles computed
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Matrix
    •  
      dihedral_angle (H1, H2) → Float

      Compute the dihedral angle between two (oriented) affine or linear hyperplanes.

      Parameters
      Vector<Scalar>H1
      : first hyperplane
      Vector<Scalar>H2
      : second hyperplane
      Options
      deg=>0 : output in degrees rather than radians
      cone=>0 : hyperplanes seen as linear hyperplanes
      Returns
      Float
    •  
      induced_lattice_basis (p) → Matrix<Integer>

      Returns a basis of the affine lattice spanned by the vertices

      Parameters
      Polytopep
      the input polytope
      Returns
      Matrix<Integer>
      - the lattice basis.
    •  
      integer_points_bbox (P) → Matrix<Integer>

      Enumerate all integer points in the given polytope by searching a bounding box.

    •  
      is_vertex (q, points) → Bool

      Checks whether a given point q is a vertex of the polytope P generated by q and a set of other points points via solving a suitable LP (compare cdd redundancy check). Works without knowing the facets of P!

      Parameters
      Vectorq
      the vertex (candidate) which is to be separated from points
      Matrixpoints
      the points from which q is to be separated
      Returns
      Bool
      'true' if q is a vertex
    •  
      minimal_vertex_angle (P) → Float

      Computes the minimal angle between two vertices of the input polytope P.

      Parameters
      PolytopeP
      Returns
      Float
    •  
      print_face_lattice (VIF, 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
      IncidenceMatrixVIF
      Booldual
    •  
      steiner_point (P) → Vector

      Compute the Steiner point of a polyhedron P using a randomized approximation of the angles.

      Parameters
      PolytopeP
      Options
      epscontrols
      the accuracy of the angles computed
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Vector
    •  
      zonotope_tiling_lattice (P) → AffineLattice

      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
      PolytopeP
      the zonotope.
      Options
      lattice_origin_is_vertexBool
      true if the origin of the tiling lattice should be a vertex of P; default false, ie, the origin will be the barycenter of P
      Returns
      AffineLattice
  •  
    UNDOCUMENTED
    •  
      core_point_algo (p, optLPvalue) → perl::ListReturn

      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
      Polytopep
      RationaloptLPvalue
      optimal value of LP approximation
      Options
      Boolverbose
      Returns
      perl::ListReturn
      (optimal solution, optimal value) or empty
    •  
      core_point_algo_Rote (p, optLPvalue) → perl::ListReturn

      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
      Polytopep
      RationaloptLPvalue
      optimal value of LP approximation
      Options
      Boolverbose
      Returns
      perl::ListReturn
      (optimal solution, optimal value) or empty
    •  
      find_transitive_lp_sol (Inequalities) → perl::ListReturn

      Algorithm to solve symmetric linear programs (LP) of the form max ctx , c=(0,1,1,..,1) subject to the inequality system given by Inequalities. It is required that the symmetry group of the LP acts transitively on the coordinate directions.

      Parameters
      MatrixInequalities
      the inequalities describing the feasible region
      Returns
      perl::ListReturn
      (optLPsolution,optLPvalue,feasible,max_bounded)
    •  
      inner_point (points)

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

      Parameters
      Matrixpoints
    •  
      lp2poly (file) → Polytope<Float>

      Read a linear programming problem given in LP-Format (as used by cplex & Co.) and convert it to a Polytope<Float> object

      WARNING The property FEASIBLE is NOT computed upon creation. This is done to avoid possibly long computation times before the object becomes available to the caller. This is NOT in keeping with standard practice in polymake, but after, all, these are linear programs and not polytopes.

      Parameters
      Stringfile
      filename of a linear programming problem in LP-Format
      Options
      Vectortestvec
      If present, after reading in each line of the LP it is checked whether testvec fulfills it
      Stringprefix
      If testvec is present, all variables in the LP file are assumed to have the form $prefix$i
      Returns
      Polytope<Float>
    •  
      poly2lp (P, LP, maximize, 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
      PolytopeP
      LinearProgramLP
      default value: P->LP
      Boolmaximize
      produces a maximization problem; default value: 0 (minimize)
      Stringfile
      default value: standard output
    •  
      porta2poly (file) → Polytope<Rational>

      Read an .ieq or .poi file (porta input) or .poi.ieq or .ieq.poi (porta output) and convert it to a Polytope<Rational> object

      Parameters
      Stringfile
      filename of a porta file (.ieq or .poi)
      Returns
      Polytope<Rational>
    •  
      print_constraints (P) → bool

      Write the FACETS / INEQUALITIES and the AFFINE_HULL / EQUATIONS of a polytope P in a readable way. COORDINATE_LABELS are adopted if present.

      Parameters
      Polytope<Scalar>P
      the given polytope
      Returns
      bool
    •  
      random_edge_epl (G) → Vector<Rational>

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

      Parameters
      Graph<Directed>G
      a directed graph
      Returns
      Vector<Rational>
    •  
      rand_aof (P, start) → Vector<Rational>

      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
      PolytopeP
      a simple polytope
      Intstart
      the index of the starting vertex; default value: random
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Vector<Rational>
    •  
      rel_int_point (P)

      Computes a relative interior point of a polyhedron P and stores it in P->REL_INT_POINT. The unbounded flag needs to be set to true if the polyhedron could be unbounded.

      Parameters
      PolytopeP
    •  
      separating_hyperplane (q, points) → ListReturn

      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 returns a zero vector and sets answer to 'false'. Works without knowing the facets of P!

      Parameters
      Vectorq
      the vertex (candidate) which is to be separated from points
      Matrixpoints
      the points from which q is to be separated
      Returns
      ListReturn
      (Bool answer, Vector sep_hyp)
    •  
      separating_hyperplane_poly (p1, p2) → Vector

      Computes (the normal vector of) a hyperplane which separates two given polytopes p1 and p2 if possible.

      Parameters
      Polytopep1
      the first polytope
      Polytopep2
      the second polytope
      Returns
      Vector
      a hyperplane separating p1 from p2
    •  
      totally_dual_integral (inequalities) → Bool

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

      Parameters
      Matrixinequalities
      Returns
      Bool
    •  
      vertex_colors (P, LP) → Array<RGB>

      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
      PolytopeP
      LinearProgramLP
      Options
      RGBmin
      the minimal RGB value
      RGBmax
      the maximal RGB value
      Returns
      Array<RGB>
  •  
    UNDOCUMENTED
    •  
      wronski_system (M, lambda, coeff_array, s)

      returns a Wronski system of a topaz::FOLDABLE triangulation of a lattice polytope

      Parameters
      Matrix<Int>M
      points (in homogeneous coordinates); affinely span the space
      Vector<Int>lambda
      height function on lattice points
      Array<Array<Rational>>coeff_array
      coefficients
      Scalar<Rational>s
      additional Parameter in the polynomial
      Options
      topaz::SimplicialComplextriangulation
      The triangulation of the pointset corresponding to the lifting function
      Ringring
      the ring in which the polynomial should be
  •  
    UNDOCUMENTED
  •  

    Another important way of constructing polytopes is to modify an already existing polytope.

    Actually, these function 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.

    •  
      UNDOCUMENTED
      •  
        wronski_center_ideal (L, lambda)

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

        Parameters
        Matrix<Int>L
        lattice points
        Vector<Int>lambda
        height function on lattice points
      •  
        wronski_polynomial (M, lambda, coeff, s)

        retuns a Wronski polynomial of a topaz::FOLDABLE triangulation of a lattice polytope

        Parameters
        Matrix<Int>M
        points (in homogeneous coordinates); affinely span the space
        Vector<Int>lambda
        height function on lattice points
        Array<Rational>coeff
        coefficients
        Scalar<Rational>s
        additional Parameter in the polynomial
        Options
        topaz::SimplicialComplextriangulation
        The triangulation of the pointset corresponding to the lifting function
        Ringring
        the ring in which the polynomial should be
    •  
      UNDOCUMENTED
      •  
        cut_polytope (G) → Polytope

        Cut polytope of an undirected graph.

        Parameters
        GraphG
        Returns
        Polytope
      •  
        matching_polytope (G) → Polytope

        Matching polytope of an undirected graph.

        Parameters
        GraphG
        Returns
        Polytope
      •  
        tutte_lifting (G) → Polytope

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

        Parameters
        GraphG
        Returns
        Polytope
    •  
      UNDOCUMENTED
      •  
        bipyramid (P, z, 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
        PolytopeP
        Scalarz
        distance between the vertex barycenter and the first apex, default value is 1.
        Scalarz_prime
        distance between the vertex barycenter and the second apex, default value is -z.
        Options
        Boolnoc
        : don't compute the coordinates, purely combinatorial description is produced.
        Boolrelabel
        copy the vertex labels from the original polytope, label the new vertices with "Apex" and "Apex'".
      •  
        blending (P1, v1, P2, v2) → Polytope

        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
        PolytopeP1
        Intv1
        the index of the first vertex
        PolytopeP2
        Intv2
        the index of the second vertex
        Options
        Array<Int>permutation
        Boolrelabel
        copy vertex labels from the original polytope
        Returns
        Polytope
      •  
        cayley_embedding (P, P_prime, z, z_prime) → Polytope

        Create a Cayley embedding of two polytopes (one of them must be pointed). The vertices of the first polytope P get an extra coordinate z and the vertices of the second polytope P_prime get z_prime.

        Default values are z=1 and z_prime=-z.

        The option relabel creates an additional section VERTEX_LABELS. The vertices of P inherit the original labels unchanged; the vertex labels of P_prime get a tick (') appended.

        Parameters
        PolytopeP
        the first polytope
        PolytopeP_prime
        the second polytope
        Scalarz
        the extra coordinate for the vertices of P
        Scalarz_prime
        the extra coordinate for the vertices of P_prime
        Options
        Boolrelabel
        Returns
        Polytope
      •  
        cayley_polytope (P_Array) → Polytope

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

        Parameters
        Array<LatticePolytope>P_Array
        an array containing the lattice polytopes P1,...,Pk
        Options
        Boolproj
        Returns
        Polytope
      •  
        cells_from_subdivision (P, cells) → Polytope<Scalar>

        Extract the given cells of the subdivision of a polyhedron and write their union as a new polyhedron.

        Parameters
        Polytope<Scalar>P
        Set<Int>cells
        Options
        Boolrelabel
        copy the vertex labels from the original polytope
        Returns
        Polytope<Scalar>
      •  
        cell_from_subdivision (P, cell) → Polytope

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

        Parameters
        PolytopeP
        Intcell
        Options
        Boolrelabel
        copy the vertex labels from the original polytope
        Returns
        Polytope
      •  
        conv (P_Array) → PropagatedPolytope

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

        Parameters
        Array<Polytope>P_Array
        Returns
        PropagatedPolytope
      •  
        dual_linear_program (P, maximize) → Polytope

        Produces a polyhedron with an totally dual integral inequality formulation of a full dimensional polyhedron

        Parameters
        PolytopeP
        boolmaximize
        weather we maximize our primal problem or not. Default value is 0 (= minimize)
        Returns
        Polytope
      •  
        edge_middle (P) → Polytope

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

        Parameters
        PolytopeP
        Returns
        Polytope
      •  
        facet (P, facet) → Cone

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

        Parameters
        ConeP
        Intfacet
        Options
        Boolnoc
        don't copy the coordinates, produce purely combinatorial description.
        Boolrelabel
        copy the vertex labels from the original polytope.
        Returns
        Cone
      •  
        facet_to_infinity (i) → Polytope

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

        Parameters
        Inti
        the facet index
        Returns
        Polytope
      •  
        free_sum (P1, P2) → Polytope

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

        Parameters
        PolytopeP1
        PolytopeP2
        Returns
        Polytope
      •  
        gc_closure (P) → Polytope

        Produces the gomory-chvatal closure of a full dimensional polyhedron

        Parameters
        PolytopeP
        Returns
        Polytope
      •  
        integer_hull (P) → Polytope

        Produces the integer hull of a polyhedron

        Parameters
        PolytopeP
        Returns
        Polytope
      •  
        intersection (C ...) → Cone

        Construct a new polyhedron or cone as the intersection of given polyhedra and/or cones. Works only if all CONE_AMBIENT_DIM values are equal. If the input contains both cones and polytopes, the output will be a polytope.

        Parameters
        ConeC ...
        polyhedra and cones to be intersected
        Returns
        Cone
      •  
        join_polytopes (P1, P2) → Polytope

        Construct a new polyhedron as the join of two given pointed ones.

        Parameters
        PolytopeP1
        PolytopeP2
        Returns
        Polytope
      •  
        lattice_bipyramid (P, v, v_prime, z, z_prime) → Polytope

        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
        PolytopeP
        Vectorv
        basis point for the first apex
        Vectorv_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.
        Rationalz
        height for the first apex, default value is 1
        Rationalz_prime
        height for the second apex, default value is -z
        Options
        Boolrelabel
        copy the vertex labels from the original polytope, label the new vertices with "Apex" and "Apex'".
        Returns
        Polytope
      •  
        lattice_pyramid (P, z, v) → Polytope

        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
        PolytopeP
        Rationalz
        the height for the apex (v,z), default value is 1.
        Vectorv
        the lattice point to use as apex, default is the first vertex of P.
        Options
        Boolrelabel
        copy the original vertex labels, label the new top vertex with "Apex".
        Returns
        Polytope
      •  
        lawrence (P) → Cone

        Create the Lawrence polytope Lambda(P) corresponding to P. If V is the matrix whose rows are the n vertices of P, then the vertices of Lambda(P) are the rows of the matrix ( V I_n ) ( 0_n I_n ). Lambda(P) has the property that Gale(Lambda(P)) = Gale(P) union -Gale(P).

        Parameters
        ConeP
        an input cone or polytope
        Returns
        Cone
        the Lawrence cone or polytope to P
      •  
        make_totally_dual_integral (P) → Polytope

        Produces a polyhedron with an totally dual integral inequality formulation of a full dimensional polyhedron

        Parameters
        PolytopeP
        Returns
        Polytope
      •  
        mapping_polytope (P1, P2) → Polytope

        Construct a new polytope as the mapping polytope of two polytopes P1 and P2. The mapping polytope is the set of all affine maps from Rp to Rq, that map P1 into P2.

        The label of a new facet corresponding to v1 and h1 will have the form "v1*h1".

        Parameters
        PolytopeP1
        PolytopeP2
        Options
        Boolrelabel
        Returns
        Polytope
      •  
        minkowski_sum (lambda, P1, mu, P2) → Polytope

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

        Parameters
        Scalarlambda
        PolytopeP1
        Scalarmu
        PolytopeP2
        Returns
        Polytope
      •  
        minkowski_sum (P1, P2) → Polytope

        Produces the Minkowski sum of P1 and P2.

        Parameters
        PolytopeP1
        PolytopeP2
        Returns
        Polytope
      •  
        minkowski_sum_fukuda ()

        UNDOCUMENTED
      •  
        mixed_integer_hull (P, int_coords) → Polytope

        Produces the mixed integer hull of a polyhedron

        Parameters
        PolytopeP
        Array<Int>int_coords
        the coordinates to be integral;
        Returns
        Polytope
      •  
        pointed_part (P) → Polytope

        Produces the pointed part of a polyhedron

        Parameters
        PolytopeP
        Returns
        Polytope
      •  
        prism (P, z1, z2) → Polytope

        Make a prism over a pointed polyhedron. The prism is the product of the input polytope P and the interval [z1, z2].

        Parameters
        PolytopeP
        the input polytope
        Rationalz1
        the left endpoint of the interval; default value: -1
        Rationalz2
        the right endpoint of the interval; default value: -z1
        Options
        Boolnoc
        only combinatorial information is handled
        Boolrelabel
        creates an additional section VERTEX_LABELS; 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
      •  
        product (P1, P2) → Polytope

        Construct a new polytope as the product of two given polytopes P1 and P2.

        Parameters
        PolytopeP1
        PolytopeP2
        Options
        Boolnoc
        only combinatorial information is handled
        Boolrelabel
        creates an additional section VERTEX_LABELS; the label of a new vertex corresponding to v1 ⊕ v2 will have the form LABEL_1*LABEL_2.
        Returns
        Polytope
      •  
        projection (P, indices) → Cone

        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
        ConeP
        Array<Int>indices
        Options
        Boolrevert
        inverts the coordinate list
        Boolnofm
        suppresses Fourier-Motzkin elimination
        Returns
        Cone
      •  
        projection_full (P) → Cone

        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
        ConeP
        Options
        Boolnofm
        suppresses Fourier-Motzkin elimination
        Boolrelabel
        copy labels to projection
        Returns
        Cone
      •  
        pyramid (P, z) → Polytope

        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
        PolytopeP
        Rationalz
        is the distance between the vertex barycenter and v, default value is 1.
        Options
        Boolnoc
        don't compute new coordinates, produce purely combinatorial description.
        Boolrelabel
        copy vertex labels from the original polytope, label the new top vertex with "Apex".
        Returns
        Polytope
      •  
        rand_inner_points (P, n) → Polytope

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

        Parameters
        PolytopeP
        the input polytope
        Intn
        the number of random points
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Polytope
      •  
        rand_vert (V, n) → Matrix

        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
        MatrixV
        the vertices of a polytope
        Intn
        the number of random points
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Matrix
      •  
        spherize (P) → Polytope

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

        Parameters
        PolytopeP
        Returns
        Polytope
      •  
        stack (P, stack_facets) → Polytope

        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
        PolytopeP
        Set<Int>stack_facets
        the facets to be stacked; A single facet to be stacked is specified by its number. Several facets can be passed in a Set or in an anonymous array of indices: [n1,n2,...] Special keyword All means that all factes are to be stacked.
        Options
        Rationallift
        controls the exact coordinates of the new vertices; rational number between 0 and 1; default value: 1/2
        Boolnoc
        produces a pure combinatorial description (in contrast to lift)
        Boolrelabel
        creates an additional section VERTEX_LABELS; New vertices get labels 'f(FACET_LABEL)' in the simplicial case, and 'f(FACET_LABEL)-NEIGHBOR_VERTEX_LABEL' in the cubical case.
        Returns
        Polytope
      •  
        stellar_all_faces (P, d) → Polytope

        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
        PolytopeP
        , must be bounded
        Intd
        the lowest dimension of the faces to be divided; negative values: treated as the co-dimension; default value: 1.
        Returns
        Polytope
      •  
        stellar_indep_faces (P, in_faces) → Polytope

        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
        PolytopeP
        , must be bounded
        Array<Set<Int>>in_faces
        Returns
        Polytope
      •  
        tensor (P1, P2) → Polytope

        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
        PolytopeP1
        PolytopeP2
        Returns
        Polytope
      •  
        truncation (P, trunc_vertices) → Polytope

        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 noc (no coordinates) can be specified to produce a pure combinatorial description of the resulting polytope, which corresponds to the cutoff factor 1/2.

        Parameters
        PolytopeP
        Set<Int>trunc_vertices
        the vertex/vertices to be cut off; A single vertex to be cut off is specified by its number. Several vertices can be passed in a Set or in an anonymous array of indices: [n1,n2,...] Special keyword All means that all vertices are to be cut off.
        Options
        Rationalcutoff
        controls the exact location of the cutting hyperplane(s); rational number between 0 and 1; default value: 1/2
        Boolnoc
        produces a pure combinatorial description (in contrast to cutoff)
        Boolrelabel
        creates an additional section VERTEX_LABELS; 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
      •  
        unirand (Polytope, n) → Polytope

        Produce a polytope with n random points that are uniformly distributed within the given polytope P. P must be bounded and full-dimensional.

        Parameters
        PPolytope
        Intn
        the number of random points
        Options
        Boolboundary
        forces the points to lie on the boundary of the given polytope
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Polytope
      •  
        vertex_figure (p, n) → Polytope

        Construct the vertex figure of the vertex n of a polyhedron. The vertex figure is dual to a facet of the dual polytope.

        Parameters
        Polytopep
        Intn
        number of the chosen vertex
        Options
        Rationalcutoff
        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.
        Boolnoc
        skip the coordinates computation, producing a pure combinatorial description.
        Boolrelabel
        inherit vertex labels from the corresponding neighbor vertices of the original polytope.
        Returns
        Polytope
      •  
        wedge (P, facet, z, z_prime) → Polytope

        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
        PolytopeP
        , must be bounded
        Intfacet
        the `cutting edge'.
        Scalarz
        default value is 0.
        Scalarz_prime
        default value is -z, or 1 if z==0.
        Options
        Boolnoc
        don't compute coordinates, pure combinatorial description is produced.
        Boolrelabel
        create vertex labels: 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
      •  
        wreath (P1, P2) → Polytope

        Construct a new polytope as the wreath product of two input polytopes P1, P2. P1 and P2 have to be BOUNDED.

        Parameters
        PolytopeP1
        PolytopeP2
        Options
        Booldual
        invokes the computation of the dual wreath product
        Boolrelabel
        creates an additional section VERTEX_LABELS; the label of a new vertex corresponding to v1 ⊕ v2 will have the form LABEL_1*LABEL_2.
        Returns
        Polytope
    •  

      With these clients you can create polytopes belonging to various parameterized families which occur frequently in polytope theory, as well as random polytopes with different models of randomness.

      •  
        associahedron (d) → Polytope

        Produce a d-dimensional associahedron (or Stasheff polytope). We use the facet description given in Ziegler's book on polytopes, section 9.2.

        Parameters
        Intd
        the dimension
        Returns
        Polytope
      •  
        binary_markov_graph (observation) → PropagatedPolytope

        Defines a very simple graph for a polytope propagation related to a Hidden Markov Model. The propagated polytope is always a polygon. For a detailed description see

        M. Joswig: Polytope propagation, in: Algebraic statistics and computational biology
        by L. Pachter and B. Sturmfels (eds.), Cambridge, 2005.
        Parameters
        Array<Bool>observation
        Returns
        PropagatedPolytope
      •  
        binary_markov_graph (observation)

        Parameters
        Stringobservation
        encoded as a string of "0" and "1".
      •  
        birkhoff (n, even) → Polytope

        Constructs the Birkhoff polytope of dimension n2 (also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope).

        Parameters
        Intn
        Booleven
        Returns
        Polytope
      •  
        constructible_n_gon () → Polytope

        Create exact constructible regular polygon.

        Returns
        Polytope
      •  
        cross <Scalar> (d, d, scale) → Polytope<Scalar>

        Produce a d-dimensional cross polytope. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.

        All coordinates are +/- scale or 0.

        Type Parameters
        Scalar
        Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.
        Parameters
        Intd
        the dimension
        Intd
        the dimension
        Scalarscale
        the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.
        Options
        Boolgroup
        add a symmetry group description to the resulting polytope
        Returns
        Polytope<Scalar>
      •  
        cube <Scalar> (d, x_up, x_low) → Polytope<Scalar>

        Produce a d-dimensional cube. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.

        The bounding hyperplanes are xi <= x_up and xi >= x_low.

        Type Parameters
        Scalar
        Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.
        Parameters
        Intd
        the dimension
        Scalarx_up
        upper bound in each dimension
        Scalarx_low
        lower bound in each dimension
        Options
        Boolgroup
        add a symmetry group description to the resulting polytope
        Returns
        Polytope<Scalar>
      •  
        cuboctahedron () → Polytope

        Create cuboctahedron. An Archimedean solid.

        Returns
        Polytope
      •  
        cyclic (d, n) → Polytope

        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
        Intd
        the dimension
        Intn
        the number of points
        Options
        Intstart
        defaults to 0 (or to 1 if spherical)
        boolspherical
        defaults to false
        Returns
        Polytope
      •  
        cyclic_caratheodory (d, n) → Polytope

        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.

        Parameters
        Intd
        the dimension
        Intn
        the number of points
        Returns
        Polytope
      •  
        dodecahedron () → Polytope

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

        Returns
        Polytope
      •  
        dwarfed_cube (d) → Polytope

        Produce a d-dimensional dwarfed cube.

        Parameters
        Intd
        the dimension
        Returns
        Polytope
      •  
        dwarfed_product_polygons (d, s) → Polytope

        Produce a d-dimensional dwarfed product of polygons of size s.

        Parameters
        Intd
        the dimension
        Ints
        the size
        Returns
        Polytope
      •  
        explicit_zonotope (zones) → Polytope

        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
        Matrixzones
        the input vectors
        Options
        boolrows_are_points
        the rows of the input matrix represent affine points(true, default) or linear vectors(false)
        Returns
        Polytope
      •  
        flow_polytope (G, Arc_Bounds, Source, Sink) → Polytope

        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

        Parameters
        Graph<Directed>G
        EdgeMap<Directed, Scalar>Arc_Bounds
        IntSource
        IntSink
        Returns
        Polytope
      •  
        flow_polytope (G, Arc_Bounds, Source, Sink) → Polytope

        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

        Parameters
        Graph<Directed>G
        EdgeMap<Directed, Scalar>Arc_Bounds
        IntSource
        IntSink
        Returns
        Polytope
      •  
        goldfarb (d, e, g) → Polytope

        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
        Intd
        the dimension
        Rationale
        Rationalg
        Returns
        Polytope
      •  
        hypersimplex (k, d) → Polytope

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

        Parameters
        Intk
        number of 1s
        Intd
        ambient dimension
        Returns
        Polytope
      •  
        hypertruncated_cube (d, k, lambda) → Polytope

        Produce a d-dimensional hypertruncated cube. With symmetric linear objective function (0,1,1,...,1).

        Parameters
        Intd
        the dimension
        Rationalk
        cutoff parameter
        Rationallambda
        scaling of extra vertex
        Returns
        Polytope
      •  
        icosahedron () → Polytope

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

        Returns
        Polytope
      •  
        icosidodecahedron () → Polytope

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

        Returns
        Polytope
      •  
        knapsack (b) → Polytope

        Produce a knapsack polytope defined by one linear inequality (and non-negativity constraints).

        Parameters
        Vector<Rational>b
        linear inequality
        Returns
        Polytope
      •  
        k_cyclic (n, s) → Polytope

        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
        Intn
        Vectors
        s=(s_1,...,s_k)
        Returns
        Polytope
      •  
        max_GC_rank (d) → Polytope

        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
        Intd
        the dimension
        Returns
        Polytope
      •  
        multiplex (d, n) → Polytope

        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
        Intd
        the dimension
        Intn
        Returns
        Polytope
      •  
        neighborly_cubical (d, n) → Polytope

        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
        Intd
        dimension of the polytope
        Intn
        dimension of the equivalent cube
        Returns
        Polytope
      •  
        newton (p) → LatticePolytope

        Produce the Newton polytope of a polynomial p.

        Parameters
        Polynomialp
        Returns
        LatticePolytope
      •  
        n_gon (n, r) → Polytope

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

        Parameters
        Intn
        the number of vertices
        Rationalr
        the radius
        Options
        boolgroup
        Returns
        Polytope
      •  
        perles_irrational_8_polytope () → Polytope

        Create an 8-dimensional polytope without rational realizations due to Perles

        Returns
        Polytope
      •  
        permutahedron (d) → Polytope

        Produce a d-dimensional permutahedron. The vertices correspond to the elements of the symmetric group of degree d+1.

        Parameters
        Intd
        the dimension
        Options
        Boolgroup
        Returns
        Polytope
      •  
        pile (sizes) → Polytope

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

        Parameters
        Vector<Int>sizes
        a vector (s1,...,sd, where si specifies the number of boxes in the i-th dimension.
        Returns
        Polytope
      •  
        platonic_solids () → Array<Polytope<QuadraticExtension>>

        Produce the list of all five Platonic solids with ascending number of vertices.

      •  
        rand01 (d, n) → Polytope

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

        Parameters
        Intd
        the dimension
        Intn
        the number of random vertices
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Polytope
      •  
        rand_box (d, n, b) → Polytope

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

        Parameters
        Intd
        the dimension of the box
        Intn
        the number of random points
        Intb
        the size of the box
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Polytope
      •  
        rand_cyclic (d, n) → Polytope

        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
        Intd
        the dimension
        Intn
        the number of vertices
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Polytope
      •  
        rand_metric <Scalar> (n) → Matrix

        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
        Intn
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Matrix
      •  
        rand_metric_int <Scalar> (n) → Matrix

        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
        Intn
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Matrix
      •  
        rand_sphere (d, n) → Polytope

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

        Parameters
        Intd
        the dimension
        Intn
        the number of random vertices
        Options
        Intseed
        controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
        Returns
        Polytope
      •  
        regular_120_cell () → Polytope

        Create exact regular 120-cell in Q(sqrt{5}).

        Returns
        Polytope
      •  
        regular_24_cell () → Polytope

        Create regular 24-cell.

        Returns
        Polytope
      •  
        regular_600_cell () → Polytope

        Create exact regular 600-cell in Q(sqrt{5}).

        Returns
        Polytope
      •  
        rhombicosidodecahedron () → Polytope

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

        Returns
        Polytope
      •  
        rss_associahedron (l) → Polytope

        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
        Intl
        ambient dimension
        Returns
        Polytope
      •  
        signed_permutahedron (d) → Polytope

        Produce a d-dimensional signed permutahedron.

        Parameters
        Intd
        the dimension
        Returns
        Polytope
      •  
        simplex (d, scale) → Polytope

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

        Parameters
        Intd
        the dimension
        Scalarscale
        default value: 1
        Options
        Boolgroup
        Returns
        Polytope
      •  
        simple_roots_type_A (index) → SparseMatrix

        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
        Intindex
        of the arrangement (3, 4, etc)
        Returns
        SparseMatrix
      •  
        simple_roots_type_B (index) → SparseMatrix

        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
        Intindex
        of the arrangement (3, 4, etc)
        Returns
        SparseMatrix
      •  
        simple_roots_type_C (index) → SparseMatrix

        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
        Intindex
        of the arrangement (3, 4, etc)
        Returns
        SparseMatrix
      •  
        simple_roots_type_D (index) → SparseMatrix

        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
        Intindex
        of the arrangement (3, 4, etc)
        Returns
        SparseMatrix
      •  
        simple_roots_type_E8 () → SparseMatrix

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

      •  
        simple_roots_type_F4 () → SparseMatrix

        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

      •  
        simple_roots_type_G2 () → SparseMatrix

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

      •  
        simple_roots_type_H3 () → SparseMatrix

        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

      •  
        simple_roots_type_H4 () → SparseMatrix

        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}

      •  
        stable_set (G) → Polytope

        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
        GraphG
        Returns
        Polytope
      •  
        tetrahedron () → Polytope

        Create regular tetrahedron. A Platonic solid.

        Returns
        Polytope
      •  
        transportation (r, c) → Polytope

        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
        Vectorr
        Vectorc
        Returns
        Polytope
      •  
        truncated_cuboctahedron () → Polytope

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

        Returns
        Polytope
      •  
        truncated_dodecahedron () → Polytope

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

        Returns
        Polytope
      •  
        truncated_icosahedron () → Polytope

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

        Returns
        Polytope
      •  
        truncated_icosidodecahedron () → Polytope

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

        Returns
        Polytope
      •  
        upper_bound_theorem (d, n) → Polytope

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

        Parameters
        Intd
        the dimension
        Intn
        the number of points
        Returns
        Polytope
      •  
        wythoff (type, rings) → Polytope

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

        Parameters
        Stringtype
        single letter followed by rank representing the type of the arrangement
        Set<Int>rings
        indices of the hyperplanes corresponding to simple roots of the arrangement that the initial point should NOT lie on
        Returns
        Polytope
      •  
        zonotope <Scalar> (M) → Polytope<Scalar>

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

        Type Parameters
        Scalar
        target coordinate type
        Parameters
        Matrix<Scalar>M
        input points or vectors
        Options
        Boolrows_are_points
        true if M are points instead of vectors; default true
        Returns
        Polytope<Scalar>
        the zonotope generated by the input points or vectors
      •  
        zonotope_vertices_fukuda ()

        UNDOCUMENTED
    •  
      UNDOCUMENTED
      •  
        coxeter_group (type) → GroupOfPolytope

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

        Parameters
        Stringtype
        the type of the Coxeter group
        Returns
        GroupOfPolytope
        the Coxeter group of type type
      •  
        crosscut_complex (p) → SimplicialComplex

        Produce the crosscut complex of the boundary of a polytope.

        Parameters
        Polytopep
        Returns
        SimplicialComplex
    •  
      UNDOCUMENTED
      Contained in extension bundled:group.
      •  
        cs_quotient ()

        For a centrally symmetric polytope, return the quotient space obtained by dividing out the central symmetry, i.e, identifying diametrically opposite faces

      •  
        cylinder_2 ()

        Return a 2-dimensional cylinder obtained by identifying two opposite sides of a square

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

      •  
        quotient_space_faces (P)

        Find the faces of the Quotient space represented by P and its @see IDENTIFICATION_GROUP

        Parameters
        PolytopeP
    •  
      UNDOCUMENTED
      •  
        alternating_group (degree, domain) → GroupOfPolytope

        Constructs an alternating group of given degree.

        Contained in extension bundled:group.
        Parameters
        intdegree
        of the alternating group"
        intdomain
        of the polytope's symmetry group
        Returns
        GroupOfPolytope
        \@see group::alternating_group
      •  
        combinatorial_symmetries (poly, on_vertices) → group::GroupOfPolytope

        Compute the combinatorial symmetries (i.e. automorphisms of the face lattice) of a given polytope poly. If on_vertices is set to 1, the function returns a group::GroupOfPolytope which acts on the vertices. If on_vertices is set to any other number, the function returns a GroupOfPolytope which acts on the facets of the polytope. If on_vertices is unspecified, both groups are returned.

        Parameters
        Polytopepoly
        the given polytope
        Inton_vertices
        specifies whether the returned group should act on vertices (1) or on facets
        Returns
        group::GroupOfPolytope
        the combinatorial symmetry group acting on the vertices or the facets depending on on_vertices or (group::GroupOfPolytope,group::GroupOfPolytope) group on vertices, group on facets
      •  
        convert_coord_action (group, mat, dom_out) → group::Group

        Converts the generators of a group acting on coordinates to generators of the corresponding group which acts on the rows of the given matrix mat. The parameter dom_out specifies whether mat describes vertices or facets.

        Parameters
        group::Groupgroup
        input group acting on coordinates
        Matrixmat
        vertices or facets of a polytope
        intdom_out
        OnRays(1) or OnFacets(2)
        Returns
        group::Group
        a new group object with the generators induced on the new domain
      •  
        convert_group_domain (group, VIF) → group::Group

        Converts the generators of the input group from the domain onRays to generators on the domain onFacets, and vice versa.

        Parameters
        group::Groupgroup
        input group
        IncidenceMatrixVIF
        the vertex-facet incidence matrix of the cone or polytope
        Returns
        group::Group
        a new group object with the generators induced on the new domain
      •  
        cyclic_group (degree, domain) → GroupOfPolytope

        Constructs a cyclic group of given degree.

        Contained in extension bundled:group.
        Parameters
        intdegree
        of the cyclic group"
        intdomain
        of the polytope's symmetry group
        Returns
        GroupOfPolytope
        \@see group::cyclic_group
      •  
        group_from_cyclic_notation0 (group, domain) → GroupOfPolytope

        Constructs a group from a string with generators in cyclic notation. All numbers in the string are 0-based. Example: "(0,2)(1,3)"

        Contained in extension bundled:group.
        Parameters
        Stringgroup
        generators in cyclic notation
        intdomain
        of the polytope symmetry group
        Returns
        GroupOfPolytope
        \@see group_from_cyclic_notation1
      •  
        group_from_cyclic_notation1 (group, domain) → GroupOfPolytope

        Constructs a group from a string with generators in cyclic notation. All numbers in the string are 1-based. Example: "(1,3)(2,4)"

        Contained in extension bundled:group.
        Parameters
        Stringgroup
        generators in cyclic notation
        intdomain
        of the polytope symmetry group
        Returns
        GroupOfPolytope
        \@see group_from_cyclic_notation0
      •  
        lattice_automorphisms_smooth_polytope (P)

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

        Parameters
        LatticePolytopeP
      •  
        lex_min_representative (G, S) → Set

        Computes the lexicographically smallest representative of a given set with respect to a group

        Parameters
        GroupG
        a symmetry group
        SetS
        a set
        Returns
        Set
        the lex-min representative of S
      •  
        linear_symmetries (c, dual) → GroupOfCone

        Computes the linear symmetries of a given polytope p via 'sympol'. If the input is a cone, it may compute only a subgroup of the linear symmetry group.

        Parameters
        Conec
        the cone (or polytope) whose linear symmetry group is to be computed
        booldual
        true if group action on vertices, false if action on facets
        Returns
        GroupOfCone
        the linear symmetry group of p (or a subgroup if p is a cone)
      •  
        nestedOPGraph (gen_point, points, lattice_points, group, verbose) → PerlArray

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

        Parameters
        Vectorgen_point
        the generating point
        Matrixpoints
        the vertices of the orbit polytope
        Matrixlattice_points
        the lattice points of the orbit polytope
        group::GroupOfPolytopegroup
        the generating group
        Boolverbose
        print out additional information
        Returns
        PerlArray
        ($Graph, $lp_reps, $minInStartOrbit, \@core_point_reps, $CPindices)
      •  
        orbit_polytope (gen_point, group) → OrbitPolytope

        Constructs the orbit polytope of a given point gen_point with respect to a given permutation group group.

        Parameters
        Vector<Rational>gen_point
        the basis point of the orbit polytope
        group::GroupOfPolytopegroup
        a group acting on coordinates
        Returns
        OrbitPolytope
        the orbit polytope of gen_point w.r.t. group
      •  
        ortho_project (p) → Polytope

        Projects a symmetric polytope in R4 cap H1,k to R3. (See also the polymake extension 'tropmat' by S. Horn.)

        Parameters
        Polytopep
        the symmetric polytope to be projected
        Returns
        Polytope
        the image of p in R3
      •  
        representation_conversion_up_to_symmetry (c, a, dual, rayCompMethod) → perl::ListReturn

        Computes the dual description of a polytope up to its linear symmetry group.

        Parameters
        Conec
        the cone (or polytope) whose dual description is to be computed
        Groupa
        symmetry group of the cone c (GroupOfCone or GroupOfPolytope)
        booldual
        true if V to H, false if H to V
        boolrayCompMethod
        specifies sympol's method of ray computation via lrs(0), cdd(1), beneath_and_beyond(2)
        Returns
        perl::ListReturn
        list which contains success as bool, vertices/inequalities and lineality/equations as Matrix<Rational>
      •  
        symmetric_group (degree, domain) → GroupOfPolytope

        Constructs a symmetric group of given degree.

        Contained in extension bundled:group.
        Parameters
        intdegree
        of the symmetric group"
        intdomain
        of the polytope's symmetry group
        Returns
        GroupOfPolytope
        \@see group::symmetric_group
      •  
        truncated_orbit_polytope (v, group, eps) → SymmetricPolytope

        Constructs an orbit polytope of a given point v with respect to a given group group, in which all vertices are cut off by hyperplanes in distance eps

        Parameters
        Vectorv
        point of which orbit polytope is to be constructed
        group::GroupOfPolytopegroup
        group for which orbit polytope is to be constructed
        Rationaleps
        scaled distance by which the vertices of the orbit polytope are to be cut off
        Returns
        SymmetricPolytope
        the truncated orbit polytope
      •  
        visualizeNOP (orb, colors_ref, trans_ref) → void

        Visualizes all (nested) orbit polytopes contained in orb in one picture.

        Parameters
        OrbitPolytopeorb
        the orbit polytope
        Scalarcolors_ref
        the reference to an array of colors
        Scalartrans_ref
        the reference to an array of transparency values
        Returns
        void
      •  
        visualizeNOPGraph (orb, filename) → void

        Visualizes the NOP-graph of an orbit polytope. Requires 'graphviz' and a Postscript viewer. Produces a file which is to be processed with the program 'dot' from the graphviz package. If 'dot' is installed, the NOP-graph is visualized by the Postscript viewer.

        Parameters
        OrbitPolytopeorb
        the orbit polytope
        Stringfilename
        the filename for the 'dot' file
        Returns
        void
    •  
      UNDOCUMENTED
      •  
        ambient_lattice_normalization (p) → Polytope

        Transform to a full-dimensional polytope while preserving the ambient lattice Z^n

        Parameters
        Polytopep
        the input polytope,
        Options
        Boolstore_transform
        store the reverse transformation as an attachement
        Returns
        Polytope
        - the transformed polytope defined by its vertices. Facets are only written if available in p.
      •  
        bound (P) → Polytope

        Make a positive polyhedron bounded. Apply a projective linear transformation to a polyhedron mapping the far hyperplane to the hyperplane spanned by the points (1,0,...,0,1,0,...). The origin (1,0,...,0) is fixed.

        The input polyhedron should be POSITIVE; i.e. no negative coordinates.

        Parameters
        PolytopeP
        a positive polyhedron
        Returns
        Polytope
      •  
        center (P) → Polytope

        Make a polyhedron centered. Apply a linear transformation to a polyhedron P such that a relatively interior point (preferably the vertex barycenter) is moved to the origin (1,0,...,0).

        Parameters
        PolytopeP
        Returns
        Polytope
      •  
        orthantify (P, v) → Polytope

        Make a polyhedron POSITIVE. Apply an affine transformation to a polyhedron such that the vertex v is mapped to the origin (1,0,...,0) and as many facets through this vertex as possible are mapped to the bounding facets of the first orthant.

        Parameters
        PolytopeP
        Intv
        vertex to be moved to the origin. By default it is the first affine vertex of the polyhedron.
        Returns
        Polytope
      •  
        polarize (C) → Cone

        Given a bounded, centered, not necessarily full-dimensional polytope P, produce its polar with respect to the standard Euclidean scalar product. Note that the definition of the polar has changed after version 2.10: the polar is reflected in the origin to conform with cone polarization If P is not full-dimensional, the output is the intersection of the cone polar to P with the affine span of P. In particular, polarize() of a not full dimensional polytope is a polytope of the same dimension.

        Parameters
        ConeC
        Options
        Boolnoc
        only combinatorial information is handled
        Returns
        Cone
      •  
        revert (P) → Polytope

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

        Applying revert to the transformed polytope reconstructs the original polyhedron.

        Parameters
        PolytopeP
        a (transformed) polytope
        Returns
        Polytope
      •  
        scale (P, factor, store) → Polytope

        Scale a polyhedron P by a given scaling parameter factor.

        Parameters
        PolytopeP
        the polyhedron to be scaled
        Scalarfactor
        the scaling factor
        Boolstore
        stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.
        Returns
        Polytope
      •  
        transform (P, trans, store) → Polytope

        Transform a polyhedron P according to the linear transformation trans.

        Parameters
        PolytopeP
        the polyhedron to be transformed
        Matrixtrans
        the transformation matrix
        Boolstore
        stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.
        Returns
        Polytope
      •  
        translate (P, trans, store) → Polytope

        Translate a polyhedron P by a given translation vector trans.

        Parameters
        PolytopeP
        the polyhedron to be translated
        Vectortrans
        the translation vector
        Boolstore
        stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.
        Returns
        Polytope
      •  
        vertex_lattice_normalization (p) → Polytope

        Transform to a full-dimensional polytope while preserving the lattice spanned by vertices induced lattice of new vertices = Z^dim

        Parameters
        Polytopep
        the input polytope,
        Options
        Boolstore_transform
        store the reverse transformation as an attachement
        Returns
        Polytope
        - the transformed polytope defined by its vertices. Facets are only written if available in p.
    •  

      These functions take a realized polytope and produce a new one by applying a suitable affine or projective transformation in order to obtain some special coordinate description but preserve the combinatorial type.

      For example, before you can polarize an arbitrary polyhedron, it must be transformed to a combinatorially equivalent bounded polytope with the origin as a relatively interior point. It is achieved with the sequence orthantify - bound - center - polarize.

      •  
        UNDOCUMENTED
        •  
          barycentric_subdivision (c) → SimplicialComplex

          Create a simplicial complex as a barycentric subdivision of a given cone or polytope. Each vertex in the new complex corresponds to a face in the old complex.

          Parameters
          Conec
          input cone or polytope
          Options
          Boolrelabel
          generate vertex labels from the faces of the original complex; default true
          Boolgeometric_realization
          read RAYS of the input complex, compute the coordinates of the new vertices and store them as RAYS of the produced complex; default true
          Returns
          SimplicialComplex
          or GeometricSimplicialComplex
        •  
          barycentric_subdivision (pc) → PointConfiguration

          Create a simplicial complex as the barycentric subdivision of a given point configuration. Each vertex in the new complex corresponds to a face in the old complex.

          Parameters
          PointConfigurationpc
          input point configuration
          Options
          Boolrelabel
          generate vertex labels from the faces of the original complex; default true
          Boolgeometric_realization
          read POINTS of the input complex, compute the coordinates of the new vertices and store them as POINTS of the produced complex; default false
          Returns
          PointConfiguration
        •  
          cocircuit_equations (P) → ListMatrix

          Find the cocircuit equations of a polytope P. There is one of these for each interior cocircuit of P, and they come as the rows of a matrix whose columns correspond to the maximal-dimensional simplices of P.

          Contained in extension bundled:group.
          Parameters
          PolytopeP
          the input polytope
          Options
          filenamethe
          name of a file to store the equations
          Returns
          ListMatrix
        •  
          common_refinement (points, sub1, sub2, dim) → Array<Set<Int>>

          Computes the common refinement of two subdivisions of points. It is assumed that there exists a common refinement of the two subdivisions.

          Parameters
          Matrixpoints
          Array<Set>sub1
          first subdivision
          Array<Set>sub2
          second subdivision
          Intdim
          dimension of the point configuration
          Returns
          Array<Set<Int>>
          the common refinement
        •  
          common_refinement (p1, p2) → Polytope

          Computes the common refinement of two subdivisions of the same polytope p1, p2. It is assumed that there exists a common refinement of the two subdivisions. It is not checked if p1 and p2 are indeed the same!

          Parameters
          Polytopep1
          Polytopep2
          Returns
          Polytope
        •  
          delaunay_triangulation (V) → Array<Set<Int>>

          Compute the (a) Delaunay triangulation of the given SITES of a VoronoiDiagram V. If the sites are not in general position, the non-triangular facets of the Delaunay subdivision are triangulated (by applying the beneath-beyond algorithm).

        •  
          foldable_max_signature_ilp (d, points, volume, cocircuit_equations) → an

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

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          Matrixpoints
          the input points or vertices
          Rationalvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Options
          filenamea
          name for a file in .lp format to store the linear program
          Returns
          an
          ILP that provides the result
        •  
          foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → the

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

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          Matrixpoints
          the input points or vertices
          Rationalvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Returns
          the
          optimal value of an LP that provides a bound
        •  
          interior_and_boundary_ridges (P) → Pair<Array<Set>,Array<Set>>

          Find the (d-1)-dimensional simplices in the interior and in the boundary of a d-dimensional polytope or cone

          Parameters
          PolytopeP
          the input polytope or cone
          Returns
          Pair<Array<Set>,Array<Set>>
        •  
          is_regular (points, subdiv) → Pair<bool,Vector>

          For a given subdivision subdiv of points tests if the subdivision is regular and if yes computes a weight vector inducing this subdivsion. The output is a pair of bool and the weight vector. Options can be used to ensure properties of the resulting vector. The default is having 0 on all vertices of the first face of subdiv.

          Parameters
          Matrixpoints
          in homogeneous coordinates
          Array<Set<Int> >subdiv
          Options
          Matrix<Scalar>equations
          system of linear equation the cone is cut with.
          Set<Int>lift_to_zero
          gives only lifting functions lifting the designated vertices to 0
          Intlift_face_to_zero
          gives only lifting functions lifting all vertices of the designated face to 0
          Returns
          Pair<bool,Vector>
        •  
          is_subdivision (points, faces)

          Checks whether faces forms a valid subdivision of points, where points is a set of points, and faces is a collection of subsets of (indices of) points. If the set of interior points of points is known, this set can be passed by assigning it to the option interior_points. If points are in convex position (i.e., if they are vertices of a polytope), the option interior_points should be set to [ ] (the empty set).

          Parameters
          Matrixpoints
          Array<Set<Int>>faces
          Options
          Set<Int>interior_points
        •  
          iterated_barycentric_subdivision (c, how) → SimplicialComplex

          Create a simplicial complex as an iterated barycentric subdivision of a given cone or polytope.

          Parameters
          Conec
          input cone or polytope
          Inthow
          many times to subdivide
          Options
          Boolrelabel
          write labels of new points; default don't write labels
          Boolgeometric_realization
          read RAYS of the input complex, compute the coordinates of the new vertices and store them as RAYS of the produced complex; default false
          Returns
          SimplicialComplex
        •  
          max_interior_simplices (P) → Array<Set>

          Find the maximal interior simplices of a polytope P. Symmetries of P are NOT taken into account.

          Contained in extension bundled:group.
          Parameters
          PolytopeP
          the input polytope
          Returns
          Array<Set>
        •  
          max_interior_simplices (P)

          find the maximal interior simplices of a point configuration that DO NOT contain any point in their closure, except for the vertices. Symmetries of the configuration are NOT taken into account.

          Contained in extension bundled:group.
          Parameters
          PointConfigurationP
          the input point configuration
        •  
          max_interior_simplices_impl (P) → Array<Set>

          Find the interior d-dimensional simplices of a polytope or cone of combinatorial dimension d

          Parameters
          PolytopeP
          the input polytope or cone
          Returns
          Array<Set>
        •  
          max_metric (n) → Matrix

          Compute a metric such that the f-vector of its tight span is maximal among all metrics with n points.

          S. Herrmann and M. Joswig: Bounds on the f-vectors of tight spans.
          Contrib. Discrete Math., Vol.2, 2007 161-184
          Parameters
          Intn
          the number of points
          Returns
          Matrix
        •  
          metric2hyp_triang (FMS) → Polytope

          Given a generic finite metric space FMS, construct the associated (i.e. dual) triangulation of the hypersimplex.

          Parameters
          TightSpanFMS
          Returns
          Polytope
        •  
          metric2splits (D) → Array<Pair<Set>>

          Computes all non-trivial splits of a metric space D (encoded as a symmetric distance matrix).

          Parameters
          MatrixD
          Returns
          Array<Pair<Set>>
          each split is encoded as a pair of two sets.
        •  
          min_metric (n) → Matrix

          Compute a metric such that the f-vector of its tight span is minimal among all metrics with n points.

          S. Herrmann and M. Joswig: Bounds on the f-vectors of tight spans.
          Contrib. Discrete Math., Vol.2, 2007 161-184
          Parameters
          Intn
          the number of points
          Returns
          Matrix
        •  
          mixed_volume (P1, P2, Pn) → E

          Produces the mixed volume of polytopes P1,P2,...,Pn.

          Parameters
          PolytopeP1
          first polytope
          PolytopeP2
          second polytope
          PolytopePn
          last polytope
          Returns
          E
          mixed volume
        •  
          placing_triangulation (Points, permutation) → Array<Set<Int>>

          Compute the placing triangulation of the given point set using the beneath-beyond algorithm.

          Parameters
          MatrixPoints
          the given point set
          Array<Int>permutation
          Returns
          Array<Set<Int>>
        •  
          points2metric (points) → Matrix

          Define a metric by restricting the Euclidean distance function to a given set of points. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-nomr is used instead (with exact computation).

          Parameters
          Matrixpoints
          Options
          Boolmax
          triggers the usage of the max-norm (exact computation)
          Booll1
          triggers the usage of the l1-norm (exact computation)
          Returns
          Matrix
        •  
          poly2metric (P) → Matrix

          Define a metric by restricting the Euclidean distance function to the vertex set of a given polytope P. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-nomr is used instead (with exact computation).

          Parameters
          PolytopeP
          Options
          Boolmax
          triggers the usage of the max-norm (exact computation)
          Returns
          Matrix
        •  
          positive_circuits (or, S) → Set<Set<Int>>

          returns all sets of points that form a circuit with the given list of points

          Parameters
          Polytopeor
          PointConfiguration P
          Set<Int>S
          subset of point indices
          Returns
          Set<Set<Int>>
          A list of point sets that intersect positively the set S
        •  
          quotient_space_simplexity_ilp (d, V, volume, cocircuit_equations) → an

          Set up an LP whose MINIMAL_VALUE is a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          MatrixV
          the input points or vertices
          Scalarvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Options
          filenamea
          name for a file in .lp format to store the linear program
          Returns
          an
          LP that provides a lower bound
        •  
          quotient_space_simplexity_lower_bound (d, V, volume, cocircuit_equations) → the

          Calculate a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          MatrixV
          the input points or vertices
          Scalarvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Returns
          the
          optimal value of an LP that provides a lower bound
        •  
          regularity_lp (points, subdiv) → Polytope<Scalar>

          For a given subdivision subdiv of points determines a LinearProgram to decide whether the subdivision is regular. The output a Polytope with an attached LP. Options can be used to ensure properties of the resulting LP. The default is having 0 on all vertices of the first face of subdiv.

          Parameters
          Matrixpoints
          in homogeneous coordinates
          Array<Set<Int> >subdiv
          Options
          Matrix<Scalar>equations
          system of linear equation the cone is cut with.
          Set<Int>lift_to_zero
          gives only lifting functions lifting the designated vertices to 0
          Intlift_face_to_zero
          gives only lifting functions lifting all vertices of the designated face to 0
          Scalarepsilon
          minimum distance from all inequalities
          Returns
          Polytope<Scalar>
        •  
          regular_subdivision (points, weights) → Array<Set<Int>>

          Compute a regular subdivision of the polytope obtained by lifting points to weights and taking the lower complex of the resulting polytope. If the weight is generic the output is a triangulation.

          Parameters
          Matrixpoints
          Vectorweights
          Returns
          Array<Set<Int>>
        •  
          secondary_cone (points, subdiv) → Cone

          For a given subdivision subdiv of points tests computes the corresponding secondary cone. If the subdivision is not regular, the cone will be the secondary cone of the finest regular coarsening of subdiv. (See option test_regularity) Options can be used to make the Cone POINTED.

          Parameters
          Matrixpoints
          in homogeneous coordinates
          Array<Set<Int> >subdiv
          Options
          Matrix<Scalar>equations
          system of linear equation the cone is cut with.
          Set<Int>lift_to_zero
          gives only lifting functions lifting the designated vertices to 0
          Intlift_face_to_zero
          gives only lifting functions lifting all vertices of the designated face to 0
          booltest_regularity
          throws an exception if the subdivision is not regular
          Returns
          Cone
        •  
          simplexity_ilp (d, points, the, volume, cocircuit_equations) → an

          Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          Matrixpoints
          the input points or vertices
          Array<Set>the
          (representative) maximal interior simplices
          Scalarvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Options
          filenamea
          name for a file in .lp format to store the linear program
          Returns
          an
          LP that provides a lower bound
        •  
          simplexity_ilp_with_angles (d, points, the, volume, cocircuit_equations) → an

          Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          Matrixpoints
          the input points or vertices
          Array<Set>the
          (representative) maximal interior simplices
          Scalarvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Options
          filenamea
          name for a file in .lp format to store the linear program
          Returns
          an
          LP that provides a lower bound
        •  
          simplexity_lower_bound (d, points, volume, cocircuit_equations) → the

          Calculate the LP relaxation lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          Matrixpoints
          the input points or vertices
          Scalarvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Returns
          the
          optimal value of an LP that provides a lower bound
        •  
          splits (V, G, F, dimension) → Matrix

          Computes the SPLITS of a polytope. The splits are normalized by dividing by the first non-zero entry. If the polytope is not fulldimensional the first entries are set to zero unless coords are specified.

          Parameters
          MatrixV
          vertices of the polytope
          GraphG
          graph of the polytope
          MatrixF
          facets of the polytope
          Intdimension
          of the polytope
          Options
          Set<Int>coords
          entries that should be set to zero
          Returns
          Matrix
        •  
          splits_in_subdivision (vertices, subdivision, splits) → Set<Int>

          Tests which of the splits of a polyhedron are coarsenings of the given subdivision.

          Parameters
          Matrixvertices
          the vertices of the polyhedron
          Array<Set<Int>>subdivision
          a subdivision of the polyhedron
          Matrixsplits
          the splits of the polyhedron
          Returns
          Set<Int>
        •  
          split_compatibility_graph (splits, P) → Graph

          DOC_FIXME: Incomprehensible description! Computes the compatibility graph among the splits of a polytope P.

          Parameters
          Matrixsplits
          the splits given by split equations
          PolytopeP
          the input polytope
          Returns
          Graph
        •  
          split_polyhedron (P) → Polytope

          Computes the split polyhedron of a full-dimensional polyhdron P.

          Parameters
          PolytopeP
          Returns
          Polytope
        •  
          staircase_weight (k, l) → Vector<Rational>

          Gives a weight vector for the staircase triangulation of the product of a k- and an l-dimensional simplex.

          Parameters
          Intk
          the dimension of the first simplex
          Intl
          the dimension of the second simplex
          Returns
          Vector<Rational>
        •  
          stellar_subdivision (pc, faces) → PointConfiguration

          Computes the complex obtained by stellar subdivision of all faces of the TRIANGULATION of the PointConfiguration.

          Parameters
          PointConfigurationpc
          input point configuration
          Array<Set<Int>>faces
          list of faces to subdivide
          Options
          Boolno_labels
          : do not write any labels
          Returns
          PointConfiguration
        •  
          symmetrized_foldable_max_signature_ilp (d, points, volume, generators, symmetrized_foldable_cocircuit_equations) → an

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

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          Matrixpoints
          the input points or vertices
          Rationalvolume
          the volume of the convex hull
          Array<Array<Int>>generators
          the generators of the symmetry group
          SparseMatrixsymmetrized_foldable_cocircuit_equations
          the matrix of symmetrized cocircuit equations
          Options
          filenamea
          name for a file in .lp format to store the linear program
          Returns
          an
          ILP that provides the result
        •  
          symmetrized_foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → the

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

          Parameters
          Intd
          the dimension of the input polytope, point configuration or quotient manifold
          Matrixpoints
          the input points or vertices
          Rationalvolume
          the volume of the convex hull
          SparseMatrixcocircuit_equations
          the matrix of cocircuit equations
          Returns
          the
          optimal value of an LP that provides a bound
        •  
          thrackle_metric (n) → Matrix

          Compute a metric such that the f-vector of its tight span is maximal among all metrics with n points. This metric can be interpreted as a lifting function for the thrackle triangulation (see de Loera, Sturmfels and Thomas: Groebner Basis and triangultaions of the second hypersimplex)

          Parameters
          Intn
          the number of points
          Returns
          Matrix
        •  
          tight_span (points, weight, full) → Polytope

          Compute the tight span dual to the regular subdivision obtained by lifting points to weight and taking the lower complex of the resulting polytope.

          Parameters
          Matrixpoints
          Vectorweight
          Boolfull
          true if the polytope is full-dimensional. Default value is 1.
          Returns
          Polytope
          (The polymake object TightSpan is only used for tight spans of finite metric spaces, not for tight spans of subdivisions in general.)
        •  
          tight_span (P) → Polytope

          Compute the tight span dual to the regular subdivision of a polytope P obtained by the WEIGHTS and taking the lower complex of the resulting polytope.

          Parameters
          PolytopeP
          Returns
          Polytope
          (The polymake object TightSpan is only used for tight spans of finite metric spaces, not for tight spans of subdivisions in general.)
        •  
          topcom_all_triangulations (pc) → Array<Array<Set<Int>>>

          Compute all triangulations of a point configuration via its chirotope.

          Parameters
          PointConfigurationpc
          input point configuration
          Returns
          Array<Array<Set<Int>>>
        •  
          ts_max_metric (n) → TightSpan

          Computes the tight span of a metric such that its f-vector is maximal among all metrics with n points.

          S. Herrmann and M. Joswig: Bounds on the f-vectors of tight spans.
          Contrib. Discrete Math., Vol.2, 2007 161-184
          Parameters
          Intn
          the number of points
          Returns
          TightSpan
        •  
          ts_min_metric (n) → TightSpan

          Compute the tight span of a metric such its f-vector is minimal among all metrics with n points.

          S. Herrmann and M. Joswig: Bounds on the f-vectors of tight spans.
          Contrib. Discrete Math., Vol.2, 2007 161-184
          Parameters
          Intn
          the number of points
          Returns
          TightSpan
        •  
          ts_thrackle_metric (n) → TightSpan

          Compute a tight span of a metric such that its f-vector is maximal among all metrics with n points. This metric can be interpreted as a lifting function for the thrackle triangulation (see de Loera, Sturmfels and Thomas: Groebner Basis and triangultaions of the second hypersimplex)

          Parameters
          Intn
          the number of points
          Returns
          TightSpan
      •  
        UNDOCUMENTED
        •  
          bounding_box (V, surplus_k, voronoi) → Matrix

          Introduce artificial boundary facets (which are always vertical, i.e., the last coordinate is zero) to allow for bounded images of unbounded polyhedra (e.g. Voronoi polyhedra). If the voronoi flag is set, the last direction is left unbounded.

          Parameters
          MatrixV
          vertices that should be in the box
          Scalarsurplus_k
          size of the bounding box relative to the box spanned by V
          Boolvoronoi
          useful for visualizations of Voronoi diagrams that do not have enough vertices default value is 0.
          Returns
          Matrix
        •  
          splitstree (vis_obj ...)

          Call wiki:external_software#SplitsTree with the given visual objects.

          Parameters
          Visual::Objectvis_obj ...
          objects to display
          Options
          StringFile
          "filename" or "AUTO" Only create a NEXUS format file, don't start the GUI.
          The .nex suffix is automatically added to the file name.
          Specify AUTO if you want the filename be automatically derived from the drawing title.
          You can also use any expression allowed for the open function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe.
        •  
          vlabels (vertices, wo_zero) → arrayref

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

          Parameters
          Matrixvertices
          the vertices of the polytope
          Boolwo_zero
          includes (0) or omits (1) the entry at position 0
          Returns
          arrayref
          a reference to an array of vertex label strings

      Common Option Lists