[[application: polytope]]

# 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

- ###
  GeometricGraph

  An undirected graph with given node coordinates and a bounding box

  derived from: graph::Graph<Undirected>

  #### Properties of GeometricGraph

  - BOUNDING_BOX: common::Matrix<Rational>

    Since a Voronoi polyhedron is unbounded it must be artificially bounded for visualization purposes. Allowed is any set of hyperplanes which makes the projection onto the last d-1 coordinates bounded. By default, these are the vertical facets of a suitably scaled cube.

  - COORDINATES: common::NodeMap<Undirected, Vector<Rational>>

    The coordinates of the nodes of the graph.

- ###
  GroebnerBasis

  The Groebner basis of the homogeneous toric ideal associated to the polytope, the term order is given in matrix form.

  #### Properties of GroebnerBasis

  - BASIS: common::Matrix<Integer>

    The Groebner basis for a defined term order

  - TERM_ORDER_MATRIX: common::Matrix<Integer>

    The term order in matrix form; if not square, then a tie breaker is used.

  - TERM_ORDER_NAME: common::String

    A term order by name; allowed acronyms are `lex`, `deglex` and `degrevlex`.

- ###
  LatticePolytope

  Polytope all of whose vertex coordinates are integral

  derived from: Polytope<Rational>

  #### Properties of LatticePolytope

  - CANONICAL: common::Bool

    The polytope is canonical if there is exactly one interior lattice point.

  - COMPRESSED: common::Bool

    True if the facet width is one.

  - EHRHART_POLYNOMIAL_COEFF: common::Vector<Rational>

    The coefficients of the Ehrhart polynomial starting at the constant coefficient.

  - FACET_VERTEX_LATTICE_DISTANCES: common::Matrix<Integer>

    The entry (i,j) equals the lattice distance of vertex j from facet i.

  - FACET_WIDTH: common::Integer

    The maximal integral width of the polytope with respect to the facet normals.

  - FACET_WIDTHS: common::Vector<Integer>

    The integral width of the polytope with respect to each facet normal.

  - GORENSTEIN: common::Bool

    The polytope is Gorenstein if a dilation of the polytope is reflexive up to translation.

  - GORENSTEIN_INDEX: common::Integer

    If the polytope is Gorenstein then this is the multiple such that the polytope is reflexive.

  - GORENSTEIN_VECTOR: common::Vector<Integer>

    If the polytope is Gorenstein, then this is the unique interior lattice point in the multiple of the polytope that is reflexive.

  - GROEBNER_BASIS: GroebnerBasis

    The Groebner basis for the toric ideal associated to the lattice points in the polytope using any term order.

  - H_STAR_VECTOR: common::Vector<Integer>

    The coefficients of the h^*-polynomial starting at the constant coefficient

  - LATTICE_CODEGREE: common::Int

    DIM+1-LATTICE_DEGREE or the smallest integer k such that k*P has an interior lattice point.

  - LATTICE_DEGREE: common::Int

    The degree of the h*-polynomial or Ehrhart polynomial.

  - LATTICE_EMPTY: common::Bool

    True if the polytope contains no lattice points other than the vertices.

  - LATTICE_VOLUME: common::Integer

    The normalized volume of the polytope.

  - NORMAL: common::Bool

    The polytope is normal if the cone spanned by P x {1} is generated in height 1.

  - REFLEXIVE: common::Bool

    True if the polytope and its dual have integral vertices.

  - SMOOTH: common::Bool

    The polytope is smooth if the associated projective variety is smooth; the determinant of the edge directions is +/-1 at every vertex.

  - TERMINAL: common::Bool

    The polytope is terminal if there is exactly one interior lattice point and all other lattice points are vertices.

  - VERY_AMPLE: common::Bool

    The polytope is very ample if the Hilbert Basis of the cone spanned by the edge-directions of any vertex lies inside the polytope.

  #### User Methods of LatticePolytope

  - ###
    Lattice polytopes

  - FACET_POINT_LATTICE_DISTANCES (v) → Vector<Integer>

    Vector containing the distances of a given point v from all facets

    ##### Parameters

    Vector<Rational> | v | point in the ambient space of the polytope

    ##### Returns

    Vector<Integer> |

  - N_LATTICE_POINTS_IN_DILATION (n)

    The number of LATTICE_POINTS in the n-th dilation of the polytope

    ##### Parameters

    Int | n | dilation factor

- ###
  LinearProgram

  Category: Optimization

  A linear program specified by a linear or abstract objective function

  #### Properties of LinearProgram

  - ABSTRACT_OBJECTIVE: common::Vector<Scalar>

    Abstract objective function. Defines a direction for each edge such that each non-empty face has a unique source and a unique sink. The i-th element is the value of the objective function at vertex number i. Only defined for bounded polytopes.

  - DIRECTED_GRAPH: graph::Graph<Directed>

    Subgraph of Polytope::GRAPH. Consists only of directed arcs along which the value of the objective function increases.

  - LINEAR_OBJECTIVE: common::Vector<Scalar>

    Linear objective function. In d-space a linear objective function is given by a (d+1)-vector. The first coordinate specifies a constant that is added to the resulting value.

  - MAXIMAL_FACE: common::Set<Int>

    Indices of vertices at which the maximum of the objective function is attained.

  - MAXIMAL_VALUE: Scalar

    Maximum value of the objective function. Negated if linear problem is unbounded.

  - MAXIMAL_VERTEX: common::Vector<Scalar>

    Coordinates of a (possibly not unique) affine vertex at which the maximum of the objective function is attained.

  - MINIMAL_FACE: common::Set<Int>

    Similar to MAXIMAL_FACE.

  - MINIMAL_VALUE: Scalar

    Similar to MAXIMAL_VALUE.

  - MINIMAL_VERTEX: common::Vector<Scalar>

    Similar to MAXIMAL_VERTEX.

  - RANDOM_EDGE_EPL: common::Vector<Rational>

    Expected average path length for a simplex algorithm employing "random edge" pivoting strategy.

  - ###
    Unbounded polyhedra

  - DIRECTED_BOUNDED_GRAPH: graph::Graph<Directed>

    Subgraph of BOUNDED_GRAPH. Consists only of directed arcs along which the value of the objective function increases.

#### User Methods of LinearProgram

- VERTEX_IN_DEGREES ()

  Array of in-degrees for all nodes of DIRECTED_GRAPH or numbers of objective decreasing edges at each vertex

- VERTEX_OUT_DEGREES ()

  Array of out-degrees for all nodes of DIRECTED_GRAPH or numbers of objective increasing edges at each vertex

- ###
  PointConfiguration

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

  #### Properties of PointConfiguration

  - SPLITS: common::Matrix<Scalar>

    The splits of the point configuration, i.e., hyperplanes cutting the configuration in two parts such that we have a regular subdivision.

  - SPLITS_IN_SUBDIVISION: common::Set<Int>

    The splits that are coarsenings of the current POLYTOPAL_SUBDIVISION. If the subdivision is regular these form the unique split decomposition of the corresponding weight function.

  - SPLIT_COMPATIBILITY_GRAPH: graph::Graph<Undirected>

    Two SPLITS are compatible if the defining hyperplanes do not intersect in the interior of the point configuration. This defines a graph.

  - ###
    Basic properties

  - AFFINE_HULL: common::Matrix<Scalar>

    Dual basis of the affine hull of the polyhedron.

  - AMBIENT_DIM: common::Int

    Dimension of the space in which the point configuration lives.

  - BARYCENTER: common::Vector<Scalar>

    The center of gravity of the point configuration.

  - BOUNDED: common::Bool

    True if the point configuration is a bounded polytope.

  - CONVEX: common::Bool

    True if the POINTS are in convex position.

  - CONVEX_HULL: Polytope<Scalar>

    The polytope being the convex hull of the point configuration.

    #### Properties of CONVEX_HULL

    - VERTEX_POINT_MAP: common::Array<Int>

      Indices of Polytope::VERTICES of the CONVEX_HULL as POINTS.

  - DIM: common::Int

    Dimension of the affine hull of the point configuration.

  - LABELS: common::Array<String>

    Unique names assigned to the POINTS. If specified, they are shown by visualization tools instead of point indices.

  - NON_VERTICES: common::Set<Int>

    POINTS that are not Polytope::VERTICES of the CONVEX_HULL

  - N_POINTS: common::Int

    Number of POINTS.

  - POINTS: common::Matrix<Scalar>

    The Points of the configuration

  - VERTEX_POINT_MAP: common::Array<Int>

    Indices of Polytope::VERTICES of the CONVEX_HULL as POINTS

- ###
  Combinatorics

- GRAPH: graph::Graph<Undirected>

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

- ###
  Oriented matroids

- CHIROTOPE: common::Text

  Chirotope corresponding to POINTS

- ###
  Triangulation and volume

- GKZ_VECTOR: common::Vector<Scalar>

  GKZ-vector of TRIANGULATION.

- 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

  - FACET_TRIANGULATIONS: common::Array<Set<Int>>

    DOC_FIXME: Incomprehensible description! For each facet the set of simplex indices of BOUNDARY that triangulate it.

  - GKZ_VECTOR: common::Vector<Scalar>

    GKZ-vector

    > See Chapter 7 in Gelfand, Kapranov, and Zelevinsky:
    > Discriminants, Resultants and Multidimensional Determinants, Birkhäuser 1994

  - REFINED_SPLITS: common::Set<Int>

    The splits that are coarsenings of the current TRIANGULATION. If the triangulation is regular these form the unique split decomposition of the corresponding weight function.

- WEIGHTS: common::Vector<Scalar>

  The weight vector to construct a TRIANGULATION.

- WEIGHTS_GENERIC: common::Bool

  Tells that WEIGHTS are generic.

- ###
  Unbounded polyhedra

- FAR_POINTS: common::Set<Int>

  Indices of POINTS that are rays.

- ###
  Visualization

- PIF_CYCLIC_NORMAL: common::Array<List<Int>>

  Polytope::VIF_CYCLIC_NORMAL of the CONVEX_HULL, but with the indices form POINTS instead of Polytope::VERTICES

#### User Methods of PointConfiguration

- VISUAL ()

  UNDOCUMENTED

  ##### Options

  option list: | Visual::Polygons::decorations

- ###
  Triangulation and volume

- TRIANGULATION_SIGNS () → Array<int>

  For each simplex in the TRIANGULATION, this contains the sign of the determinant of its coordinate matrix, which is the orientation of the simplex.

  ##### Returns

  Array<int> |

- ###
  Visualization

- VISUAL () → Visual::PointConfiguration

  Visualize a point configuration.

  ##### Options

  option list: | Visual::Polygons::decorations

  ##### Returns

  Visual::PointConfiguration |

- VISUAL_POINTS () → Visual::PointSet

  Visualize the POINTS of a point configuration.

  ##### Options

  option list: | Visual::Polygons::decorations

  ##### Returns

  Visual::PointSet |

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

  - CENTROID: common::Vector<Scalar>

    Centroid (center of mass) of the polytope.

  - SPLITS: common::Matrix<Scalar>

    The splits of the polytope, i.e., hyperplanes cutting the polytope in two parts such that we have a regular subdivision.

  - SPLITS_IN_SUBDIVISION: common::Set<Int>

    The splits that are coarsenings of the current POLYTOPAL_SUBDIVISION. If the subdivision is regular these form the unique split decomposition of the corresponding weight function.

  - SPLIT_COMPATIBILITY_GRAPH: graph::Graph<Undirected>

    Two SPLITS are compatible if the defining hyperplanes do not intersect in the interior of the polytope. This defines a graph.

  - STEINER_POINT: common::Vector<Scalar>

    Steiner point of the whole polytope

  - ###
    Basic properties

  - AFFINE_HULL: common::Matrix<Scalar>

    Dual basis of the affine hull of the polyhedron.

  - AMBIENT_DIM: common::Int

    Dimension of the space in which the polyhedron lives.

  - BOUNDED: common::Bool

    True if the polyhedron is a bounded polytope.

  - CENTERED: common::Bool

    True if (1, 0, 0, ...) is in the relative interior. Polar to BOUNDED.

  - DIM: common::Int

    Dimension of the affine hull of the polyhedron = dimension of the polyhedron. If the polytope is given purely combinatorially, this is the dimension of a minimal embedding space deduced from the combinatorial structure.

  - EQUATIONS: common::Matrix<Scalar>

    Equations that hold for all points of the polyhedron.

    A vector (A0, A1, ..., Ad) describes the hyperplane of all points (1, x1, ..., xd) such that A0 + A1 x1 + ... + Ad xd = 0.

    Input section only. Ask for AFFINE_HULL if you want to see an irredundant description of the affine span.

  - FACETS: common::Matrix<Scalar>

    Facets of the polyhedron, encoded as INEQUALITIES. Dual to VERTICES.

  - FACET_LABELS: common::Array<String>

    Unique names assigned to the FACETS, analogous to VERTEX_LABELS.

  - FEASIBLE: common::Bool

    True if the polyhedron is not empty.

  - GALE_TRANSFORM: common::Matrix<Scalar>

    Coordinates of the Gale transform.

  - INEQUALITIES: common::Matrix<Scalar>

    Inequalities that describe half-spaces such that the polyhedron is their intersection. Redundancies are allowed. Dual to POINTS.

    A vector (A0, A1, ..., Ad) defines the (closed affine) half-space of points (1, x1, ..., xd) such that A0 + A1 x1 + ... + Ad xd >= 0.

    Input section only. Ask for FACETS and AFFINE_HULL if you want to compute an H-representation from a V-representation.

  - LINEALITY_DIM: common::Int

    Dimension of the LINEALITY_SPACE (>0 in the non-POINTED case)

  - LINEALITY_SPACE: common::Matrix<Scalar>

    Basis of the linear subspace orthogonal to all INEQUALITIES and EQUATIONS

  - MINIMAL_VERTEX_ANGLE: common::Float

    The minimal angle between any two vertices (seen from the VERTEX_BARYCENTER).

  - N_INEQUALITIES: common::Int

    Number of INEQUALITIES.

  - N_POINTS: common::Int

    Number of POINTS.

  - ONE_VERTEX: common::Vector<Scalar>

    A vertex of a pointed polyhedron.

  - POINTED: common::Bool

    True if the polyhedron does not contain an affine line.

  - POINTS: common::Matrix<Scalar>

    Points such that the polyhedron is their convex hull. Redundancies are allowed. The vector (x0, x1, ... xd) represents a point in d-space given in homogeneous coordinates. Affine points are identified by x0 > 0. Points with x0 = 0 can be interpreted as rays.

    polymake automatically normalizes each coordinate vector, dividing them by the first non-zero element. The clients and rule subroutines can always assume that x0 is either 0 or 1. Dual to INEQUALITIES.

    Input section only. Ask for VERTICES if you want to compute a V-representation from an H-representation.

  - POSITIVE: common::Bool

    True if all vertices of the polyhedron have non-negative coordinates, that is, it lies entirely in the positive orthant.

  - STEINER_POINTS: common::Matrix<Scalar>

    A weighted inner point depending on the outer angle called Steiner point for all faces of dimensions 2 to d.

  - VALID_POINT: common::Vector<Scalar>

    Some point belonging to the polyhedron.

  - VERTEX_BARYCENTER: common::Vector<Scalar>

    The center of gravity of the vertices of a bounded polytope.

  - VERTEX_LABELS: common::Array<String>

    Unique names assigned to the VERTICES. If specified, they are shown by visualization tools instead of vertex indices.

    For a polytope build from scratch, you should create this property by yourself, either manually in a text editor, or with a client program.

    If you build a polytope with a construction function taking some other input polytope(s), you can create the labels automatically if you call the function with a relabel option. The exact format of the labels is dependent on the construction, and is described in the corresponding help topic.

  - VERTEX_NORMALS: common::Matrix<Scalar>

    The i-th row is the normal vector of a hyperplane separating the i-th vertex from the others. This property is a by-product of redundant point elimination algorithm.

  - VERTICES: common::Matrix<Scalar>

    Vertices of the polyhedron. No redundancies are allowed. The coordinates are normalized the same way as POINTS. Dual to FACETS.

  - ZONOTOPE_INPUT_VECTORS: common::Matrix<Scalar>

    DOC_FIXME: Incomprehensible! Contains the vector configuration for which a zonotope can be built.

- ###
  Combinatorics

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

- BALANCED: common::Bool

  Dual to NEIGHBORLY.

- CD_INDEX_COEFFICIENTS: common::Vector<Integer>

  Coefficients of the cd-index.

- COCUBICAL: common::Bool

  Dual to CUBICAL.

- COCUBICALITY: common::Int

  Dual to CUBICALITY.

- 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

  - EDGE_DIRECTIONS: common::EdgeMap<Undirected, Vector<Scalar>>

    Difference of the vertices for each edge (only defined up to signs).

- 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

- INEQUALITIES_THRU_VERTICES: common::IncidenceMatrix<NonSymmetric>

  transposed VERTICES_IN_INEQUALITIES

- 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_FACETS: common::Int

  Number of FACETS.

- N_VERTEX_FACET_INC: common::Int

  Number of pairs of incident vertices and facets.

- N_VERTICES: common::Int

  Number of VERTICES.

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

- ###
  Convex hull computation

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

- ###
  Optimization

- LP: LinearProgram<Scalar>

  Linear program applied to the polytope

- ###
  Oriented matroids

- CHIROTOPE: common::Text

  Chirotope corresponding to the VERTICES

- ###
  Polarization

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

- ###
  Triangulation and volume

- 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

  - FACET_TRIANGULATIONS: common::Array<Set<Int>>

    For each facet the set of simplex indices of BOUNDARY that triangulate it.

  - GKZ_VECTOR: common::Vector<Scalar>

    GKZ-vector

    > See Chapter 7 in Gelfand, Kapranov, and Zelevinsky:
    > Discriminants, Resultants and Multidimensional Determinants, Birkhäuser 1994

  - REFINED_SPLITS: common::Set<Int>

    The splits that are coarsenings of the current TRIANGULATION. If the triangulation is regular these form the unique split decomposition of the corresponding weight function.

- TRIANGULATION_INT: common::Array<Set<Int>>

  Similar to TRIANGULATION, but using POINTS.

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

- ###
  Unbounded polyhedra

- 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

  - EDGE_COLORS: common::EdgeMap<Undirected, Int>

    Each edge indicates the maximal dimension of a bounded face containing it. Mainly used for visualization purposes.

  - EDGE_DIRECTIONS: common::EdgeMap<Undirected, Vector<Scalar>>

    Difference of the vertices for each edge (only defined up to signs).

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

- ###
  Visualization

- FTV_CYCLIC_NORMAL: common::Array<List<Int>>

  Reordered transposed VERTICES_IN_FACETS. Dual to VIF_CYCLIC_NORMAL.

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

- NEIGHBOR_VERTICES_CYCLIC_NORMAL: common::Array<List<Int>>

  Reordered GRAPH. Dual to NEIGHBOR_FACETS_CYCLIC_NORMAL.

- 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

- labeled_vertices (label ...) → Set<Int>

  Find the vertices by given labels.

  ##### Parameters

  String | label ... | vertex labels

  ##### Returns

  Set<Int> | vertex indices

- ###
  Backward compatibility

- DIAMETER ()

  The diameter of the GRAPH of the polytope

- DUAL_DIAMETER ()

  The diameter of the DUAL_GRAPH

- DUAL_TRIANGLE_FREE ()

  True if the DUAL_GRAPH contains no triangle

- N_EDGES ()

  The number of edges of the GRAPH

- TRIANGLE_FREE ()

  True if the GRAPH contains no triangle

- ###
  Combinatorics

- CONNECTIVITY ()

  Connectivity of the GRAPH this is the minimum number of nodes that have to be removed from the GRAPH to make it disconnected

- DUAL_CONNECTIVITY ()

  Connectivity of the DUAL_GRAPH this is the minimum number of nodes that have to be removed from the DUAL_GRAPH to make it disconnected

- DUAL_EVEN ()

  True if the DUAL_GRAPH is bipartite

- EVEN ()

  True if the GRAPH is bipartite

- FACET_DEGREES () → Vector<Int>

  Facet degrees of the polytope. The degree of a facet is the number of adjacent facets.

  ##### Returns

  Vector<Int> | - in the same order as FACETS

- N_FLAGS (type ...)

  Determine the number of flags of a given type. type must belong to {0,...,DIM-1}. Example: "N_FLAGS(0,3,4)" determines the entry f034 of the flag vector.

  ##### Parameters

  Int | type ... | flag type

- N_RIDGES ()

  The number of ridges (faces of codimension 2) of the polytope equals the number of edges of the DUAL_GRAPH

- VERTEX_DEGREES () → Vector<Int>

  Vertex degrees of the polytope

  ##### Returns

  Vector<Int> | - in the same order as VERTICES

- ###
  Formatting

- CD_INDEX ()

  Prettily print the cd-index given in CD_INDEX_COEFFICIENTS

- ###
  Topology

- DUAL_GRAPH_SIGNATURE ()

  Difference of the black and white nodes if the DUAL_GRAPH is BIPARTITE. Otherwise -1.

- GRAPH_SIGNATURE ()

  Difference of the black and white nodes if the GRAPH is BIPARTITE. Otherwise -1.

- ###
  Triangulation and volume

- TRIANGULATION_INT_SIGNS () → Array<Int>

  the orientation of the simplices of TRIANGULATION_INT in the given order of the POINTS

  ##### Returns

  Array<Int> | - +1/-1 array specifying the sign of the determinant of each simplex

- TRIANGULATION_SIGNS () → Array<Int>

  For each simplex in the TRIANGULATION, contains the sign of the determinant of its coordinate matrix, telling about its orientation.

  ##### Returns

  Array<Int> |

- ###
  Unbounded polyhedra

- BOUNDED_FACETS () → Set<Int>

  Indices of FACETS that are bounded.

  ##### Returns

  Set<Int> |

- BOUNDED_VERTICES () → Set<Int>

  Indices of VERTICES that are no rays.

  ##### Returns

  Set<Int> |

- ###
  Visualization

- GALE () → Visual::Gale

  Generate the Gale diagram of a d-polyhedron with at most d+4 vertices.

  ##### Returns

  Visual::Gale |

- SCHLEGEL () → Visual::SchlegelDiagram

  Create a Schlegel diagram and draw it.

  ##### Options

  FIXME | proj_facet | decorations for the Edges of the projection face
  option list: | schlegel_init
  option list: | Visual::Wire::decorations

  ##### Returns

  Visual::SchlegelDiagram |

- VISUAL () → Visual::Polytope

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

  ##### Options

  option list: | Visual::Polygons::decorations

  ##### Returns

  Visual::Polytope |

- VISUAL_BOUNDED_GRAPH () → Visual::PolytopeGraph

  Visualize the BOUNDED_GRAPH of a polyhedron.

  ##### Options

  Int | seed | random seed value for the string embedder
  option list: | Visual::Graph::decorations

  ##### Returns

  Visual::PolytopeGraph |

- VISUAL_DUAL () → Visual::Polygons

  Visualize the dual polytope as a solid 3-d object. The polytope must be BOUNDED and CENTERED.

  ##### Options

  option list: | Visual::Polygons::decorations

  ##### Returns

  Visual::Polygons |

- VISUAL_DUAL_FACE_LATTICE () → Visual::PolytopeLattice

  Visualize the dual face lattice of a polyhedron as a multi-layer graph.

  ##### Options

  Int | seed | random seed value for the node placement
  option list: | Visual::Lattice::decorations

  ##### Returns

  Visual::PolytopeLattice |

- VISUAL_DUAL_GRAPH () → Visual::Graph

  Visualize the DUAL_GRAPH of a polyhedron.

  ##### Options

  Int | seed | random seed value for the string embedder
  option list: | Visual::Graph::decorations

  ##### Returns

  Visual::Graph |

- VISUAL_FACE_LATTICE () → Visual::PolytopeLattice

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

  ##### Options

  Int | seed | random seed value for the node placement
  option list: | Visual::Lattice::decorations

  ##### Returns

  Visual::PolytopeLattice |

- VISUAL_GRAPH () → Visual::PolytopeGraph

  Visualize the GRAPH of a polyhedron.

  ##### Options

  Int | seed | random seed value for the string embedder
  option list: | Visual::Graph::decorations

  ##### Returns

  Visual::PolytopeGraph |

- VISUAL_TRIANGULATION_BOUNDARY () → Visual::Polygons

  Visualize the TRIANGULATION_BOUNDARY of the polytope. Obsolete: the preferred procedure is to create a SimplicialComplex using the boundary_complex client of the application <a target="_top" href="../../topaz/model.html">topaz</a> and call its VISUAL method.

  ##### Options

  option list: | Visual::Polygon::decorations

  ##### Returns

  Visual::Polygons |

#### Permutations of Polytope

- FacetPerm
  UNDOCUMENTED

  #### Properties of FacetPerm

  - PERMUTATION: common::Array<Int>

    Transforming FACETS from this into basic object

- VertexPerm
  UNDOCUMENTED

  #### Properties of VertexPerm

  - PERMUTATION: common::Array<Int>

    Transforming VERTICES from this into basic object

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

  - EPSILON: common::Float

    Threshold for zero test for scalar products (e.g. vertex * facet normal)

- ###
  Polytope<Rational>

  derived from: Polytope

  #### Properties of Polytope<Rational>

  - BOUNDARY_LATTICE_POINTS: common::Matrix<Integer>

    The lattice points on the boundary of the polytope, including the vertices

  - HILBERT_BASIS: common::Matrix<Integer>

    The Hilbert basis spanned of the cone spanned by P x {1}

  - INTERIOR_LATTICE_POINTS: common::Matrix<Integer>

    The lattice points strictly in the interior of the polytope

  - LATTICE_POINTS: common::Matrix<Integer>

    The lattice points in the polytope

  - N_BOUNDARY_LATTICE_POINTS: common::Int

    The number of BOUNDARY_LATTICE_POINTS

  - N_HILBERT_BASIS: common::Int

    The number of elements of HILBERT_BASIS

  - N_INTERIOR_LATTICE_POINTS: common::Int

    The number of INTERIOR_LATTICE_POINTS

  - N_LATTICE_POINTS: common::Int

    The number of LATTICE_POINTS

  - ###
    0/1-polytopes

  - N_01POINTS: common::Int

    Number of points with 0/1-coordinates in a polytope.

- ###
  Lattice polytopes

- 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

  - SUM_PRODUCT_GRAPH: graph::Graph<Directed>

    Directed graph to define the propagated polytope. There is a (translation) vector assigned to each arc. We assume that this graph is acyclic with a unique sink.

    #### Properties of SUM_PRODUCT_GRAPH

    - TRANSLATIONS: common::EdgeMap<Directed, Vector<Rational>>

      The translation vectors of the arcs.

- ###
  SchlegelDiagram

  A Schlegel diagram of a polytope

  #### Properties of SchlegelDiagram

  - FACET: common::Int

    The facet number in the original polytope, giving the projection plane.

  - FACET_POINT: common::Vector<Scalar>

    The intersection point of the projection facet and the view ray.

  - INNER_POINT: common::Vector<Scalar>

    A point on the view ray lying inside the polytope.

  - ROTATION: common::Matrix<Float>

    Rotation matrix making the projection facet coinciding with (0 0 0 -1) We want a negatively oriented coordinate system since the view point lies on the negative side of the facet.

  - TRANSFORM: common::Matrix<Scalar>

    Matrix of a projective transformation mapping the whole polytope into the FACET The points belonging to this facet stay fixed.

  - VERTICES: common::Matrix<Float>

    Coordinates in affine 3-space of the vertices which correspond to a 3-dimensional (Schlegel-) projection of a 4-polytope.

  - VIEWPOINT: common::Vector<Scalar>

    The center point of the projection, lying outside the polytope.

  - ZOOM: Scalar

    Zoom factor.

  #### User Methods of SchlegelDiagram

  - VISUAL () → Visual::SchlegelDiagram

    Draw the Schlegel diagram

    ##### Options

    pm::perl::Hash | proj_facet | decoration for the edges of the projection face
    option list: | Visual::Graph::decorations

    ##### Returns

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

  - ###
    Phylogenetic Analysis

  - COHERENT_SPLITS: common::Array<Pair<Set<Int>, Set<Int>>>

    Coherent splits.

  - METRIC: common::Matrix<Scalar>

    Finite metric space encoded as a (symmetric) distance matrix.

  - TAXA: common::Array<String>

    Labels for the rows and columns of the METRIC space. Default TAXA are just consecutive numbers.

  - VERTICES_IN_METRIC: common::Array<Int>

    Row indices in the METRIC matrix or -1

#### User Methods of TightSpan

- ###
  Visualization

- VISUAL_BOUNDED_GRAPH () → Visual::PolytopeGraph

  Visualize the BOUNDED_GRAPH of a tight span.

  ##### Options

  Int | seed | random seed value for the string embedder
  option list: | Visual::Graph::decorations

  ##### Returns

  Visual::PolytopeGraph |

- VISUAL_TIGHT_SPAN () → Visual::Graph

  This is a variation of Polytope::VISUAL_BOUNDED_GRAPH for the special case of a tight span. The tropical vertices are embedded according to the METRIC, the others are hanged in between.

  ##### Options

  Int | seed | random seed value for the string embedder
  String | norm | which norm to use when calculating the distances between metric vectors ("max" or "square")
  option list: | Visual::Graph::decorations

  ##### Returns

  Visual::Graph |

- ###
  Visual::PointConfiguration

  Category: Visualization

  Visualization of the point configuration.

  #### User Methods of Visual::PointConfiguration

  - ###
    Visualization

  - POLYTOPAL_SUBDIVISION () → Visual::PointConfiguration

    Visualize the POLYTOPAL_SUBDIVISION of a point configuration

    ##### Options

    option list: | Visual::Polygons::decorations

    ##### Returns

    Visual::PointConfiguration |

  - TRIANGULATION () → Visual::PointConfiguration

    Visualize the TRIANGULATION of a point configuration

    ##### Options

    option list: | Visual::Polygons::decorations

    ##### Returns

    Visual::PointConfiguration |

  - TRIANGULATION_BOUNDARY () → Visual::PointConfiguration

    Draw the edges of the TRIANGULATION_BOUNDARY. The facets are made transparent.

    ##### Options

    option list: | Visual::Graph::decorations

    ##### Returns

    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

  - DIRECTED_GRAPH (lp) → Visual::Polytope

    Illustrate the behavior of a linear objective function on the polytope. Superpose the drawing with the directed graph induced by the objective function.

    ##### Parameters

    LinearProgram | lp | a Linear Program object attached to the polytope

    ##### Returns

    Visual::Polytope |

  - MIN_MAX_FACE (lp) → Visual::Polytope

    Illustrate the behavior of a linear objective function on the polytope. Draw the facets contained in 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 vertices and/or facets)
    Color | max | maximal face decoration (default: red vertices and/or facets)

    ##### Returns

    Visual::Polytope |

  - VERTEX_COLORS (lp) → Visual::Polytope

    Illustrate the behavior of a linear objective function on the polytope. Color the vertices according to the values of the objective function.

    ##### Parameters

    LinearProgram | lp | a LinearProgram object attached to the polytope

    ##### Options

    Color | min | minimal vertex color (default: yellow)
    Color | max | maximal vertex color (default: red)

    ##### Returns

    Visual::Polytope |

  - ###
    Visualization

  - LATTICE () → Visual::Polytope

    Visualize the LATTICE_POINTS of a polytope

    ##### Options

    option list: | Visual::PointSet::decorations

    ##### Returns

    Visual::Polytope |

  - LATTICE_COLORED () → Visual::Polytope

    Visualize the LATTICE_POINTS of a polytope in different colors (interior / boundary / vertices)

    ##### Options

    option list: | Visual::PointSet::decorations

    ##### Returns

    Visual::Polytope |

  - STEINER () → Visual::Polytope

    Add the STEINER_POINTS to the 3-d visualization. The facets become transparent.

    ##### Options

    option list: | Visual::PointSet::decorations

    ##### Returns

    Visual::Polytope |

  - TRIANGULATION (TR) → Visual::Polytope

    Add the triangulation to the drawing. The facets of the whole polytope become transparent.

    You may specify any triangulation of the current polytope. Per default, the TRIANGULATION property is taken. (Currently there is only one possible alternative triangulation: TRIANGULATION_INT).

    Hint: Use the method Method -> Effect -> Explode Group of Geometries of JavaView for better insight in the internal structure.

    ##### Parameters

    Array<Set<Int>> | TR | facets of the triangulation

    ##### Options

    option list: | Visual::Polygons::decorations

    ##### Returns

    Visual::Polytope |

  - TRIANGULATION_BOUNDARY () → Visual::Polytope

    Draw the edges of the Polytope::TRIANGULATION_BOUNDARY. The facets are made transparent.

    ##### Options

    option list: | Visual::Graph::decorations

    ##### Returns

    Visual::Polytope |

- ###
  Visual::PolytopeGraph

  Category: Visualization

  Visualization of the graph of a polyhedron.

  #### User Methods of Visual::PolytopeGraph

  - ###
    Visualization

  - 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

    ##### Returns

    Visual::PolytopeGraph |

  - 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

  - STEINER ()

    UNDOCUMENTED

    ##### Options

    option list: | Visual::PointSet::decorations

  - ###
    Visualization

  - CONSTRUCTION () → Visual::SchlegelDiagram

    Visualize the construction of a 3D Schlegel diagram, that is, the Viewpoint, the 3-polytope and the projection onto one facet

    ##### Options

    option list: | Visual::Polygons::decorations

    ##### Returns

    Visual::SchlegelDiagram |

  - DIRECTED_GRAPH (lp) → Visual::SchlegelDiagram

    Illustrate the behavior of a linear objective function on the polytope. Superpose the drawing with the directed graph induced by the objective function.

    ##### Parameters

    LinearProgram | lp | a LinearProgram object attached to the polytope.

    ##### Returns

    Visual::SchlegelDiagram |

  - MIN_MAX_FACE (lp) → Visual::SchlegelDiagram

    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

    ##### Parameters

    LinearProgram | lp | a LinearProgram object attached to the polytope.

    ##### Options

    Color | min | minimal face decoration (default: yellow vertices and/or facets)
    Color | max | maximal face decoration (default: red vertices and/or facets)

    ##### Returns

    Visual::SchlegelDiagram |

  - SOLID () → Visual::SchlegelDiagram

    Draw the facets of the Schlegel diagram as polytopes.

    ##### Options

    option list: | Visual::Polygons::decorations

    ##### Returns

    Visual::SchlegelDiagram |

  - TRIANGULATION_BOUNDARY () → Visual::SchlegelDiagram

    Draw the edges of the TRIANGULATION_BOUNDARY

    ##### Options

    option list: | Visual::Graph::decorations

    ##### Returns

    Visual::SchlegelDiagram |

  - TRIANGULATION_BOUNDARY_SOLID () → Visual::SchlegelDiagram

    Draw the boundary simplices of the triangulation as solid tetrahedra

    ##### Options

    option list: | Visual::Polygons::decorations

    ##### Returns

    Visual::SchlegelDiagram |

  - VERTEX_COLORS (lp) → Visual::SchlegelDiagram

    Illustrate the behavior of a linear objective function on the polytope. Color the vertices according to the values of the objective function.

    ##### Parameters

    LinearProgram | lp | a LinearProgram object attached to the polytope.

    ##### Options

    Color | min | minimal vertex color (default: yellow)
    Color | max | maximal vertex color (default: red)

    ##### Returns

    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

  - CRUST_GRAPH: graph::Graph<Undirected>

    Graph of the crust as defined by Amenta, Bern, and Eppstein.

  - DELAUNAY_GRAPH: graph::Graph<Undirected>

    Graph of the Delaunay decomposition Del(SITES).

  - DELAUNAY_TRIANGULATION: common::Array<Set<Int>>

    Delaunay triangulation of the sites. (Delaunay subdivision, non-simplices are triangulated.)

  - ITERATED_DELAUNAY_GRAPH: graph::Graph<Undirected>

    Graph of the Del(SITES) + Vor(SITES).

  - ITERATED_VORONOI_GRAPH: GeometricGraph

    Graph of the joint Voronoi diagram of the SITES and the vertices of Vor(SITES). The coordinates (homogeneous, before projection) are stored as node attributes. The graph is truncated according to the VORONOI_GRAPH.BOUNDING_BOX. For the default BOUNDING_BOX it may happen that some of the iterated Voronoi vertices are truncated. Create new objects of type VoronoiDiagram to produce proper iterated Voronoi diagrams.

  - NN_CRUST_GRAPH: graph::Graph<Undirected>

    Graph of the nearest neighbor crust, as defined in:

    > T. K. Dey and P. Kumar: A simple provable algorithm for curve reconstruction.
    > Proc. 10th. Annu. ACM-SIAM Sympos. Discrete Alg., 1999, 893-894.

    Polygonal reconstruction of a smooth planar curve from a finite set of samples. Sampling rate of <= 1/3 suffices.

  - NN_GRAPH: graph::Graph<Undirected>

    Graph of the nearest neighbors. This is a subgraph of NN_CRUST_GRAPH.

  - N_SITES: common::Int

    Number of SITES

  - SITES: common::Matrix<Rational>

    Coordinates of the sites in case the polyhedron is Voronoi. Sites must be pairwise distinct.

  - SITE_LABELS: common::Array<String>

    Unique names assigned to the SITES. Works like VERTEX_LABELS.

  - VORONOI_GRAPH: GeometricGraph

    Graph of the Voronoi diagram of the SITES. The homogeneous coordinates after projection are stored as node attributes. The graph is truncated according to the BOUNDING_BOX. All vertices of the Voronoi diagram are visible (and represented in the VORONOI_GRAPH) for the default BOUNDING_BOX.

  - VORONOI_VERTICES: common::Matrix<Rational>

    Vertices of the Voronoi diagram of the SITES.

  #### User Methods of VoronoiDiagram

  - ###
    Visualization

  - VISUAL_CRUST () → Visual::Container

    Draw a Voronoi diagram, its |dual graph and the crust. Use the interactive features of the viewer to select.

    ##### Options

    option list: | Visual::Graph::decorations

    ##### Returns

    Visual::Container |

  - VISUAL_NN_CRUST () → Visual::Container

    Draw a Voronoi diagram, its dual graph and the nearest neighbor crust. Use the interactive features of the viewer to select.

    ##### Options

    option list: | Visual::Graph::decorations

    ##### Returns

    Visual::Container |

  - VISUAL_VORONOI () → Visual::Container

    Draw a Voronoi diagram and its dual. Use the interactive features of the viewer to select.

    ##### Options

    option list: | Visual::Graph::decorations

    ##### Returns

    Visual::Container |

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

  Polytope | P1 |
  Polytope | P2 |

- equal_polyhedra (P1, P2)

  Tests if the two polyhedra P1 and P2 are equal.

  ##### Parameters

  Polytope | P1 |
  Polytope | P2 |

- 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

  Polytope | P1 |
  Polytope | P2 |

  ##### Returns

  Pair<Array<Int>, Array<Int>> |

- included_polyhedra (P1, P2)

  Tests if polyhedron P1 is included in polyhedron P2.

  ##### Parameters

  Polytope | P1 |
  Polytope | P2 |

- 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

  Polytope | P1 |
  Polytope | P2 |

- lattice_isomorphic_smooth_polytopes (P1, P2)

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

  ##### Parameters

  LatticePolytope | P1 |
  LatticePolytope | P2 |

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

  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 |

- ###
  Coordinate conversions

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

  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 |

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

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

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

  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 |

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

  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)

- ###
  Other

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

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

  String | observation | encoded as a string of "0" and "1".

- ###
  Producing a new polyhedron from others

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

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

  Matrix | zones | the input vectors

  ##### Returns

  Matrix |

- ###
  Producing from other

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

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

  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 |

- ###
  Subdivisions

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

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

  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 |

- ###
  Transforming a lattice polyhedron

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

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

  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 |

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

  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 |

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

  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 |

## Common Option Lists

- ###
  Visualization

- schlegel_init

  Initial properties of the Schlegel diagram to be displayed.

  ##### Options

  Int | FACET | index of the projection facet, see SchlegelDiagram::FACET
  Rational | ZOOM | zoom factor, see SchlegelDiagram::ZOOM
  Vector | FACET_POINT | see SchlegelDiagram::FACET_POINT
  Vector | INNER_POINT | see SchlegelDiagram::INNER_POINT