Navigation

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

  •  
    minkowski_sum ()

    UNDOCUMENTED

  •  
    minkowski_sum ()

    UNDOCUMENTED

  •  
    minkowski_sum ()

    UNDOCUMENTED

  •  
    minkowski_sum ()

    UNDOCUMENTED

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

    Calculations

    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
  •  

    Combinatorial properties

    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
  •  

    Comparing

    UNDOCUMENTED
    •  
      congruent (P1, P2) → Scalar

      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
      the first polytope
      PolytopeP2
      the second polytope
      Returns
      Scalar
      the scale factor or 0 if the polytopes are not congruent
    •  
      equal_polyhedra (P1, P2) → Bool

      Tests if the two polyhedra P1 and P2 are equal.

      Parameters
      PolytopeP1
      the first polytope
      PolytopeP2
      the second polytope
      Returns
      Bool
      true if the two polyhedra are equal, false otherwise
    •  
      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, the vertex permutation is the second component of the return value.

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

      Parameters
      ConeP1
      the first cone/polytope
      ConeP2
      the second cone/polytope
      Returns
      Pair<Array<Int>, Array<Int>>
      the facet and the vertex permutations
    •  
      included_polyhedra (P1, P2) → Bool

      Tests if polyhedron P1 is included in polyhedron P2.

      Parameters
      PolytopeP1
      the first polytope
      PolytopeP2
      the second polytope
      Returns
      Bool
      'true' if P1 is included in P2, 'false' otherwise
    •  
      isomorphic (P1, P2) → Bool

      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
      the first cone/polytope
      ConeP2
      the second cone/polytope
      Returns
      Bool
      'true' if the face lattices are isomorphic, 'false' otherwise
    •  
      lattice_isomorphic_smooth_polytopes (P1, P2) → Bool

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

      Parameters
      LatticePolytopeP1
      the first lattice polytope
      LatticePolytopeP2
      the second lattice polytope
      Returns
      Bool
      'true' if the polytopes are lattice equivalent, 'false' otherwise
  •  

    Consistency check

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

      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
      Returns
      Bool
      'true' if all relations are satisfied, 'false' otherwise
    •  
      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
      the resulting polytope under the assumption that VIF actually defines a 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
      the given polytope
      Returns
      Bool
      'true' if the Moebius strip edges form such a Moebius strip, 'false' otherwise
    •  
      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 and returns the MOEBIUS_STRIP_EDGES if the answer is affirmative.

      Parameters
      PolytopeP
      the given polytope
      Options
      Boolverbose
      print details
      Returns
      Matrix<Int>
      the Moebius strip edges
  •  

    Coordinate conversions

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

    •  
      affine_float_coords (P) → Matrix<Float>

      Dehomogenize the vertex coordinates and convert them to Float

      Parameters
      PolytopeP
      source object
      Returns
      Matrix<Float>
      the dehomogenized vertices converted to 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
  •  

    Geometric properties

    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.

      Parameters
      Polytope<Scalar>P
      Returns
      Matrix<Integer>
    •  
      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
    •  
      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
      Boolfacets
      compute support hyperplanes (=FACETS,LINEAR_SPAN)
      Boolrays
      compute extreme rays (=RAYS)
      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, facets, linear_span, rays) (if they are requested)
    •  
      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
  •  

    Optimization

    UNDOCUMENTED
    •  
      ball_lifting_lp (c, facet_index, conv_eps) → Polytope

      Computes the inequalities and the linear objective for an LP to lift a simplicial d-ball embedded starshaped in Rd.

      Parameters
      topaz::GeometricSimplicialComplexc
      Intfacet_index
      index of the facet to be lifted
      Rationalconv_eps
      some epsilon > 0
      Returns
      Polytope
    •  
      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>
  •  

    Producing a cone

    UNDOCUMENTED
  •  

    Producing a polynomial

    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)

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

    Producing a polytope from graphs

    UNDOCUMENTED
    •  
      cut_polytope (G) → Polytope

      Cut polytope of an undirected graph.

      Parameters
      GraphG
      Returns
      Polytope
    •  
      flow_polytope <Scalar> (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

      Type Parameters
      Scalar
      Parameters
      Graph<Directed>G
      EdgeMap<Directed, Scalar>Arc_Bounds
      Intsource
      Intsink
      Returns
      Polytope
    •  
      flow_polytope <Scalar> (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

      Type Parameters
      Scalar
      Parameters
      Graph<Directed>G
      Array<Scalar>Arc_Bounds
      Intsource
      Intsink
      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
  •  

    Producing a polytope from polytopes

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

    Actually, these functions don't alter the input polytope (it is forbidden in polymake), but create a new polytope object.

    Many functions can at your choice either calculate the vertex or facet coordinates, or constrain themselves on the purely combinatorial description of the resulting polytope.

    •  
      bipyramid (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_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
  •  

    Producing a polytope from scratch

    With these clients you can create polytopes belonging to various parameterized families which occur frequently in polytope theory, as well as 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
    •  
      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.

      Returns
      Array<Polytope<QuadraticExtension>>
    •  
      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.

      Returns
      SparseMatrix
    •  
      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

      Returns
      SparseMatrix
    •  
      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

      Returns
      SparseMatrix
    •  
      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

      Returns
      SparseMatrix
    •  
      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}

      Returns
      SparseMatrix
    •  
      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
  •  

    Producing other objects

    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
  •  

    Quotient spaces

    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
  •  

    Symmetry

    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) → Array<Array<Int>>

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

      Parameters
      LatticePolytopeP
      the given polytope
      Returns
      Array<Array<Int>>
      the generating set for the lattice automorphism group
    •  
      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
  •  

    Transformations

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

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

    •  
      ambient_lattice_normalization (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 polytope.

      Parameters
      PolytopeP
      a (transformed) polytope
      Returns
      Polytope
      the original 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.
  •  

    Triangulations, subdivisions and volume

    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
    •  
      coherency_index (p1, p2, points, w1, w2)

      DOC_FIXME: Incomprehensible description! Computes the coherency index of w1 w.r.t. w2

      Parameters
      Polytopep1
      Polytopep2
      Matrixpoints
      Vectorw1
      Vectorw2
    •  
      coherency_index (points, w1, w2)

      DOC_FIXME: Incomprehensible description! Computes the coherency index of w1 w.r.t. w2

      Parameters
      Matrixpoints
      Vectorw1
      Vectorw2
    •  
      coherency_index (p1, p2)

      DOC_FIXME: Erroneous description! w1 is not a parameter here! Computes the coherency index of p1 w.r.t. p2

      Parameters
      Polytopep1
      Polytopep2
    •  
      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).

      Parameters
      VoronoiDiagramV
      Returns
      Array<Set<Int>>
    •  
      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
      representatives of 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
  •  

    Visualization

    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