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

Objects

  •  

    LinearProgram

    Category: Optimization

    A linear program specified by a linear or abstract objective function

    Properties of LinearProgram

  • User Methods of LinearProgram

  •  

    PointConfiguration

    The object point configuration also deals with non-convex finite point sets.

    Properties of PointConfiguration

  •  
  •  
    GRAPH: graph::Graph<Undirected>

    Graph of the point configuration. Two points are adjacent if they lie in a common edge of the CONVEX_HULL.

  •  
  •  
    CHIROTOPE: common::Text

    Chirotope corresponding to POINTS

  •  
  •  
  •  
    POLYTOPAL_SUBDIVISION: common::Array<Set<Int>>

    Polytopal Subdivision of the point configuration. Each line contains indices from POINTS comprising a facet of the subdivision.

  •  
    TRIANGULATION: topaz::SimplicialComplex

    Some triangulation of the point configuration.

    Properties of TRIANGULATION

  •  
    WEIGHTS: common::Vector<Scalar>

    The weight vector to construct a TRIANGULATION.

  •  
    WEIGHTS_GENERIC: common::Bool

    Tells that WEIGHTS are generic.

  •  
  •  
    FAR_POINTS: common::Set<Int>

    Indices of POINTS that are rays.

  •  
  •  
  • User Methods of PointConfiguration

  •  

    Polytope

    A bounded or unbounded pointed polyhedron. Note that a pointed polyhedron is projectively equivalent to a polytope. Scalar is the numeric data type used for the coordinates.

    Properties of Polytope

  •  
  •  
    ALTSHULER_DET: common::Integer

    Let M be the vertex-facet incidence matrix, then the Altshulter determinant is defined as max{det(M ∗ M^T), det(M^T &lowast M)}.

  •  
    BALANCE: common::Int

    Maximal dimension in which all facets are balanced.

  •  
  •  
    CD_INDEX_COEFFICIENTS: common::Vector<Integer>

    Coefficients of the cd-index.

  •  
  •  
  •  
    COMPLEXITY: common::Float

    Parameter describing the shape of the face-lattice of a 4-polytope.

  •  
    CUBICAL: common::Bool

    True if all facets are cubes.

  •  
    CUBICALITY: common::Int

    Maximal dimension in which all facets are cubes.

  •  
    CUBICAL_H_VECTOR: common::Vector<Integer>

    Cubical h-vector. Defined for cubical polytopes.

  •  
    DUAL_BOUNDED_H_VECTOR: common::Vector<Integer>

    h-vector of the bounded subcomplex, defined for not necessarily bounded polyhedra which are simple (as polyhedra, i.e., VERTEX_DEGREES on the FAR_FACE do not matter). Coincides with the reverse h-vector of the dual simplicial ball. Note that this vector will usually start with a number of zero entries.

  •  
    DUAL_GRAPH: graph::Graph<Undirected>

    Facet-ridge graph. Dual to GRAPH.

  •  
    DUAL_H_VECTOR: common::Vector<Integer>

    h-vector, defined via recursion on the face lattice of a polytope. Coincides for simple polytopes with the combinatorial definition of the h-vector via abstract objective functions.

  •  
    ESSENTIALLY_GENERIC: common::Bool

    All intermediate polytopes (with respect to the given insertion order) in the beneath-and-beyond algorithm are simplicial. We have the implications: VERTICES in general position => ESSENTIALLY_GENERIC => SIMPLICIAL

  •  
    F2_VECTOR: common::Matrix<Integer>

    fik is the number of incident pairs of i-faces and k-faces; the main diagonal contains the F_VECTOR.

  •  
    FACETS_THRU_VERTICES: common::IncidenceMatrix<NonSymmetric>

    transposed VERTICES_IN_FACETS Notice that this is a temporary property; it will not be stored in any file.

  •  
    FACET_SIZES: common::Array<Int>

    Number of incident vertices for each facet.

  •  
    FACE_SIMPLICITY: common::Int

    Maximal dimension in which all faces are simple polytopes.

  •  
    FATNESS: common::Float

    Parameter describing the shape of the face-lattice of a 4-polytope.

  •  
    FLAG_VECTOR: common::Vector<Integer>

    Condensed form of the flag vector, containing all entries indexed by sparse sets in {0, ..., DIM-1} in the following order:

    (1, f0, f1, f2, f02, f3, f03, f13, f4, f04, f14, f24, f024, f5, ...).

    Use Dehn-Sommerville equations, via user function N_FLAGS, to extend.

  •  
    F_VECTOR: common::Vector<Integer>

    fk is the number of k-faces.

  •  
    GRAPH: graph::Graph<Undirected>

    Vertex-edge graph.

    Properties of GRAPH

  •  
    G_VECTOR: common::Vector<Integer>

    (Toric) g-vector, defined via the (generalized) h-vector as gi = hi - hi-1.

  •  
    HASSE_DIAGRAM: graph::FaceLattice

    The face lattice of the polytope organized as a directed graph. Each node corresponds to some proper face of the polytope. The nodes corresponding to the vertices and facets appear in the same order as the elements of VERTICES and FACETS properties.

    Two special nodes represent the whole polytope and the empty face.

  •  
    H_VECTOR: common::Vector<Integer>

    h-vector, defined via recursion on the face lattice of a polytope. Coincides for simplicial polytopes with the combinatorial definition of the h-vector via shellings

  •  
  •  
    MINIMAL_NON_FACES: common::Array<Set<Int>>

    Minimal non-faces of a SIMPLICIAL polytope.

  •  
    NEIGHBORLINESS: common::Int

    Maximal dimension in which all facets are neighborly.

  •  
    NEIGHBORLY: common::Bool

    True if the polytope is neighborly.

  •  
  •  
    N_VERTEX_FACET_INC: common::Int

    Number of pairs of incident vertices and facets.

  •  
  •  
    SELF_DUAL: common::Bool

    True if the polytope is self-dual.

  •  
    SIMPLE: common::Bool

    True if the polytope is simple. Dual to SIMPLICIAL.

  •  
    SIMPLICIAL: common::Bool

    True if the polytope is simplicial.

  •  
    SIMPLICIALITY: common::Int

    Maximal dimension in which all faces are simplices.

  •  
    SIMPLICITY: common::Int

    Maximal dimension in which all dual faces are simplices.

  •  
    SUBRIDGE_SIZES: common::Map<Int, Int>

    Lists for each occurring size (= number of incident facets or ridges) of a subridge how many there are.

  •  
    TWO_FACE_SIZES: common::Map<Int, Int>

    Lists for each occurring size (= number of incident vertices or edges) of a 2-face how many there are.

  •  
    VERTEX_SIZES: common::Array<Int>

    Number of incident facets for each vertex.

  •  
    VERTICES_IN_FACETS: common::IncidenceMatrix<NonSymmetric>

    Vertex-facet incidence matrix, with rows corresponding to facets and columns to vertices. Vertices and facets are numbered from 0 to N_VERTICES-1 rsp. N_FACETS-1, according to their order in VERTICES rsp. FACETS.

  •  
  •  
    POINTS_IN_FACETS: common::IncidenceMatrix<NonSymmetric>

    Similar to VERTICES_IN_FACETS, but with columns corresponding to POINTS instead of VERTICES. This property is a byproduct of convex hull computation algorithms. It is discarded as soon as VERTICES_IN_FACETS is computed.

  •  
    VERTICES_IN_INEQUALITIES: common::IncidenceMatrix<NonSymmetric>

    Similar to VERTICES_IN_FACETS, but with rows corresponding to INEQUALITIES instead of FACETS. This property is a byproduct of convex hull computation algorithms. It is discarded as soon as VERTICES_IN_FACETS is computed.

  •  
  •  
    LP: LinearProgram<Scalar>

    Linear program applied to the polytope

  •  
  •  
    CHIROTOPE: common::Text

    Chirotope corresponding to the VERTICES

  •  
  •  
    FAR_HYPERPLANE: common::Vector<Scalar>

    Valid strict inequality for all affine points of the polyhedron.

  •  
    REL_INT_POINT: common::Vector<Scalar>

    Relatively interior point of the polyhedron.

  •  
  •  
    POLYTOPAL_SUBDIVISION: common::Array<Set<Int>>

    Polytopal Subdivision of the polytope using only its vertices. Each line contains indices from VERTICES comprising a facet of the subdivision.

  •  
    TRIANGULATION: topaz::SimplicialComplex

    Some triangulation of the polytope using only its vertices. Each line contains indices from VERTICES comprising a simplex.

    Properties of TRIANGULATION

  •  
  •  
    VOLUME: Scalar

    Volume of the polytope.

  •  
    WEIGHTS: common::Vector<Scalar>

    Weight vector to construct a regular TRIANGULATION.

  •  
    WEIGHTS_GENERIC: common::Bool

    Tells that WEIGHTS are generic.

  •  
  •  
    BOUNDED_COMPLEX: common::IncidenceMatrix<NonSymmetric>

    Bounded subcomplex. FIXME: type should be a newly defined "PolyhedralComplex"

  •  
    BOUNDED_DIM: common::Int

    Dimension of the BOUNDED_COMPLEX of an unbounded polyhedron.

  •  
    BOUNDED_DUAL_GRAPH: graph::Graph<Undirected>

    Dual graph of the bounded subcomplex.

  •  
    BOUNDED_F_VECTOR: common::Vector<Int>

    fk is the number of bounded k-faces.

  •  
    BOUNDED_GRAPH: graph::Graph<Undirected>

    Graph of the bounded subcomplex.

    Properties of BOUNDED_GRAPH

  •  
    BOUNDED_HASSE_DIAGRAM: graph::FaceLattice

    HASSE_DIAGRAM constrained to affine vertices Nodes representing the maximal inclusion-independent faces are connected to the top-node regardless of their dimension

  •  
    FAR_FACE: common::Set<Int>

    Indices of vertices that are rays.

  •  
    N_BOUNDED_VERTICES: common::Int

    Number of bounded vertices (non-rays).

  •  
    SIMPLE_POLYHEDRON: common::Bool

    True if each bounded vertex of a (possibly unbounded) d-polyhedron has vertex degree d in the GRAPH. The vertex degrees of the vertices on the FAR_FACE do not matter.

  •  
    TOWARDS_FAR_FACE: common::Vector<Scalar>

    A linear objective function for which each unbounded edge is increasing; only defined for unbounded polyhedra.

  •  
    UNBOUNDED_FACETS: common::Set<Int>

    Indices of facets that are unbounded.

  •  
  •  
  •  
    GALE_VERTICES: common::Matrix<Float>

    Coordinates of points for an affine Gale diagram.

  •  
    NEIGHBOR_FACETS_CYCLIC_NORMAL: common::Array<List<Int>>

    Reordered DUAL_GRAPH for 3d-polytopes. The neighbor facets are listed in the order corresponding to VIF_CYCLIC_NORMAL, so that the first two vertices in VIF_CYCLIC_NORMAL make up the ridge to the first neighbor facet and so on.

  •  
  •  
    SCHLEGEL_DIAGRAM: SchlegelDiagram<Scalar>

    Holds one special projection (the Schlegel diagram) of the polytope.

  •  
    VIF_CYCLIC_NORMAL: common::Array<List<Int>>

    Reordered VERTICES_IN_FACETS for 2d and 3d-polytopes. Vertices are listed in the order of their appearance when traversing the facet border counterclockwise seen from outside of the polytope.

    For a 2d-polytope (which is a closed polygon), lists all vertices in the border traversing order.

  • User Methods of Polytope

    Permutations of Polytope

  •  

    Polytope<Float>

    A pointed polyhedron realized in Rd.

    Convex hull and related algorithms use floating-point arithmetics. Due to numerical errors inherent to this kind of computations, the resulting combinatorial description can be arbitrarily far away from the truth, or even not correspond to any valid polytope. You have been warned.

    None of the standard construction clients produces objects of this type. If you want to get one, create it with the explicit constructor or convert_to.

    derived from: Polytope

    Properties of Polytope<Float>

  •  

    Polytope<Rational>

    derived from: Polytope

    Properties of Polytope<Rational>

  •  
  •  
    LATTICE: common::Bool

    This is the defining property: A polytope is lattice if each vertex has integer coordinates.

  •  

    PropagatedPolytope

    Polytope propagation means to define a polytope inductively by assigning vectors to arcs of a directed graph. At each node of such a graph a polytope arises as the joint convex hull of the polytopes at the translated sources of the inward pointing arcs.

    For details see

    Joswig: Polytope Propagation on Graphs.
    Chapter 6 in
    Pachter/Sturmfels: Algebraic Statistics for Computational Biology, Cambridge 2005.
    derived from: Polytope<Rational>

    Properties of PropagatedPolytope

  •  

    SchlegelDiagram

    A Schlegel diagram of a polytope

    Properties of SchlegelDiagram

    User Methods of SchlegelDiagram

  •  

    TightSpan

    Bounded subcomplex of an unbounded polyhedron, which is associated with a finite metric space. The tight span is 1-dimensional if and only if the metric is tree-like. In this sense, the tight span captures the deviation of the metric from a tree-like one.

    derived from: Polytope

    Properties of TightSpan

  • User Methods of TightSpan

  •  

    Visual::PointConfiguration

    Category: Visualization

    Visualization of the point configuration.

    User Methods of Visual::PointConfiguration

  •  

    Visual::Polytope

    Category: Visualization

    Visualization of a polytope as a graph (if 1d), or as a solid object (if 2d or 3d), or as a Schlegel diagram (4d).

    User Methods of Visual::Polytope

  •  

    Visual::PolytopeGraph

    Category: Visualization

    Visualization of the graph of a polyhedron.

    User Methods of Visual::PolytopeGraph

    •  
      DIRECTED_GRAPH (lp) → Visual::PolytopeGraph

      Show the growth direction of a linear objective function via arrowed edges.

      Parameters
      LinearProgram lp
      a LinearProgram object attached to the polytope
      Returns
      Visual::PolytopeGraph
    •  
      EDGE_COLORS () → Visual::PolytopeGraph

      produce an edge coloring of a bounded graph from local data in the Hasse diagram

    •  
      MIN_MAX_FACE (lp) → Visual::PolytopeGraph

      Illustrate the behavior of a linear objective function on the polytope. The vertices belonging to MINIMAL_FACE and MAXIMAL_FACE are drawn in distinct colors

      The spring embedder applies an additional force, which tries to arrange the nodes in the z-axis direction corresponding to the objective function values.

      Parameters
      LinearProgram lp
      a LinearProgram object attached to the polytope
      Options
      Color min
      minimal face decoration (default: yellow nodes)
      Color max
      maximal face decoration (default: red nodes)
      Returns
      Visual::PolytopeGraph
    •  
      VERTEX_COLORS (lp) → Visual::PolytopeGraph

      Illustrate the behavior of a linear objective function on the polytope. Color the nodes according to the value the objective function takes on the vertices.

      The spring embedder applies an additional force, which tries to arrange the nodes in the z-axis direction corresponding to the objective function values.

      Parameters
      LinearProgram lp
      a LinearProgram object attached to the polytope.
      Options
      Color min
      minimal face color (default: yellow)
      Color max
      maximal face color (default: red)
      Returns
      Visual::PolytopeGraph
  •  

    Visual::PolytopeLattice

    Category: Visualization

    Visualization of the HASSE_DIAGRAM of a polyhedron as a multi-layer graph..

    User Methods of Visual::PolytopeLattice

    •  
      MIN_MAX_FACE (lp) → Visual::PolytopeLattice

      Illustrate the behavior of a linear objective function on the polytope. Draw the filters of the MAXIMAL_FACE and MINIMAL_FACE in distinct colors.

      Parameters
      LinearProgram lp
      a LinearProgram object attached to the polytope
      Options
      Color min
      minimal face decoration (default: yellow border and ingoing edges)
      Color max
      maximal face decoration (default: red border and ingoing edges)
      Returns
      Visual::PolytopeLattice
  •  

    Visual::SchlegelDiagram

    Category: Visualization

    Visualization of the Schlegel diagram of a polytope.

    User Methods of Visual::SchlegelDiagram

  •  

    VoronoiDiagram

    For a finite set of SITES S the Voronoi region of each site is the set of points closest (with respect to Euclidean distance) to the given site. All Voronoi regions (and their faces) form a polyhedral complex which is a vertical projection of the boundary complex of an unbounded polyhedron P(S). This way VoronoiDiagram becomes a derived class from Polytope<Rational>.

    derived from: Polytope<Rational>

    Properties of VoronoiDiagram

    User Methods of VoronoiDiagram

  • User Functions

  •  
  •  
    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
    Matrix points
    Matrix hyperplanes
    String sign
    composed of one or two characters from [-+0], representing the allowed domain of the vector inner products.
    Bool verbose
    print all products violating the required relation
  •  
    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
    IncidenceMatrix VIF
    Options
    Bool dual
    transposes the incidence matrix
    Bool verbose
    prints information about the check.
    Returns
    Polytope
  •  
  •  
    affine_float_coords (P) → Matrix<Float>

    dehomogenize the vertex coordinates and convert them to Float

    Parameters
    Polytope P
    source object
    Returns
    Matrix<Float>
  •  
    convert_to <Coord> (P) → Polytope<Coord>

    provide a Polytope object with desired coordinate type

    Type Parameters
    Coord
    target coordinate type
    Parameters
    Polytope P
    source object
    Returns
    Polytope<Coord>
    P if it already has the requested type, a new object otherwise
  •  
  •  
    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
    VoronoiDiagram V
    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 vertex have been computed.

    Parameters
    VoronoiDiagram V
    Returns
    Matrix
  •  
  •  
    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
    Polytope P
    LinearProgram LP
    Options
    Bool inverse
    inverts the direction
    Bool generic
    breaks ties
    Returns
    Graph<Directed>
  •  
    inner_point (points)

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

    Parameters
    Matrix points
  •  
    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) → Array<Int>

    Produce a random abstract objective function on a given simple polytope P. It is assumed that the boundary complex of the dual polytope is extendibly shellable. If, during the computation, it turns out that a certain partial shelling cannot be extended, then this is given instead of an abstract objective function. It is possible (but not required) to specify the index of the starting vertex start.

    Parameters
    Polytope P
    a simple polytope
    Int start
    the index of the starting vertex; default value: random
    Options
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Array<Int>
  •  
    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
    Polytope P
    Bool unbounded
    needs to be set to true if P could be unbounded; default value: 0
    Bool affine_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
    Polytope P
    LinearProgram LP
    Options
    RGB min
    the minimal RGB value
    RGB max
    the maximal RGB value
    Returns
    Array<RGB>
  •  
  •  
    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
    Polytope P
    Options
    eps controls
    the accuracy of the angles computed
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Matrix
  •  
    steiner_point (P) → Vector

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

    Parameters
    Polytope P
    Options
    eps controls
    the accuracy of the angles computed
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Vector
  •  
  •  
    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
    Polytope p
    Rational optLPvalue
    optimal value of LP approximation
    Options
    Bool verbose
    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
    Matrix Inequalities
    the inequalities describing the feasible region
    Returns
    perl::ListReturn
    (optLPsolution,optLPvalue,feasible,max_bounded)
  •  
  •  
    induced_lattice_basis (p) → Matrix<Integer>

    Returns a basis of the affine lattice spanned by the vertices

    Parameters
    Polytope p
    the input polytope
    Returns
    Matrix<Integer>
    - the lattice basis.
  •  
    minimal_vertex_angle (P) → Float

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

    Parameters
    Polytope P
    Returns
    Float
  •  
    perturb_matrix (input_matrix, eps, not_hom) → Matrix

    Perturb a given input_matrix by adding a random matrix. The random matrix consists of vectors that are uniformly distributed on the unit sphere. Optionally, the random matrix can be scaled by a factor eps.

    Parameters
    Matrix input_matrix
    Scalar eps
    the factor by which the random matrix is multiplied default value: 1
    Bool not_hom
    if set to 1, the first column will also be perturbed; otherwise the first columns of the input_matrix and the perturbed one coincide (useful for working with homogenized coordinates); default value: 0 (homogen. coords)
    Options
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Matrix
  •  
    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
    Graph G
    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
    String observation
    encoded as a string of "0" and "1".
  •  
  •  
    bipyramid (P, z, z_prime)

    Make a bipyramid over a polyhedron. The bipyramid is the convex hull of the input polyhedron P and two points (v, z), (v, z_prime) on both sides of the affine span of P. For bounded polyhedra, the apex projections v to the affine span of P coincide with the vertex barycenter of P.

    Parameters
    Polytope P
    Rational z
    distance between the vertex barycenter and the first apex, default value is 1.
    Rational z_prime
    distance between the vertex barycenter and the second apex, default value is -z.
    Options
    Bool noc
    : don't compute the coordinates, purely combinatorial description is produced.
    Bool relabel
    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
    Polytope P1
    Int v1
    the index of the first vertex
    Polytope P2
    Int v2
    the index of the second vertex
    Options
    Array<Int> permutation
    Bool relabel
    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. 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
    Polytope P
    the first polytope
    Polytope P_prime
    the second polytope
    Rational z
    the extra coordinate for the vertices of P
    Rational z_prime
    the extra coordinate for the vertices of P_prime
    Options
    Bool relabel
    Returns
    Polytope
  •  
    cayley_polytope (P_Array) → Polytope

    Construct the cayley polytope of a set of 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
    Bool proj
    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
    Polytope P
    Set<Int> cells
    Options
    Bool relabel
    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
    Polytope P
    Int cell
    Options
    Bool relabel
    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
    Polytope P
    Returns
    Polytope
  •  
    facet (P, facet) → Polytope

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

    Parameters
    Polytope P
    Int facet
    Options
    Bool noc
    don't copy the coordinates, produce purely combinatorial description.
    Bool relabel
    copy the vertex labels from the original polytope.
    Returns
    Polytope
  •  
    facet_to_infinity (i) → Polytope

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

    Parameters
    Int i
    the facet index
    Returns
    Polytope
  •  
    intersection (P ...) → Polytope

    Construct a new polyhedron as the intersection of given polyhedra.

    Parameters
    Polytope P ...
    polyhedra to be intersected
    Returns
    Polytope
  •  
    join_polytopes (P1, P2) → Polytope

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

    Parameters
    Polytope P1
    Polytope P2
    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
    Polytope P
    Vector v
    basis point for the first apex
    Vector v_prime
    basis for the second apex If v_prime is omitted, v will be used for both apices. If both v and v_prime are omitted, it tries to find two vertices which don't lie in a common facet. If no such vertices can be found or P is a simplex, it uses an interior lattice point as both v and v_prime.
    Rational z
    height for the first apex, default value is 1
    Rational z_prime
    hieght for the second apex, default value is -z
    Options
    Bool relabel
    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
    Polytope P
    Rational z
    the height for the apex (v,z), default value is 1.
    Vector v
    the lattice point to use as apex, default is the first vertex of P.
    Options
    Bool relabel
    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
    Polytope P1
    Polytope P2
    Options
    Bool relabel
    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
    Scalar lambda
    Polytope P1
    Scalar mu
    Polytope P2
    Returns
    Polytope
  •  
    minkowski_sum (P1, P2) → Polytope

    Produces the Minkowski sum of P1 and P2.

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

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

    Parameters
    Polytope P
    the input polytope
    Rational z1
    the left endpoint of the interval; default value: -1
    Rational z2
    the right endpoint of the interval; default value: -z1
    Options
    Bool noc
    only combinatorial information is handled
    Bool relabel
    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
    Polytope P1
    Polytope P2
    Options
    Bool noc
    only combinatorial information is handled
    Bool relabel
    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 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
    Polytope P
    Array<Int> indices
    Options
    Bool revert
    inverts the coordinate list
    Bool nofm
    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
    Polytope P
    Options
    Bool nofm
    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
    Polytope P
    Rational z
    is the distance between the vertex barycenter and v, default value is 1.
    Options
    Bool noc
    don't compute new coordinates, produce purely combinatorial description.
    Bool relabel
    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
    Polytope P
    the input polytope
    Int n
    the number of random points
    Options
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Polytope
  •  
    rand_vert (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
    Matrix V
    the vertices of a polytope
    Int n
    the number of random points
    Options
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Matrix
  •  
    spherize (P) → Polytope

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

    Parameters
    Polytope P
    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
    Polytope P
    Set<Int> stack_facets
    the facets to be stacked; A single facet to be stacked is specified by its number. Several facets can be passed in a Set or in an anonymous array of indices: [n1,n2,...] Special keyword All means that all factes are to be stacked.
    Options
    Rational lift
    controls the exact coordinates of the new vertices; rational number between 0 and 1; default value: 1/2
    Bool noc
    produces a pure combinatorial description (in contrast to lift)
    Bool relabel
    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
    Polytope P
    the input polytope
    Int d
    the lowest dimension of the faces to be divided; negative values: treated as the co-dimension; default value: 1.
    Returns
    Polytope
  •  
    stellar_indep_faces (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
    Polytope P
    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
    Polytope P1
    Polytope P2
    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
    Polytope P
    Set<Int> trunc_vertices
    the vertex/vertices to be cut off; A single vertex to be cut off is specified by its number. Several vertices can be passed in a Set or in an anonymous array of indices: [n1,n2,...] Special keyword All means that all vertices are to be cut off.
    Options
    Rational cutoff
    controls the exact location of the cutting hyperplane(s); rational number between 0 and 1; default value: 1/2
    Bool noc
    produces a pure combinatorial description (in contrast to cutoff)
    Bool relabel
    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 (n) → Polytope

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

    Parameters
    Int n
    the number of random points
    Options
    Bool boundary
    forces the points to lie on the boundary of the given polytope
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Polytope
  •  
    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
    Polytope p
    Int n
    number of the chosen vertex
    Options
    Rational cutoff
    controls the exact location of the cutting hyperplane. It should lie between 0 and 1. Value 0 would let the hyperplane go through the chosen vertex, thus degenerating the vertex figure to a single point. Value 1 would let the hyperplane touch the nearest neighbor vertex of a polyhedron. Default value is 1/2.
    Bool noc
    skip the coordinates computation, producing a pure combinatorial description.
    Bool relabel
    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
    Polytope P
    Int facet
    the `cutting edge'.
    Rational z
    default value is 0.
    Rational z_prime
    default value is -z, or 1 if z==0.
    Options
    Bool noc
    don't compute coordinates, pure combinatorial description is produced.
    Bool relabel
    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
    Polytope P1
    Polytope P2
    Options
    Bool dual
    invokes the computation of the dual wreath product
    Bool relabel
    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
  •  
  •  
    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
    Matrix zones
    the input vectors
    Returns
    Matrix
  •  
  •  
    cut_polytope (G) → Polytope

    Cut polytope of an undirected graph.

    Parameters
    Graph G
    Returns
    Polytope
  •  
    matching_polytope (G) → Polytope

    Matching polytope of an undirected graph.

    Parameters
    Graph G
    Returns
    Polytope
  •  
  •  
    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
    Int d
    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
    Int n
    Bool even
    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
    Int d
    the dimension
    Rational scale
    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
    Int d
    the dimension
    Rational x_up
    Rational x_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
    Int d
    the dimension
    Int n
    the number of points
    Int start
    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
    Int d
    the dimension
    Int n
    the number of points
    Returns
    Polytope
  •  
    dwarfed_cube (d) → Polytope

    Produce a d-dimensional dwarfed cube.

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

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

    Parameters
    Int d
    the dimension
    Int s
    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
    Int d
    the dimension
    Rational e
    Rational g
    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
    Int k
    number of 1s
    Int d
    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
    Int d
    the dimension
    Rational k
    cutoff parameter
    Rational lambda
    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
    Int n
    Vector s
    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
    Int d
    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
    Int d
    the dimension
    Int n
    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
    Int d
    dimension of the polytope
    Int n
    dimension of the equivalent cube
    Returns
    Polytope
  •  
    newton (p) → LatticePolytope

    Produce the Newton polytope of a polynomial p.

    Parameters
    Polynomial p
    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
    Int n
    the number of vertices
    Double r
    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
    Int d
    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
    Int d
    the dimension
    Int n
    the number of random vertices
    Options
    Int seed
    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
    Int d
    the dimension of the box
    Int n
    the number of random points
    Int b
    the size of the box
    Options
    Int seed
    controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
    Returns
    Polytope
  •  
    rand_metric (n) → Matrix

    Produce an n-point metric with random distances. The values are uniformily distributed in [1,2].

    Parameters
    Int n
    Options
    Int seed
    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
    Int d
    the dimension
    Int n
    the number of random vertices
    Options
    Int seed
    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
    Int l
    ambient dimension
    Returns
    Polytope
  •  
    signed_permutahedron (d) → Polytope

    Produce a d-dimensional signed permutahedron.

    Parameters
    Int d
    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
    Int d
    the dimension
    Rational scale
    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
    Vector r
    Vector c
    Returns
    Polytope
  •  
  •  
    barycentric_subdivision (pc) → PointConfiguration

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

    Parameters
    PointConfiguration pc
    input point configuration
    Options
    Bool no_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
    Matrix points
    Array<Set> sub1
    first subdivision
    Array<Set> sub2
    second subdivision
    Int dim
    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
    Polytope p1
    Polytope p2
    Returns
    Polytope
  •  
    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
    Matrix points
    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
    Matrix Points
    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
    Matrix points
    Vector weights
    Returns
    Array<Set<Int>>
  •  
    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
    Matrix V
    vertices of the polytope
    Graph G
    graph of the polytope
    Matrix F
    facets of the polytope
    Int dimension
    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
    Matrix vertices
    the vertices of the polyhedron
    Array<Set<Int>> subdivision
    a subdivision of the polyhedron
    Matrix splits
    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
    Matrix splits
    the splits given by split equations
    Polytope P
    the input polytope
    Returns
    Graph
  •  
    split_polyhedron (P) → Polytope

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

    Parameters
    Polytope P
    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
    Int k
    the dimension of the first simplex
    Int l
    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
    PointConfiguration pc
    input point configuration
    Array<Set<Int>> faces
    list of faces to subdivide
    Options
    Bool no_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
    Matrix points
    Vector weight
    Bool full
    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
    Polytope P
    Returns
    Polytope
    (The polymake object TightSpan is only used for tight spans of finite metric spaces, not for tight spans of subdivisions in general.)
  •  
  •  
    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
    Int n
    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
    TightSpan FMS
    Returns
    Polytope
  •  
    metric2splits (D) → Array<Pair<Set>>

    Computes the split decomposition of a metric space D (encoded as a symmetric distance matrix).

    Parameters
    Matrix D
    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
    Int n
    the number of points
    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
    Polytope P
    Options
    Bool max
    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
    Int n
    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
    Int n
    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
    Int n
    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
    Int n
    the number of points
    Returns
    TightSpan
  •  
  •  
    ambient_lattice_normalization (p) → Polytope

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

    Parameters
    Polytope p
    the input polytope,
    Options
    Bool store_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
    Polytope p
    the input polytope,
    Options
    Bool store_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
    Polytope P
    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
    Polytope P
    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
    Polytope P
    Int v
    vertex to be moved to the origin. By default it is the first affine vertex of the polyhedron.
    Returns
    Polytope
  •  
    polarize (P) → Polytope

    Given a bounded, centered, and full-dimensional polytope P, produce its polar, that is, polar with respect to the standard Euclidean scalar product.

    Parameters
    Polytope P
    Options
    Bool noc
    only combinatorial information is handled
    Returns
    Polytope
  •  
    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
    Polytope P
    a (transformed) polytope
    Returns
    Polytope
  •  
    scale (P, factor, store) → Polytope

    Scale a polyhedron P by a given scaling parameter factor.

    Parameters
    Polytope P
    the polyhedron to be scaled
    Scalar factor
    the scaling factor
    Bool store
    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
    Polytope P
    the polyhedron to be transformed
    Matrix trans
    the transformation matrix
    Bool store
    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
    Polytope P
    the polyhedron to be translated
    Vector trans
    the translation vector
    Bool store
    stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.
    Returns
    Polytope
  •  
  •  
    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
    String file
    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
    Polytope P
    LinearProgram LP
    default value: P->LP
    Bool maximize
    produces a maximization problem; default value: 0 (minimize)
    String file
    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
    String file
    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
    IncidenceMatrix VIF
    Bool dual
  •  
  •  
    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
    Matrix V
    vertices that should be in the box
    Rational surplus_k
    size of the bounding box relative to the box spanned by V
    Bool voronoi
    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
    Polytope p
    Matrix V
    Graph G
  •  
    splitstree (vis_obj ...)

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

    Parameters
    Visual::Object vis_obj ...
    objects to display
    Options
    String File
    "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.
  • Common Option Lists