# application: polytope

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

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

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

**imports from:**common, graph

**uses:**group, topaz

**Objects**

A polyhedral cone, not necessarily pointed. Note that in contrast to the vertices of a polytope, the RAYS are given in affine coordinates.

#### Properties of Cone

**CONE_DIM**: common::IntDimension of the linear span of the cone = dimension of the cone. If the cone is given purely combinatorially, this is the dimension of a minimal embedding space deduced from the combinatorial structure.

**COORDINATE_LABELS**: common::Array<String>Unique names assigned to the coordinate directions, analogous to RAY_LABELS.

**EQUATIONS**: common::Matrix<Scalar, NonSymmetric>Equations that hold for all INPUT_RAYS of the cone.

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

**FACETS**: common::Matrix<Scalar, NonSymmetric>Facets of the cone, encoded as inequalities. Dual to RAYS. This section is empty if and only if the cone is trivial (e.g. if it encodes an empty polytope). Notice that a polytope which is a single points defines a one-dimensional cone, the face a t infinity is a facet.

**FULL_DIM**: common::BoolCONE_AMBIENT_DIM and CONE_DIM coincide. Notice that this makes sense also for the derived Polytope class.

**INEQUALITIES**: common::Matrix<Scalar, NonSymmetric>Inequalities giving rise to the cone; redundancies are allowed. Dual to INPUT_RAYS.

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

**LINEALITY_SPACE**: common::Matrix<Scalar, NonSymmetric>Basis of the linear subspace orthogonal to all INEQUALITIES and EQUATIONS

**POSITIVE**: common::BoolTrue if all RAYS of the cone have non-negative coordinates, that is, if the pointed part of the cone lies entirely in the positive orthant. FIXME should we set POSITIVE = false for non-pointed cones?

**RAY_LABELS**: common::Array<String>Unique names assigned to the RAYS. If specified, they are shown by visualization tools instead of ray indices.

For a cone built from scratch, you should create this property by yourself, either manually in a text editor, or with a client program. If you build a cone with a construction client taking some other input cone(s), you can create the labels automatically if you call the client with a

*relabel*option. The exact format of the labels is dependent on the construction, and is described by the corresponding client.**RAY_SEPARATORS**: common::Matrix<Scalar, NonSymmetric>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.

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

**F2_VECTOR**: common::Matrix<Integer, NonSymmetric>The vector counting the number of incidences between pairs of faces. `f

_{ik}` is the number of incident pairs of `(i+1)`-faces and `(k+1)`-faces. The main diagonal contains the F_VECTOR.**FACETS_THRU_INPUT_RAYS**: common::IncidenceMatrix<NonSymmetric>transposed INPUT_RAYS_IN_FACETS Notice that this is a temporary property; it will not be stored in any file.

**FACETS_THRU_RAYS**: common::IncidenceMatrix<NonSymmetric>transposed RAYS_IN_FACETS Notice that this is a temporary property; it will not be stored in any file.

**FLAG_VECTOR**: common::Vector<Integer>Condensed form of the flag vector, containing all entries indexed by sparse sets in {0, ..., COMBINATORIAL_DIM-1} in the following order: (1, f

_{0}, f_{1}, f_{2}, f_{02}, f_{3}, f_{03}, f_{13}, f_{4}, f_{04}, f_{14}, f_{24}, f_{024}, f_{5}, ...). Use Dehn-Sommerville equations, via user function N_FLAGS, to extend.**F_VECTOR**: common::Vector<Integer>The vector counting the number of faces (`f

_{k}` is the number of `(k+1)`-faces).**GRAPH**: graph::Graph<Undirected>Vertex-edge graph obtained by intersecting the cone with a transversal hyperplane.

**INEQUALITIES_THRU_RAYS**: common::IncidenceMatrix<NonSymmetric>transposed RAYS_IN_INEQUALITIES Notice that this is a temporary property; it will not be stored in any file.

**INPUT_RAYS_IN_FACETS**: common::IncidenceMatrix<NonSymmetric>Input_ray-facet incidence matrix, with rows corresponding to facets and columns to input_rays. Input_rays and facets are numbered from 0 to N_INPUT_RAYS-1 rsp. N_FACETS-1, according to their order in INPUT_RAYS rsp. FACETS.

**RAYS_IN_INEQUALITIES**: common::IncidenceMatrix<NonSymmetric>Ray-inequality incidence matrix, with rows corresponding to facets and columns to rays. Rays and inequalities are numbered from 0 to N_RAYS-1 rsp. N_INEQUALITIES-1, according to their order in RAYS rsp. INEQUALITIES.

**INPUT_LINEALITY**: common::Matrix<Scalar, NonSymmetric>(Non-homogenous) vectors whose linear span defines a subset of the lineality space of the cone; redundancies are allowed. Dual to EQUATIONS.

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

**INPUT_RAYS**: common::Matrix<Scalar, NonSymmetric>(Non-homogenous) vectors whose positive span form the cone; redundancies are allowed. Dual to INEQUALITIES.

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

**TRIANGULATION**: topaz::SimplicialComplexSome triangulation of the cone using only its RAYS.

#### Properties of TRIANGULATION

**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>Weight vector to construct a regular TRIANGULATION. Must be generic.

**BOUNDARY**: topaz::SimplicialComplexSpecialization of topaz::SimplicialComplex::BOUNDARY for Cone::TRIANGULATION

#### Properties of BOUNDARY

**FACET_TRIANGULATIONS**: common::Array<Set<Int>>For each facet the set of simplex indices of BOUNDARY that triangulate it.

**FTR_CYCLIC_NORMAL**: common::Array<List<Int>>Reordered transposed RAYS_IN_FACETS. Dual to VIF_CYCLIC_NORMAL.

**NEIGHBOR_FACETS_CYCLIC_NORMAL**: common::Array<List<Int>>Reordered DUAL_GRAPH for 3d-cones. The neighbor facets are listed in the order corresponding to RIF_CYCLIC_NORMAL, so that the first two vertices in RIF_CYCLIC_NORMAL make up the ridge to the first neighbor facet and so on.

**NEIGHBOR_RAYS_CYCLIC_NORMAL**: common::Array<List<Int>>Reordered GRAPH. Dual to NEIGHBOR_FACETS_CYCLIC_NORMAL.

**RIF_CYCLIC_NORMAL**: common::Array<Array<Int>>Reordered RAYS_IN_FACETS for 2d and 3d-cones. Rays are listed in the order of their appearance when traversing the facet border counterclockwise seen from outside of the origin.

#### User Methods of Cone

**AMBIENT_DIM**()FIXME why do the following clients use different methods to determine their type?

**DIM**()UNDOCUMENTED

**DUAL_DIAMETER**()The diameter of the DUAL_GRAPH

**DUAL_TRIANGLE_FREE**()True if the DUAL_GRAPH contains no triangle

**TRIANGLE_FREE**()True if the GRAPH contains no triangle

**CONNECTIVITY**()**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

**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,...,COMBINATORIAL_DIM-1}. Example: "N_FLAGS(0,3,4)" determines the entry f_{034}of the flag vector.##### Parameters

Int type ... flag type**VERTEX_DEGREES**() → Vector<Int>

**DUAL_GRAPH_SIGNATURE**()Difference of the black and white nodes if the DUAL_GRAPH is BIPARTITE. Otherwise -1.

#### Permutations of Cone

**FacetPerm**UNDOCUMENTED

#### Properties of FacetPerm

**VertexPerm**UNDOCUMENTED

#### Properties of VertexPerm

**derived from:**Cone#### Properties of Cone<Rational>

**HILBERT_BASIS**: common::Matrix<Integer, NonSymmetric>The Hilbert basis spanned of the cone spanned by P x {1}

**HOMOGENEOUS**: common::Booltrue if the primitive generators of the rays lie on an affine hyperplane in the span of the rays

**Q_GORENSTEIN_CONE**: common::BoolA cone is Q-Gorenstein if all primitive generators of the cone lie in an affine hyperplane spanned by a lattice functional in the dual cone (but not in the lineality space of the dual cone).

**Q_GORENSTEIN_CONE_INDEX**: common::IntIf a cone is Q-Gorenstein, then its index is the common lattice height of the primitive generators with respect to the origin. Otherwise Q_GORENSTEIN_CONE_INDEX is undefined.

An undirected graph with given node coordinates and a bounding box

**derived from:**graph::Graph<Undirected>#### Properties of GeometricGraph

**BOUNDING_BOX**: common::Matrix<Scalar, NonSymmetric>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.

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

#### Properties of GroebnerBasis

**TERM_ORDER_MATRIX**: common::Matrix<Integer, NonSymmetric>The term order in matrix form; if not square, then a tie breaker is used.

**TERM_ORDER_NAME**: common::StringA term order by name; allowed acronyms are

`lex`

,`deglex`

and`degrevlex`

.

Polytope all of whose vertex coordinates are integral

**derived from:**Polytope<Rational>#### Properties of LatticePolytope

**EHRHART_POLYNOMIAL_COEFF**: common::Vector<Rational>The coefficients of the Ehrhart polynomial starting at the constant coefficient.

**FACET_VERTEX_LATTICE_DISTANCES**: common::Matrix<Integer, NonSymmetric>The entry (i,j) equals the lattice distance of vertex j from facet i.

**FACET_WIDTH**: common::IntegerThe 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::BoolThe polytope is

*Gorenstein*if a dilation of the polytope is reflexive up to translation.**GORENSTEIN_INDEX**: common::IntegerIf 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**: GroebnerBasisThe 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_BASIS**: common::Matrix<Rational, NonSymmetric>VERTICES are interpreted as coefficient vectors for this basis given in affine form assumed to the the standard basis if not explicitely specified

**LATTICE_CODEGREE**: common::IntPOLYTOPE_DIM+1-LATTICE_DEGREE or the smallest integer k such that k*P has an interior lattice point.

**LATTICE_EMPTY**: common::BoolTrue if the polytope contains no lattice points other than the vertices.

**NORMAL**: common::BoolThe polytope is

*normal*if the cone spanned by P x {1} is generated in height 1.**SMOOTH**: common::BoolThe polytope is

*smooth*if the associated projective variety is smooth; the determinant of the edge directions is +/-1 at every vertex.**TERMINAL**: common::BoolThe polytope is

*terminal*if there is exactly one interior lattice point and all other lattice points are vertices.**VERY_AMPLE**: common::BoolThe polytope is

*very ample*if the Hilbert Basis of the cone spanned by the edge-directions of any vertex lies inside the polytope.**GRAPH**: graph::Graph<Undirected>Specialization of Polytope::GRAPH for LatticePolytope

#### Properties of GRAPH

**LATTICE_EDGE_LENGTHS**: common::EdgeMap<Undirected, Integer>the lattice lengths of the edges of the polytope i.e. for each edge one less than the number of lattice points on that edge

#### User Methods of LatticePolytope

**POLYTOPE_IN_STD_BASIS**()UNDOCUMENTED

**FACET_POINT_LATTICE_DISTANCES**(v) → Vector<Integer>Vector containing the distances of a given point

*v*from all facets

**Category:**OptimizationA 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**: ScalarMaximum 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.

**RANDOM_EDGE_EPL**: common::Vector<Rational>Expected average path length for a simplex algorithm employing "random edge" pivoting strategy.

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

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

#### Properties of PointConfiguration

**SPLITS**: common::Matrix<Scalar, NonSymmetric>The splits of the point configuration, i.e., hyperplanes cutting the configuration in two parts such that we have a regular subdivision.

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

**CONVEX_HULL**: Polytope<Scalar>The polytope being the convex hull of the point configuration.

#### Properties of CONVEX_HULL

**LABELS**: common::Array<String>Unique names assigned to the POINTS. If specified, they are shown by visualization tools instead of point indices.

**GRAPH**: graph::Graph<Undirected>Graph of the point configuration. Two points are adjacent if they lie in a common edge of the CONVEX_HULL.

**POLYTOPAL_SUBDIVISION**: fan::PolyhedralComplex<Scalar>Polytopal Subdivision of the point configuration

#### Properties of POLYTOPAL_SUBDIVISION

**REFINED_SPLITS**: common::Set<Int>The splits that are coarsenings of the subdivision. If the subdivision is regular these form the unique split decomposition of the corresponding weight function.

**WEIGHTS**: common::Vector<Scalar>Vector assigning a weight to each point to get a regular subdivision.

**TRIANGULATION**: topaz::SimplicialComplexSome triangulation of the point configuration.

#### Properties of TRIANGULATION

**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>Weight vector to construct a regular TRIANGULATION. Must be generic.

**BOUNDARY**: topaz::SimplicialComplexSpecialization of topaz::SimplicialComplex::BOUNDARY for PointConfiguration::TRIANGULATION

#### Properties of BOUNDARY

**FACET_TRIANGULATIONS**: common::Array<Set<Int>>DOC_FIXME: Incomprehensible description! For each facet the set of simplex indices of BOUNDARY that triangulate it.

**PIF_CYCLIC_NORMAL**: common::Array<Array<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_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>

**VISUAL**() → Visual::PointConfigurationVisualize a point configuration.

**VISUAL_POINTS**() → Visual::PointSetVisualize the POINTS of a point configuration.

##### Options

option list: Visual::Polygons::decorations ##### Returns

Visual::PointSet

Not necessarily bounded or unbounded polyhedron. Nonetheless, the name "Polytope" is used for two reasons: Firstly, combinatorially we always deal with polytopes; see the description of VERTICES_IN_FACETS for details. The second reason is historical. We use homogeneous coordinates, which is why Polytope is derived from Cone. Note that a pointed polyhedron is projectively equivalent to a polytope.

*Scalar*is the numeric data type used for the coordinates.**derived from:**Cone#### Properties of Polytope

**SPLITS**: common::Matrix<Scalar, NonSymmetric>The splits of the polytope, i.e., hyperplanes cutting the polytope in two parts such that we have a regular subdivision.

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

**AFFINE_HULL**: common::Matrix<Scalar, NonSymmetric>Dual basis of the affine hull of the polyhedron. Alias for property LINEAR_SPAN.

**CENTERED**: common::BoolTrue if (1, 0, 0, ...) is in the relative interior. If full-dimensional then polar to BOUNDED.

**MINIMAL_VERTEX_ANGLE**: common::FloatThe minimal angle between any two vertices (seen from the VERTEX_BARYCENTER).

**POINTS**: common::Matrix<Scalar, NonSymmetric>Points such that the polyhedron is their convex hull. Redundancies are allowed. The vector (x

_{0}, x_{1}, ... x_{d}) represents a point in d-space given in homogeneous coordinates. Affine points are identified by x_{0}> 0. Points with x_{0}= 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 x

_{0}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. Alias for property INPUT_RAYS.

**STEINER_POINTS**: common::Matrix<Scalar, NonSymmetric>A weighted inner point depending on the outer angle called Steiner point for all faces of dimensions 2 to d.

**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, NonSymmetric>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. Alias for property RAY_SEPARATORS.

**ZONOTOPE_INPUT_VECTORS**: common::Matrix<Scalar, NonSymmetric>DOC_FIXME: Incomprehensible! Contains the vector configuration for which a zonotope can be built.

**ALTSHULER_DET**: common::IntegerLet M be the vertex-facet incidence matrix, then the Altshulter determinant is defined as max{det(M ∗ M

^{T}), det(M^{T}∗ M)}.**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_H_VECTOR**: common::Vector<Integer>dual 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.

**F2_VECTOR**: common::Matrix<Integer, NonSymmetric>f

_{ik}is the number of incident pairs of i-faces and k-faces; the main diagonal contains the F_VECTOR.**FACETS_THRU_POINTS**: common::IncidenceMatrix<NonSymmetric>similar to FACETS_THRU_VERTICES, but with POINTS instead of VERTICES Notice that this is a temporary property; it will not be stored in any file. Alias for property FACETS_THRU_INPUT_RAYS.

**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. Alias for property FACETS_THRU_RAYS.

**GRAPH**: graph::Graph<Undirected>Specialization of Cone::GRAPH for Polytope

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

_{i}= h_{i}- h_{i-1}.**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

**N_VERTEX_FACET_INC**: common::IntNumber of pairs of incident vertices and facets. Alias for property N_RAY_FACET_INC.

**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. Alias for property RAY_SIZES.

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

This property is at the core of all combinatorial properties. It has the following semantics: (1) The combinatorics of an unbounded and pointed polyhedron is defined to be the combinatorics of the projective closure. (2) The combiantorics of an unbounded polyhedron which is not pointed is defined to be the combinatorics of the quotient modulo the lineality space. Therefore: VERTICES_IN_FACETS and each other property which is grouped under "Combinatorics" always refers to some polytope. Alias for property RAYS_IN_FACETS.

**INEQUALITIES_THRU_VERTICES**: common::IncidenceMatrix<NonSymmetric>transposed VERTICES_IN_INEQUALITIES Alias for property INEQUALITIES_THRU_RAYS.

**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. Alias for property INPUT_RAYS_IN_FACETS.

**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. Alias for property RAYS_IN_INEQUALITIES.

**FAR_HYPERPLANE**: common::Vector<Scalar>Valid strict inequality for all affine points of the polyhedron.

**SPECIAL_FACETS**: common::Set<Int>The following is defined for

*CENTERED*polytopes only: A facet is special if the cone over that facet with the origin as the apex contains the*VERTEX_BARYCENTER*. Motivated by Obro's work on Fano polytopes.

**POLYTOPAL_SUBDIVISION**: fan::PolyhedralComplex<Scalar>Polytopal Subdivision of the polytope using only its vertices.

#### Properties of POLYTOPAL_SUBDIVISION

**REFINED_SPLITS**: common::Set<Int>The splits that are coarsenings of the subdivision. If the subdivision is regular these form the unique split decomposition of the corresponding weight function.

**WEIGHTS**: common::Vector<Scalar>Vector assigning a weight to each vertex to get a regular subdivision.

**BOUNDED_COMPLEX**: fan::PolyhedralComplex<Rational>Bounded subcomplex.

#### Properties of BOUNDED_COMPLEX

**GRAPH**: graph::Graph<Undirected>Specialization of fan::PolyhedralFan::GRAPH for Polytope::BOUNDED_COMPLEX

#### Properties of 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).

**EDGE_LENGTHS**: common::EdgeMap<Undirected, Scalar>The length of each edge measured in the maximum metric.

**TOWARDS_FAR_FACE**: common::Vector<Scalar>A linear objective function for which each unbounded edge is increasing; only defined for unbounded polyhedra.

**FTV_CYCLIC_NORMAL**: common::Array<List<Int>>Reordered transposed VERTICES_IN_FACETS. Dual to VIF_CYCLIC_NORMAL. Alias for property FTR_CYCLIC_NORMAL.

**GALE_VERTICES**: common::Matrix<Float, NonSymmetric>Coordinates of points for an affine Gale diagram.

**NEIGHBOR_VERTICES_CYCLIC_NORMAL**: common::Array<List<Int>>Reordered GRAPH. Dual to NEIGHBOR_FACETS_CYCLIC_NORMAL. Alias for property NEIGHBOR_RAYS_CYCLIC_NORMAL.

**SCHLEGEL_DIAGRAM**: SchlegelDiagram<Scalar>Holds one special projection (the Schlegel diagram) of the polytope.

**VIF_CYCLIC_NORMAL**: common::Array<Array<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. Alias for property RIF_CYCLIC_NORMAL.

#### User Methods of Polytope

**AMBIENT_DIM**()UNDOCUMENTED

**contains**()UNDOCUMENTED

**contains_in_interior**()FIXME the implementation of the following user_method is *not* efficient, if FIXME the polytope is given via vertices FIXME should be done in the same way as the one above

**DIM**()UNDOCUMENTED

**labeled_vertices**(label ...) → Set<Int>**N_RIDGES**()The number of ridges (faces of codimension 2) of the polytope equals the number of edges of the DUAL_GRAPH

**CD_INDEX**()Prettily print the cd-index given in CD_INDEX_COEFFICIENTS

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

**BOUNDED_DUAL_GRAPH**()Dual graph of the bounded subcomplex.

**BOUNDED_FACETS**() → Set<Int>**BOUNDED_GRAPH**()Graph of the bounded subcomplex.

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

**BOUNDED_VERTICES**() → Set<Int>

**GALE**() → Visual::GaleGenerate the Gale diagram of a

*d*-polyhedron with at most*d+4*vertices.##### Returns

Visual::Gale **SCHLEGEL**() → Visual::SchlegelDiagramCreate a Schlegel diagram and draw it.

##### Options

FIXME proj_facet decorations for the Edges of the projection faceoption list: schlegel_init option list: Visual::Wire::decorations ##### Returns

Visual::SchlegelDiagram **VISUAL**() → Visual::PolytopeVisualize a polytope as a graph (if 1d), or as a solid object (if 2d or 3d), or as a Schlegel diagram (4d).

**VISUAL_BOUNDED_GRAPH**() → Visual::PolytopeGraphVisualize the BOUNDED_COMPLEX.GRAPH of a polyhedron.

##### Options

Int seed random seed value for the string embedderoption list: Visual::Graph::decorations ##### Returns

Visual::PolytopeGraph **VISUAL_DUAL**() → Visual::Polygons**VISUAL_DUAL_FACE_LATTICE**() → Visual::PolytopeLatticeVisualize the dual face lattice of a polyhedron as a multi-layer graph.

##### Options

Int seed random seed value for the node placementoption list: Visual::Lattice::decorations ##### Returns

Visual::PolytopeLattice **VISUAL_DUAL_GRAPH**() → Visual::GraphVisualize the DUAL_GRAPH of a polyhedron.

##### Options

Int seed random seed value for the string embedderoption list: Visual::Graph::decorations ##### Returns

Visual::Graph **VISUAL_FACE_LATTICE**() → Visual::PolytopeLatticeVisualize the HASSE_DIAGRAM of a polyhedron as a multi-layer graph.

##### Options

Int seed random seed value for the node placementoption list: Visual::Lattice::decorations ##### Returns

Visual::PolytopeLattice **VISUAL_GRAPH**() → Visual::PolytopeGraphVisualize the GRAPH of a polyhedron.

##### Options

Int seed random seed value for the string embedderoption list: Visual::Graph::decorations ##### Returns

Visual::PolytopeGraph **VISUAL_TRIANGULATION_BOUNDARY**() → Visual::PolygonsVisualize 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

A pointed polyhedron realized in R

^{d}.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**derived from:**Polytope#### Properties of Polytope<Rational>

**MINKOWSKI_SUMMAND_CONE**: Cone<Rational>The cone of all Minkowski summands of the polytope P. Up to scaling, a polytope S is a Minkowski summand of P if and only if the edge directions of S are a subset of those of P, and the closing condition around any 2-face of P is preserved. Coordinates of the cone correspond to the rescaled lengths of the edges of the graph of P (in the order given by the property EDGES of the GRAPH of P). The Minkowski cone is defined as the intersection of all equations given by the closing condition around 2-faces with the positive orthant. For more information see e.g. Klaus Altmann: The versal deformation of an isolated toric Gorenstein singularity

**BOUNDARY_LATTICE_POINTS**: common::Matrix<Integer, NonSymmetric>The lattice points on the boundary of the polytope, including the vertices

**INTERIOR_LATTICE_POINTS**: common::Matrix<Integer, NonSymmetric>The lattice points strictly in the interior of the polytope

**LATTICE**: common::BoolThis is the defining property: A polytope is lattice if each vertex has integer coordinates.

#### User Methods of Polytope<Rational>

**MINKOWSKI_SUMMAND_COEFF**(coeff) → Polytope<Rational>returns the Minkowski summand of a polytope P given by a coefficient vector to the rays of the MINKOWSKI_SUMMAND_CONE.

##### Parameters

Vector<Rational> coeff coefficient vector to the rays of the Minkowski summand cone##### Returns

Polytope<Rational> **MINKOWSKI_SUMMAND_POINT**(point) → Polytope<Rational>returns the Minkowski summand of a polytope P given by a point in the MINKOWSKI_SUMMAND_CONE.

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

A Schlegel diagram of a polytope

#### Properties of SchlegelDiagram

**FACET_POINT**: common::Vector<Scalar>The intersection point of the projection facet and the view ray.

**ROTATION**: common::Matrix<Float, NonSymmetric>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, NonSymmetric>Matrix of a projective transformation mapping the whole polytope into the FACET The points belonging to this facet stay fixed.

**VERTICES**: common::Matrix<Float, NonSymmetric>Coordinates in affine 3-space of the vertices which correspond to a 3-dimensional (Schlegel-) projection of a 4-polytope.

#### User Methods of SchlegelDiagram

**VISUAL**() → Visual::SchlegelDiagramDraw the Schlegel diagram

##### Options

pm::perl::Hash proj_facet decoration for the edges of the projection faceoption list: Visual::Graph::decorations ##### Returns

Visual::SchlegelDiagram

UNDOCUMENTED

**derived from:**Cone#### Properties of SymmetricCone

**GEN_EQUATIONS**: common::Matrix<Scalar, NonSymmetric>category: Symmetric Cones Some generating equations for (a subset of) the linear span of the symmetric cone. Redundancies are allowed.

Input section only.

**GEN_INEQUALITIES**: common::Matrix<Scalar, NonSymmetric>category: Symmetric Cones Some generating inequalities for the symmetric cone; redundancies are allowed.

Input section only. Ask for REPRESENTATIVE_FACETS if you want a list of representatives for the orbits of facets of a symmetric cone.

**GEN_INPUT_LINEALITY**: common::Matrix<Scalar, NonSymmetric>category: Symmetric Cones Some generating input rays for (a subset of) the lineality space of the symmetric cone. Redundancies are allowed.

Input section only.

**GEN_INPUT_RAYS**: common::Matrix<Scalar, NonSymmetric>category: Symmetric Cones Some generating input rays for the symmetric cone; redundancies are allowed.

Input section only. Ask for REPRESENTATIVE_RAYS if you want a list of representatives for the orbits of rays of a symmetric cone.

**GENERATING_GROUP**: group::GroupOfConeThe group which generates the cone by being applied to some GEN_INPUT_RAYS (and GEN_INPUT_LINEALITY) or some GEN_INEQUALITIES (and GEN_EQUATIONS).

#### User Methods of SymmetricCone

**VISUAL_ORBIT_COLORED_GRAPH**() → Visual::ConeGraphcategory: Visualization FIXME: Should be a method of a SymmetricGraph object (to be defined!)! Visualizes the graph of a symmetric cone: All nodes belonging to one orbit get the same color.

##### Options

option list: Visual::Graph::decorations ##### Returns

Visual::ConeGraph

UNDOCUMENTED

**derived from:**SymmetricCone#### Properties of SymmetricPolytope

#### User Methods of SymmetricPolytope

**AMBIENT_DIM**()must be copied (from common.rules) since SymmetricPolytope is derived from both objects, SymmetricCone and Polytope

**DIM**()must be copied (from common.rules) since SymmetricPolytope is derived from both objects, SymmetricCone and Polytope

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

**METRIC**: common::Matrix<Scalar, NonSymmetric>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.

#### User Methods of TightSpan

**VISUAL_BOUNDED_GRAPH**() → Visual::PolytopeGraphVisualize the BOUNDED_COMPLEX.GRAPH of a tight span.

##### Options

Int seed random seed value for the string embedderoption list: Visual::Graph::decorations ##### Returns

Visual::PolytopeGraph **VISUAL_SPLITS**() → Visual::FiniteMetricSpaceVisualize the splits of a finite metric space (that is, a planar image of a tight span). Calls SplitsTree.

##### Returns

Visual::FiniteMetricSpace **VISUAL_TIGHT_SPAN**() → Visual::GraphThis is a variation of Polytope::VISUAL_BOUNDED_GRAPH for the special case of a tight span. The vertices are embedded according to the METRIC, the others are hanged in between.

**Category:**VisualizationVisualization of the point configuration.

#### User Methods of Visual::PointConfiguration

**POLYTOPAL_SUBDIVISION**() → Visual::PointConfigurationVisualize the POLYTOPAL_SUBDIVISION of a point configuration

**TRIANGULATION**() → Visual::PointConfigurationVisualize the TRIANGULATION of a point configuration

**TRIANGULATION_BOUNDARY**() → Visual::PointConfigurationDraw the edges of the TRIANGULATION_BOUNDARY. The facets are made transparent.

**Category:**VisualizationVisualization 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::PolytopeIllustrate the behavior of a linear objective function on the polytope. Superpose the drawing with the directed graph induced by the objective function.

**MIN_MAX_FACE**(lp) → Visual::PolytopeIllustrate 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::PolytopeIllustrate 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 **LATTICE**() → Visual::PolytopeVisualize the LATTICE_POINTS of a polytope

**LATTICE_COLORED**() → Visual::PolytopeVisualize the LATTICE_POINTS of a polytope in different colors (interior / boundary / vertices)

**STEINER**() → Visual::PolytopeAdd the STEINER_POINTS to the 3-d visualization. The facets become transparent.

**TRIANGULATION**(TR) → Visual::PolytopeAdd 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::PolytopeDraw the edges of the Polytope::TRIANGULATION_BOUNDARY. The facets are made transparent.

**Category:**VisualizationVisualization of the graph of a polyhedron.

#### User Methods of Visual::PolytopeGraph

**DIRECTED_GRAPH**(lp) → Visual::PolytopeGraphShow 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::PolytopeGraphproduce an edge coloring of a bounded graph from local data in the Hasse diagram

##### Returns

Visual::PolytopeGraph **MIN_MAX_FACE**(lp) → Visual::PolytopeGraphIllustrate 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::PolytopeGraphIllustrate 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

**Category:**VisualizationVisualization of the HASSE_DIAGRAM of a polyhedron as a multi-layer graph..

#### User Methods of Visual::PolytopeLattice

**MIN_MAX_FACE**(lp) → Visual::PolytopeLatticeIllustrate 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

**Category:**VisualizationVisualization of the Schlegel diagram of a polytope.

#### User Methods of Visual::SchlegelDiagram

**STEINER**()UNDOCUMENTED

##### Options

option list: Visual::PointSet::decorations **CONSTRUCTION**() → Visual::SchlegelDiagramVisualize the construction of a 3D Schlegel diagram, that is, the Viewpoint, the 3-polytope and the projection onto one facet

**DIRECTED_GRAPH**(lp) → Visual::SchlegelDiagramIllustrate 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::SchlegelDiagramIllustrate 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::SchlegelDiagramDraw the facets of the Schlegel diagram as polytopes.

**TRIANGULATION_BOUNDARY**() → Visual::SchlegelDiagramDraw the edges of the TRIANGULATION_BOUNDARY

**TRIANGULATION_BOUNDARY_SOLID**() → Visual::SchlegelDiagramDraw the boundary simplices of the triangulation as solid tetrahedra

**VERTEX_COLORS**(lp) → Visual::SchlegelDiagramIllustrate 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

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<Scalar>.**derived from:**Polytope#### Properties of VoronoiDiagram

**DELAUNAY_TRIANGULATION**: common::Array<Set<Int>>Delaunay triangulation of the sites. (Delaunay subdivision, non-simplices are triangulated.)

**ITERATED_VORONOI_GRAPH**: GeometricGraph<Rational>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.

**SITES**: common::Matrix<Scalar, NonSymmetric>Coordinates of the sites in case the polyhedron is Voronoi. Sites must be pairwise distinct.

**VORONOI_GRAPH**: GeometricGraph<Rational>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<Scalar, NonSymmetric>Vertices of the Voronoi diagram of the SITES.

#### User Methods of VoronoiDiagram

**VISUAL_CRUST**() → Visual::ContainerDraw 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::ContainerDraw 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::ContainerDraw 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

**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**equal_polyhedra**(P1, 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.

**included_polyhedra**(P1, P2)**isomorphic**(P1, 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

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

**check_poly**(VIF) → PolytopeTry 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 matrixBool verbose prints information about the check.##### Returns

Polytope

**normal_cone**(p, v)

**affine_float_coords**(P) → Matrix<Float>dehomogenize the vertex coordinates and convert them to Float

**convert_to**<Coord> (c) → Cone<Coord>Creates a new Cone object with different coordinate type target coordinate type

*Coord*must be specified in angle brackets e.g. $new_cone = convert_to<Coord>($cone)##### Type Parameters

Coord target coordinate type##### Parameters

Cone c the input cone##### Returns

Cone<Coord> a new cone object or*C*itself it has the requested type**convert_to**<Coord> (P) → Polytope<Coord>provide a Polytope object with desired coordinate type

##### Type Parameters

Coord target coordinate type##### Parameters

Polytope P source object##### Returns

Polytope<Coord> *P*if it already has the requested type, a new object otherwise

**delaunay_triangulation**(V) → Array<Set<Int>>Compute the (a) Delaunay triangulation of the given SITES of a VoronoiDiagram

*V*. If the sites are not in general position, the non-triangular facets of the Delaunay subdivision are triangulated (by applying the beneath-beyond algorithm).**voronoi**(V) → MatrixCompute the inequalities of the Voronoi polyhedron of a given VoronoiDiagram

*V*. The polyhedron is always unbounded. Introduce artificial cut facets later (e.g., for visualization); this must be done after the vertices have been computed.

**print_constraints**(P) → boolWrite the FACETS / INEQUALITIES and the AFFINE_HULL / EQUATIONS of a polytope

*P*in a readable way. COORDINATE_LABELS are adopted if present.

**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 directionBool generic breaks ties##### Returns

Graph<Directed> **inner_point**(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.**rand_aof**(P, start) → Vector<Rational>Produce a random abstract objective function on a given

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

Polytope P a*simple*polytopeInt 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

Vector<Rational> **rel_int_point**(P, unbounded, affine_hull)Computes a relative interior point of a polyhedron

*P*and stores it in*P*->REL_INT_POINT. The*unbounded*flag needs to be set to true if the polyhedron could be unbounded.**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 valueRGB max the maximal RGB value##### Returns

Array<RGB>

**all_steiner_points**(P) → MatrixCompute the Steiner points of all faces of a polyhedron

*P*using a randomized approximation of the angles.*P*must be BOUNDED.**integer_points_bbox**(P) → Matrix<Integer>Enumerate all integer points in the given polytope by searching a bounding box.

**steiner_point**(P) → Vector

**core_point_algo**(p, optLPvalue) → perl::ListReturnAlgorithm 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).

**find_transitive_lp_sol**(Inequalities) → perl::ListReturnAlgorithm to solve symmetric linear programs (LP) of the form max c

^{t}x , 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)

**truncated_orbit_polytope**(v, group, eps) → SymmetricPolytopeConstructs an orbit polytope of a given point

*v*with respect to a given group*group*, in which all vertices are cut off by hyperplanes in distance*eps*##### Parameters

Vector v point of which orbit polytope is to be constructedgroup::GroupOfPolytope group group for which orbit polytope is to be constructedRational eps scaled distance by which the vertices of the orbit polytope are to be cut off##### Returns

SymmetricPolytope the truncated orbit polytope

**induced_lattice_basis**(p) → Matrix<Integer>Returns a basis of the affine lattice spanned by the vertices

**is_vertex**(q, points) → BoolChecks whether a given point

*q*is a vertex of the polytope P generated by*q*and a set of other points*points*via solving a suitable LP (compare cdd redundancy check). Works without knowing the facets of P!**minimal_vertex_angle**(P) → Float**separating_hyperplane**(q, points) → ListReturnComputes (the normal vector of) a hyperplane which separates a given point

*q*from*points*via solving a suitable LP. The scalar product of the normal vector of the separating hyperplane and a point in*points*is greater or equal than 0 (same behavior as for facets!). If*q*is not a vertex of P=conv(*points*,*q*), the function returns a zero vector and sets*answer*to 'false'. Works without knowing the facets of P!

**binary_markov_graph**(observation) → PropagatedPolytopeDefines 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 biologyby L. Pachter and B. Sturmfels (eds.), Cambridge, 2005.**binary_markov_graph**(observation)##### Parameters

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

**bipyramid**(P, z, z_prime)Make a bipyramid over a pointed polyhedron. The bipyramid is the convex hull of the input polyhedron

*P*and two points (*v*,*z*), (*v*,*z_prime*) on both sides of the affine span of*P*. For bounded polyhedra, the apex projections*v*to the affine span of*P*coincide with the vertex barycenter of*P*.##### Parameters

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

**cayley_embedding**(P, P_prime, z, z_prime) → PolytopeCreate a Cayley embedding of two polytopes (one of them must be pointed). The vertices of the first polytope

*P*get an extra coordinate*z*and the vertices of the second polytope*P_prime*get*z_prime*.Default values are

*z*=1 and*z_prime*=-*z*.The option

*relabel*creates an additional section VERTEX_LABELS. The vertices of*P*inherit the original labels unchanged; the vertex labels of*P_prime*get a tick (') appended.**cayley_polytope**(P_Array) → PolytopeConstruct the cayley polytope of a set of pointed lattice polytopes contained in

*P_Array*which is the convex hull of P_{1}×e_{1}, ..., P_{k}×e_{k}where e_{1}, ...,e_{k}are the standard unit vectors in R^{k}. 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 P_{1},...,P_{k}##### Options

Bool proj ##### Returns

Polytope **cells_from_subdivision**(P, cells) → Polytope**cell_from_subdivision**(P, cell) → Polytope**conv**(P_Array) → PropagatedPolytopeConstruct a new polyhedron as the convex hull of the polyhedra given in

*P_Array*.**edge_middle**(P) → Polytope**facet_to_infinity**(i) → Polytope**intersection**(C ...) → ConeConstruct a new polyhedron or cone as the intersection of given polyhedra and/or cones. Works only if all CONE_AMBIENT_DIM values are equal. If the input contains both cones and polytopes, the output will be a polytope.

**join_polytopes**(P1, P2) → Polytope**lattice_bipyramid**(P, v, v_prime, z, z_prime) → PolytopeMake 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 apexVector 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 1Rational z_prime height 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) → PolytopeMake 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*.**mapping_polytope**(P1, P2) → PolytopeConstruct a new polytope as the

*mapping polytope*of two polytopes*P1*and*P2*. The mapping polytope is the set of all affine maps from R^{p}to R^{q}, that map*P1*into*P2*.The label of a new facet corresponding to v

_{1}and h_{1}will have the form "v_{1}*h_{1}".**minkowski_sum**(lambda, P1, mu, P2) → Polytope**minkowski_sum**(P1, P2) → Polytope**minkowski_sum_fukuda**()UNDOCUMENTED**pointed_part**(P) → Polytope**prism**(P, z1, z2) → PolytopeMake a prism over a pointed polyhedron. The prism is the product of the input polytope

*P*and the interval [*z1*,*z2*].##### Parameters

Polytope P the input polytopeRational z1 the left endpoint of the interval; default value: -1Rational z2 the right endpoint of the interval; default value: -*z1*##### Options

Bool noc only combinatorial information is handledBool 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) → PolytopeConstruct a new polytope as the product of two given polytopes

*P1*and*P2*.**projection**(P, indices) → PolytopeOrthogonally project a pointed polyhedron to a coordinate subspace.

The subspace the polyhedron

*P*is projected on is given by the coordinate indices in the set*indices*. The option*revert*inverts the coordinate list. The client scans for all coordinate sections and produces proper output from each. If a description in terms of inequalities is found, the client performs Fourier-Motzkin elimination unless the*nofm*option is set. Setting the*nofm*option is useful if the corank of the projection is large; in this case the number of inequalities produced grows quickly.##### Parameters

Polytope P Array<Int> indices ##### Options

Bool revert inverts the coordinate listBool nofm suppresses Fourier-Motzkin elimination##### Returns

Polytope **projection_full**(P) → PolytopeOrthogonally 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.**pyramid**(P, z) → PolytopeMake 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*.**rand_inner_points**(P, n) → PolytopeProduce 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.**rand_vert**(V, n) → MatrixSelects

*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.**stack**(P, stack_facets) → PolytopeStack 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/2Bool 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) → PolytopePerform 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.**stellar_indep_faces**(P, in_faces) → PolytopePerform 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.

**truncation**(P, trunc_vertices) → PolytopeCut 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/2Bool 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**(Polytope, n) → PolytopeProduce a polytope with

*n*random points that are uniformly distributed within the given polytope*P*.*P*must be bounded and full-dimensional.**vertex_figure**(p, n) → PolytopeConstruct 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) → PolytopeMake 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 , must be boundedInt 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

**cut_polytope**(G) → Polytope**matching_polytope**(G) → Polytope**tutte_lifting**(G) → Polytope

**associahedron**(d) → Polytope**create_24_cell**() → Polytope**create_600_cell**() → Polytope**cube**(d, x_up, x_low) → Polytope**cyclic**(d, n, start) → PolytopeProduce 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.**cyclic_caratheodory**(d, n) → Polytope**dwarfed_cube**(d) → Polytope**dwarfed_product_polygons**(d, s) → Polytope**goldfarb**(d, e, g) → PolytopeProduces 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.**hypersimplex**(k, d) → Polytope**hypertruncated_cube**(d, k, lambda) → Polytope**knapsack**(b) → PolytopeProduce a knapsack polytope defined by one linear inequality (and non-negativity constraints).

**k_cyclic**(n, s) → PolytopeProduce 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**max_GC_rank**(d) → Polytope**metric_cone**(n) → Cone**multiplex**(d, n) → PolytopeProduce 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.**neighborly_cubical**(d, n) → PolytopeProduce 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).**newton**(p) → LatticePolytope**permutahedron**(d) → Polytope**pile**(sizes) → PolytopeProduce 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 (s_{1},...,s_{d}, where s_{i}specifies the number of boxes in the i-th dimension.##### Returns

Polytope **rand_box**(d, n, b) → PolytopeComputes the convex hull of

*n*points sampled uniformly at random from the integer points in the cube [0,*b*]^{d}.**rand_metric**<Scalar> (n) → Matrix**rand_metric_int**<Scalar> (n) → Matrix**rand_sphere**(d, n) → Polytope**rss_associahedron**(l) → PolytopeProduce a polytope of constrained expansions in dimension

*l*according toRote, Santos, and Streinu: Expansive motions and the polytope of pointed pseudo-triangulations.Discrete and computational geometry, 699--736, Algorithms Combin., 25, Springer, Berlin, 2003.**signed_permutahedron**(d) → Polytope**transportation**(r, c) → Polytope

**barycentric_subdivision**(pc) → PointConfigurationCreate 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 subdivisionArray<Set> sub2 second subdivisionInt dim dimension of the point configuration##### Returns

Array<Set<Int>> the common refinement**common_refinement**(p1, p2) → Polytope**is_regular**(points, subdiv) → Pair<bool,Cone>For a given subdivision

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

Matrix points Array<Set<Int> > subdiv ##### Options

Matrix<Rational> equations system of linear equation the cone is cut with.Set<Int> lift_to_zero gives only lifting functions lifting the designated vertices to 0Int lift_face_to_zero gives only lifting functions lifting all vertices of the designated face to 0##### Returns

Pair<bool,Cone> **is_subdivision**(points, faces)Checks whether

*faces*forms a valid subdivision of*points*, where*points*is a set of points, and*faces*is a collection of subsets of (indices of)*points*. If the set of interior points of*points*is known, this set can be passed by assigning it to the option*interior_points*. If*points*are in convex position (i.e., if they are vertices of a polytope), the option*interior_points*should be set to [ ] (the empty set).**placing_triangulation**(Points, permutation) → Array<Set<Int>>Compute the placing triangulation of the given point set using the beneath-beyond algorithm.

**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.**secondary_cone**(points, subdiv) → ConeFor a given subdivision

*subdiv*of*points*tests computes the corresponding secondary cone. If the subdivision is not regular, the result will be the trivial cone. Options can be used to make the Cone POINTED.##### Parameters

Matrix points Array<Set<Int> > subdiv ##### Options

Matrix<Rational> equations system of linear equation the cone is cut with.Set<Int> lift_to_zero gives only lifting functions lifting the designated vertices to 0Int lift_face_to_zero gives only lifting functions lifting all vertices of the designated face to 0##### Returns

Cone **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 polyhedronArray<Set<Int>> subdivision a subdivision of the polyhedronMatrix splits the splits of the polyhedron##### Returns

Set<Int> **split_compatibility_graph**(splits, P) → Graph**split_polyhedron**(P) → 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 simplexInt l the dimension of the second simplex##### Returns

Vector<Rational> **stellar_subdivision**(pc, faces) → PointConfigurationComputes the complex obtained by stellar subdivision of all

*faces*of the TRIANGULATION of the PointConfiguration.##### Parameters

PointConfiguration pc input point configurationArray<Set<Int>> faces list of faces to subdivide##### Options

Bool no_labels : do not write any labels##### Returns

PointConfiguration **tight_span**(points, weight, full) → PolytopeCompute the tight span dual to the regular subdivision obtained by lifting

*points*to*weight*and taking the lower complex of the resulting polytope.**tight_span**(P) → PolytopeCompute 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.**topcom_all_triangulations**(pc) → Array<Array<Set<Int>>>Compute all triangulations of a point configuration via its chirotope.

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

##### Parameters

LatticePolytope P

**max_metric**(n) → Matrix**metric2hyp_triang**(FMS) → Polytope**metric2splits**(D) → Array<Pair<Set>>Computes all non-trivial splits of a metric space

*D*(encoded as a symmetric distance matrix).**min_metric**(n) → Matrix**points2metric**(points) → MatrixDefine a metric by restricting the Euclidean distance function to a given set of

*points*. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option*max*or*l1*is set to true the max-norm or l1-nomr is used instead (with exact computation).**poly2metric**(P) → MatrixDefine 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).**thrackle_metric**(n) → MatrixCompute 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)**ts_max_metric**(n) → TightSpan**ts_min_metric**(n) → TightSpan**ts_thrackle_metric**(n) → TightSpanCompute 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)

**ambient_lattice_normalization**(p) → PolytopeTransform to a full-dimensional polytope while preserving the ambient lattice Z^n

**vertex_lattice_normalization**(p) → PolytopeTransform to a full-dimensional polytope while preserving the lattice spanned by vertices induced lattice of new vertices = Z^dim

**bound**(P) → PolytopeMake 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.

**orthantify**(P, v) → PolytopeMake 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.**polarize**(C) → ConeGiven a bounded, centered, and full-dimensional polytope

*P*, produce its polar, that is, polar with respect to the standard Euclidean scalar product. Note that the definition of the polar has changed after version 2.10: the polar is reflected in the origin to conform with cone dualization**revert**(P) → PolytopeApply 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.

**transform**(P, trans, store) → Polytope**translate**(P, trans, store) → Polytope

**positive_circuits**(or, S) → Set<Set<Int>>returns all sets of points that form a circuit with the given list of points

##### Parameters

Polytope or PointConfiguration PSet<Int> S subset of point indices##### Returns

Set<Set<Int>> A list of point sets that intersect positively the set S

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

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

**print_face_lattice**(VIF, dual)Write the face lattice of a vertex-facet incidence matrix

*VIF*to stdout. If*dual*is set true the face lattice of the dual is printed.##### Parameters

IncidenceMatrix VIF Bool dual

**bounding_box**(V, surplus_k, voronoi) → MatrixIntroduce 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.**clip_graph**(p, V, G)**splitstree**(vis_obj ...)Call wiki:external_software#SplitsTree with the given visual objects.

##### Parameters

Visual::Object vis_obj ... objects to display##### Options

String File "filename" or "AUTO" Only create a NEXUS format file, don't start the GUI.The`.nex`

suffix is automatically added to the file name.Specify*AUTO*if you want the filename be automatically derived from the drawing title.You can also use any expression allowed for the`open`

function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe.

**linear_symmetries**(c, dual) → voidComputes the linear symmetries of a given polytope

*p*via 'sympol'. The symmetry group is stored in the property GROUP.##### Parameters

Cone c the cone whose linear symmetry group is to be computedbool dual true if group action on vertices, false if action on facets##### Returns

void **representation_conversion_up_to_symmetry**(c, a, dual) → perl::ListReturnComputes the dual description of a polytope up to its linear symmetry group.

##### Parameters

Cone c the cone whose dual description is to be computedGroup a symmetry group of the cone*c*(GroupOfCone or GroupOfPolytope)bool dual true if V to H, false if H to V##### Returns

perl::ListReturn list which contains success as bool, vertices/inequalities and lineality/equations as Matrix<Rational>

## Common Option Lists

**schlegel_init**Initial properties of the Schlegel diagram to be displayed.

##### Options

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