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, topaz

Objects

User Functions

  •  

    Comparing

    •  
      congruent (P1, P2)

      Check whether two given polytopes P1 and P2 are congruent, i.e. whether there is an affine isomorphism between them that is induced by a (possibly scaled) orthogonal matrix. Returns the scale factor, or 0 if the polytopes are not congruent.

      We are using the reduction of the congruence problem (for arbitrary point sets) to the graph isomorphism problem due to:

      Akutsu, T.: On determining the congruence of point sets in `d` dimensions.
      Comput. Geom. Theory Appl. 9, 247--256 (1998), no. 4
      Parameters
      PolytopeP1
      PolytopeP2
    •  
      equal_polyhedra (P1, P2)

      Tests if the two polyhedra P1 and P2 are equal.

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

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

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

      Parameters
      PolytopeP1
      PolytopeP2
      Returns
      Pair<Array<Int>, Array<Int>>
    •  
      included_polyhedra (P1, P2)

      Tests if polyhedron P1 is included in polyhedron P2.

      Parameters
      PolytopeP1
      PolytopeP2
    •  
      isomorphic (P1, P2)

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

      Parameters
      PolytopeP1
      PolytopeP2
    •  
      lattice_isomorphic_smooth_polytopes (P1, P2)

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

      Parameters
      LatticePolytopeP1
      LatticePolytopeP2
  •  

    Consistency check

    •  
      check_inc (points, hyperplanes, sign, verbose)

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

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

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

      Parameters
      IncidenceMatrixVIF
      Options
      Booldual
      transposes the incidence matrix
      Boolverbose
      prints information about the check.
      Returns
      Polytope
  •  

    Constructing a cone

    •  
      normal_cone (p, v)

      Computes the outer normal cone of p at the vertex v.

      Parameters
      Polytopep
      intv
      vertex number
  •  

    Coordinate conversions

    •  
      affine_float_coords (P) → Matrix<Float>

      dehomogenize the vertex coordinates and convert them to Float

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

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

      Type Parameters
      Coord
      target coordinate type
      Parameters
      Conec
      the input cone
      Returns
      Cone<Coord>
      a new cone object or C itself it has the requested type
    •  
      convert_to <Coord> (P) → Polytope<Coord>

      provide a Polytope object with desired coordinate type

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

    Delaunay subdivisions and Voronoi diagrams

    •  
      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>>
    •  
      voronoi (V) → Matrix

      Compute the inequalities of the Voronoi polyhedron of a given VoronoiDiagram V. The polyhedron is always unbounded. Introduce artificial cut facets later (e.g., for visualization); this must be done after the vertices have been computed.

      Parameters
      VoronoiDiagramV
      Returns
      Matrix
  •  

    Formatting

  •  

    Linear optimization

    •  
      dgraph (P, LP) → Graph<Directed>

      Direct the graph of a polytope P according to a linear or abstract objective function. The maximal and minimal values, which are attained by the objective function, as well as the minimal and the maximal face are written into separate sections.

      The option inverse directs the graph with decreasing instead of increasing edges. If the option generic is set, ties will be broken by lexicographical ordering.

      Parameters
      PolytopeP
      LinearProgramLP
      Options
      Boolinverse
      inverts the direction
      Boolgeneric
      breaks ties
      Returns
      Graph<Directed>
    •  
      inner_point (points)

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

      Parameters
      Matrixpoints
    •  
      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, unbounded, affine_hull)

      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
      Boolunbounded
      needs to be set to true if P could be unbounded; default value: 0
      Boolaffine_hull
      indicates that the affine hull of P is already computed; default value: 0
    •  
      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>
  •  

    Metric properties

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

    Optimization

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

    Orbits

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

    Other

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

    Polytope Propagation

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

    Producing a new polyhedron from others

    •  
      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
      Rationalz
      distance between the vertex barycenter and the first apex, default value is 1.
      Rationalz_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
      Rationalz
      the extra coordinate for the vertices of P
      Rationalz_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

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

      Parameters
      PolytopeP
      Set<Int>cells
      Options
      Boolrelabel
      copy the vertex labels from the original polytope
      Returns
      Polytope
    •  
      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
    •  
      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
    •  
      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
    •  
      mapping_polytope (P1, P2) → Polytope

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

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

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

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

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

      Produces the Minkowski sum of P1 and P2.

      Parameters
      PolytopeP1
      PolytopeP2
      Returns
      Polytope
    •  
      minkowski_sum_fukuda ()

      UNDOCUMENTED
    •  
      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) → Polytope

      Orthogonally project a pointed polyhedron to a coordinate subspace.

      The subspace the polyhedron P is projected on is given by the coordinate 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
      PolytopeP
      Array<Int>indices
      Options
      Boolrevert
      inverts the coordinate list
      Boolnofm
      suppresses Fourier-Motzkin elimination
      Returns
      Polytope
    •  
      projection_full (P) → Polytope

      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
      PolytopeP
      Options
      Boolnofm
      suppresses Fourier-Motzkin elimination
      Returns
      Polytope
    •  
      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'.
      Rationalz
      default value is 0.
      Rationalz_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 from given data

    •  
      zonotope (zones) → Matrix

      Produce the points of a zonotope from the vectors given in zones. The zonotope is obtained as the iterated Minkowski sum of all intervals [-x,x], where x ranges over the rows of a given matrix.

      Parameters
      Matrixzones
      the input vectors
      Returns
      Matrix
  •  

    Producing from other

    •  
      cut_polytope (G) → Polytope

      Cut polytope of an undirected graph.

      Parameters
      GraphG
      Returns
      Polytope
    •  
      matching_polytope (G) → Polytope

      Matching polytope of an undirected graph.

      Parameters
      GraphG
      Returns
      Polytope
    •  
      tutte_lifting (G) → Polytope

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

      Parameters
      GraphG
      Returns
      Polytope
  •  

    Producing from scratch

    •  
      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
    •  
      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
    •  
      create_24_cell () → Polytope

      Create the 24-cell polytope.

      Returns
      Polytope
    •  
      create_600_cell () → Polytope

      Create the 600-cell polytope. Cf. Coxeter, Introduction to Geometry, pp 403-404.

      Returns
      Polytope
    •  
      cross (d, scale) → Polytope

      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.

      Parameters
      Intd
      the dimension
      Rationalscale
      Needs to be positive. The default value is 1.
      Returns
      Polytope
    •  
      cube (d, x_up, x_low) → Polytope

      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. Default values: x_up=1, x_low=-x_up or 1 if x_up==0.

      Parameters
      Intd
      the dimension
      Rationalx_up
      Rationalx_low
      Returns
      Polytope
    •  
      cyclic (d, n, start) → 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 moment curve at integer steps from start, or 0 if not specified.

      Parameters
      Intd
      the dimension
      Intn
      the number of points
      Intstart
      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
    •  
      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
    •  
      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
    •  
      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
      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
      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
    •  
      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_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
    •  
      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
      Rationalscale
      default value: 1
      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
  •  

    Subdivisions

    •  
      barycentric_subdivision (pc) → PointConfiguration

      Create a point configuration as a barycentric subdivision of a given one.

      Parameters
      PointConfigurationpc
      input point configuration
      Options
      Boolno_labels
      do not write any labels
      Returns
      PointConfiguration
    •  
      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
    •  
      is_regular (points, subdiv) → Pair<bool,Cone>

      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
      Array<Set<Int> >subdiv
      Options
      Matrix<Rational>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,Cone>
    •  
      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
    •  
      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>>
    •  
      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 result will be the trivial cone. Options can be used to make the Cone POINTED.

      Parameters
      Matrixpoints
      Array<Set<Int> >subdiv
      Options
      Matrix<Rational>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
      Cone
    •  
      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
    •  
      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>>>
  •  

    Symmetry

  •  

    Tight Span

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

    Transforming a lattice polyhedron

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

    Transforming a polyhedron

    •  
      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, and full-dimensional polytope P, produce its polar, that is, 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 dualization

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

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

      Applying revert to the transformed polytope reconstructs the original polyhedron.

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

      Scale a polyhedron P by a given scaling parameter factor.

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

      Transform a polyhedron P according to the linear transformation trans.

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

      Translate a polyhedron P by a given translation vector trans.

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

    Triangulation and Volume

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

    Utilities

    •  
      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

      Parameters
      Stringfile
      filename of a linear programming problem in LP-Format
      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.

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

    Visualization

    •  
      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
      Rationalsurplus_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
    •  
      clip_graph (p, V, G)

      Clip a graph with respect to a given bounding box. Used for the visualization of Voronoi diagrams.

      Parameters
      Polytopep
      MatrixV
      GraphG
    •  
      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.
  •  

    Working with symmetries

    •  
      linear_symmetries (c, dual) → void

      Computes the linear symmetries of a given polytope p via 'sympol'. The symmetry group is stored in the property GROUP.

      Parameters
      Conec
      the cone whose linear symmetry group is to be computed
      booldual
      true if group action on vertices, false if action on facets
      Returns
      void
    •  
      representation_conversion_up_to_symmetry (c, a, dual) → perl::ListReturn

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

      Parameters
      Conec
      the cone 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
      Returns
      perl::ListReturn
      list which contains success as bool, vertices/inequalities and lineality/equations as Matrix<Rational>

Common Option Lists