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.
uses: group, ideal, topaz
Objects
- Category: Geometry
a lattice that is displaced from the origin, i.e., a set of the form x + L, where x is a non-zero vector and L a (linear) lattice
Properties of AffineLattice
A polyhedral cone, not necessarily pointed. Note that in contrast to the vertices of a polytope, the RAYS are given in affine coordinates.
Type Parameters
Scalar numeric data type used for the coordinates, must be an ordered fieldSpecializations of Cone
- Cone<Rational>
An affine rational cone realized in Rd.
- Cone<Float>
An affine cone with float coordinates realized in Rd.
- Cone::ExactCoord
An affine cone with an exact coordinate type, like Rational.
Properties of Cone
Properties from algebraic geometry.
- TORIC_IDEAL: fulton::BinomialIdealOnly defined for Cone<Rational>
The matrix containing the exponent vectors of the binomials whose vanishing set is the affine toric variety given by the cone. In other words the rows of this matrix give the relations between the Hilbert basis elements.
Depends on: 4ti2
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- ALTSHULER_DET: common::Integer
Let M be the vertex-facet incidence matrix, then the Altshuler determinant is defined as max{det(M ∗ MT), det(MT ∗ M)}.
Example:- This prints the Altshuler determinant of the built-in pentagonal pyramid (Johnson solid 2):
> print johnson_solid("pentagonal_pyramid")->ALTSHULER_DET;
25
- COCIRCUIT_EQUATIONS: common::SparseMatrix<Rational, NonSymmetric>
A matrix whose rows contain the cocircuit equations of P. The columns correspond to the MAX_INTERIOR_SIMPLICES.
- COMBINATORIAL_DIM: common::Int
Combinatorial dimension This is the dimension all combinatorial properties of the cone like e.g. RAYS_IN_FACETS or the HASSE_DIAGRAM refer to.
Geometrically, the combinatorial dimension is the dimension of the intersection of the pointed part of the cone with a hyperplane that creates a bounded intersection.
- 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: RAYS in general position => ESSENTIALLY_GENERIC => SIMPLICIAL
- EXCESS_FACET_DEGREE: common::Int
Measures the deviation of the cone from being simple in terms of the DUAL_GRAPH.
- EXCESS_RAY_DEGREE: common::Int
Measures the deviation of the cone from being simple in terms of the GRAPH.
- F2_VECTOR: common::Matrix<Integer, NonSymmetric>
The vector counting the number of incidences between pairs of faces. `fik` is the number of incident pairs of `(i+1)`-faces and `(k+1)`-faces. The main diagonal contains the F_VECTOR.
- FACETS_THRU_RAYS: common::IncidenceMatrix<NonSymmetric>
Transposed to 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, f0, f1, f2, f02, f3, f03, f13, f4, f04, f14, f24, f024, f5, ...). Use Dehn-Sommerville equations, via user function N_FLAGS, to extend.
- FOLDABLE_COCIRCUIT_EQUATIONS: common::SparseMatrix<Rational, NonSymmetric>
A matrix whose rows contain the foldable cocircuit equations of P. The columns correspond to 2 * MAX_INTERIOR_SIMPLICES. col 0 = 0, col 1 = first simplex (black copy), col 2 = first simplex (white copy), col 3 = second simplex (black copy), ...
- F_VECTOR: common::Vector<Integer>
The vector counting the number of faces (`fk` is the number of `(k+1)`-faces).
- GRAPH: graph::Graph<Undirected>
Vertex-edge graph obtained by intersecting the cone with a transversal hyperplane.
- HASSE_DIAGRAM: Lattice<BasicDecoration, Sequential> as Cone::HASSE_DIAGRAM
The face lattice of the cone organized as a directed graph. Top and bottom nodes represent the whole cone and the empty face. Every other node corresponds to some proper face of the cone.
- MAX_BOUNDARY_SIMPLICES: common::Array<Set<Int>>
The boundary (d-1)-dimensional simplices of a cone of combinatorial dimension d
- MAX_INTERIOR_SIMPLICES: common::Array<Set<Int>>
The interior d-dimensional simplices of a cone of combinatorial dimension d
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- CONE_DIM: common::Int
Dimension 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.
- EPSILON: common::FloatOnly defined for Cone<Float>
Threshold for zero test for scalar products (e.g. vertex * facet normal)
- FACETS: common::Matrix
Facets of the cone, encoded as inequalities. All vectors in this section must be non-zero. 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 point defines a one-dimensional cone, the face at infinity is a facet. The property FACETS appears only in conjunction with the property LINEAR_SPAN, or AFFINE_HULL, respectively. The specification of the property FACETS requires the specification of LINEAR_SPAN, or AFFINE_HULL, respectively, and vice versa.
- FACETS_THRU_INPUT_RAYS: common::IncidenceMatrix<NonSymmetric>
Transposed to INPUT_RAYS_IN_FACETS. Notice that this is a temporary property; it will not be stored in any file.
- FULL_DIM: common::Bool
CONE_AMBIENT_DIM and CONE_DIM coincide. Notice that this makes sense also for the derived Polytope class.
- 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 facet 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.
- LINEALITY_SPACE: common::Matrix
Basis of the linear subspace orthogonal to all INEQUALITIES and EQUATIONS All vectors in this section must be non-zero. The property LINEALITY_SPACE appears only in conjunction with the property RAYS, or VERTICES, respectively. The specification of the property RAYS or VERTICES requires the specification of LINEALITY_SPACE, and vice versa.
- LINEAR_SPAN: common::Matrix
Dual basis of the linear span of the cone. All vectors in this section must be non-zero. The property LINEAR_SPAN appears only in conjunction with the property FACETS. The specification of the property FACETS requires the specification of LINEAR_SPAN, or AFFINE_HULL, respectively, and vice versa.
- POSITIVE: common::Bool
True 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.
- RAYS: common::Matrix
Rays of the cone. No redundancies are allowed. All vectors in this section must be non-zero. The property RAYS appears only in conjunction with the property LINEALITY_SPACE. The specification of the property RAYS requires the specification of LINEALITY_SPACE, and vice versa.
- 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. number of INEQUALITIES-1, according to their order in RAYS rsp. INEQUALITIES.
- RAY_SEPARATORS: common::Matrix
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.
- TRIVIAL: common::Bool
True if the only valid point in the cone is the unique non-sensical point (0,...,0)
These properties are for input only. They allow redundant information.
- EQUATIONS: common::Matrix
Equations that hold for all INPUT_RAYS of the cone. All vectors in this section must be non-zero.
Input section only. Ask for LINEAR_SPAN if you want to see an irredundant description of the linear span.
- INEQUALITIES: common::Matrix
Inequalities giving rise to the cone; redundancies are allowed. All vectors in this section must be non-zero. Dual to INPUT_RAYS.
Input section only. Ask for FACETS if you want to compute an H-representation from a V-representation.
- INPUT_LINEALITY: common::Matrix
(Non-homogenous) vectors whose linear span defines a subset of the lineality space of the cone; redundancies are allowed. All vectors in the input must be non-zero. 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
(Non-homogenous) vectors whose positive span form the cone; redundancies are allowed. Dual to INEQUALITIES. All vectors in the input must be non-zero.
Input section only. Ask for RAYS if you want to compute a V-representation from an H-representation.
These properties capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- DEGREE_ONE_GENERATORS: common::Matrix<Integer, NonSymmetric>Only defined for Cone<Rational>
Elements of the HILBERT_BASIS for the cone of degree 1 with respect to the MONOID_GRADING.
- GORENSTEIN_CONE: common::BoolOnly defined for Cone<Rational>
A cone is Gorenstein if it is Q-Gorenstein with index one
- HILBERT_BASIS_GENERATORS: common::Array<Matrix<Integer, NonSymmetric>>Only defined for Cone<Rational>
Generators for the HILBERT_BASIS of a posiibly non-pointed cone the first matrix is a Hilbert basis of a pointed part of the cone the second matrix is a lattice basis of the lineality space note: the pointed part used in this property need not be the same as the one described by RAYS or INPUT_RAYS it will be if the cone is pointed (the polytope is bounded)
Depends on: 4ti2 (unbounded) or libnormaliz (bounded) - HILBERT_SERIES: common::RationalFunction<Rational, Int>Only defined for Cone<Rational>
Hilbert series of the monoid, given by the intersection of the cone with the lattice Z^d with respect to the MONOID_GRADING
Depends on: libnormaliz - HOMOGENEOUS: common::BoolOnly defined for Cone<Rational>
True if the primitive generators of the rays lie on an affine hyperplane in the span of the rays.
- H_STAR_VECTOR: common::Vector<Integer>Only defined for Cone<Rational>
The coefficients of the Hilbert polynomial, the h^*-polynomial for lattice polytopes, with respect to the MONOID_GRADING starting at the constant coefficient. For lattice polytopes the length of this vector is CONE_DIM. In general the length is one less than the degree of the denominator of the HILBERT_SERIES.
Depends on: latte or libnormaliz - MONOID_GRADING: common::Vector<Integer>Only defined for Cone<Rational>
A grading for the monoid given by the intersection of the cone with the lattice Z^d, should be positive for all generators.
If this property is not specified by the user there are two defaults: For rational polytopes the affine hyperplane defined by (1,0,\ldots,0) will be used. For HOMOGENEOUS cones the affine hyperplane containing the primitive generators will be used.
- N_HILBERT_BASIS: common::IntOnly defined for Cone<Rational>
The number of elements of the HILBERT_BASIS.
- Q_GORENSTEIN_CONE: common::BoolOnly defined for Cone<Rational>
A 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::IntOnly defined for Cone<Rational>
If 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.
- SMOOTH_CONE: common::BoolOnly defined for Cone<Rational>
A cone is smooth if the primitive generators are part of a lattice basis.
These properties capture information of the object that is concerned with the action of permutation groups.
- GROUP: Group as Cone::GROUPUNDOCUMENTED
Properties of GROUP
These properties capture information of the object that is concerned with the action of permutation groups.
- MATRIX_ACTION: MatrixActionOnVectors as Cone::GROUP::MATRIX_ACTIONUNDOCUMENTED
Properties of MATRIX_ACTION
These properties capture information of the object that is concerned with the action of permutation groups.
- RAYS_ORBITS: common::Array<Set<Int>>
Alias for property group::MatrixActionOnVectors::VECTORS_ORBITS.
- REPRESENTATIVE_BOUNDARY_RIDGE_SIMPLICES: common::Array<Bitset>
One representative for each orbit of boundary ridge simplices
- REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES: common::Array<Bitset>
One representative for each orbit of interior ridge simplices
- REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES: common::Array<Bitset>
One representative for each orbit of maximal-dimensional boundary simplices
- REPRESENTATIVE_MAX_INTERIOR_SIMPLICES: common::Array<Bitset>
One representative for each orbit of maximal-dimensional interior simplices
These properties collect information about triangulations of the object and properties usually computed from such, as the volume.
- TRIANGULATION: GeometricSimplicialComplex as Cone::TRIANGULATION
Some triangulation of the cone using only its RAYS.
Properties of TRIANGULATION
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- BOUNDARY: GeometricSimplicialComplex as Cone::TRIANGULATION::BOUNDARY
Augmented subobject SimplicialComplex::BOUNDARY
Properties of BOUNDARY
- FACET_TRIANGULATIONS: common::Array<Set<Int>>
For each facet the set of simplex indices of BOUNDARY that triangulate it.
- 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.
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- TRIANGULATION_INT: common::Array<Set<Int>>
Conceptually, similar to TRIANGULATION, but using INPUT_RAYS. However, here we use a small object type. The main reason for the existence of this property (in this form) is the beneath_beyond algorithm, which automatically produces this data as a by-product of the conversion from INPUT_RAYS to FACETS. And that data is too valuable to throw away. Use big objects of type VectorConfiguration if you want to work with triangulations using redundant points.
These properties are for visualization.
- COORDINATE_LABELS: common::Array<String>
Unique names assigned to the coordinate directions, analogous to RAY_LABELS. For Polytopes this should contain "inhomog_var" for the homogenization coordinate and this will be added automatically if necessary and CONE_AMBIENT_DIM can be computed.
- FTR_CYCLIC_NORMAL: common::Array<Array<Int>>
Reordered transposed RAYS_IN_FACETS. Dual to RIF_CYCLIC_NORMAL.
- INEQUALITY_LABELS: common::Array<String>
Unique names assigned to the INEQUALITIES, analogous to RAY_LABELS.
- INPUT_RAY_LABELS: common::Array<String>
Unique names assigned to the INPUT_RAYS, analogous to RAY_LABELS.
- NEIGHBOR_FACETS_CYCLIC_NORMAL: common::Array<Array<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<Array<Int>>
Reordered GRAPH. Dual to NEIGHBOR_FACETS_CYCLIC_NORMAL.
- 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.
- 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
These methods are provided for backward compatibility with older versions of polymake only. They should not be used in new code.
- DUAL_DIAMETER () → Int
- DUAL_TRIANGLE_FREE () → Bool
- TRIANGLE_FREE () → Bool
These methods capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- CONNECTIVITY () → Int
- DUAL_CONNECTIVITY () → Int
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
Returns
Int - DUAL_EVEN () → Bool
- faces_of_dim (c) → Array<Set<Int>>
- 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 ...) → Int
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 f034 of the flag vector.
- VERTEX_DEGREES () → Vector<Int>
These methods capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- AMBIENT_DIM () → Int
- contains (v) → Bool
- contains_in_interior (v) → Bool
checks whether a given point is contained in the strict interior of a cone
- DIM () → Int
returns the geometric dimension of the cone (including the lineality space) for the dimension of the pointed part ask for COMBINATORIAL_DIM
Returns
Int
These methods capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- HILBERT_BASIS () → Matrix<Integer>Only defined for Cone<Rational>
for a cone this method returns a Hilbert basis of the cone for a polytope this method returns a Hilbert basis of the homogenization cone of the polytope note: if the cone is not pointed (the polytope is not bounded) then the returned basis is not unique and usually not minimal
Returns
Matrix<Integer>
The following methods compute topological invariants.
- DUAL_GRAPH_SIGNATURE () → Int
- GRAPH_SIGNATURE () → Int
These methods are for visualization.
- VISUAL () → Visual::Cone
Visualizes the cone, intersected with the unit ball.
Options
option list: Visual::Polygons::decorations option list: geometric_options_linear Returns
Visual::Cone
Permutations of Cone
- VertexPerm
permuting the RAYS TODO: rename into RaysPerm and introduce an overriding alias in Polytope
- Category: Lattice points in cones
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::String
A term order by name; allowed acronyms are
lex
,deglex
anddegrevlex
.
- Category: Optimization
A linear program specified by a linear or abstract objective function
Properties of LinearProgram
- ABSTRACT_OBJECTIVE: common::Vector
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.
Example:- The following creates a new LinearProgram object and assigns an abstract objective to it:
> $l = cube(2)->LP(ABSTRACT_OBJECTIVE=>[1,2,3,4]);
> print $l->ABSTRACT_OBJECTIVE;
1 2 3 4
- DIRECTED_BOUNDED_GRAPH: graph::Graph<Directed>
Subgraph of BOUNDED_GRAPH. Consists only of directed arcs along which the value of the objective function increases.
- DIRECTED_GRAPH: graph::Graph<Directed>
Subgraph of Polytope::GRAPH. Consists only of directed arcs along which the value of the objective function increases.
Example:- The following defines a LinearProgram together with a linear objective for the centered square with side length 2. The directed graph according to the linear objective is stored in a new variable and the corresponding edges are printend.
> $c = new Vector([0, 1, 0]);
> $p = cube(2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> $g = $p->LP->DIRECTED_GRAPH;
> print $g->EDGES;
{0 1}
{2 3}
- LINEAR_OBJECTIVE: common::Vector
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.
Example:- The following creates a new LinearProgram object and assigns a linear objective to it:
> $l = cube(2)->LP(LINEAR_OBJECTIVE=>[0,1,1]);
> print $l->LINEAR_OBJECTIVE;
0 1 1
- MAXIMAL_FACE: common::Set<Int>
Indices of vertices at which the maximum of the objective function is attained.
Example:- The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks for the maximal face:
> $c = new Vector([0, 1, 0]);
> $p = cube(2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MAXIMAL_FACE;
{1 3}
- MAXIMAL_VALUE: LinearProgram::Scalar
Maximum value of the objective function. Negated if linear problem is unbounded.
Examples:- The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks for the maximal value:
> $c = new Vector([0, 1, 0]);
> $p = cube(2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MAXIMAL_VALUE;
1
- The following defines a LinearProgram together with a linear objective with bias 3 for the centered square with side length 4 and asks for the maximal value:
> $c = new Vector([3, 1, 0]);
> $p = cube(2,2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MAXIMAL_VALUE;
5
- The following defines a LinearProgram together with a linear objective for the positive quadrant (unbounded) and asks for the maximal value:
> $c = new Vector([0, 1, 1]);
> $p = facet_to_infinity(simplex(2),0);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MAXIMAL_VALUE;
inf
- MAXIMAL_VERTEX: common::Vector
Coordinates of a (possibly not unique) affine vertex at which the maximum of the objective function is attained.
Example:- The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks for a maximal vertex:
> $c = new Vector([0, 1, -1/2]);
> $p = cube(2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MAXIMAL_VERTEX;
1 1 -1
- MINIMAL_FACE: common::Set<Int>
Similar to MAXIMAL_FACE.
Example:- The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks for the minimal face:
> $c = new Vector([0, 1, 0]);
> $p = cube(2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MINIMAL_FACE;
{0 2}
- MINIMAL_VALUE: LinearProgram::Scalar
Similar to MAXIMAL_VALUE.
Examples:- The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks for the minimal value:
> $c = new Vector([0, 1, 0]);
> $p = cube(2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MINIMAL_VALUE;
-1
- The following defines a LinearProgram together with a linear objective with bias 3 for the centered square with side length 4 and asks for the minimal value:
> $c = new Vector([3, 1, 0]);
> $p = cube(2,2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MINIMAL_VALUE;
1
- MINIMAL_VERTEX: common::Vector
Similar to MAXIMAL_VERTEX.
Example:- The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks for a minimal vertex:
> $c = new Vector([0, 1, 0]);
> $p = cube(2);
> $p->LP(LINEAR_OBJECTIVE=>$c);
> print $p->LP->MINIMAL_VERTEX;
1 -1 -1
- RANDOM_EDGE_EPL: common::Vector<Rational>
Expected average path length for a simplex algorithm employing "random edge" pivoting strategy.
User Methods of LinearProgram
- VERTEX_IN_DEGREES () → Array<Int>
Array of in-degrees for all nodes of DIRECTED_GRAPH or numbers of objective decreasing edges at each vertex
Returns
Array<Int> - VERTEX_OUT_DEGREES () → Array<Int>
Array of out-degrees for all nodes of DIRECTED_GRAPH or numbers of objective increasing edges at each vertex
Returns
Array<Int>
- Category: Optimization
A mixed integer linear program specified by a linear or abstract objective function
Properties of MixedIntegerLinearProgram
- INTEGER_VARIABLES: common::Set<Int>
Set of integers that indicate which entries of the solution should be integral. If no value is specified, all entries are required to be integral. If all entries should be rational, please use an LinearProgram instead.
Examples:- The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,1,0]);
> $intvar = new Set<Int>([0,1,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->INTEGER_VARIABLES;
{0 1 2}
- Same as the previous example, but we do not require the first coordinate to be integral anymore.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,1,0]);
> $intvar = new Set<Int>([0,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->INTEGER_VARIABLES;
{0 2}
- LINEAR_OBJECTIVE: common::Vector
Linear objective funtion. 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.
Example:- The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,-1,0]);
> $intvar = new Set<Int>([0,1,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->LINEAR_OBJECTIVE;
0 -1 0
- MAXIMAL_SOLUTION: common::Vector
Coordinates of a (possibly not unique) affine vertex at which the maximum of the objective function is attained.
Examples:- The following defines a MixedIntegerLinearProgram together with a linear objective for the centered square with side length 2 and asks for a maximal solution:
> $c = new Vector([0, 1, -1/2]);
> $p = cube(2);
> $p->MILP(LINEAR_OBJECTIVE=>$c);
> print $p->MILP->MAXIMAL_SOLUTION;
1 1 -1
- The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space. Note that the maximal solution is not a vertex/endpoint of the line segment.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,1,0]);
> $intvar = new Set<Int>([0,1,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->MAXIMAL_SOLUTION;
1 1 0
- Same as the previous example, but we do not require the first coordinate to be integral anymore. Now the maximal solution is an endpoint of the line segment.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,1,0]);
> $intvar = new Set<Int>([0,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->MAXIMAL_SOLUTION;
1 3/2 0
- MAXIMAL_VALUE: MixedIntegerLinearProgram::Scalar
Maximum value the objective funtion takes under the restriction given by INTEGER_VARIABLES.
Examples:- The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space. Note that the maximal value is integral and not the same as the value of the objective function on any of the vertices.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,1,0]);
> $intvar = new Set<Int>([0,1,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->MAXIMAL_VALUE;
1
- Same as the previous example, but we do not require the first coordinate to be integral anymore.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,1,0]);
> $intvar = new Set<Int>([0,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->MAXIMAL_VALUE;
3/2
- MINIMAL_SOLUTION: common::Vector
Similar to MAXIMAL_SOLUTION
Example:- The following defines a MixedIntegerLinearProgram together with a linear objective for the centered square with side length 2 and asks for a maximal solution:
> $c = new Vector([0, 1, -1/2]);
> $p = cube(2);
> $p->MILP(LINEAR_OBJECTIVE=>$c);
> print $p->MILP->MINIMAL_SOLUTION;
1 -1 1
- MINIMAL_VALUE: MixedIntegerLinearProgram::Scalar
Similar to MAXIMAL_VALUE.
Examples:- The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space. Note that the maximal value is integral and not the same as the value of the objective function on any of the vertices.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,-1,0]);
> $intvar = new Set<Int>([0,1,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->MINIMAL_VALUE;
-1
- Same as the previous example, but we do not require the first coordinate to be integral anymore.
> $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
> $obj = new Vector([0,-1,0]);
> $intvar = new Set<Int>([0,2]);
> $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
> print $milp->MINIMAL_VALUE;
-3/2
- derived from: VectorConfiguration
The POINTS of an object of type PointConfiguration encode a not necessarily convex finite point set. The difference to a parent VectorConfiguration is that the points have homogeneous coordinates, i.e. they will be normalized to have first coordinate 1 without warning.
Type Parameters
Scalar default: RationalSpecializations of PointConfiguration
- PointConfiguration::ExactCoord
A point configuration with an exact coordinate type, like Rational.
Properties of PointConfiguration
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- COCIRCUIT_EQUATIONS: common::SparseMatrix<Rational, NonSymmetric>
Tells the cocircuit equations that hold for the configuration, one for each interior ridge
- GRAPH: graph::Graph<Undirected>
Graph of the point configuration. Two points are adjacent if they are neigbours in a edge of the CONVEX_HULL.
- INTERIOR_RIDGE_SIMPLICES: common::Array<Set<Int>>
Tells the number of codimension 1 simplices that are not on the boundary
- MAX_BOUNDARY_SIMPLICES: common::Array<Set<Int>>
Tells the full-dimensional simplices on the boundary that contain no points except for the vertices.
- MAX_INTERIOR_SIMPLICES: common::Array<Set<Int>>
Tells the full-dimensional simplices that contain no points except for the vertices.
- SIMPLEXITY_LOWER_BOUND: common::Int
A lower bound for the minimal number of simplices in a triangulation
- SPLITS: common::Matrix
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.
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- CONVEX_HULL: Polytope as PointConfiguration::CONVEX_HULL
The polytope being the convex hull of the point configuration.
Properties of CONVEX_HULL
- MULTIPLE_POINTS: common::Bool
Tells if multiple points exist. Alias for property VectorConfiguration::MULTIPLE_VECTORS.
These properties are for input only. They allow redundant information.
- POINTS: common::Matrix
The points of the configuration. Multiples allowed. Alias for property VectorConfiguration::VECTORS.
These properties capture information of the object that is concerned with the action of permutation groups.
- GROUP: Group as PointConfiguration::GROUP
Augmented subobject VectorConfiguration::GROUP
Properties of GROUP
These properties capture information of the object that is concerned with the action of permutation groups.
- MATRIX_ACTION: MatrixActionOnVectors as PointConfiguration::GROUP::MATRIX_ACTION
Augmented subobject Group as VectorConfiguration::GROUP::MATRIX_ACTION
Properties of MATRIX_ACTION
These properties capture information of the object that is concerned with the action of permutation groups.
- POINTS_ORBITS: common::Array<Set<Int>>
Alias for property group::MatrixActionOnVectors::VECTORS_ORBITS.
- POINTS_ACTION: PermutationAction<Int, Rational> as PointConfiguration::GROUP::POINTS_ACTION
Alias for property group::Group::VECTOR_ACTION.
Properties of POINTS_ACTION
These properties capture information of the object that is concerned with the action of permutation groups.
- SYMMETRIZED_COCIRCUIT_EQUATIONS: SymmetrizedCocircuitEquations
The cocircuit equations, projected to a certain direct sum of isotypic components
- REPRESENTATIVE_BOUNDARY_RIDGE_SIMPLICES: common::Array<Bitset>
One representative for each orbit of boundary ridge simplices
- REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES: common::Array<Bitset>
One representative for each orbit of interior ridge simplices
- REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES: common::Array<Bitset>
One representative for each orbit of maximal-dimensional boundary simplices
- REPRESENTATIVE_MAX_INTERIOR_SIMPLICES: common::Array<Bitset>
One representative for each orbit of maximal-dimensional interior simplices
These properties collect information about triangulations of the object and properties usually computed from such, as the volume.
- POLYTOPAL_SUBDIVISION: SubdivisionOfPoints as PointConfiguration::POLYTOPAL_SUBDIVISION
Polytopal Subdivision of the point configuration
Properties of POLYTOPAL_SUBDIVISION
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- 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.
- TRIANGULATION: GeometricSimplicialComplex as PointConfiguration::TRIANGULATION
Some triangulation of the point configuration.
Properties of TRIANGULATION
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- BOUNDARY: GeometricSimplicialComplex as PointConfiguration::TRIANGULATION::BOUNDARY
Augmented subobject SimplicialComplex::BOUNDARY
Properties of BOUNDARY
These properties collect information about triangulations of the object and properties usually computed from such, as the volume.
- FACET_TRIANGULATIONS: common::Array<Set<Int>>
DOC_FIXME: Incomprehensible description! For each facet the set of simplex indices of BOUNDARY that triangulate it.
These properties collect information about triangulations of the object and properties usually computed from such, as the volume.
- GKZ_VECTOR: common::Vector
GKZ-vector
See Chapter 7 in Gelfand, Kapranov, and Zelevinsky:Discriminants, Resultants and Multidimensional Determinants, Birkhäuser 1994 - MASSIVE_GKZ_VECTOR: common::Vector
Calculate the massive GKZ vectors of the triangulations of a integral PointConfiguration A. For a definition see Chapter 11 of Gelfand, Kapranov, and Zelevinsky: Discriminants, Resultants and Multidimensional Determinants, Birkhäuser 1994.
Example:- To calculate the massive GKZ vector of a triangulation of a point configuration. This example is from the book mentioned above (p. 369, top right example).
> $A=new PointConfiguration(POINTS=>[[1,0,0],[1,1,0],[1,2,0],[1,3,0],[1,0,1],[1,1,1],[1,0,2]]);
> $A->add("TRIANGULATION", WEIGHTS=>[0,1,0,1,1,1,0]);
> print $A->TRIANGULATION->MASSIVE_GKZ_VECTOR;
1 0 3 1 0 0 4
- 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.
These properties are for visualization.
- 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
- POINT_LABELS: common::Array<String>
Unique names assigned to the POINTS. Alias for property VectorConfiguration::LABELS.
User Methods of PointConfiguration
These methods capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- faces_of_dim (p) → Array<Set<Int>>
Output the faces of a given dimension
These methods capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- AMBIENT_DIM () → Int
Ambient dimension of the point configuration (without the homogenization coordinate). Similar to Polytope::AMBIENT_DIM.
Returns
Int - DIM () → Int
These methods are for visualization.
- VISUAL () → Visual::PointConfiguration
Visualize a point configuration.
Options
option list: Visual::Polygons::decorations option list: geometric_options Returns
Visual::PointConfiguration - VISUAL_POINTS () → Visual::Object
Visualize the POINTS of a point configuration.
Not necessarily bounded convex polyhedron, i.e., the feasible region of a linear program. Nonetheless, the name "Polytope" is used for two reasons: Firstly, as far as the combinatorics is concerned we always deal with polytopes; see the description of VERTICES_IN_FACETS for details. Note that a pointed polyhedron is projectively equivalent to a polytope. The second reason is historical. We use homogeneous coordinates, which is why Polytope is derived from Cone.
Examples:derived from: Cone- To construct a polytope as the convex hull of three points in the plane use
> $p=new Polytope(POINTS=>[[1,0,0],[1,1,0],[1,0,1]]);
> print $p->N_FACETS
3
Note that homogeneous coordinates are used throughout. - Many standard constructions are available directly. For instance, to get a regular 120-cell (which is 4-dimensional) use:
> $c=regular_120_cell();
> print $c->VOLUME;
1575+705r5
This is the exact volume 1575+705*\sqrt{5}. polymake has limited support for polytopes with non-rational coordinates.
Specializations of Polytope
- Polytope<Rational>
A rational polyhedron realized in Q^d
- Polytope<Float>
A pointed polyhedron with float coordinates realized in Rd.
It mainly exists for visualization.
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.
- Polytope::Lattice
A polytope all of whose vertex coordinates are integral.
- Symmetry
These specializations capture information of the object that is concerned with the action of permutation groups.
Properties of Polytope
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- BALANCE: common::Int
Maximal dimension in which all facets are balanced.
Example:- The following full dimensional polytope given by 10 specific vertices on the 8-dimensional sphere is 3-neighborly. Hence the dual polytope is 3-balanced, where we first center and then polarize it.
> $p = rand_sphere(8,10,seed=>8866463);
> $q = polarize(center($p));
> print $q->BALANCE;
3
- BALANCED: common::Bool
Dual to NEIGHBORLY.
Example:- Since cyclic polytopes generated by vertices on the moment curve are neighborly, their dual polytopes are balanced. The following checks this for the 4-dimensional case by centering the cyclic polytope and then polarizing it:
> $p = cyclic(4,6);
> $q = polarize(center($p));
> print $q->BALANCED;
true
- COCUBICAL: common::Bool
Dual to CUBICAL.
Example:- Since the cross-polytope is dual to a cube of same dimension, it is cocubical. The following checks this for the 3-dimensional case:
> print cross(3)->COCUBICAL;
true
- COCUBICALITY: common::Int
Dual to CUBICALITY.
Example:- After stacking a facet of the 3-dimensional cube, its cubicality is lowered to 2. Hence its dual polytope has cocubicality 2 as well. The following produces such a stacked cube and asks for its cocubicality after polarization:
> $p = stack(cube(3),5);
> print polarize($p)->COCUBICALITY;
2
- CUBICAL: common::Bool
True if all facets are cubes.
Examples:- A k-dimensional cube has k-1-dimensional cubes as facets and is therefore cubical. The following checks if this holds for the 3-dimensional case:
> print cube(3)->CUBICAL;
true
- This checks if a zonotope generated by 4 random points on the 3-dimensional sphere is cubical, which is always the case.
> print zonotope(rand_sphere(3,4)->VERTICES)->CUBICAL;
true
- CUBICALITY: common::Int
Maximal dimension in which all facets are cubes.
Example:- We will modify the 3-dimensional cube in two different ways. While stacking some facets (in this case facets 4 and 5) preserves the cubicality up to dimension 2, truncating an arbitrary vertex reduces the cubicality to 1.
> print stack(cube(3),[4,5])->CUBICALITY;
2
> print truncation(cube(3),5)->CUBICALITY;
1
- 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<Undirected> as Polytope::DUAL_GRAPH
Augmented subobject Cone::DUAL_GRAPH
Properties of DUAL_GRAPH
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- DIHEDRAL_ANGLES: common::EdgeMap<Undirected, Float>
Dihedral angles (in radians) between the two facets corresponding to each edge of the dual graph, i.e. the ridges of the polytope.
- 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.
- EDGE_ORIENTABLE: common::Bool
True if there exists an edge-orientation (see EDGE_ORIENTATION for a definition). The polytope is required to be 2-cubical.
Examples:- The following checks a 3-dimensional cube for edge orientability:
> $p = cube(3);
> print $p->EDGE_ORIENTABLE;
true
- A 3-dimensinal cube with one stacked facet is still 2-cubical. Therefore we can check for edge orientability:
> $p = stack(cube(3),5);
> print $p->EDGE_ORIENTABLE;
true
- EDGE_ORIENTATION: common::Matrix<Int, NonSymmetric>
List of all edges with orientation, such that for each 2-face the opposite edges point in the same direction. Each line is of the form (u v), which indicates that the edge {u,v} is oriented from u to v. The polytope is required to be 2-cubical.
Example:- The following prints a list of oriented edges of a 2-dimensional cube such that opposing edges have the same orientation:
> $p = cube(2);
> print $p->EDGE_ORIENTATION;
0 2
1 3
0 1
2 3
- EXCESS_VERTEX_DEGREE: common::Int
Measures the deviation of the cone from being simple in terms of the GRAPH. Alias for property Cone::EXCESS_RAY_DEGREE.
Example:- The excess vertex degree of an egyptian pyramid is one.
> print pyramid(cube(2))->EXCESS_VERTEX_DEGREE;
1
- F2_VECTOR: common::Matrix<Integer, NonSymmetric>
fik is the number of incident pairs of i-faces and k-faces; the main diagonal contains the F_VECTOR.
Example:- The following prints the f2-vector of a 3-dimensional cube:
> print cube(3)->F2_VECTOR;
8 24 24
24 12 24
24 24 6
- 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 Cone::FACETS_THRU_RAYS.
- FACE_SIMPLICITY: common::Int
Maximal dimension in which all faces are simple polytopes. This checks the 3-dimensional cube for face simplicity. Since the cube is dual to the cross-polytope of equal dimension and it is simplicial, the result is 3. > print cube(3)->SIMPLICITY; | 3
- FOLDABLE_MAX_SIGNATURE_UPPER_BOUND: common::Int
An upper bound for the maximal signature of a foldable triangulation of a polytope The signature is the absolute difference of the normalized volumes of black minus white maximal simplices, where only odd normalized volumes are taken into account.
- F_VECTOR: common::Vector<Integer>
fk is the number of k-faces.
Examples:- This prints the f-vector of a 3-dimensional cube. The first entry represents the vertices.
> print cube(3)->F_VECTOR;
8 12 6
- This prints the f-vector of the 3-dimensional cross-polytope. Since the cube and the cross polytope of equal dimension are dual, their f-vectors are the same up to reversion.
> print cross(3)->F_VECTOR;
6 12 8
- After truncating the first standard basis vector of the 3-dimensional cross-polytope the f-vector changes. Only segments of the incident edges of the cut off vertex remain and the intersection of these with the new hyperplane generate four new vertices. These also constitute four new edges and a new facet.
> print truncation(cross(3),4)->F_VECTOR;
9 16 9
- GRAPH: Graph<Undirected> as Polytope::GRAPH
Augmented subobject Cone::GRAPH
Properties of GRAPH
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- EDGE_DIRECTIONS: common::EdgeMap
Difference of the vertices for each edge (only defined up to signs).
These properties capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- LATTICE_ACCUMULATED_EDGE_LENGTHS: common::Map<Integer, Int>Only defined for Polytope::Lattice
a map associating to each edge length of the polytope the number of edges with this length the lattice edge length of an edge is one less than the number of lattice points on that edge
- LATTICE_EDGE_LENGTHS: common::EdgeMap<Undirected, Integer>Only defined for Polytope::Lattice
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
- G_VECTOR: common::Vector<Integer>
(Toric) g-vector, defined via the (generalized) h-vector as gi = hi - hi-1.
- HASSE_DIAGRAM: Lattice<BasicDecoration, Sequential> as Cone::HASSE_DIAGRAM
Number of incident vertices for each facet.
- 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
- MOEBIUS_STRIP_EDGES: common::Matrix<Int, NonSymmetric>
Ordered list of edges of a Moebius strip with parallel interior edges. Consists of k lines of the form (vi wi), for i=1, ..., k.
The Moebius strip in question is given by the quadrangles (vi, wi, wi+1,vi+1), for i=1, ..., k-1, and the quadrangle (v1, w1, vk, wk).
Validity can be verified with the client validate_moebius_strip. The polytope is required to be 2-cubical.
- MOEBIUS_STRIP_QUADS: common::Matrix<Int, NonSymmetric>
Unordered list of quads which forms a Moebius strip with parallel interior edges. Each line lists the vertices of a quadrangle in cyclic order.
Validity can be verified with the client validate_moebius_strip_quads. The polytope is required to be 2-cubical.
- NEIGHBORLINESS: common::Int
Maximal dimension in which all facets are neighborly.
Example:- This determines that the full dimensional polytope given by 10 specific vertices on the 8-dimensional sphere is 3-neighborly, i.e. all 3-dimensional faces are tetrahedra. Hence the polytope is not neighborly.
> print rand_sphere(8,10,seed=>8866463)->NEIGHBORLINESS;
3
- NEIGHBORLY: common::Bool
True if the polytope is neighborly.
Example:- This checks the 4-dimensional cyclic polytope with 6 points on the moment curve for neighborliness, i.e. if it is ⌊dim/2⌋ neighborly:
> print cyclic(4,6)->NEIGHBORLY;
true
- N_VERTEX_FACET_INC: common::Int
Number of pairs of incident vertices and facets. Alias for property Cone::N_RAY_FACET_INC.
- N_VERTICES: common::Int
Number of VERTICES. Alias for property Cone::N_RAYS.
Examples:- The following prints the number of vertices of a 3-dimensional cube:
> print cube(3)->N_VERTICES;
8
- The following prints the number of vertices of the convex hull of 10 specific points lying in the unit square [0,1]^2:
> print rand_box(2,10,1,seed=>4583572)->N_VERTICES;
4
- SELF_DUAL: common::Bool
True if the polytope is self-dual.
Examples:- The following checks if the centered square with side length 2 is self dual:
> print cube(2)->SELF_DUAL;
true
- The elongated square pyramid (Johnson solid 8) is dual to itself, since the apex of the square pyramid attachted to the cube and the opposing square of the cube swap roles. The following checks this property and prints the result:
> print johnson_solid(8)->SELF_DUAL;
true
- SIMPLE: common::Bool
True if the polytope is simple. Dual to SIMPLICIAL.
Example:- This determines if a 3-dimensional cube is simple or not:
> print cube(3)->SIMPLE;
true
- SIMPLEXITY_LOWER_BOUND: common::Int
A lower bound for the minimal number of simplices in a triangulation
- SIMPLICIAL: common::Bool
True if the polytope is simplicial.
Example:- A polytope with random vertices uniformly distributed on the unit sphere is simplicial. The following checks this property and prints the result for 8 points in dimension 3:
> print rand_sphere(3,8)->SIMPLICIAL;
true
- SIMPLICIALITY: common::Int
Maximal dimension in which all faces are simplices.
Example:- The 3-dimensional cross-polytope is simplicial, i.e. its simplicity is 2. After truncating an arbitrary vertex the simplicity is reduced to 1.
> print cross(3)->SIMPLICIALITY;
2
> print truncation(cross(3),4)->SIMPLICIALITY;
1
- SIMPLICITY: common::Int
Maximal dimension in which all dual faces are simplices.
Example:- This checks the 3-dimensional cube for simplicity. Since the cube is dual to the cross-polytope of equal dimension and all its faces are simplices, the result is 2.
> print cube(3)->SIMPLICITY;
2
- 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.
Example:- This prints the number of facets spanned by 3,4 or 5 vertices a truncated 3-dimensional cube has.
> $p = truncation(cube(3),5);
> print $p->TWO_FACE_SIZES;
{(3 1) (4 3) (5 3)}
- VERTEX_SIZES: common::Array<Int>
Number of incident facets for each vertex. Alias for property Cone::RAY_SIZES.
Example:- The following prints the number of incident facets for each vertex of the elongated pentagonal pyramid (Johnson solid 9)
> print johnson_solid(9)->VERTEX_SIZES;
5 4 4 4 4 4 3 3 3 3 3
- 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 Cone::RAYS_IN_FACETS.
Examples:- The following prints the vertex-facet incidence matrix of a 5-gon by listing all facets as a set of contained vertices in a cyclic order (each line corresponds to an edge):
> print n_gon(5)->VERTICES_IN_FACETS;
{1 2}
{2 3}
{3 4}
{0 4}
{0 1}
- The following prints the Vertex_facet incidence matrix of the standard 3-simplex together with the facet numbers:
> print rows_numbered(simplex(3)->VERTICES_IN_FACETS);
0:1 2 3
1:0 2 3
2:0 1 3
3:0 1 2
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- AFFINE_HULL: common::Matrix
Dual basis of the affine hull of the polyhedron. The property AFFINE_HULL appears only in conjunction with the property FACETS. The specification of the property FACETS requires the specification of AFFINE_HULL, and vice versa. Alias for property Cone::LINEAR_SPAN.
- BOUNDED: common::Bool
True if and only if LINEALITY_SPACE trivial and FAR_FACE is trivial.
Example:- A pyramid over a square is bounded. Removing the base square yields an unbounded pointed polyhedron (the vertices with first entry equal to zero correspond to rays).
> $p = pyramid(cube(2));
> print $p->BOUNDED;
true
> $q = facet_to_infinity($p,4);
> print $q->BOUNDED;
false
- CENTERED: common::Bool
True if (1, 0, 0, ...) is in the relative interior. If full-dimensional then polar to BOUNDED.
Example:- The cube [0,1]^3 is not centered, since the origin is on the boundary. By a small translation we can make it centered:
> $p = cube(3,0,0);
> print $p->CENTERED;
false
> $t = new Vector([-1/2,-1/2,-1/2]);
> print translate($p,$t)->CENTERED;
true
- CENTERED_ZONOTOPE: common::Bool
is the zonotope calculated from ZONOTOPE_INPUT_POINTS or ZONOTOPE_INPUT_VECTORS to be centered at the origin? The zonotope is always calculated as the Minkowski sum of all segments conv {x,v}, where * v ranges over the ZONOTOPE_INPUT_POINTS or ZONOTOPE_INPUT_VECTORS, and * x = -v if CENTERED_ZONOTOPE = 1, * x = 0 if CENTERED_ZONOTOPE = 0. Input section only.
- CENTRALLY_SYMMETRIC: common::Bool
True if P = -P.
Example:- A centered 3-cube is centrally symmetric. By stacking a single facet (5), this property is lost. We can recover it by stacking the opposing facet (4) as well.
> $p = cube(3);
> print $p->CENTRALLY_SYMMETRIC;
true
> print stack($p,5)->CENTRALLY_SYMMETRIC;
false
> print stack($p,new Set<Int>(4,5))->CENTRALLY_SYMMETRIC;
true
- CONE_AMBIENT_DIM: common::Int
One more than the dimension of the space in which the polyhedron lives. = dimension of the space in which the homogenization of the polyhedron lives
- CONE_DIM: common::Int
One more than the dimension of the affine hull of the polyhedron = one more than the dimension of the polyhedron. = dimension of the homogenization of the polyhedron If the polytope is given purely combinatorially, this is the dimension of a minimal embedding space
Example:- This prints the cone dimension of a 3-cube. Since the dimension of its affine closure is 3, the result is 4.
> print cube(3)->CONE_DIM;
4
- 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 Cone::FACETS_THRU_INPUT_RAYS.
- INEQUALITIES_THRU_VERTICES: common::IncidenceMatrix<NonSymmetric>
transposed VERTICES_IN_INEQUALITIES Alias for property Cone::INEQUALITIES_THRU_RAYS.
- LATTICE: common::BoolOnly defined for Polytope<Rational>
A rational polytope is lattice if each bounded vertex has integer coordinates.
- MINIMAL_VERTEX_ANGLE: common::Float
The minimal angle between any two vertices (seen from the VERTEX_BARYCENTER).
- MINKOWSKI_CONE: Cone<Rational>Only defined for Polytope<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
- N_01POINTS: common::IntOnly defined for Polytope<Rational>
Number of points with 0/1-coordinates in a polytope.
Depends on: azove - ONE_VERTEX: common::Vector
A vertex of a pointed polyhedron. Alias for property Cone::ONE_RAY.
Example:- This prints the first vertex of the 3-cube (corresponding to the first row in the vertex matrix).
> print cube(3)->ONE_VERTEX;
1 -1 -1 -1
- POINTED: common::Bool
True if the polyhedron does not contain an affine line.
Example:- A square does not contain an affine line and is therefore pointed. Removing one facet does not change this, although it is no longer bounded. After removing two opposing facets, it contains infinitely many affine lines orthogonal to the removed facets.
> $p = cube(2);
> print $p->POINTED;
true
> print facet_to_infinity($p,0)->POINTED;
true
> print new Polytope(INEQUALITIES=>$p->FACETS->minor([0,1],All))->POINTED;
false
- 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 Cone::INPUT_RAYS_IN_FACETS.
- QUOTIENT_SPACE: QuotientSpace
A topological quotient space obtained from a polytope by identifying faces.
- 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.
- SPLITS: common::Matrix
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.
- STEINER_POINTS: common::Matrix
A weighted inner point depending on the outer angle called Steiner point for all faces of dimensions 2 to d.
- VALID_POINT: common::Vector
Some point belonging to the polyhedron.
Example:- This stores a (homogeneous) point belonging to the 3-cube as a vector and prints its coordinates:
> $v = cube(3)->VALID_POINT;
> print $v;
1 -1 -1 -1
- VERTEX_BARYCENTER: common::Vector
The center of gravity of the vertices of a bounded polytope.
Example:- This prints the vertex barycenter of the standard 3-simplex:
> print simplex(3)->VERTEX_BARYCENTER;
1 1/4 1/4 1/4
- VERTEX_NORMALS: common::Matrix
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. All vectors in this section must be non-zero. Alias for property Cone::RAY_SEPARATORS.
Example:- This prints a matrix in which each row represents a normal vector of a hyperplane seperating one vertex of a centered square with side length 2 from the other ones. The first and the last hyperplanes as well as the second and third hyperplanes are the same up to orientation.
> print cube(2)->VERTEX_NORMALS;
0 1/2 1/2
0 -1/2 1/2
0 1/2 -1/2
0 -1/2 -1/2
- VERTICES: common::Matrix
Vertices of the polyhedron. No redundancies are allowed. All vectors in this section must be non-zero. The coordinates are normalized the same way as POINTS. Dual to FACETS. This section is empty if and only if the polytope is empty. The property VERTICES appears only in conjunction with the property LINEALITY_SPACE. The specification of the property VERTICES requires the specification of LINEALITY_SPACE, and vice versa. Alias for property Cone::RAYS.
Examples:- To print the vertices (in homogeneous coordinates) of the standard 2-simplex, i.e. a right-angled isoceles triangle, type this:
> print simplex(2)->VERTICES;
(3) (0 1)
1 1 0
1 0 1
- If we know some points to be vertices of their convex hull, we can store them as rows in a Matrix and construct a new polytope with it. The following produces a 3-dimensioanl pyramid over the standard 2-simplex with the specified vertices:
> $M = new Matrix([[1,0,0,0],[1,1,0,0],[1,0,1,0],[1,0,0,3]]);
> $p = new Polytope(VERTICES=>$M);
- The following adds a (square) pyramid to one facet of a 3-cube. We do this by extracting the vertices of the cube via the built-in method and then attach the apex of the pyramid to the matrix.
> $v = new Vector([1,0,0,3/2]);
> $M = cube(3)->VERTICES / $v;
> $p = new Polytope(VERTICES=>$M);
- 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 Cone::RAYS_IN_INEQUALITIES.
- WEAKLY_CENTERED: common::Bool
True if (1, 0, 0, ...) is contained (possibly in the boundary).
Example:- The cube [0,1]^3 is only weakly centered, since the origin is on the boundary.
> $p = cube(3,0,0);
> print $p->WEAKLY_CENTERED;
true
> print $p->CENTERED;
false
- ZONOTOPE_INPUT_POINTS: common::Matrix
The rows of this matrix contain a configuration of affine points in homogeneous cooordinates. The zonotope is obtained as the Minkowski sum of all rows, normalized to x_0 = 1. Thus, if the input matrix has n columns, the ambient affine dimension of the resulting zonotope is n-1.
These properties are for input only. They allow redundant information.
- EQUATIONS: common::Matrix
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. All vectors in this section must be non-zero.
Input section only. Ask for AFFINE_HULL if you want to see an irredundant description of the affine span.
- INEQUALITIES: common::Matrix
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.
- POINTS: common::Matrix
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. All vectors in this section must be non-zero. Dual to INEQUALITIES.
Input section only. Ask for VERTICES if you want to compute a V-representation from an H-representation. Alias for property Cone::INPUT_RAYS.
Example:- Given some (homogeneous) points in 3-space we first construct a matrix containing them. Assume we don't know wether these are all vertices of their convex hull or not. To safely produce a polytope from these points, we set the input to the matrix representing them. In the following the points under consideration are the vertices of the 3-simplex together with their barycenter, which will be no vertex:
> $M = new Matrix([[1,0,0,0],[1,1,0,0],[1,0,1,0],[1,0,0,1],[1,1/4,1/4,1/4]]);
> $p = new Polytope(POINTS=>$M);
> print $p->VERTICES;
1 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1
These properties capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- CANONICAL: common::BoolOnly defined for Polytope::Lattice
The polytope is canonical if there is exactly one interior lattice point.
- EHRHART_QUASI_POLYNOMIAL: common::Array<UniPolynomial<Rational, Int>>Only defined for Polytope<Rational>
The Ehrhart quasi-polynomial of a rational polytope. Coefficients are periodic functions of integral period.
Example:- To obtain the Ehrhart quasi-polynomial of a scaled 2-dimensional cross polytope write:
> $p=scale(cross(2),1/3);
> print join("\n",@{$p->EHRHART_QUASI_POLYNOMIAL});
2/9*x^2 + 2/3*x + 1
2/9*x^2 + 2/9*x + 5/9
2/9*x^2 -2/9*x + 5/9
Depends on: libnormaliz - FACET_VERTEX_LATTICE_DISTANCES: common::Matrix<Integer, NonSymmetric>Only defined for Polytope::Lattice
The entry (i,j) equals the lattice distance of vertex j from facet i.
- FACET_WIDTH: common::IntegerOnly defined for Polytope::Lattice
The maximal integral width of the polytope with respect to the facet normals.
- FACET_WIDTHS: common::Vector<Integer>Only defined for Polytope::Lattice
The integral width of the polytope with respect to each facet normal.
- GORENSTEIN: common::BoolOnly defined for Polytope::Lattice
The polytope is Gorenstein if a dilation of the polytope is REFLEXIVE up to translation.
- GORENSTEIN_INDEX: common::IntegerOnly defined for Polytope::Lattice
If the polytope is GORENSTEIN then this is the multiple such that the polytope is REFLEXIVE.
- GORENSTEIN_VECTOR: common::Vector<Integer>Only defined for Polytope::Lattice
If the polytope is GORENSTEIN, then this is the unique interior lattice point in the multiple of the polytope that is REFLEXIVE.
- GROEBNER_BASIS: GroebnerBasisOnly defined for Polytope::Lattice
The Groebner basis for the toric ideal associated to the lattice points in the polytope using any term order.
- LATTICE_BASIS: common::Matrix<Rational, NonSymmetric>Only defined for Polytope::Lattice
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::IntOnly defined for Polytope::Lattice
COMBINATORIAL_DIM+1-LATTICE_DEGREE or the smallest integer k such that k*P has an interior lattice point.
- LATTICE_DEGREE: common::IntOnly defined for Polytope::Lattice
The degree of the h*-polynomial or Ehrhart polynomial.
- LATTICE_EMPTY: common::BoolOnly defined for Polytope::Lattice
True if the polytope contains no lattice points other than the vertices.
- LATTICE_VOLUME: common::IntegerOnly defined for Polytope::Lattice
The normalized volume of the polytope.
- LATTICE_WIDTH: common::IntegerOnly defined for Polytope::Lattice
The minimal integral width of the polytope.
- LATTICE_WIDTH_DIRECTION: common::Vector<Integer>Only defined for Polytope::Lattice
One direction which realizes LATTICE_WIDTH of the polytope.
- NORMAL: common::BoolOnly defined for Polytope::Lattice
The polytope is normal if the Hilbert basis of the cone spanned by P x {1} is at height 1. Equivalently points in integral dilates of P are postive integral sums of lattice points of P.
Depends on: 4ti2 or libnormaliz - REFLEXIVE: common::BoolOnly defined for Polytope::Lattice
True if the polytope and its dual have integral vertices.
- SMOOTH: common::BoolOnly defined for Polytope::Lattice
The polytope is smooth if the associated projective variety is smooth; the determinant of the edge directions is +/-1 at every vertex.
- SPANNING: common::BoolOnly defined for Polytope::Lattice
The polytope is spanning if the lattice points generate the lattice
- TERMINAL: common::BoolOnly defined for Polytope::Lattice
The polytope is terminal if there is exactly one interior lattice point and all other lattice points are vertices.
- VERY_AMPLE: common::BoolOnly defined for Polytope::Lattice
The polytope is very ample if the Hilbert Basis of the cone spanned by the edge-directions of any vertex lies inside the polytope.
Depends on: 4ti2 or libnormaliz
These properties capture information that depends on the lattice structure of the polytope. polymake always works with the integer lattice.
- BOUNDARY_LATTICE_POINTS: common::Matrix<Integer, NonSymmetric>Only defined for Polytope<Rational>
The lattice points on the boundary of the polytope, including the vertices.
- INTERIOR_LATTICE_POINTS: common::Matrix<Integer, NonSymmetric>Only defined for Polytope<Rational>
The lattice points strictly in the interior of the polytope
- LATTICE_POINTS_GENERATORS: common::Array<Matrix<Integer, NonSymmetric>>Only defined for Polytope<Rational>
The lattice points generators in the polytope. The output consists of three matrices [P,R,L], where P are lattice points which are contained in the polytope R are rays and L is the lineality. Together they form a description of all lattice points. Every lattice point can be described as p + lambda*R + mu*L where p is a row in P and lambda has only non-negative integral coordinates and mu has arbitrary integral coordinates.
Depends on: 4ti2 for unbounded polytopes - N_BOUNDARY_LATTICE_POINTS: common::IntegerOnly defined for Polytope<Rational>
The number of BOUNDARY_LATTICE_POINTS
- N_INTERIOR_LATTICE_POINTS: common::IntegerOnly defined for Polytope<Rational>
The number of INTERIOR_LATTICE_POINTS
Properties which belong to the corresponding (oriented) matroid
These properties provide tools from linear, integer and dicrete optimization. In particular, linear programs are defined here.
These properties capture information of the object that is concerned with the action of permutation groups.
- GROUP: Group as Polytope::GROUP
Augmented subobject Cone::GROUP
Properties of GROUP
These properties capture information of the object that is concerned with the action of permutation groups.
- COORDINATE_ACTION: PermutationAction<Int, Rational> as Polytope::GROUP::COORDINATE_ACTION
Alias for property group::Group::HOMOGENEOUS_COORDINATE_ACTION.
Properties of COORDINATE_ACTION
- CP_INDICES: common::Set<Int>
The row indices of all core points among the REPRESENTATIVE_CERTIFIERS.
- NOP_GRAPH: graph::Graph<Directed>
The NOP-graph of POINTS_GENERATORS with respect to the GROUP. The nodes of the NOP-graph correspond to the REPRESENTATIVE_CERTIFIERS, which represent the different orbit polytopes contained in the given orbit polytope.
- REPRESENTATIVE_CERTIFIERS: common::Matrix<Rational, NonSymmetric>
A matrix of representatives of all certifiers for POINTS_GENERATORS with respect to the GROUP. A certifier is an integer point in the given orbit polytope. Note that the representative certifiers must be in the same order as the corresponding nodes in the NOP_GRAPH. Further, the CP_INDICES refer to row indices of this property.
- REPRESENTATIVE_CORE_POINTS: common::Matrix<Rational, NonSymmetric>
A matrix of representatives of all core points in the given orbit polytope. A core point is an integer point whose orbit polytope is lattice-free (i.e. does not contain integer points besides its vertices).
- VERTICES_GENERATORS: common::Matrix<Rational, NonSymmetric>
Alias for property group::Action::RAYS_GENERATORS.
- MATRIX_ACTION: MatrixActionOnVectors as Polytope::GROUP::MATRIX_ACTION
Augmented subobject Group as Cone::GROUP::MATRIX_ACTION
Properties of MATRIX_ACTION
- VERTICES_ORBITS: common::Array<Set<Int>>
Alias for property group::MatrixActionOnVectors::VECTORS_ORBITS.
- POINTS_ACTION: group::PermutationAction<Int, Rational>
Alias for property group::Group::INPUT_RAYS_ACTION.
- VERTICES_ACTION: PermutationAction<Int, Rational> as Polytope::GROUP::VERTICES_ACTION
Alias for property group::Group::RAYS_ACTION.
Properties of VERTICES_ACTION
These properties capture information of the object that is concerned with the action of permutation groups.
- SYMMETRIZED_COCIRCUIT_EQUATIONS: SymmetrizedCocircuitEquations
The cocircuit equations, projected to a certain direct sum of isotypic components
Everything in this group is defined for BOUNDED polytopes only.
- MAHLER_VOLUME: Polytope::Scalar
Mahler volume (or volume product) of the polytope. Defined as the volume of the polytope and the volume of its polar (for BOUNDED, CENTERED and FULL_DIM polytopes only). Often studied for centrally symmetric convex bodies, where the regular cubes are conjectured to be the global minimiers.
Example:- The following prints the Mahler volume of the centered 2-cube:
> print cube(2)->MAHLER_VOLUME;
8
- POLYTOPAL_SUBDIVISION: SubdivisionOfPoints as Polytope::POLYTOPAL_SUBDIVISION
Polytopal Subdivision of the polytope using only its vertices.
Properties of POLYTOPAL_SUBDIVISION
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- 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.
- RELATIVE_VOLUME: common::Map<Rational, Rational>Only defined for Polytope<Rational>
The k-dimensional Euclidean volume of a k-dimensional rational polytope embedded in R^n. This value is obtained by summing the square roots of the entries in SQUARED_RELATIVE_VOLUMES using the function naive_sum_of_square_roots. Since this latter function does not try very hard to compute the real value, you may have to resort to a computer algebra package. The value is encoded as a map collecting the coefficients of various roots encountered in the sum. For example, {(3 1/2),(5 7)} represents sqrt{3}/2 + 7 sqrt{5}. If the output is not satisfactory, please use a symbolic algebra package.
Example:- The following prints the 2-dimensional volume of a centered square with side length 2 embedded in the 3-space (the result is 4):
> $M = new Matrix([1,-1,1,0],[1,-1,-1,0],[1,1,-1,0],[1,1,1,0]);
> $p = new Polytope<Rational>(VERTICES=>$M);
> print $p->RELATIVE_VOLUME;
{(1 4)}
- SQUARED_RELATIVE_VOLUMES: common::Array
Array of the squared relative k-dimensional volumes of the simplices in a triangulation of a d-dimensional polytope.
- TRIANGULATION: GeometricSimplicialComplex as Polytope::TRIANGULATION
Augmented subobject Cone::TRIANGULATION
Properties of TRIANGULATION
These properties collect information about triangulations of the object and properties usually computed from such, as the volume.
- GKZ_VECTOR: common::Vector
GKZ-vector
See Chapter 7 in Gelfand, Kapranov, and Zelevinsky:Discriminants, Resultants and Multidimensional Determinants, Birkhäuser 1994
- VOLUME: Polytope::Scalar
Volume of the polytope.
Example:- The following prints the volume of the centered 3-dimensional cube with side length 2:
> print cube(3)->VOLUME;
8
These properties collect geometric information of a polytope only relevant if it is unbounded, e. g. the far face or the complex of bounded faces.
- BOUNDED_COMPLEX: PolyhedralComplex as Polytope::BOUNDED_COMPLEX
Bounded subcomplex. Defined as the bounded cells of the boundary of the pointed part of the polytope. Therefore it only depends on VERTICES_IN_FACETS and FAR_FACE.
Properties of BOUNDED_COMPLEX
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- GRAPH: Graph<Undirected> as Polytope::BOUNDED_COMPLEX::GRAPH
Augmented subobject PolyhedralFan::GRAPH
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
Difference of the vertices for each edge (only defined up to signs).
These properties collect geometric information of a polytope only relevant if it is unbounded, e. g. the far face or the complex of bounded faces.
- TOWARDS_FAR_FACE: common::Vector
A linear objective function for which each unbounded edge is increasing; only defined for unbounded polyhedra.
These properties are for visualization.
- FACET_LABELS: common::Array<String>
Unique names assigned to the FACETS, analogous to VERTEX_LABELS.
- FTV_CYCLIC_NORMAL: common::Array<Array<Int>>
Reordered transposed VERTICES_IN_FACETS. Dual to VIF_CYCLIC_NORMAL. Alias for property Cone::FTR_CYCLIC_NORMAL.
- GALE_VERTICES: common::Matrix<Float, NonSymmetric>
Coordinates of points for an affine Gale diagram.
- INEQUALITY_LABELS: common::Array<String>
Unique names assigned to the INEQUALITIES, analogous to VERTEX_LABELS.
- NEIGHBOR_VERTICES_CYCLIC_NORMAL: common::Array<Array<Int>>
Reordered GRAPH. Dual to NEIGHBOR_FACETS_CYCLIC_NORMAL. Alias for property Cone::NEIGHBOR_RAYS_CYCLIC_NORMAL.
- POINT_LABELS: common::Array<String>
Unique names assigned to the POINTS, analogous to VERTEX_LABELS. Alias for property Cone::INPUT_RAY_LABELS.
- SCHLEGEL_DIAGRAM: SchlegelDiagram
Holds one special projection (the Schlegel diagram) of the 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), the labels are created the labels automatically except if you call the function with a no_labels option. The exact format of the abels is dependent on the construction, and is described in the corresponding help topic. Alias for property Cone::RAY_LABELS.
- 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 Cone::RIF_CYCLIC_NORMAL.
User Methods of Polytope
These methods capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- CD_INDEX () → String
- N_RIDGES () → Int
The number of ridges (faces of codimension 2) of the polytope equals the number of edges of the DUAL_GRAPH
Returns
Int
These methods capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- AMBIENT_DIM () → Int
- INNER_DESCRIPTION () → Array<Matrix<Scalar>>
Returns the inner description of a Polytope: [V,L] where V are the vertices and L is the lineality space
Returns
Array<Matrix<Scalar>> - labeled_vertices (label ...) → Set<Int>
- MINKOWSKI_CONE_COEFF (coeff) → Polytope<Rational>Only defined for Polytope<Rational>
returns the Minkowski summand of a polytope P given by a coefficient vector to the rays of the MINKOWSKI_CONE.
Parameters
Vector<Rational> coeff coefficient vector to the rays of the Minkowski summand coneReturns
Polytope<Rational> - MINKOWSKI_CONE_POINT (point) → Polytope<Rational>Only defined for Polytope<Rational>
returns the Minkowski summand of a polytope P given by a point in the MINKOWSKI_CONE.
- OUTER_DESCRIPTION () → Array<Matrix<Scalar>>
Returns the outer description of a Polytope: [F,A] where F are the facets and A is the affine hull
Returns
Array<Matrix<Scalar>>
These methods capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- EHRHART_POLYNOMIAL_COEFF () → Vector<Rational>Only defined for Polytope::Lattice
Vector containing the coefficients of the EHRHART_POLYNOMIAL, ordered by increasing degree of the corresponding term.
Returns
Vector<Rational> - FACET_POINT_LATTICE_DISTANCES (v) → Vector<Integer>Only defined for Polytope::Lattice
Vector containing the distances of a given point v from all facets
- N_LATTICE_POINTS_IN_DILATION (n) → IntOnly defined for Polytope::Lattice
The number of LATTICE_POINTS in the n-th dilation of the polytope
- POLYTOPE_IN_STD_BASIS (P) → Polytope<Rational>Only defined for Polytope::Lattice
returns a polytope in the integer lattice basis if a LATTICE_BASIS is given
These methods capture information that depends on the lattice structure of the polytope. polymake always works with the integer lattice.
- LATTICE_POINTS () → Matrix<Integer>Only defined for Polytope<Rational>
Returns the lattice points in bounded Polytopes.
Returns
Matrix<Integer>
These methods capture information of the object that is concerned with the action of permutation groups.
- VISUAL_NOP (colors_ref, trans_ref)Only defined for Polytope::PointOrbit
Visualizes all (nested) orbit polytopes contained in orb in one picture.
- VISUAL_NOP_GRAPH (filename)Only defined for Polytope::PointOrbit
Visualizes the NOP-graph of an orbit polytope. Requires 'graphviz' and a Postscript viewer. Produces a file which is to be processed with the program 'dot' from the graphviz package. If 'dot' is installed, the NOP-graph is visualized by the Postscript viewer.
Parameters
String filename the filename for the 'dot' file
These methods collect information about triangulations of the object and properties usually computed from such, as the 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
These methods collect geometric information of a polytope only relevant if it is unbounded, e. g. the far face or the complex of bounded faces.
- 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>
These methods are for visualization.
- GALE () → Visual::Gale
- SCHLEGEL () → Visual::SchlegelDiagram
Create a Schlegel diagram and draw it.
Options
Visual::Graph::decorations proj_facet decorations for the edges of the projection faceoption 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 option list: Visual::Wire::decorations option list: Visual::PointSet::decorations option list: geometric_options Returns
Visual::Polytope - VISUAL_BOUNDED_GRAPH () → Visual::PolytopeGraph
Visualize 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::Object
- 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 placementoption 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 embedderoption 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 placementoption 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 embedderoption list: Visual::Graph::decorations Returns
Visual::PolytopeGraph - VISUAL_ORBIT_COLORED_GRAPH () → Visual::PolytopeGraph
Visualizes the graph of a symmetric cone: All nodes belonging to one orbit get the same color.
- derived from: Polytope
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.
Properties of PropagatedPolytope
- SUM_PRODUCT_GRAPH: Graph<Directed> as PropagatedPolytope::SUM_PRODUCT_GRAPH
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
- Category: Symmetry
A topological quotient space obtained from a Polytope by identifying faces. This object will sit inside the polytope.
Properties of QuotientSpace
Properties defining a quotient space.
- IDENTIFICATION_ACTION: group::PermutationAction<Int, Rational>
The group encoding the quotient space. The faces of the space are the orbits of the faces of the polytope under the group.
These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- COCIRCUIT_EQUATIONS: common::SparseMatrix<Rational, NonSymmetric>
a SparseMatrix whose rows are the sum of all cocircuit equations corresponding to a fixed symmetry class of interior ridge
- FACES: common::Array<Set<Set<Int>>>
The faces of the quotient space, ordered by dimension. One representative of each orbit class is kept.
- FACE_ORBITS: common::Array<Set<Array<Set<Int>>>>
The orbits of faces of the quotient space, ordered by dimension.
- N_SIMPLICES: common::Array<Int>
The simplices made from points of the quotient space (also internal simplices, not just faces)
- REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES: common::Array<Bitset>
The (d-1)-dimensional simplices in the interior.
- REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES: common::Array<Bitset>
The boundary (d-1)-dimensional simplices of a cone of combinatorial dimension d
- REPRESENTATIVE_MAX_INTERIOR_SIMPLICES: common::Array<Bitset>
The interior d-dimensional simplices of a cone of combinatorial dimension d
- SIMPLEXITY_LOWER_BOUND: common::Int
A lower bound for the number of simplices needed to triangulate the quotient space
- SIMPLICIAL_COMPLEX: topaz::SimplicialComplex
A simplicial complex obtained by two stellar subdivisions of the defining polytope.
- SYMMETRY_GROUP: group::Group
The symmetry group induced by the symmetry group of the polytope on the FACES of the quotient space
A Schlegel diagram of a polytope.
Type Parameters
Scalar default RationalProperties of SchlegelDiagram
- 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
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::SchlegelDiagram
Draw the Schlegel diagram.
Options
Visual::Graph::decorations proj_facet decorations for the edges of the projection faceoption list: Visual::Graph::decorations Returns
Visual::SchlegelDiagram
- Category: SymmetryUNDOCUMENTED
Properties of SymmetrizedCocircuitEquations
- PROJECTED_EQUATIONS: common::SparseMatrix<Rational, NonSymmetric>
the equations themselves, projected to the direct sum of ISOTYPIC_COMPONENTS. The columns are indexed by the concatenation of the BASES of the direct sum of ISOTYPIC_COMPONENTS
- Category: Geometry
An object of type VectorConfiguration deals with properties of row vectors, assembled into an n x d matrix called VECTORS. The entries of these row vectors are interpreted as non-homogeneous coordinates. In particular, the coordinates of a VECTOR will *NOT* be normalized to have a leading 1.
Type Parameters
Scalar default: RationalProperties of VectorConfiguration
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- POSITIVE: common::Bool
True if all VECTORS have non-negative coordinates, that is, if they all lie entirely in the positive orthant.
- VECTOR_AMBIENT_DIM: common::Int
Dimension of the space in which the vector configuration lives. Similar to Cone::CONE_AMBIENT_DIM.
- VECTOR_DIM: common::Int
Dimension of the linear hull of the vector configuration. Similar to Cone::CONE_DIM.
These properties are for input only. They allow redundant information.
Properties which belong to the corresponding (oriented) matroid
These properties capture information of the object that is concerned with the action of permutation groups.
- GROUP: Group as VectorConfiguration::GROUPUNDOCUMENTED
Properties of GROUP
These properties capture information of the object that is concerned with the action of permutation groups.
These properties are for visualization.
- LABELS: common::Array<String>
Unique names assigned to the VECTORS. If specified, they are shown by visualization tools instead of point indices.
User Methods of VectorConfiguration
These methods are for visualization.
- VISUAL () → Visual::PointConfiguration
Visualize a vector configuration.
Options
option list: Visual::Polygons::decorations option list: geometric_options_linear Returns
Visual::PointConfiguration
- Category: Visualizationderived from: Visual::Container
Visualization of a Cone as a graph (if 1d), or as a solid object (if 2d or 3d)
- Category: Visualization
Visualization of the point configuration.
User Methods of Visual::PointConfiguration
- POLYTOPAL_SUBDIVISION (index) → Visual::PointConfiguration
Visualize a POLYTOPAL_SUBDIVISION of a point configuration.
Parameters
Int index Index of the subdivision to visualizeOptions
option list: Visual::Polygons::decorations option list: geometric_options Returns
Visual::PointConfiguration - TRIANGULATION (t) → Visual::PointConfiguration
Visualize the TRIANGULATION of a point configuration
Parameters
Array<Set<Int>> t facets of the triangulationOptions
option list: Visual::Polygons::decorations Returns
Visual::PointConfiguration
- 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.
Example:- Attaches a linear program to the 3-dimensional cube and visualizes the directed graph, giving the cube a blue facet color
> $p = cube(3);
> $p->LP = new LinearProgram(LINEAR_OBJECTIVE=>[0,0,0,1]);
> $p->VISUAL(FacetColor=>"blue")->DIRECTED_GRAPH;
- LATTICE () → Visual::Polytope
Visualize the LATTICE_POINTS of a polytope
Example:- Visualizes the lattice points of the threedimensional cube.
> cube(3)->VISUAL->LATTICE;
- LATTICE_COLORED () → Visual::Polytope
Visualize the LATTICE_POINTS of a polytope in different colors (interior / boundary / vertices)
Example:- Creates the threedimensional unit cube scaled by 1.5 and displays the colored version of its lattice points
> cube(3,(3/2),0)->VISUAL->LATTICE_COLORED;
- 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 Example:- Attaches a linear program to the threedimensional cube and displays the minimal/maximal faces in a different color, choosing purple instead of the default red for the maximal face
> $p = cube(3);
> $p->LP = new LinearProgram(LINEAR_OBJECTIVE=>[0,1,0,0]);
> $p->VISUAL->MIN_MAX_FACE(max=>"purple");
- STEINER () → Visual::Polytope
Add the STEINER_POINTS to the 3-d visualization. The facets become transparent.
Example:- Displays the Steiner points of a random threedimensional sphere with 20 vertices. The labels of the vertices are turned off.
> rand_sphere(3,20)->VISUAL(VertexLabels=>"hidden")->STEINER;
- TRIANGULATION (t) → Visual::Polytope
Add the triangulation to the drawing.
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>> t facets of the triangulationOptions
option list: Visual::Polygons::decorations Returns
Visual::Polytope Example:- Displays a triangulation of the threedimensional cube. Facets are made transparent and vertices are hidden.
> cube(3)->VISUAL->TRIANGULATION(FacetTransparency=>0.7,VertexStyle=>"hidden");
- TRIANGULATION_BOUNDARY () → Visual::Polytope
Draw the edges of the TRIANGULATION_BOUNDARY. The facets are made transparent.
Examples:- Displays the boundary triangulation of the threedimensional cube.
> cube(3)->VISUAL->TRIANGULATION_BOUNDARY;
- For a slightly different visualization of essentially the same:
> cube(3)->TRIANGULATION->BOUNDARY->VISUAL;
- 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 polytopeOptions
Color min minimal vertex color (default: yellow)Color max maximal vertex color (default: red)Returns
Visual::Polytope Example:- Attaches a linear program to the threedimensional cube and displays the minimal/maximal vertices in a different color, choosing purple instead of the default red for the maximal vertices
> $p = cube(3);
> $p->LP = new LinearProgram(LINEAR_OBJECTIVE=>[0,1,0,0]);
> $p->VISUAL->VERTEX_COLORS(max=>"purple");
- Category: Visualization
Visualization of the graph of a polyhedron.
User Methods of Visual::PolytopeGraph
- DIRECTED_GRAPH (lp) → Visual::PolytopeGraph
Show the growth direction of a linear objective function via arrowed edges.
Parameters
LinearProgram lp a LinearProgram object attached to the polytopeReturns
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 polytopeOptions
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
- 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 polytopeOptions
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: Visualization
Visualization of the Schlegel diagram of a polytope.
User Methods of Visual::SchlegelDiagram
- CONSTRUCTION () → Visual::SchlegelDiagram
Visualize the construction of a 3D Schlegel diagram, that is, the Viewpoint, the 3-polytope and the projection onto one facet.
- 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.
- STEINER ()
- TRIANGULATION_BOUNDARY () → Visual::SchlegelDiagram
Draw the edges of the TRIANGULATION_BOUNDARY
- TRIANGULATION_BOUNDARY_SOLID () → Visual::SchlegelDiagram
Draw the boundary simplices of the triangulation as solid tetrahedra.
- 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
- derived from: Polytope
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 VoronoiPolyhedron becomes a derived class from Polytope<Scalar>.
Properties of VoronoiPolyhedron
- DELAUNAY_TRIANGULATION: common::Array<Set<Int>>
Delaunay triangulation of the sites. (Delaunay subdivision, non-simplices are triangulated.)
- ITERATED_VORONOI_GRAPH: 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 VoronoiPolyhedron 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
Homogeneous coordinates of the sites in case the polyhedron is Voronoi. Sites must be pairwise distinct.
- VORONOI_DIAGRAM: fan::PolyhedralComplex
The Voronoi regions as polyhedral complex. Polyhedron indices correspond to site indices.
- VORONOI_GRAPH: 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.
User Methods of VoronoiPolyhedron
These methods are for visualization.
- VISUAL_CRUST () → Visual::Container
Draw a Voronoi diagram, its |dual graph and the crust. Use the interactive features of the viewer to select.
- 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.
- VISUAL_VORONOI () → Visual::Container
Visualize the Voronoi diagram together with its sites.
User Functions
These functions capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
- circuits2matrix (co) → SparseMatrix<Rational>
Convert CIRCUITS or COCIRCUITS to a 0/+1/-1 matrix, with one row for each circuit/cocircuit, and as many columns as there are VECTORs/POINTS.
Parameters
Set<Pair<Set<Int>,Set<Int>>> co /circuits a set of circuits or cocircuitsReturns
SparseMatrix<Rational> - cocircuit_equations (C, interior_ridge_simplices, interior_simplices) → SparseMatrix<Int>
A matrix whose rows contain the cocircuit equations of a cone C with respect to a list of interior ridge simplices symmetries of the cone are NOT taken into account
Parameters
Cone C Array<Set> interior_ridge_simplices interior codimension 1 simplicesArray<Set> interior_simplices interior simplices of maximal dimensionOptions
String filename where to write the output (default empty)Bool reduce_rows whether to perform row reduction (default 1)Int log_frequency how often to print log messagesReturns
SparseMatrix<Int> - cocircuit_equation_of_ridge (C, rho) → HashMap<Set,Rational>
The cocircuit equations of a cone C corresponding to some interior ridge rho with respect to a list of interior simplices symmetries of the cone are NOT taken into account
- codegree <Scalar> (P)
Calculate the codegree of a cone or polytope P. This is the maximal positive integer c such that every subset of size < c lies in a common facet of conv P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.
Example:- To find the codegree of the 3-cube, type
> print codegree(cube(3));
1
- codegree <Scalar> (P)
Calculate the codegree of a point configuration P. This is the maximal positive integer c such that every subset of size < c lies in a common facet of conv P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.
- contraction (C, v)
Contract a vector configuration C along a specified vector v.
Parameters
VectorConfiguration C Int v index of the vector to contract - degree <Scalar> (P)
Calculate the degree of a cone, polytope or point configuration P. This is the maximal dimension of an interior face of P, where an interior face is a subset of the points of P whose convex hull does not lie on the boundary of P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.
Example:- To find the degree of the 3-cube, type
> print degree(cube(3));
3
- deletion (C, v)
Delete a specified vector v from a vector configuration C.
Parameters
VectorConfiguration C Int v index of the vector to delete
Functions based on graph isomorphisms.
- congruent (P1, P2) → Scalar
Check whether two given polytopes P1 and P2 are congruent, i.e. whether there is an affine isomorphism between them that is induced by a (possibly scaled) orthogonal matrix. Returns the scale factor, or 0 if the polytopes are not congruent.
We are using the reduction of the congruence problem (for arbitrary point sets) to the graph isomorphism problem due to:
Akutsu, T.: On determining the congruence of point sets in `d` dimensions.Comput. Geom. Theory Appl. 9, 247--256 (1998), no. 4Parameters
Polytope P1 the first polytopePolytope P2 the second polytopeReturns
Scalar the square of the scale factor or 0 if the polytopes are not congruentExample:- Let's first consider an isosceles triangle and its image of the reflection in the origin:
> $t = simplex(2);
> $tr = simplex(2,-1);
Those two are congruent:> print congruent($t,$tr);
1
If we scale one of them, we get a factor:> print congruent(scale($t,2),$tr);
4
But if we instead take a triangle that is not isosceles, we get a negative result.> $tn = new Polytope(VERTICES => [[1,0,0],[1,2,0],[1,0,1]]);
> print congruent($t,$tn);
0
- equal_polyhedra (P1, P2) → BoolUNDOCUMENTED
Parameters
Polytope P1 the first polytopePolytope P2 the second polytopeOptions
Bool verbose Prints information on the difference between P1 and P2 if they are not equal.Returns
Bool true if the two polyhedra are equal, false otherwiseExample:> $p = new Polytope(VERTICES => [[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]);
> print equal_polyhedra($p,cube(2));
true
To see why two polytopes are unequal, try this:> print equal_polyhedra($p,cube(3),verbose => 1);
Cones/Polytopes do no live in the same ambient space.
false
> print equal_polyhedra($p,simplex(2),verbose => 1);
Inequality 1 -1 -1 not satisfied by point 1 1 1.
false
- find_facet_vertex_permutations (P1, P2) → Pair<Array<Int>, Array<Int>>
Find the permutations of facets and vertices which maps the cone or polyhedron P1 to P2. The facet permutation is the first component, the vertex permutation is the second component of the return value.
Only the combinatorial isomorphism is considered. If the polytopes are not isomorphic, an exception is thrown.
Parameters
Cone P1 the first cone/polytopeCone P2 the second cone/polytopeReturns
Pair<Array<Int>, Array<Int>> the facet and the vertex permutationsExample:- To print the vertex permutation that maps the 3-simplex to its mirror image, type this:
> $p = find_facet_vertex_permutations(simplex(3),scale(simplex(3),-1));
> print $p->first;
1 2 3 0
- included_polyhedra (P1, P2) → BoolUNDOCUMENTED
Parameters
Polytope P1 the first polytopePolytope P2 the second polytopeOptions
Bool verbose Prints information on the difference between P1 and P2 if none is included in the other.Returns
Bool 'true' if P1 is included in P2, 'false' otherwiseExample:> print included_polyhedra(simplex(3),cube(3));
true
To see in what way the two polytopes differ, try this:> print included_polyhedra(cube(2),cube(3),verbose=>1);
Cones/Polytopes do no live in the same ambient space.
false
- isomorphic (P1, P2) → Bool
Check whether the face lattices of two cones or polytopes are isomorphic. The problem is reduced to graph isomorphism of the vertex-facet incidence graphs.
Parameters
Cone P1 the first cone/polytopeCone P2 the second cone/polytopeReturns
Bool 'true' if the face lattices are isomorphic, 'false' otherwiseExample:- The following compares the standard 2-cube with a polygon generated as the convex hull of five points. The return value is true since both polygons are quadrangles.
> $p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]);
> print isomorphic(cube(2),$p);
true
- lattice_isomorphic_smooth_polytopes (P1, P2) → Bool
Tests whether two smooth lattice polytopes are lattice equivalent by comparing lattice distances between vertices and facets.
Parameters
Polytope P1 the first lattice polytopePolytope P2 the second lattice polytopeReturns
Bool 'true' if the polytopes are lattice equivalent, 'false' otherwiseExample:> $t = new Vector(2,2);
> print lattice_isomorphic_smooth_polytopes(cube(2),translate(cube(2),$t));
true
These functions are for checking the consistency of some properties.
- check_inc (points, hyperplanes, sign, verbose) → Bool
Check coordinate data. For each pair of vectors from two given matrices their inner product must satisfy the given relation.
Parameters
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 relationReturns
Bool 'true' if all relations are satisfied, 'false' otherwiseExample:- Let's check which vertices of the square lie in its zeroth facet:
> $H = cube(2)->FACETS->minor([0],All);
> print check_inc(cube(2)->VERTICES,$H,'0',1);
<1,0> ( 1 1 -1 ) * [ 1 1 0 ] == 2
<3,0> ( 1 1 1 ) * [ 1 1 0 ] == 2
#points==4, #hyperplanes==1, -:0, 0:2, +:2, total:4
false
Thus, the first and third vertex don't lie on the hyperplane defined by the facet but on the positive side of it, and the remaining two lie on the hyperplane.
- 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 matrixBool verbose prints information about the check.Returns
Polytope the resulting polytope under the assumption that VIF actually defines a polytope - validate_moebius_strip (P) → Bool
Validates the output of the client edge_orientable, in particular it checks whether the MOEBIUS_STRIP_EDGES form a Moebius strip with parallel opposite edges. Prints a message to stdout.
- validate_moebius_strip_quads (P) → Matrix<Int>
Checks whether the MOEBIUS_STRIP_QUADS form a Moebius strip with parallel opposite edges. Prints a message to stdout and returns the MOEBIUS_STRIP_EDGES if the answer is affirmative.
Parameters
Polytope P the given polytopeOptions
Bool verbose print detailsReturns
Matrix<Int> the Moebius strip edges
The following functions allow for the conversion of the coordinate type of cones and polytopes.
- affine_float_coords (P) → Matrix<Float>
Dehomogenize the vertex coordinates and convert them to Float
Example:> print cube(2,1/2)->VERTICES;
1 -1/2 -1/2
1 1/2 -1/2
1 -1/2 1/2
1 1/2 1/2
> print affine_float_coords(cube(2,1/2));
-0.5 -0.5
0.5 -0.5
-0.5 0.5
0.5 0.5
- 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 typeParameters
Cone c the input coneReturns
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 typeParameters
Polytope P source objectReturns
Polytope<Coord> P if it already has the requested type, a new object otherwiseExample:> print cube(2)->type->full_name;
Polytope<Rational>
> $pf = convert_to<Float>(cube(2));
> print $pf->type->full_name;
Polytope<Float>
Tight spans and their connections to polyhedral geometry
- tight_span_envelope (sd) → Polytope
Computes the envelope for a given subdivision of points.
Parameters
fan::SubdivisionOfPoints sd Options
Bool extended If True, the envelope of the extended tight span is computed.Returns
Polytope
These functions capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
- 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.
- center_distance (p) → Float
Compute the mean or median distance of the VERTICES to the VERTEX_BARYCENTER.
- circuit_completions (L, R) → Array<Set>
Given two matrices L (n x d) and R (m x d) such that (L/R) has rank r, select all (r+1-n)-subsets C of rows of R such that (L,S) or (S,L) is a circuit. Optionally, if d > r, a basis H for the orthogonal span of the affine hull of (L/R) may be given.
Example:- Divide the vertex set of the 3-cube into a body diagonal L and six remaining vertices R. To find the subsets of R that complete L to a circuit, type
> $c = cube(3);
> $L = $c->VERTICES->minor([0,7],All);
> $R = $c->VERTICES->minor([1,2,3,4,5,6],All);
> print circuit_completions($L,$R);
{0 1 3}
{2 4 5}
- containing_normal_cone (P, q) → Set
Return the vertices of the face of P whose normal cone contains a point q.
Example:- To find the face whose normal cone contains a given point, type
> $p = new Polytope(VERTICES=>[[1,-1,0],[1,0,-1],[1,0,1],[1,100,0]]);
> print containing_normal_cone($p, new Vector([1,1,2]));
{2 3}
- containing_outer_cone (P, q) → Set
- dihedral_angle (H1, H2) → Float
Compute the dihedral angle between two (oriented) affine or linear hyperplanes.
Parameters
Vector<Scalar> H1 : first hyperplaneVector<Scalar> H2 : second hyperplaneOptions
Bool deg output in degrees rather than radians, default is falseBool cone hyperplanes seen as linear hyperplanes, default is falseReturns
Float Example:> $H1 = new Vector(1,5,5);
> $H2 = new Vector(1,-5,5);
> print dihedral_angle($H1,$H2,deg=>1);
90
- induced_lattice_basis (p) → Matrix<Integer>
Returns a basis of the affine lattice spanned by the vertices
Example:- The vertices of the 2-simplex span all of Z^2...
> print induced_lattice_basis(simplex(2));
0 1 0
0 0 1
...but if we scale it with 2, we get only every second lattice point.> print induced_lattice_basis(scale(simplex(2),2));
0 2 0
0 0 2
- integer_points_bbox (P) → Matrix<Integer>
Enumerate all integer points in the given polytope by searching a bounding box.
Example:> $p = new Polytope(VERTICES=>[[1,13/10,1/2],[1,1/5,6/5],[1,1/10,-3/2],[1,-7/5,1/5]]);
> print integer_points_bbox($p);
1 0 -1
1 -1 0
1 0 0
1 1 0
1 0 1
- minimal_vertex_angle (P) → Float
- normaliz_compute (C) → List
Compute degree one elements, Hilbert basis or Hilbert series of a cone C with libnormaliz Hilbert series and Hilbert h-vector depend on the given grading and will not work unless C is HOMOGENEOUS or a MONOID_GRADING is set
Contained in extensionlibnormaliz
.Parameters
Cone C Options
Bool from_facets supply facets instead of rays to normalizBool degree_one_generators compute the generators of degree one, i.e. lattice points of the polytopeBool hilbert_basis compute Hilbert basis of the cone CBool h_star_vector compute Hilbert h-vector of the cone CBool hilbert_series compute Hilbert series of the monoidBool ehrhart_quasi_polynomial compute Ehrhart quasi polynomial of a polytopeBool facets compute support hyperplanes (=FACETS,LINEAR_SPAN)Bool rays compute extreme rays (=RAYS)Bool dual_algorithm use the dual algorithm by PottierBool skip_long do not try to use long coordinates firstBool verbose libnormaliz debug outputReturns
List (Matrix<Integer> degree one generators, Matrix<Integer> Hilbert basis, Vector<Integer> Hilbert h-vector, RationalFunction Hilbert series, Matrix<Rational> facets, Matrix<Rational> linear_span, Matrix<Rational> rays) (only requested items) - occluding_cone (P, F) → Cone
For a face F of a cone or polytope P, return the polyhedral cone C such that taking the convex hull of P and any point in C destroys the face F
Example:- To find the occluding cone of an edge of the 3-cube, type
> $c=occluding_cone(cube(3), [0,1]);
> print $c->FACETS;
-1 0 -1 0
-1 0 0 -1
- 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 Example:- To get a nice representation of the squares face lattice, do this:
> print_face_lattice(cube(2)->VERTICES_IN_FACETS);
FACE_LATTICE
[ -1 : 4 ]
{{0 1} {0 2} {1 3} {2 3}}
[ -2 : 4 ]
{{0} {1} {2} {3}}
- separable (q, P) → Bool
Checks whether there exists a hyperplane separating a given point q from a polytope/cone P by solving a suitable LP. If true, q is a vertex of the polytope defined by q and the vertices of P. To get the separating hyperplane, use separating_hyperplane. Works without knowing the facets of P!
Parameters
Vector q the vertex (candidate) which is to be separated from PCone P the polytope/cone from which q is to be separatedOptions
Bool strong Test for strong separability. default: trueReturns
Bool 'true' if q is separable from pExample:> $q = cube(2)->VERTICES->row(0);
> print separable(cube(2), $q, strong=>0);
true
- steiner_point (P) → Vector
- violations (P, q) → Set
Check which relations, if any, are violated by a point.
Parameters
Cone P Vector q Options
String section Which section of P to test against qInt violating_criterion has the options: +1 (positive values violate; this is the default), 0 (*non*zero values violate), -1 (negative values violate)Returns
Set Example:- This calculates and prints the violated equations defining a square with the origin as its center and side length 2 with respect to a certain point:
> $p = cube(2);
> $v = new Vector([1,2,2]);
> $S = violations($p,$v);
> print $S;
{1 3}
- visible_facet_indices (P, q) → Set
Return the indices of all facets that are visible from a point q.
Example:- This prints the facets of a square with the origin as its center and side length 2 that are visible from a certain point:
> $p = cube(2);
> $v = new Vector([1,2,2]);
> map { print $p->VERTICES_IN_FACETS->[$_], "\n" } @{visible_facet_indices($p,$v)};
{1 3}
{2 3}
- visible_face_indices (P, q) → Set
Return the indices (in the HASSE_DIAGRAM) of all faces that are visible from a point q.
Example:- This prints the faces of a square with the origin as its center and side length 2 that are visible from a certain point:
> $p = cube(2);
> $v = new Vector([1,2,2]);
> map { print $p->HASSE_DIAGRAM->FACES->[$_], "\n" } @{visible_face_indices($p,$v)};
{}
{1}
{2}
{3}
{1 3}
{2 3}
- zonotope_tiling_lattice (P) → AffineLattice
Calculates a generating set for a tiling lattice for P, i.e., a lattice L such that P + L tiles the affine span of P.
Parameters
Polytope P the zonotopeOptions
Bool lattice_origin_is_vertex true if the origin of the tiling lattice should be a vertex of P; default false, ie, the origin will be the barycenter of PReturns
AffineLattice Example:- This determines a tiling lattice for a parallelogram with the origin as its vertex barycenter and prints it base vectors:
> $M = new Matrix([[1,1,0],[1,1,1]]);
> $p = zonotope($M);
> $A = zonotope_tiling_lattice($p);
> print $A->BASIS;
0 -1 -1
0 0 1
These functions provide tools from linear, integer and dicrete optimization. In particular, linear programs are defined here.
- ball_lifting_lp (c, facet_index, conv_eps) → Polytope
Computes the inequalities and the linear objective for an LP to lift a simplicial d-ball embedded starshaped in Rd.
Contained in extensionlocal
.Parameters
topaz::GeometricSimplicialComplex c Int facet_index index of the facet to be liftedRational conv_eps some epsilon > 0Returns
Polytope - core_point_algo (p, optLPvalue) → List
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).
- core_point_algo_Rote (p, optLPvalue) → List
Version of core_point_algo with improved running time (according to a suggestion by G. Rote). The core_point_algo is an algorithm to solve highly symmetric integer linear programs (ILP). It is required that the group of the ILP induces the alternating or symmetric group on the set of coordinate directions. The linear objective function is the vector (0,1,1,..,1).
- find_transitive_lp_sol (Inequalities) → List
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 regionReturns
List (Vector<Rational> optimal solution, Rational optimal value, Bool feasible, Bool max_bounded)Example:- Consider the LP described by the facets of the 3-cube:
> @sol=find_transitive_lp_sol(cube(3)->FACETS);
> print $_, "\n" for @sol;
1 1 1 1
3
true
true
The optimal solution is [1,1,1,1], its value under c is 3, and the LP is feasible and bounded in direction of c.
- inner_point (points) → Vector
- lp2poly <Scalar> (file, testvec, prefix) → Polytope<Scalar>
Read a linear programming problem given in LP-Format (as used by cplex & Co.) and convert it to a Polytope<Scalar> object.
Type Parameters
Scalar coordinate type of the resulting polytope; default is Rational.Parameters
String file filename of a linear programming problem in LP-FormatVector testvec If present, after reading in each line of the LP it is checked whether testvec fulfills itString prefix If testvec is present, all variables in the LP file are assumed to have the form $prefix$iOptions
Bool nocheck Do not automatically compute FEASIBLE for the polytope (recommended for very large LPs)Returns
Polytope<Scalar> - poly2lp (P, LP, maximize, file)
Convert a polymake description of a polyhedron to LP format (as used by CPLEX and other linear problem solvers) and write it to standard output or to a file. If LP comes with an attachment 'INTEGER_VARIABLES' (of type Array<Bool>), the output will contain an additional section 'GENERAL', allowing for IP computations in CPLEX. If the polytope is not FEASIBLE, the function will throw a runtime error.
Parameters
Polytope P LinearProgram LP default value: P->LPBool maximize produces a maximization problem; default value: 0 (minimize)String file default value: standard output - poly2porta (p, file)
take a rational polytope and write a porta input file (.ieq or .poi)
Parameters
Polytope<Rational> p String file filename for the porta file (.ieq or .poi) or an open IO handleOptions
Bool primal true if points should be written, false if inequalities should be written (default is true) - 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_constraints (C)
Write the FACETS / INEQUALITIES and the LINEAR_SPAN / EQUATIONS (if present) of a polytope P or cone C in a readable way. COORDINATE_LABELS are adopted if present.
Parameters
Cone<Scalar> C the given polytope or coneOptions
Array<String> ineq_labels changes the labels of the inequality rowsArray<String> eq_labels changes the labels of the equation rowsExample:- The following prints the facet inequalities of the square, changing the labels.
> print_constraints(cube(2),ineq_labels=>['zero','one','two','three']);
Facets:
zero: x1 >= -1
one: -x1 >= -1
two: x2 >= -1
three: -x2 >= -1
- 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: randomOptions
Int seed controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.Returns
Vector<Rational> - separating_hyperplane (q, points) → Vector
Computes (the normal vector of) a hyperplane which separates a given point q from points via solving a suitable LP. The scalar product of the normal vector of the separating hyperplane and a point in points is greater or equal than 0 (same behavior as for facets!). If q is not a vertex of P=conv(points,q), the function throws an infeasible exception. Works without knowing the facets of P!
Parameters
Vector q the vertex (candidate) which is to be separated from pointsMatrix points the points from which q is to be separatedReturns
Vector sep_hypExample:- The following stores the result in the List @r and then prints the answer and a description of the hyperplane separating the zeroth vertex of the square from the others.
> $q = cube(2)->VERTICES->row(0);
> $points = cube(2)->VERTICES->minor(sequence(1,3),All);
> print separating_hyperplane($q,$points);
0 1/2 1/2
- separating_hyperplane (p1, p2) → Vector
Computes (the normal vector of) a hyperplane which separates two given polytopes p1 and p2 if possible. Works by solving a linear program, not by facet enumeration.
Parameters
Polytope p1 the first polytope, will be on the positive side of the separating hyperplanePolytope p2 the second polytopeOptions
Bool strong If this is set to true, the resulting hyperplane will be strongly separating, i.e. it wont touch either of the polytopes. If such a plane does not exist, an exception will be thrown. default: trueReturns
Vector a hyperplane separating p1 from p2 - totally_dual_integral (inequalities) → Bool
- vertex_colors (P, LP) → Array<RGB>
Calculate RGB-color-values for each vertex depending on a linear or abstract objective function. Maximal and minimal affine vertices are colored as specified. Far vertices (= rays) orthogonal to the linear function normal vector are white. The colors for other affine vertices are linearly interpolated in the HSV color model.
If the objective function is linear and the corresponding LP problem is unbounded, then the affine vertices that would become optimal after the removal of the rays are painted pale.
Parameters
Polytope P LinearProgram LP Options
RGB min the minimal RGB valueRGB max the maximal RGB valueReturns
Array<RGB> Example:- This calculates a vertex coloring with respect to a linear program. For a better visualization, we also set the vertex thickness to 2.
> $p = cube(3);
> $p->LP(LINEAR_OBJECTIVE=>[0,1,2,3]);
> $v = vertex_colors($p,$p->LP);
> $p->VISUAL(VertexColor=>$v,VertexThickness=>2);
- write_foldable_max_signature_ilp (P, outfile_name)
construct a linear program whose optimal value is an upper bound for the algebraic signature of a triangulation of P. This is the absolute value of the difference of normalized volumes of black minus white simplices (counting only those with odd normalized volume) in a triangulation of P whose dual graph is bipartite. If P has a GROUP, it will be used to construct the linear program.
Examples:- For the 0/1 2-cube without a GROUP, the foldable max signature lp is computed as follows:
> write_foldable_max_signature_ilp(cube(2,0));
MINIMIZE
obj: +1 x1 -1 x2 +1 x3 -1 x4 +1 x5 -1 x6 +1 x7 -1 x8
Subject To
ie0: +1 x1 >= 0
ie1: +1 x2 >= 0
ie2: +1 x3 >= 0
ie3: +1 x4 >= 0
ie4: +1 x5 >= 0
ie5: +1 x6 >= 0
ie6: +1 x7 >= 0
ie7: +1 x8 >= 0
ie8: -1 x1 -1 x2 >= -1
ie9: -1 x3 -1 x4 >= -1
ie10: -1 x5 -1 x6 >= -1
ie11: -1 x7 -1 x8 >= -1
eq0: -1 x4 +1 x5 = 0
eq1: +1 x3 -1 x6 = 0
eq2: -1 x2 +1 x7 = 0
eq3: +1 x1 -1 x8 = 0
eq4: +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 = 2
BOUNDS
x1 free
x2 free
x3 free
x4 free
x5 free
x6 free
x7 free
x8 free
GENERAL
x1
x2
x3
x4
x5
x6
x7
x8
END
There are eight variables, one for each possible black or white maximal interior simplex. The optimal value of this LP is zero, because any triangulation has exactly one black and one white simplex of odd normalized volume. Notice that the objective function becomes empty for cube(2), because in the +1/-1 cube, each simplex has even volume. - For the 0/1 3-cube, we use a GROUP property:
> write_foldable_max_signature_ilp(cube(3,0,group=>1));
MINIMIZE
obj: +1 x1 -1 x2 +1 x3 -1 x4 +1 x5 -1 x6
Subject To
ie0: +1 x1 >= 0
ie1: +1 x2 >= 0
ie2: +1 x3 >= 0
ie3: +1 x4 >= 0
ie4: +1 x5 >= 0
ie5: +1 x6 >= 0
ie6: +1 x7 >= 0
ie7: +1 x8 >= 0
ie8: -1 x1 -1 x2 >= -8
ie9: -1 x3 -1 x4 >= -24
ie10: -1 x5 -1 x6 >= -24
ie11: -1 x7 -1 x8 >= -2
eq0: +2 x3 -2 x4 +2 x5 -2 x6 = 0
eq1: -2 x3 +2 x4 -2 x5 +2 x6 = 0
eq2: -6 x2 +6 x5 +24 x7 = 0
eq3: -6 x1 +6 x6 +24 x8 = 0
eq4: +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +2 x7 +2 x8 = 6
BOUNDS
x1 free
x2 free
x3 free
x4 free
x5 free
x6 free
x7 free
x8 free
GENERAL
x1
x2
x3
x4
x5
x6
x7
x8
END
There are again 8 variables, but now they correspond to the black and white representatives of the four symmetry classes of maximal interior simplices. The optimal value of this linear program is 4, because the most imbalanced triangulation is the one with 5 simplices, in which the volume of the big interior simplex is even and doesn't get counted in the objective function.
- write_simplexity_ilp (P)
construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P.
Parameters
Polytope P Options
String outfile_name . If the string is '-' (as is the default), the linear program is printed to STDOUT.Example:- To print the linear program for the 2-dimensional cube, write
> write_simplexity_ilp(cube(2));
MINIMIZE
obj: +1 x1 +1 x2 +1 x3 +1 x4
Subject To
ie0: +1 x1 >= 0
ie1: +1 x2 >= 0
ie2: +1 x3 >= 0
ie3: +1 x4 >= 0
eq0: +4 x1 +4 x2 +4 x3 +4 x4 = 8
eq1: -1 x2 +1 x3 = 0
eq2: -1 x1 +1 x4 = 0
BOUNDS
x1 free
x2 free
x3 free
x4 free
GENERAL
x1
x2
x3
x4
END
- write_simplexity_ilp_with_angles (P, outfile_name)
construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P, and that takes into account the angle constraint around codimension 2 faces. The first set of variables correspond to possible maximal internal simplices, the second set to the simplices of codimension 2. See the source file polytope/src/symmetrized_codim_2_angle_sums.cc for details.
Example:- To print the linear program for the 2-dimensional cube, write
> write_simplexity_ilp_with_angles(cube(2));
MINIMIZE
obj: +1 x1 +1 x2 +1 x3 +1 x4
Subject To
ie0: +1 x1 >= 0
ie1: +1 x2 >= 0
ie2: +1 x3 >= 0
ie3: +1 x4 >= 0
ie4: +1 x5 >= 0
ie5: +1 x6 >= 0
ie6: +1 x7 >= 0
ie7: +1 x8 >= 0
eq0: -1 x2 +1 x3 = 0
eq1: -1 x1 +1 x4 = 0
eq2: +0.5 x1 +0.25 x2 +0.2500000000000001 x3 -0.5 x5 = 0
eq3: +0.25 x1 +0.5 x3 +0.2500000000000001 x4 -0.5 x6 = 0
eq4: +0.25 x1 +0.5 x2 +0.2500000000000001 x4 -0.5 x7 = 0
eq5: +0.25 x2 +0.2500000000000001 x3 +0.5 x4 -0.5 x8 = 0
eq6: +1 x5 = 1
eq7: +1 x6 = 1
eq8: +1 x7 = 1
eq9: +1 x8 = 1
eq10: +4 x1 +4 x2 +4 x3 +4 x4 = 8
BOUNDS
x1 free
x2 free
x3 free
x4 free
x5 free
x6 free
x7 free
x8 free
GENERAL
x1
x2
x3
x4
x5
x6
x7
x8
END
- write_symmetrized_simplexity_ilp (P, isotypic_components, outfile_name)
construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P. The symmetry group of P is taken into account, in that the variables in the linear program are projections of the indicator variables of the maximal interior simplices to a given direct sum of isotypic components of the symmetry group of P acting on these simplices.
Parameters
Polytope P Set<Int> isotypic_components the set of indices of isotypic components to project to; default [0]String outfile_name . Setting this to '-' (as is the default) prints the LP to stdout.Example:- For the 3-cube, the symmetrized LP for isotypic component 0 reads as follows:
> write_symmetrized_simplexity_ilp(cube(3,group=>1));
MINIMIZE
obj: +1 x1 +1 x2 +1 x3 +1 x4
Subject To
ie0: +1 x1 >= 0
ie1: +1 x2 >= 0
ie2: +1 x3 >= 0
ie3: +1 x4 >= 0
eq0: +8 x1 +8 x2 +8 x3 +16 x4 = 48
eq1: -6 x1 +6 x3 +24 x4 = 0
BOUNDS
x1 free
x2 free
x3 free
x4 free
GENERAL
x1
x2
x3
x4
END
The interpretation is as follows: The variables x1,...,x4 correspond to the representatives of interior simplices:> print cube(3,group=>1)->GROUP->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES;
{0 1 2 4}
{0 1 2 5}
{0 1 2 7}
{0 3 5 6}
The solution (x1,x2,x3,x4) = (4,0,0,1) of the LP says that in a minimal triangulation of the 3-cube, there are 4 simplices in the same symmetry class as {0,1,2,4}, and one in the class of {0,3,5,6}.
Special purpose functions.
- edge_orientable (P)
Checks whether a 2-cubical polytope P is edge-orientable (in the sense of Hetyei), that means that there exits an orientation of the edges such that for each 2-face the opposite edges point in the same direction. It produces the certificates EDGE_ORIENTATION if the polytope is edge-orientable, or MOEBIUS_STRIP_EDGES otherwise. In the latter case, the output can be checked with the client validate_moebius_strip.
Parameters
Polytope P the given 2-cubical polytope - face_pair (P, S) → Pair<Set,Set>
For a given set S of rays compute the smallest face F of a cone P containing them all; see also face.
Parameters
Cone P Set S Returns
Pair<Set,Set> where the first is the set of vertices of F, while the second is the set of facets containing F.Example:- computes the dimension of the face of the 3-cube which is spanned by the vertices 0 and 1
> $c=cube(3);
> print rank($c->VERTICES->minor(face_pair($c,[0,1])->first(),All))-1;
1
- lawrence_matrix (M) → Matrix
- matroid_indices_of_hypersimplex_vertices () → Set<Int>
For a given matroid return the bases as a subset of the vertices of the hypersimplex
- m_sequence (h) → Bool
Test if the given vector is an M-sequence.
Example:- The h-vector of a simplicial or simple polytope is an M-sequence.
> print m_sequence(cyclic(7,23)->H_VECTOR);
true
- pseudopower (l, i) → Integer
- wronski_center_ideal (L, lambda)
Returns a system of polynomials which is necessary to check if degeneration avoids center of projection: compute eliminant e(s); this must not have a zero in (0,1)
Parameters
Matrix<Int> L lattice pointsVector<Int> lambda height function on lattice points - wronski_polynomial (M, lambda, coeff, s)
Returns a Wronski polynomial of a topaz::FOLDABLE triangulation of a lattice polytope
Parameters
Matrix<Int> M points (in homogeneous coordinates); affinely span the spaceVector<Int> lambda height function on lattice pointsArray<Rational> coeff coefficientsRational s additional Parameter in the polynomialOptions
topaz::SimplicialComplex triangulation The triangulation of the pointset corresponding to the lifting function - wronski_system (M, lambda, coeff_array, s)
Returns a Wronski system of a topaz::FOLDABLE triangulation of a lattice polytope
Parameters
Matrix<Int> M points (in homogeneous coordinates); affinely span the spaceVector<Int> lambda height function on lattice pointsArray<Array<Rational>> coeff_array coefficientsRational s additional Parameter in the polynomialOptions
topaz::SimplicialComplex triangulation The triangulation of the pointset corresponding to the lifting function
Various constructions of cones.
- inner_cone (p, F) → Cone
Computes the inner cone of p at a face F (or a vertex v).
Parameters
Cone p Set<Int> F (or Int v) vertex indices which are not contained in the far faceOptions
Bool outer Make it point outside the polytope? Default value is 0 (= point inside)Bool attach Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity)Returns
Cone Examples:- To compute the inner cone at a vertex of the 3-cube, do this:
> $c = inner_cone(cube(3), 1);
> print $c->RAYS;
-1 0 0
0 1 0
0 0 1
- To compute the inner cone along an edge of the 3-cube, and make it point outside the polytope, do this:
> print inner_cone(cube(3), [0,1], outer=>1)->RAYS;
0 0 -1
0 -1 0
- If you want to attach the cone to the polytope, specify the corresponding option:
> print normal_cone(cube(3), [0,1], attach=>1)->RAYS;
1 -1 -1 -1
1 1 -1 -1
0 0 1 0
0 0 0 1
- normal_cone (p, F) → Cone
Computes the normal cone of p at a face F (or vertex v). By default this is the inner normal cone.
Parameters
PointConfiguration p Set<Int> F (or Int v) point indices which are not contained in the far faceOptions
Bool outer Calculate outer normal cone? Default value is 0 (= inner)Bool attach Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity)Returns
Cone Example:- To compute the outer normal cone of a doubled 2-cube, do this:
> $v = cube(2)->VERTICES;
> $p = new PointConfiguration(POINTS=>($v/$v));
> print normal_cone($p, 4, outer=>1)->RAYS;
0 -1
-1 0
- normal_cone (p, F) → Cone
Computes the normal cone of p at a face F (or a vertex v). By default this is the inner normal cone.
Parameters
Cone p Set<Int> F (or Int v) vertex indices which are not contained in the far faceOptions
Bool outer Calculate outer normal cone? Default value is 0 (= inner)Bool attach Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity)Returns
Cone Examples:- To compute the outer normal cone at a vertex of the 3-cube, do this:
> $c = normal_cone(cube(3), 0, outer=>1);
> print $c->RAYS;
-1 0 0
0 -1 0
0 0 -1
- To compute the outer normal cone along an edge of the 3-cube, do this:
> print normal_cone(cube(3), [0,1], outer=>1)->RAYS;
0 -1 0
0 0 -1
- If you want to attach the cone to the polytope, specify the corresponding option:
> print normal_cone(cube(3), [0,1], outer=>1, attach=>1)->RAYS;
1 -1 -1 -1
1 1 -1 -1
0 0 -1 0
0 0 0 -1
- recession_cone (P) → Cone<Scalar>
retuns the recession cone (tail cone, characteristic cone) of a polytope
- subcone (C) → Cone
Make a subcone from a cone.
Constructing a point configuration, either from scratch or from existing objects.
- minkowski_sum (P1, P2) → PointConfiguration
Produces the Minkowski sum of P1 and P2.
Example:> $P1 = new PointConfiguration(POINTS=>simplex(2)->VERTICES);
> $P2 = new PointConfiguration(POINTS=>[[1,1,1],[1,-1,1],[1,1,-1],[1,-1,-1],[1,0,0]]);
> $m = minkowski_sum($P1,$P2);
> print $m->POINTS;
1 1 1
1 -1 1
1 1 -1
1 -1 -1
1 0 0
1 2 1
1 0 1
1 2 -1
1 0 -1
1 1 0
1 1 2
1 -1 2
1 1 0
1 -1 0
1 0 1
- minkowski_sum (lambda, P1, mu, P2) → PointConfiguration
Produces the polytope lambda*P1+mu*P2, where * and + are scalar multiplication and Minkowski addition, respectively.
Example:> $P1 = new PointConfiguration(POINTS=>simplex(2)->VERTICES);
> $P2 = new PointConfiguration(POINTS=>[[1,1,1],[1,-1,1],[1,1,-1],[1,-1,-1],[1,0,0]]);
> $m = minkowski_sum(1,$P1,3,$P2);
> print $m->POINTS;
1 3 3
1 -3 3
1 3 -3
1 -3 -3
1 0 0
1 4 3
1 -2 3
1 4 -3
1 -2 -3
1 1 0
1 3 4
1 -3 4
1 3 -2
1 -3 -2
1 0 1
Polytope constructions which take graphs as input.
- flow_polytope <Scalar> (G, Arc_Bounds, source, sink) → Polytope
Produces the flow polytope of a directed Graph G=(V,E) with a given source and sink. The flow polytope has the following outer description: forall v in V-{source, sink}: sum_{e in E going into v} x_e - sum_{e in E going out of v} x_e = 0
sum_{e in E going into source} x_e - sum_{e in E going out of source} x_e <= 0
sum_{e in E going into sink} x_e - sum_{e in E going out of sink} x_e >= 0
forall e in E: x_e <= given bound on edge e
Type Parameters
Scalar Parameters
Graph<Directed> G EdgeMap<Directed, Scalar> Arc_Bounds Int source Int sink Returns
Polytope - flow_polytope <Scalar> (G, Arc_Bounds, source, sink) → Polytope
Produces the flow polytope of a directed Graph G=(V,E) with a given source and sink. The flow polytope has the following outer description: forall v in V-{source, sink}: sum_{e in E going into v} x_e - sum_{e in E going out of v} x_e = 0
sum_{e in E going into source} x_e - sum_{e in E going out of source} x_e <= 0
sum_{e in E going into sink} x_e - sum_{e in E going out of sink} x_e >= 0
forall e in E: x_e <= given bound on edge e
Type Parameters
Scalar Parameters
Graph<Directed> G Array<Scalar> Arc_Bounds Int source Int sink Returns
Polytope - fractional_cut_polytope (G) → Polytope
- fractional_matching_polytope (G) → Polytope
- tutte_lifting (G) → Polytope
- weighted_digraph_polyhedron (encoding) → polytope::Polytope
Weighted digraph polyhedron of a directed graph with a weight function. The graph and the weight function are combined into a matrix.
Polytope constructions which take other big objects as input.
- billera_lee (H) → Polytope
Produces a simplicial polytope whose H-vector is the given input vector. The G-vector coming from the given vector must be an M-sequence. This is an implementation of the algorithm described in the paper "A Proof of the Sufficiency of McMullen’s Conditions of Simplicial Convex Polytopes" by Louis Billera and Carl Lee, DOI: 10.1016/0097-3165(81)90058-3
Example:> $p = billera_lee([1,5,15,15,5,1]);
> print $p->H_VECTOR;
1 5 15 15 5 1
An important way of constructing polytopes is to modify an already existing polytope.
Actually, these functions don't alter the input polytope (it is forbidden in polymake), but create a new polytope object.
Many functions can at your choice either calculate the vertex or facet coordinates, or constrain themselves on the purely combinatorial description of the resulting polytope.
- bipyramid (P, z, z_prime) → Polytope
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 Scalar z distance between the vertex barycenter and the first apex, default value is 1.Scalar z_prime distance between the vertex barycenter and the second apex, default value is -z.Options
Bool no_coordinates : don't compute the coordinates, purely combinatorial description is produced.Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new vertices with "Apex" and "Apex'".Returns
Polytope Example:- Here's a way to construct the 3-dimensional cross polytope:
> $p = bipyramid(bipyramid(cube(1)));
> print equal_polyhedra($p,cross(3));
true
- 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 vertexPolytope P2 Int v2 the index of the second vertexOptions
Array<Int> permutation Bool no_labels Do not copy VERTEX_LABELS from the original polytopes. default: 0Returns
Polytope Example:- The following gives the smallest EVEN 3-polytope which is not a zonotope.
> $c = cube(3); $bc = blending($c,0,$c,0);
> print $bc->EVEN
true
> print $bc->F_VECTOR
14 21 9
- cayley_embedding (P_0, P_1, t_0, t_1) → Polytope
Create a Cayley embedding of two polytopes (one of them must be pointed). The vertices of the first polytope P_0 get embedded to (t_0,0) and the vertices of the second polytope P_1 to (0,t_1).
Default values are t_0=t_1=1.
- cayley_embedding (A) → Polytope
Create a Cayley embedding of an array (P1,...,Pm) of polytopes. All polytopes must have the same dimension, at least one of them must be pointed, and all must be defined over the same number type. Each vertex v of the i-th polytope is embedded to v|t_i e_i, where t_i is the i-th entry of the optional array t.
Parameters
Array<Polytope> A the input polytopesOptions
Array<Scalar> factors array of scaling factors for the Cayley embedding; defaults to the all-1 vectorBool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0Returns
Polytope - cayley_polytope (P_Array) → Polytope
Construct the cayley polytope of a set of pointed lattice polytopes contained in P_Array which is the convex hull of P1×e1, ..., Pk×ek where e1, ...,ek are the standard unit vectors in Rk. In this representation the last k coordinates always add up to 1. The option proj projects onto the complement of the last coordinate.
Parameters
Array<Polytope> P_Array an array containing the lattice polytopes P1,...,PkOptions
Bool proj Returns
Polytope - cells_from_subdivision (P, cells) → Polytope<Scalar>
Extract the given cells of the subdivision of a polyhedron and create a new polyhedron that has as vertices the vertices of the cells.
Parameters
Polytope<Scalar> P Set<Int> cells Options
Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0Returns
Polytope<Scalar> Example:- First we create a nice subdivision for a small polytope:
> $p = new Polytope(VERTICES=>[[1,0,0],[1,0,1],[1,1,0],[1,1,1],[1,3/2,1/2]]);
> $p->POLYTOPAL_SUBDIVISION(MAXIMAL_CELLS=>[[0,1,3],[1,2,3],[2,3,4]]);
Then we create the polytope that has as vertices the vertices from cell 1 and 2, while keeping their labels.> $c = cells_from_subdivision($p,[1,2]);
> print $c->VERTICES;
1 0 1
1 1 0
1 1 1
1 3/2 1/2
> print $c->VERTEX_LABELS;
1 2 3 4
- 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 no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0Returns
Polytope Example:- First we create a nice subdivision for our favourite 2-polytope, the square:
> $p = cube(2);
> $p->POLYTOPAL_SUBDIVISION(MAXIMAL_CELLS=>[[0,1,3],[1,2,3]]);
Then we extract the [1,2,3]-cell, copying the vertex labels.> $c = cell_from_subdivision($p,1);
> print $c->VERTICES;
1 1 -1
1 -1 1
1 1 1
> print $c->VERTEX_LABELS;
1 2 3
- conv (P_Array) → PropagatedPolytope
Construct a new polyhedron as the convex hull of the polyhedra given in P_Array.
Example:> $p = conv([cube(2,1,0),cube(2,6,5)]);
> print $p->VERTICES;
1 0 0
1 1 0
1 0 1
1 6 5
1 5 6
1 6 6
- dual_linear_program (P, maximize) → Polytope
Produces the dual linear program for a given linear program of the form min {cx | Ax >= b, Bx = d}. Here (A,b) are given by the FACETS (or the INEQAULITIES), and (B,d) are given by the AFFINE_HULL (or by the EQUATIONS) of the polytope P, while the objective function c comes from an LP subobject.
- edge_middle (P) → Polytope
- face (P, S) → Cone
For a given set S of rays compute the smallest face F of a cone P containing them all; see also face_pair.
Parameters
Cone P Set S Options
Bool no_coordinates don't copy the coordinates, produce purely combinatorial description.Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0Returns
Cone Example:- To create a cone from the vertices of the zeroth facet of the 3-cube, type this:
> $p = face(cube(3),[0,1]);
- facet (P, facet) → Cone
Extract the given facet of a polyhedron and write it as a new polyhedron.
Parameters
Cone P Int facet Options
Bool no_coordinates don't copy the coordinates, produce purely combinatorial description.Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0Returns
Cone Example:- To create a cone from the vertices of the zeroth facet of the 3-cube, type this:
> $p = facet(cube(3),0);
- facet_to_infinity (P, i) → Polytope
Make an affine transformation such that the i-th facet is transformed to infinity
Example:- This generates the polytope that is the positive quadrant in 2-space:
> $q = new Polytope(VERTICES=>[[1,-1,-1],[1,0,1],[1,1,0]]);
> $pf = facet_to_infinity($q,2);
> print $pf->VERTICES;
0 -1 -1
0 0 1
1 0 1
- free_sum (P1, P2) → Polytope
Construct a new polyhedron as the free sum of two given bounded ones.
Parameters
Polytope P1 Polytope P2 Options
Bool force_centered if the input polytopes must be centered. Defaults to true.Bool no_coordinates produces a pure combinatorial description. Defaults to false.Returns
Polytope Example:> $p = free_sum(cube(2),cube(2));
> print $p->VERTICES;
1 -1 -1 0 0
1 1 -1 0 0
1 -1 1 0 0
1 1 1 0 0
1 0 0 -1 -1
1 0 0 1 -1
1 0 0 -1 1
1 0 0 1 1
- free_sum_decomposition (P) → Array<Polytope>
Decompose a given polytope into the free sum of smaller ones
- free_sum_decomposition_indices (P) → Array<Set>
Decompose a given polytope into the free sum of smaller ones, and return the vertex indices of the summands
Example:> $p = free_sum(cube(1),cube(1));
> print $p->VERTICES;
1 -1 0
1 1 0
1 0 -1
1 0 1
> print free_sum_decomposition_indices($p);
{0 1}
{2 3}
- gc_closure (P) → Polytope
- integer_hull (P) → Polytope
- intersection (C ...) → Cone
Construct a new polyhedron or cone as the intersection of given polyhedra and/or cones. Works only if all CONE_AMBIENT_DIM values are equal. If the input contains both cones and polytopes, the output will be a polytope.
Example:> $p = intersection(cube(2), cross(2,3/2));
> print $p->VERTICES;
1 -1/2 1
1 -1 1/2
1 1/2 1
1 1 1/2
1 1/2 -1
1 1 -1/2
1 -1/2 -1
1 -1 -1/2
- join_polytopes (P1, P2) → Polytope
Construct a new polyhedron as the join of two given bounded ones.
Parameters
Polytope P1 Polytope P2 Options
Bool no_coordinates produces a pure combinatorial description.Bool group Compute the canonical group induced by the groups on P1 and P2 Throws an exception if the GROUPs of the input polytopes are not provided. default 0Returns
Polytope Example:- To join two squares, use this:
> $p = join_polytopes(cube(2),cube(2));
> print $p->VERTICES;
1 -1 -1 -1 0 0
1 1 -1 -1 0 0
1 -1 1 -1 0 0
1 1 1 -1 0 0
1 0 0 1 -1 -1
1 0 0 1 1 -1
1 0 0 1 -1 1
1 0 0 1 1 1
- 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 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 -zOptions
Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new vertices with "Apex" and "Apex'".Returns
Polytope Example:- To create the bipyramid over a square and keep the vertex labels, do this:
> $p = lattice_bipyramid(cube(2),new Vector(1,0,0));
> print $p->VERTICES;
1 -1 -1 0
1 1 -1 0
1 -1 1 0
1 1 1 0
1 0 0 1
1 0 0 -1
> print $p->VERTEX_LABELS;
0 1 2 3 Apex Apex'
- 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 no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new top vertex with "Apex".Returns
Polytope Example:- To create the pyramid of height 5 over a square and keep the vertex labels, do this:
> $p = lattice_pyramid(cube(2),5,new Vector(1,0,0));
> print $p->VERTICES;
1 -1 -1 0
1 1 -1 0
1 -1 1 0
1 1 1 0
1 0 0 5
> print $p->VERTEX_LABELS;
0 1 2 3 Apex
- make_totally_dual_integral (P) → 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 no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0Returns
Polytope - minkowski_sum (P1, P2) → Polytope
Produces the Minkowski sum of P1 and P2.
Example:- The following stores the minkowski sum of a square and a triangle in the variable $p and then prints its vertices.
> $p = minkowski_sum(cube(2),simplex(2));
> print $p->VERTICES;
1 -1 -1
1 2 -1
1 -1 2
1 2 1
1 1 2
- minkowski_sum (lambda, P1, mu, P2) → Polytope
Produces the polytope lambda*P1+mu*P2, where * and + are scalar multiplication and Minkowski addition, respectively.
Example:- The following stores the minkowski sum of a scaled square and a triangle in the variable $p and then prints its vertices.
> $p = minkowski_sum(2,cube(2),1,simplex(2));
> print $p->VERTICES;
1 -2 -2
1 3 -2
1 -2 3
1 3 2
1 2 3
- minkowski_sum_fukuda (summands) → Polytope
Computes the (VERTICES of the) Minkowski sum of a list of polytopes using the algorithm by Fukuda described in
Komei Fukuda, From the zonotope construction to the Minkowski addition of convex polytopes, J. Symbolic Comput., 38(4):1261-1272, 2004.Example:> $p = minkowski_sum_fukuda([cube(2),simplex(2),cross(2)]);
> print $p->VERTICES;
1 3 -1
1 3 1
1 -1 -2
1 1 3
1 -1 3
1 2 -2
1 -2 2
1 -2 -1
- mixed_integer_hull (P, int_coords) → Polytope
Produces the mixed integer hull of a polyhedron
- pointed_part (P) → Polytope
- prism (P, z1, z2) → Polytope
Make a prism over a pointed polyhedron. The prism is the product of the input polytope P and the interval [z1, z2].
Parameters
Polytope P the input polytopeScalar z1 the left endpoint of the interval; default value: -1Scalar z2 the right endpoint of the interval; default value: -z1Options
Bool group Compute the canonical group induced by the group on P with an extra generator swapping the upper and lower copy. throws an exception if GROUP of P is not provided. default 0Bool no_coordinates only combinatorial information is handledBool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 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 Example:- The following saves the prism over the square and the interval [-2,2] to the variable $p, and then prints a nice representation of its vertices.
> $p = prism(cube(2),-2);
> print rows_labeled($p->VERTICES,$p->VERTEX_LABELS);
0:1 -1 -1 -2
1:1 1 -1 -2
2:1 -1 1 -2
3:1 1 1 -2
0':1 -1 -1 2
1':1 1 -1 2
2':1 -1 1 2
3':1 1 1 2
- product (P1, P2) → Polytope
Construct a new polytope as the product of two given polytopes P1 and P2. As little additional properties of the input polytopes as possible are computed. You can control this behaviour using the option flags.
Parameters
Polytope P1 Polytope P2 Options
Bool no_coordinates only combinatorial information is handledBool no_vertices do not compute verticesBool no_facets do not compute facetsBool no_labels Do not copy VERTEX_LABELS from the original polytopes, if present. the label of a new vertex corresponding to v1 ⊕ v2 will have the form LABEL_1*LABEL_2. default: 0Bool group Compute the canonical group of the product, as induced by the groups on FACETS of VERTICES of P1 and P2. If neither FACETS_ACTION nor VERTICES_ACTION of the GROUPs of the input polytopes are provided, an exception is thrown. default 0Returns
Polytope Example:- The following builds the product of a square and an interval, without computing vertices of neither the input nor the output polytopes.
> $p = product(cube(2),cube(1), no_vertices=>1);
- projection (P, indices) → Cone
Orthogonally project a pointed polyhedron to a coordinate subspace.
The subspace the polyhedron P is projected on is given by indices in the set indices. The option revert inverts the coordinate list. The client scans for all coordinate sections and produces proper output from each. If a description in terms of inequalities is found, the client performs Fourier-Motzkin elimination unless the nofm option is set. Setting the nofm option is useful if the corank of the projection is large; in this case the number of inequalities produced grows quickly.
Parameters
Cone P Array<Int> indices Options
Bool revert inverts the coordinate listBool nofm suppresses Fourier-Motzkin eliminationReturns
Cone Example:- project the 3-cube along the first coordinate, i.e. to the subspace spanned by the second and third coordinate:
> $p = projection(cube(3),[1],revert=>1);
> print $p->VERTICES;
1 1 -1
1 1 1
1 -1 1
1 -1 -1
- projection_preimage (P_Array) → Cone
Construct a new polyhedron that projects to a given array of polyhedra. If the n polyhedra are d_1, d_2, ..., d_n-dimensional and all have m vertices, the resulting polyhedron is (d_1+...+d_n)-dimensional, has m vertices, and the projection to the i-th d_i coordinates gives the i-th input polyhedron.
Example:> $p = projection_preimage(cube(2),cube(2));
> print $p->VERTICES;
1 -1 -1 -1 -1
1 1 -1 1 -1
1 -1 1 -1 1
1 1 1 1 1
- project_full (P) → Cone
Orthogonally project a polyhedron to a coordinate subspace such that redundant columns are omitted, i.e., the projection becomes full-dimensional without changing the combinatorial type. The client scans for all coordinate sections and produces proper output from each. If a description in terms of inequalities is found, the client performs Fourier-Motzkin elimination unless the nofm option is set. Setting the nofm option is useful if the corank of the projection is large; in this case the number of inequalities produced grows quickly.
Parameters
Cone P Options
Bool nofm suppresses Fourier-Motzkin eliminationBool no_labels Do not copy VERTEX_LABELS to the projection. default: 0Returns
Cone - pyramid (P, z) → Polytope
Make a pyramid over a polyhedron. The pyramid is the convex hull of the input polyhedron P and a point v outside the affine span of P. For bounded polyhedra, the projection of v to the affine span of P coincides with the vertex barycenter of P.
Parameters
Polytope P Scalar z is the distance between the vertex barycenter and v, default value is 1.Options
Bool group compute the group induced by the GROUP of P and leaving the apex fixed. throws an exception if GROUP of P is not provided. default 0Bool no_coordinates don't compute new coordinates, produce purely combinatorial description.Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new top vertex with "Apex".Returns
Polytope Example:- The following saves the pyramid of height 2 over the square to the variable $p. The vertices are relabeled.
> $p = pyramid(cube(2),2);
To print the vertices and vertex labels of the newly generated pyramid, do this:> print $p->VERTICES;
1 -1 -1 0
1 1 -1 0
1 -1 1 0
1 1 1 0
1 0 0 2
> print $p->VERTEX_LABELS;
0 1 2 3 Apex
- 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.
- 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.
- spherize (P) → PolytopeExample:
- The following scales the 2-dimensional cross polytope by 23 and then projects it back onto the unit circle.
> $p = scale(cross(2),23);
> $s = spherize($p);
> print $s->VERTICES;
1 1 0
1 -1 0
1 0 1
1 0 -1
- 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/2Bool no_coordinates produces a pure combinatorial description (in contrast to lift)Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 New vertices get labels 'f(FACET_LABEL)' in the simplicial case, and 'f(FACET_LABEL)-NEIGHBOR_VERTEX_LABEL' in the cubical case.Returns
Polytope Example:- To generate a cubical polytope by stacking all facets of the 3-cube to height 1/4, do this:
> $p = stack(cube(3),All,lift=>1/4);
- 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.
- 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.
- 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.
Example:- The following creates the tensor product polytope of two squares and then prints its vertices.
> $p = tensor(cube(2),cube(2));
> print $p->VERTICES;
1 1 1 1 1
1 -1 1 -1 1
1 1 -1 1 -1
1 -1 1 1 -1
1 1 1 -1 -1
1 1 -1 -1 1
1 -1 -1 1 1
1 -1 -1 -1 -1
- 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 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
Scalar cutoff controls the exact location of the cutting hyperplane(s); rational number between 0 and 1; default value: 1/2Bool no_coordinates produces a pure combinatorial description (in contrast to cutoff)Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 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 Example:- To truncate the second vertex of the square at 1/4, try this:
> $p = truncation(cube(2),2,cutoff=>1/4);
> print $p->VERTICES;
1 -1 -1
1 1 -1
1 1 1
1 -1 1/2
1 -1/2 1
- unirand (P, n) → Polytope
Produce a polytope with n random points that are uniformly distributed within the given polytope P. P must be bounded and full-dimensional.
Parameters
Polytope P Int n the number of random pointsOptions
Bool boundary forces the points to lie on the boundary of the given polytopeInt seed controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.Returns
Polytope Examples:- This produces a polytope as the convex hull of 5 random points in the square with the origin as its center and side length 2:
> $p = unirand(cube(2),5);
- This produces a polytope as the convex hull of 5 random points on the boundary of the square with the origin as its center and side length 2:
> $p = unirand(cube(2),5,boundary=>1);
- 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 vertexOptions
Scalar 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 no_coordinates skip the coordinates computation, producing a pure combinatorial description.Bool no_labels Do not copy VERTEX_LABELS from the original polytope. default: 0 by default, the labels are produced from the corresponding neighbor vertices of the original polytope.Returns
Polytope Example:- This produces a vertex figure of one vertex of a 3-dimensional cube with the origin as its center and side length 2. The result is a 2-simplex.
> $p = vertex_figure(cube(3),5);
> print $p->VERTICES;
1 1 -1 0
1 0 -1 1
1 1 0 1
- 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 , 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 no_coordinates don't compute coordinates, pure combinatorial description is produced.Bool no_labels Do not copy VERTEX_LABELS from the original polytopes. default: 0 By default, the vertices get labelled as follows: 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 Example:- This produces the wedge from a square (over the facet 0), which yields a prism over a triangle:
> $p = wedge(cube(2),0);
> print $p->VERTICES;
1 -1 -1 0
1 1 -1 0
1 -1 1 0
1 1 1 0
1 1 -1 2
1 1 1 2
With these clients you can create polytopes belonging to various parameterized families which occur frequently in polytope theory, as well as several kinds of random polytopes. Regular polytopes and their friends are listed separately.
- 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.
- 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 biologyby L. Pachter and B. Sturmfels (eds.), Cambridge, 2005. - binary_markov_graph (observation)
Parameters
String observation encoded as a string of "0" and "1". - birkhoff (n, even) → Polytope
Constructs the Birkhoff polytope of dimension n2. It is the polytope of nxn stochastic matrices (encoded as n2 row vectors), thus matrices with non-negative entries whose row and column entries sum up to one. Its vertices are the permutation matrices.
- cyclic (d, n) → Polytope<Rational>
Produce a d-dimensional cyclic polytope with n points. Prototypical example of a neighborly polytope. Combinatorics completely known due to Gale's evenness criterion. Coordinates are chosen on the (spherical) moment curve at integer steps from start, or 0 if unspecified. If spherical is true the vertices lie on the sphere with center (1/2,0,...,0) and radius 1/2. In this case (the necessarily positive) parameter start defaults to 1.
Parameters
Int d the dimensionInt n the number of pointsOptions
Int start defaults to 0 (or to 1 if spherical)Bool spherical defaults to falseReturns
Polytope<Rational> Example:- To create the 2-dimensional cyclic polytope with 6 points on the sphere, starting at 3:
> $p = cyclic(2,6,start=>3,spherical=>1);
> print $p->VERTICES;
1 1/10 3/10
1 1/17 4/17
1 1/26 5/26
1 1/37 6/37
1 1/50 7/50
1 1/65 8/65
- 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. For cyclic polytopes from other curves, see polytope::cyclic.
- delpezzo (d, scale) → Polytope<Scalar>
Produce a d-dimensional del-Pezzo polytope, which is the convex hull of the cross polytope together with the all-ones and minus all-ones vector.
All coordinates are +/- scale or 0.
Parameters
Int d the dimensionScalar scale the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.Returns
Polytope<Scalar> - dwarfed_cube (d) → Polytope
- dwarfed_product_polygons (d, s) → Polytope
- explicit_zonotope (zones) → Polytope
Produce the POINTS of a zonotope as the iterated Minkowski sum of all intervals [-x,x], where x ranges over the rows of the input matrix zones.
Parameters
Matrix zones the input vectorsOptions
Bool rows_are_points the rows of the input matrix represent affine points(true, default) or linear vectors(false)Returns
Polytope Example:> $M = new Matrix([1,1],[1,-1]);
> $p = explicit_zonotope($M,rows_are_points=>0);
> print $p->VERTICES;
1 2 0
1 0 -2
1 0 2
1 -2 0
- fano_simplex (d) → Polytope
- fractional_knapsack (b) → Polytope
Produce a knapsack polytope defined by one linear inequality (and non-negativity constraints).
- 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.
- goldfarb_sit (d, eps, delta) → Polytope
Produces a d-dimensional variation of the Klee-Minty cube if eps<1/2 and delta<=1/2. This Klee-Minty cube is scaled in direction x_(d-i) by (eps*delta)^i. This cube is a combinatorial cube and yields a bad example for the Simplex Algorithm using the 'steepest edge' Pivoting Strategy. Here we use a scaled description of the construction of Goldfarb and Sit.
- 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 1sInt d ambient dimensionOptions
Bool group Bool no_vertices do not compute verticesBool no_facets do not compute facetsBool no_vif do not compute vertices in facetsReturns
Polytope Example:- This creates the hypersimplex in dimension 4 with vertices with exactly two 1-entries and computes its symmetry group:
> $h = hypersimplex(2,4,group=>1);
- hypertruncated_cube <Scalar> (d, k, lambda) → Polytope<Scalar>
Produce a d-dimensional hypertruncated cube. With symmetric linear objective function (0,1,1,...,1).
Type Parameters
Scalar Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.Parameters
Int d the dimensionScalar k cutoff parameterScalar lambda scaling of extra vertexReturns
Polytope<Scalar> - klee_minty_cube (d, e) → 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-92Example:- To produce a (not exactly) regular pentagon, type this:
> $p = k_cyclic(5,[1]);
- lecture_hall_simplex (d) → Polytope
- long_and_winding (r) → Polytope<PuiseuxFraction<Max, Rational, Rational> >
Produce polytope in dimension 2r with 3r+2 facets such that the total curvature of the central path is at least Omega(2^r). This establishes a counter-example to a continuous analog of the Hirsch conjecture by Deza, Terlaky and Zinchenko, Adv. Mech. Math. 17 (2009). The same construction (written in a slightly different form) and its analysis can be found in Allamigeon, Benchimol, Gaubert and Joswig, arXiv:1405.4161 See also perturbed_long_and_winding.
Parameters
Int r defining parameterOptions
Rational eval_ratio parameter for evaluating the puiseux rational functionsInt eval_exp to evaluate at eval_ratio^eval_exp, default: 1Float eval_float parameter for evaluating the puiseux rational functionsReturns
Polytope<PuiseuxFraction<Max, Rational, Rational> > Examples:- This yields a 4-polytope over the field of Puiseux fractions.
> $p = long_and_winding(2);
- This yields a rational 4-polytope with the same combinatorics.
> $p = long_and_winding(2,eval_ratio=>2);
- max_GC_rank (d) → 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. - 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). - newton (p) → Polytope<Rational>
Produce the Newton polytope of a polynomial p.
Example:- Create the newton polytope of 1+x^2+y like so:
> local_var_names<Polynomial>(qw(x y)); $p=new Polynomial('1+x^2+y');
> $n = newton($p);
> print $n->VERTICES;
1 0 0
1 0 1
1 2 0
- n_gon (n, r, alpha_0) → 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 verticesRational r the radius (defaults to 1)Rational alpha_0 the initial angle divided by pi (defaults to 0)Options
Bool group Returns
Polytope Example:- To store the regular pentagon in the variable $p and calculate its symmetry group, do this:
> $p = n_gon(5,group=>1);
> print $p->GROUP->RAYS_ACTION->GENERATORS;
0 4 3 2 1
1 2 3 4 0
- perles_irrational_8_polytope () → Polytope
- permutahedron (d) → Polytope
Produce a d-dimensional permutahedron. The vertices correspond to the elements of the symmetric group of degree d+1.
Example:- To create the 3-permutahedron and also compute its symmetry group, do this:
> $p = permutahedron(3,group=>1);
> print $p->GROUP->COORDINATE_ACTION->GENERATORS;
1 0 2 3
3 0 1 2
- perturbed_long_and_winding (r) → Polytope<PuiseuxFraction<Max, Rational, Rational> >
Produce polytope in dimension 2r with 3r+2 facets such that the total curvature of the central path is at least Omega(2^r). This is a perturbed version of long_and_winding, which yields simple polytopes.
Parameters
Int r defining parameterOptions
Rational eval_ratio parameter for evaluating the puiseux rational functionsInt eval_exp to evaluate at eval_ratio^eval_exp, default: 1Float eval_float parameter for evaluating the puiseux rational functionsReturns
Polytope<PuiseuxFraction<Max, Rational, Rational> > Example:- This yields a simple 4-polytope over the field of Puiseux fractions.
> $p = perturbed_long_and_winding(2);
- 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 - pseudo_delpezzo (d, scale) → Polytope<Scalar>
Produce a d-dimensional del-Pezzo polytope, which is the convex hull of the cross polytope together with the all-ones vector.
All coordinates are +/- scale or 0.
Parameters
Int d the dimensionScalar scale the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.Returns
Polytope<Scalar> - 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.
- rand_cyclic (d, n) → Polytope
Computes a random instance of a cyclic polytope of dimension d on n vertices by randomly generating a Gale diagram whose cocircuits have alternating signs.
- rand_metric <Scalar> (n) → Matrix
- rand_metric_int <Scalar> (n) → Matrix
- rand_sphere <Num> (d, n) → Polytope<Rational>
Produce a rational d-dimensional polytope with n random vertices approximately uniformly distributed on the unit sphere.
Type Parameters
Num can be AccurateFloat (the default) or Rational With AccurateFloat the distribution should be closer to uniform, but the vertices will not exactly be on the sphere. With Rational the vertices are guaranteed to be on the unit sphere, at the expense of both uniformity and log-height of points.Parameters
Int d the dimension of sphereInt n the number of random verticesOptions
Int seed controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.Int precision Number of bits for MPFR sphere approximationReturns
Polytope<Rational> - 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. - signed_permutahedron (d) → 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.
Examples:- To print the vertices (in homogeneous coordinates) of the standard 2-simplex, i.e. a right-angled isoceles triangle, type this:
> print simplex(2)->VERTICES;
(3) (0 1)
1 1 0
1 0 1
The first row vector is sparse and encodes the origin. - To create a 3-simplex and also calculate its symmetry group, type this:
> simplex(3, group=>1);
- stable_set (G) → Polytope
- transportation (r, c) → Polytope
- upper_bound_theorem (d, n) → PolytopeExample:
- This produces the combinatorial data as mentioned above for 5 points in dimension 3 and prints the h-vector:
> $p = upper_bound_theorem(3,5);
> print $p->H_VECTOR;
1 2 2 1
- zonotope (M) → Polytope<Scalar>
Create a zonotope from a matrix whose rows are input points or vectors.
This method merely defines a Polytope object with the property ZONOTOPE_INPUT_POINTS.
Parameters
Matrix<Scalar> M input points or vectorsOptions
Bool rows_are_points true if M are points instead of vectors; default trueBool centered true if output should be centered; default trueReturns
Polytope<Scalar> the zonotope generated by the input points or vectorsExamples:- The following produces a parallelogram with the origin as its vertex barycenter:
> $M = new Matrix([[1,1,0],[1,1,1]]);
> $p = zonotope($M);
> print $p->VERTICES;
1 0 -1/2
1 0 1/2
1 -1 -1/2
1 1 1/2
- The following produces a parallelogram with the origin being a vertex (not centered case):
> $M = new Matrix([[1,1,0],[1,1,1]]);
> $p = zonotope($M,centered=>0);
> print $p->VERTICES;
1 1 0
1 0 0
1 1 1
1 2 1
- zonotope_vertices_fukuda (M) → Matrix
Create the vertices of a zonotope from a matrix whose rows are input points or vectors.
Example:- The following stores the vertices of a parallelogram with the origin as its vertex barycenter and prints them:
> $M = new Matrix([[1,1,0],[1,1,1]]);
> print zonotope_vertices_fukuda($M);
1 0 -1/2
1 0 1/2
1 -1 -1/2
1 1 1/2
A way of constructing vector configurations is to modify an already existing vector configuration.
- free_sum (P1, P2) → VectorConfiguration
Construct the free sum of two vector configurations.
Parameters
VectorConfiguration P1 VectorConfiguration P2 Options
Bool force_centered if the input polytopes must be centered. Defaults to true.Bool no_coordinates produces a pure combinatorial description. Defaults to false.Returns
VectorConfiguration - projection <Scalar> (P, indices) → VectorConfiguration
Orthogonally project a vector configuration to a coordinate subspace.
The subspace the VectorConfiguration P is projected on is given by indices in the set indices. The option revert inverts the coordinate list.
Type Parameters
Scalar coordinate typeParameters
VectorConfiguration P Array<Int> indices Options
Bool revert inverts the coordinate listReturns
VectorConfiguration - projection_preimage <Scalar> (P_Array) → VectorConfiguration
Construct a new vector configuration that projects to a given array of vector configurations If the n vector configurations are d_1, d_2, ..., d_n-dimensional and all have m vectors, the resulting vector configuration is (d_1+...+d_n)-dimensional, has m vectors, and the projection to the i-th d_i coordinates gives the i-th input vector configuration.
Type Parameters
Scalar coordinate typeParameters
Array<VectorConfiguration> P_Array Returns
VectorConfiguration - project_full <Scalar> (P) → VectorConfiguration
Orthogonally project a vector configuration to a coordinate subspace such that redundant columns are omitted, i.e., the projection becomes full-dimensional without changing the combinatorial type.
Type Parameters
Scalar coordinate typeParameters
VectorConfiguration P Options
Bool no_labels Do not copy VERTEX_LABELS to the projection. default: 0Returns
VectorConfiguration - project_out <Scalar> (V, B) → VectorConfiguration
Project a vector configuration V along the subspace with the given basis B. The result is still expressed in the original ambient basis. If V is a PointConfiguration and the first column of B is zero, the result is a PointConfiguration, else a VectorConfiguration.
Type Parameters
Scalar coordinate typeParameters
VectorConfiguration V Matrix B a matrix whose rows contain the basis of the space to be projected outReturns
VectorConfiguration - project_out <Scalar> (C, B) → Cone
Project a Cone C along the subspace with the given basis B The result is still expressed in the original ambient basis. If V is a Polytope and the first column of B is zero, the result is a Polytope, else a Cone.
- project_to <Scalar> (V, B) → VectorConfiguration
Project a vector configuration V to the subspace with a given basis B and express the result in that basis. A boolean flag make_affine (by default undef) determines whether the resulting coordinates acquire an extra leading '1'. The return type is a VectorConfiguration, unless (i) P is a PointConfiguration, (ii) the first column of B is zero, (iii) make_affine is not 0, in which case it is a PointConfiguration. The return type depends on the input: (1) If V is a VectorConfiguration, the result is also a VectorConfiguration. (2a) If V is a PointConfiguration and all rows in B start with a 0, the result is a PointConfiguration. If, furthermore, make_affine is undef, it is set to 1. (2b) If V is a PointConfiguration and some row of B has a non-zero first entry, the result is a VectorConfiguration. The reasoning here is that B having a zero first column or not influences the hyperplane at infinity.
Type Parameters
Scalar coordinate typeParameters
VectorConfiguration V Matrix B a matrix whose rows contain the basis of the image spaceOptions
Bool make_affine . If undef (default), apply the above reasoning. If 1 (0), unconditionally (don't) add leading 1's.Returns
VectorConfiguration or PointConfiguration - project_to <Scalar> (C, B) → Cone
Project a Polytope or Cone to the subspace with a given basis, and express the result in that basis A boolean flag make_affine (by default undef) determines whether the resulting coordinates acquire an extra leading '1'. The return type is a Cone, unless (i) P is a Polytope, (ii) the first column of B is zero, (iii) make_affine is not 0, in which case it is a Polytope. If make_affine is undef and (ii) is true, make_affine is set to 1. The reasoning here is that B having a zero first column or not influences the hyperplane at infinity.
Functions producing big objects which are not contained in application polytope.
- coxeter_group (type) → group::Group
Produces the Coxeter group of type type. The Dynkin diagrams of the different types can be found in the description of the clients simple_roots_type_*.
- crosscut_complex (p) → topaz::SimplicialComplex
Produce the crosscut complex of the boundary of a polytope.
Parameters
Polytope p Options
Bool geometric_realization create a topaz::GeometricSimplicialComplex; default is trueReturns
topaz::SimplicialComplex
This includes the Platonic solids and their generalizations into two directions. In dimension 3 there are the Archimedean, Catalan and Johnson solids. In higher dimensions there are the simplices, the cubes, the cross polytopes and three other regular 4-polytopes.
- archimedean_solid (s) → Polytope
Create Archimedean solid of the given name. Some polytopes are realized with floating point numbers and thus not exact; Vertex-facet-incidences are correct in all cases.
Parameters
String s the name of the desired Archimedean solidPossible values:- 'truncated_tetrahedron'
- Truncated tetrahedron. Regular polytope with four triangular and four hexagonal facets.
- 'cuboctahedron'
- Cuboctahedron. Regular polytope with eight triangular and six square facets.
- 'truncated_cube'
- Truncated cube. Regular polytope with eight triangular and six octagonal facets.
- 'truncated_octahedron'
- Truncated Octahedron. Regular polytope with six square and eight hexagonal facets.
- 'rhombicuboctahedron'
- Rhombicuboctahedron. Regular polytope with eight triangular and 18 square facets.
- 'truncated_cuboctahedron'
- Truncated Cuboctahedron. Regular polytope with 12 square, eight hexagonal and six octagonal facets.
- 'snub_cube'
- Snub Cube. Regular polytope with 32 triangular and six square facets. The vertices are realized as floating point numbers. This is a chiral polytope.
- 'icosidodecahedron'
- Icosidodecahedon. Regular polytope with 20 triangular and 12 pentagonal facets.
- 'truncated_dodecahedron'
- Truncated Dodecahedron. Regular polytope with 20 triangular and 12 decagonal facets.
- 'truncated_icosahedron'
- Truncated Icosahedron. Regular polytope with 12 pentagonal and 20 hexagonal facets.
- 'rhombicosidodecahedron'
- Rhombicosidodecahedron. Regular polytope with 20 triangular, 30 square and 12 pentagonal facets.
- 'truncated_icosidodecahedron'
- Truncated Icosidodecahedron. Regular polytope with 30 square, 20 hexagonal and 12 decagonal facets.
- 'snub_dodecahedron'
- Snub Dodecahedron. Regular polytope with 80 triangular and 12 pentagonal facets. The vertices are realized as floating point numbers. This is a chiral polytope.
Returns
Polytope Example:- To show the mirror image of the snub cube use:
> scale(archimedean_solid('snub_cube'),-1)->VISUAL;
- catalan_solid (s) → Polytope
Create Catalan solid of the given name. Some polytopes are realized with floating point numbers and thus not exact; Vertex-facet-incidences are correct in all cases.
Parameters
String s the name of the desired Catalan solidPossible values:- 'triakis_tetrahedron'
- Triakis Tetrahedron. Dual polytope to the Truncated Tetrahedron, made of 12 isosceles triangular facets.
- 'triakis_octahedron'
- Triakis Octahedron. Dual polytope to the Truncated Cube, made of 24 isosceles triangular facets.
- 'rhombic_dodecahedron'
- Rhombic dodecahedron. Dual polytope to the cuboctahedron, made of 12 rhombic facets.
- 'tetrakis_hexahedron'
- Tetrakis hexahedron. Dual polytope to the truncated octahedron, made of 24 isosceles triangluar facets.
- 'disdyakis_dodecahedron'
- Disdyakis dodecahedron. Dual polytope to the truncated cuboctahedron, made of 48 scalene triangular facets.
- 'pentagonal_icositetrahedron'
- Pentagonal Icositetrahedron. Dual polytope to the snub cube, made of 24 irregular pentagonal facets. The vertices are realized as floating point numbers.
- 'pentagonal_hexecontahedron'
- Pentagonal Hexecontahedron. Dual polytope to the snub dodecahedron, made of 60 irregular pentagonal facets. The vertices are realized as floating point numbers.
- 'rhombic_triacontahedron'
- Rhombic triacontahedron. Dual polytope to the icosidodecahedron, made of 30 rhombic facets.
- 'triakis_icosahedron'
- Triakis icosahedron. Dual polytope to the icosidodecahedron, made of 30 rhombic facets.
- 'deltoidal_icositetrahedron'
- Deltoidal Icositetrahedron. Dual polytope to the rhombicubaoctahedron, made of 24 kite facets.
- 'pentakis_dodecahedron'
- Pentakis dodecahedron. Dual polytope to the truncated icosahedron, made of 60 isosceles triangular facets.
- 'deltoidal_hexecontahedron'
- Deltoidal hexecontahedron. Dual polytope to the rhombicosidodecahedron, made of 60 kite facets.
- 'disdyakis_triacontahedron'
- Disdyakis triacontahedron. Dual polytope to the truncated icosidodecahedron, made of 120 scalene triangular facets.
Returns
Polytope - cross <Scalar> (d, scale) → Polytope<Scalar>
Produce a d-dimensional cross polytope. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.
All coordinates are +/- scale or 0.
Type Parameters
Scalar Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.Parameters
Int d the dimensionScalar scale the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.Options
Bool group add a symmetry group description to the resulting polytopeBool character_table add the character table to the symmetry group description, if 0<d<7; default 1Returns
Polytope<Scalar> Example:- To create the 3-dimensional cross polytope, type
> $p = cross(3);
Check out it's vertices and volume:> print $p->VERTICES;
1 1 0 0
1 -1 0 0
1 0 1 0
1 0 -1 0
1 0 0 1
1 0 0 -1
> print cross(3)->VOLUME;
4/3
If you rather had a bigger one, type> $p_scaled = cross(3,2);
> print $p_scaled->VOLUME;
32/3
To also calculate the symmetry group, do this:> $p = cross(3,group=>1);
You can then print the generators of this group like this:> print $p->GROUP->RAYS_ACTION->GENERATORS;
1 0 2 3 4 5
2 3 0 1 4 5
0 1 4 5 2 3
- cube <Scalar> (d, x_up, x_low) → Polytope<Scalar>
Produce a d-dimensional cube. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.
The bounding hyperplanes are xi <= x_up and xi >= x_low.
Type Parameters
Scalar Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.Parameters
Int d the dimensionScalar x_up upper bound in each dimensionScalar x_low lower bound in each dimensionOptions
Bool group add a symmetry group description to the resulting polytopeBool character_table add the character table to the symmetry group description, if 0<d<7; default 1Returns
Polytope<Scalar> Examples:- This yields a +/-1 cube of dimension 3 and stores it in the variable $c.
> $c = cube(3);
- This stores a standard unit cube of dimension 3 in the variable $c.
> $c = cube(3,0);
- This prints the area of a square with side length 4 translated to have its vertex barycenter at [5,5]:
> print cube(2,7,3)->VOLUME;
16
- cuboctahedron () → Polytope
- dodecahedron () → Polytope
- icosahedron () → Polytope
- icosidodecahedron () → Polytope
- johnson_solid (n) → Polytope
Create Johnson solid number n, where 1 <= n <= 92. A Johnson solid is a 3-polytope all of whose facets are regular polygons. Some are realized with floating point numbers and thus not exact; yet VERTICES_IN_FACETS is correct in all cases.
- johnson_solid (s) → Polytope
Create Johnson solid with the given name. A Johnson solid is a 3-polytope all of whose facets are regular polygons. Some are realized with floating point numbers and thus not exact; yet VERTICES_IN_FACETS is correct in all cases.
Parameters
String s the name of the desired Johnson polytopePossible values:- 'square_pyramid'
- Square pyramid with regular facets. Johnson solid J1.
- 'pentagonal_pyramid'
- Pentagonal pyramid with regular facets. Johnson solid J2.
- 'triangular_cupola'
- Triangular cupola with regular facets. Johnson solid J3.
- 'square_cupola'
- Square cupola with regular facets. Johnson solid J4.
- 'pentagonal_cupola'
- Pentagonal cupola with regular facets. Johnson solid J5.
- 'pentagonal_rotunda'
- Pentagonal rotunda with regular facets. Johnson solid J6.
- 'elongated_triangular_pyramid'
- Elongated triangular pyramid with regular facets. Johnson solid J7.
- 'elongated_square_pyramid'
- Elongated square pyramid with regular facets. Johnson solid J8.
- 'elongated_pentagonal_pyramid'
- Elongated pentagonal pyramid with regular facets. Johnson solid J9. The vertices are realized as floating point numbers.
- 'gyroelongated_square_pyramid'
- Gyroelongated square pyramid with regular facets. Johnson solid J10. The vertices are realized as floating point numbers.
- 'gyroelongated_pentagonal_pyramid'
- Gyroelongated pentagonal pyramid with regular facets. Johnson solid J11.
- 'triangular_bipyramid'
- Triangular bipyramid with regular facets. Johnson solid J12.
- 'pentagonal_bipyramid'
- Pentagonal bipyramid with regular facets. Johnson solid J13. The vertices are realized as floating point numbers.
- 'elongated_triangular_bipyramid'
- Elongated triangular bipyramid with regular facets. Johnson solid J14.
- 'elongated_square_bipyramid'
- Elongated square bipyramid with regular facets. Johnson solid J15.
- 'elongated_pentagonal_bipyramid'
- Elongated pentagonal bipyramid with regular facets. Johnson solid J16. The vertices are realized as floating point numbers.
- 'gyroelongated_square_bipyramid'
- Gyroelongted square bipyramid with regular facets. Johnson solid J17. The vertices are realized as floating point numbers.
- 'elongated_triangular_cupola'
- Elongted triangular cupola with regular facets. Johnson solid J18. The vertices are realized as floating point numbers.
- 'elongated_square_cupola'
- Elongted square cupola with regular facets. Johnson solid J19.
- 'elongated_pentagonal_cupola'
- Elongted pentagonal cupola with regular facets. Johnson solid J20 The vertices are realized as floating point numbers.
- 'elongated_pentagonal_rotunda'
- Elongated pentagonal rotunda with regular facets. Johnson solid J21. The vertices are realized as floating point numbers.
- 'gyroelongated_triangular_cupola'
- Gyroelongted triangular cupola with regular facets. Johnson solid J22. The vertices are realized as floating point numbers.
- 'gyroelongated_square_cupola'
- Gyroelongted square cupola with regular facets. Johnson solid J23. The vertices are realized as floating point numbers.
- 'gyroelongated_pentagonal_cupola'
- Gyroelongted pentagonal cupola with regular facets. Johnson solid J24. The vertices are realized as floating point numbers.
- 'gyroelongated_pentagonal_rotunda'
- Gyroelongted pentagonal rotunda with regular facets. Johnson solid J25. The vertices are realized as floating point numbers.
- 'gyrobifastigium'
- Gyrobifastigium with regular facets. Johnson solid J26.
- 'triangular_orthobicupola'
- Triangular orthobicupola with regular facets. Johnson solid J27.
- 'square_orthobicupola'
- Square orthobicupola with regular facets. Johnson solid J28.
- 'square_gyrobicupola'
- Square gyrobicupola with regular facets. Johnson solid J29.
- 'pentagonal_orthobicupola'
- Pentagonal orthobicupola with regular facets. Johnson solid J30. The vertices are realized as floating point numbers.
- 'pentagonal_gyrobicupola'
- Pentagonal gyrobicupola with regular facets. Johnson solid J31. The vertices are realized as floating point numbers.
- 'pentagonal_orthocupolarotunda'
- Pentagonal orthocupolarotunda with regular facets. Johnson solid J32. The vertices are realized as floating point numbers.
- 'pentagonal_gyrocupolarotunda'
- Pentagonal gyrocupolarotunda with regular facets. Johnson solid J33. The vertices are realized as floating point numbers.
- 'pentagonal_orthobirotunda'
- Pentagonal orthobirotunda with regular facets. Johnson solid J32. The vertices are realized as floating point numbers.
- 'elongated_triangular_orthbicupola'
- Elongated triangular orthobicupola with regular facets. Johnson solid J35. The vertices are realized as floating point numbers.
- 'elongated_triangular_gyrobicupola'
- Elongated triangular gyrobicupola with regular facets. Johnson solid J36. The vertices are realized as floating point numbers.
- 'elongated_square_gyrobicupola'
- Elongated square gyrobicupola with regular facets. Johnson solid J37.
- 'elongated_pentagonal_orthobicupola'
- Elongated pentagonal orthobicupola with regular facets. Johnson solid J38. The vertices are realized as floating point numbers.
- 'elongated_pentagonal_gyrobicupola'
- Elongated pentagonal gyrobicupola with regular facets. Johnson solid J39. The vertices are realized as floating point numbers.
- 'elongated_pentagonal_orthocupolarotunda'
- Elongated pentagonal orthocupolarotunda with regular facets. Johnson solid J40. The vertices are realized as floating point numbers.
- 'elongated_pentagonal_gyrocupolarotunda'
- Elongated pentagonal gyrocupolarotunda with regular facets. Johnson solid J41. The vertices are realized as floating point numbers.
- 'elongated_pentagonal_orthobirotunda'
- Elongated pentagonal orthobirotunda with regular facets. Johnson solid J42. The vertices are realized as floating point numbers.
- 'elongated_pentagonal_gyrobirotunda'
- Elongated pentagonal gyrobirotunda with regular facets. Johnson solid J43. The vertices are realized as floating point numbers.
- 'gyroelongated_triangular_bicupola'
- Gyroelongated triangular bicupola with regular facets. Johnson solid J44. The vertices are realized as floating point numbers.
- 'elongated_square_bicupola'
- Elongated square bicupola with regular facets. Johnson solid J45. The vertices are realized as floating point numbers.
- 'gyroelongated_pentagonal_bicupola'
- Gyroelongated pentagonal bicupola with regular facets. Johnson solid J46. The vertices are realized as floating point numbers.
- 'gyroelongated_pentagonal_cupolarotunda'
- Gyroelongated pentagonal cupolarotunda with regular facets. Johnson solid J47. The vertices are realized as floating point numbers.
- 'gyroelongated_pentagonal_birotunda'
- Gyroelongated pentagonal birotunda with regular facets. Johnson solid J48. The vertices are realized as floating point numbers.
- 'augmented_triangular_prism'
- Augmented triangular prism with regular facets. Johnson solid J49. The vertices are realized as floating point numbers.
- 'biaugmented_triangular_prism'
- Biaugmented triangular prism with regular facets. Johnson solid J50. The vertices are realized as floating point numbers.
- 'triaugmented_triangular_prism'
- Triaugmented triangular prism with regular facets. Johnson solid J51. The vertices are realized as floating point numbers.
- 'augmented_pentagonal_prism'
- Augmented prantagonal prism with regular facets. Johnson solid J52. The vertices are realized as floating point numbers.
- 'biaugmented_pentagonal_prism'
- Augmented pentagonal prism with regular facets. Johnson solid J53. The vertices are realized as floating point numbers.
- 'augmented_hexagonal_prism'
- Augmented hexagonal prism with regular facets. Johnson solid J54. The vertices are realized as floating point numbers.
- 'parabiaugmented_hexagonal_prism'
- Parabiaugmented hexagonal prism with regular facets. Johnson solid J55. The vertices are realized as floating point numbers.
- 'metabiaugmented_hexagonal_prism'
- Metabiaugmented hexagonal prism with regular facets. Johnson solid J56. The vertices are realized as floating point numbers.
- 'triaugmented_hexagonal_prism'
- triaugmented hexagonal prism with regular facets. Johnson solid J57. The vertices are realized as floating point numbers.
- 'augmented_dodecahedron'
- Augmented dodecahedron with regular facets. Johnson solid J58. The vertices are realized as floating point numbers.
- 'parabiaugmented_dodecahedron'
- Parabiaugmented dodecahedron with regular facets. Johnson solid J59. The vertices are realized as floating point numbers.
- 'metabiaugmented_dodecahedron'
- Metabiaugmented dodecahedron with regular facets. Johnson solid J60. The vertices are realized as floating point numbers.
- 'triaugmented_dodecahedron'
- Triaugmented dodecahedron with regular facets. Johnson solid J61. The vertices are realized as floating point numbers.
- 'metabidiminished_icosahedron'
- Metabidiminished icosahedron with regular facets. Johnson solid J62.
- 'tridiminished_icosahedron'
- Tridiminished icosahedron with regular facets. Johnson solid J63.
- 'augmented_tridiminished_icosahedron'
- Augmented tridiminished icosahedron with regular facets. Johnson solid J64. The vertices are realized as floating point numbers.
- 'augmented_truncated_tetrahedron'
- Augmented truncated tetrahedron with regular facets. Johnson solid J65.
- 'augmented_truncated_cube'
- Augmented truncated cube with regular facets. Johnson solid J66.
- 'biaugmented_truncated_cube'
- Biaugmented truncated cube with regular facets. Johnson solid J67.
- 'augmented_truncated_dodecahedron'
- Augmented truncated dodecahedron with regular facets. Johnson solid J68. The vertices are realized as floating point numbers.
- 'parabiaugmented_truncated_dodecahedron'
- Parabiaugmented truncated dodecahedron with regular facets. Johnson solid J69. The vertices are realized as floating point numbers.
- 'metabiaugmented_truncated_dodecahedron'
- Metabiaugmented truncated dodecahedron with regular facets. Johnson solid J70. The vertices are realized as floating point numbers.
- 'triaugmented_truncated_dodecahedron'
- Triaugmented truncated dodecahedron with regular facets. Johnson solid J71. The vertices are realized as floating point numbers.
- 'gyrate_rhombicosidodecahedron'
- Gyrate rhombicosidodecahedron with regular facets. Johnson solid J72. The vertices are realized as floating point numbers.
- 'parabigyrate_rhombicosidodecahedron'
- Parabigyrate rhombicosidodecahedron with regular facets. Johnson solid J73. The vertices are realized as floating point numbers.
- 'metabigyrate_rhombicosidodecahedron'
- Metabigyrate rhombicosidodecahedron with regular facets. Johnson solid J74. The vertices are realized as floating point numbers.
- 'trigyrate_rhombicosidodecahedron'
- Trigyrate rhombicosidodecahedron with regular facets. Johnson solid J75. The vertices are realized as floating point numbers.
- 'diminished_rhombicosidodecahedron'
- Diminished rhombicosidodecahedron with regular facets. Johnson solid J76.
- 'paragyrate_diminished_rhombicosidodecahedron'
- Paragyrate diminished rhombicosidodecahedron with regular facets. Johnson solid J77. The vertices are realized as floating point numbers.
- 'metagyrate_diminished_rhombicosidodecahedron'
- Metagyrate diminished rhombicosidodecahedron with regular facets. Johnson solid J78. The vertices are realized as floating point numbers.
- 'bigyrate_diminished_rhombicosidodecahedron'
- Bigyrate diminished rhombicosidodecahedron with regular facets. Johnson solid J79. The vertices are realized as floating point numbers.
- 'parabidiminished_rhombicosidodecahedron'
- Parabidiminished rhombicosidodecahedron with regular facets. Johnson solid J80.
- 'metabidiminished_rhombicosidodecahedron'
- Metabidiminished rhombicosidodecahedron with regular facets. Johnson solid J81.
- 'gyrate_bidiminished_rhombicosidodecahedron'
- Gyrate bidiminished rhombicosidodecahedron with regular facets. Johnson solid J82. The vertices are realized as floating point numbers.
- 'tridiminished_rhombicosidodecahedron'
- Tridiminished rhombicosidodecahedron with regular facets. Johnson solid J83.
- 'snub_disphenoid'
- Snub disphenoid with regular facets. Johnson solid J84. The vertices are realized as floating point numbers.
- 'snub_square_antisprim'
- Snub square antiprism with regular facets. Johnson solid J85. The vertices are realized as floating point numbers.
- 'sphenocorona'
- Sphenocorona with regular facets. Johnson solid J86. The vertices are realized as floating point numbers.
- 'augmented_sphenocorona'
- Augmented sphenocorona with regular facets. Johnson solid J87. The vertices are realized as floating point numbers.
- 'sphenomegacorona'
- Sphenomegacorona with regular facets. Johnson solid J88. The vertices are realized as floating point numbers.
- 'hebesphenomegacorona'
- Hebesphenomegacorona with regular facets. Johnson solid J89. The vertices are realized as floating point numbers.
- 'disphenocingulum'
- Disphenocingulum with regular facets. Johnson solid J90. The vertices are realized as floating point numbers.
- 'bilunabirotunda'
- Bilunabirotunda with regular facets. Johnson solid J91.
- 'triangular_hebesphenorotunda'
- Triangular hebesphenorotunda with regular facets. Johnson solid J92.
Returns
Polytope - octahedron () → Polytope
- platonic_solid (s) → Polytope
Create Platonic solid of the given name.
Parameters
String s the name of the desired Platonic solidPossible values:- 'tetrahedron'
- Tetrahedron. Regular polytope with four triangular facets.
- 'cube'
- Cube. Regular polytope with six square facets.
- 'octahedron'
- Octahedron. Regular polytope with eight triangular facets.
- 'dodecahedron'
- Dodecahedron. Regular polytope with 12 pentagonal facets.
- 'icosahedron'
- Icosahedron. Regular polytope with 20 triangular facets.
Returns
Polytope - reduced (t, x, s, h, r) → Polytope<Rational>
Produce a 3-dimensional reduced polytope (for suitably chosen parameters). That is, a polytope of constant width which does not properly contain a subpolytope of the same width. Construction due to Bernardo González Merino, Thomas Jahn, Alexandr Polyanskii and Gerd Wachsmuth, arXiv:1701.08629
Example:- These values yield a reduced 3-polytope (approximately). The width equals 1.
> $r = reduced(0.55, 0.6176490959800, 0.1351384931026, 0.0984300252409, 0.3547183586709);
- regular_120_cell () → Polytope
- regular_24_cell () → Polytope
- regular_600_cell () → Polytope
- regular_simplex (d) → Polytope
Produce a regular d-simplex embedded in R^d with edge length sqrt(2).
Examples:- To print the vertices (in homogeneous coordinates) of the regular 2-simplex, i.e. an equilateral triangle, type this:
> print regular_simplex(2)->VERTICES;
1 1 0
1 0 1
1 1/2-1/2r3 1/2-1/2r3
The polytopes cordinate type is QuadraticExtension<Rational>, thus numbers that can be represented as a + b*sqrt(c) with Rational numbers a, b and c. The last row vectors entrys thus represent the number 1/2*(1-sqrt(3)). - To store a regular 3-simplex in the variable $s and also calculate its symmetry group, type this:
> $s = regular_simplex(3, group=>1);
You can then print the groups generators like so:> print $s->GROUP->RAYS_ACTION->GENERATORS;
1 0 2 3
3 0 1 2
- rhombicosidodecahedron () → Polytope
- rhombicuboctahedron () → Polytope
- root_system (type) → VectorConfiguration
Produce the root systems of the Coxeter arrangement of a given type The roots lie at infinity to facilitate reflecting in them.
Parameters
String type the type of the Coxeter arrangement, for example A4 or E8Returns
VectorConfiguration - simple_roots_type_A (index) → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type A Indices are taken w.r.t. the Dynkin diagram 0 ---- 1 ---- ... ---- n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.
- simple_roots_type_B (index) → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type B Indices are taken w.r.t. the Dynkin diagram 0 ---- 1 ---- ... ---- n-2 --(4)--> n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.
- simple_roots_type_C (index) → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type C Indices are taken w.r.t. the Dynkin diagram 0 ---- 1 ---- ... ---- n-2 <--(4)-- n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.
- simple_roots_type_D (index) → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type D Indices are taken w.r.t. the Dynkin diagram n-2 / 0 - 1 - ... - n-3 # n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.
- simple_roots_type_E6 () → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type E6 Indices are taken w.r.t. the Dynkin diagram 3 | | 0 ---- 1 ---- 2 ---- 4 ---- 5 Note that the roots lie at infinity to facilitate reflecting in them.
Returns
SparseMatrix - simple_roots_type_E7 () → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type E7 Indices are taken w.r.t. the Dynkin diagram 4 | | 0 ---- 1 ---- 2 ---- 3 ---- 5 ---- 6 Note that the roots lie at infinity to facilitate reflecting in them.
Returns
SparseMatrix - simple_roots_type_E8 () → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type E8 Indices are taken w.r.t. the Dynkin diagram 5 | | 0 ---- 1 ---- 2 ---- 3 ---- 4 ---- 6 ---- 7 Note that the roots lie at infinity to facilitate reflecting in them.
Returns
SparseMatrix - simple_roots_type_F4 () → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type F4 Indices are taken w.r.t. the Dynkin diagram 0 ---- 1 --(4)--> 2 ---- 3
Returns
SparseMatrix - simple_roots_type_G2 () → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type G2 Indices are taken w.r.t. the Dynkin diagram 0 <--(6)-- 1
Returns
SparseMatrix - simple_roots_type_H3 () → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type H3 Indices are taken w.r.t. the Dynkin diagram 0 --(5)-- 1 ---- 2 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length 2
Returns
SparseMatrix - simple_roots_type_H4 () → SparseMatrix
Produce the simple roots of the Coxeter arrangement of type H4 Indices are taken w.r.t. the Dynkin diagram 0 --(5)-- 1 ---- 2 ---- 3 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}
Returns
SparseMatrix - tetrahedron () → Polytope
- truncated_cube () → Polytope
- truncated_cuboctahedron () → Polytope
Create truncated cuboctahedron. An Archimedean solid. This is actually a misnomer. The actual truncation of a cuboctahedron is normally equivalent to this construction, but has two different edge lengths. This construction has regular 2-faces.
Returns
Polytope - truncated_dodecahedron () → Polytope
- truncated_icosahedron () → Polytope
Create exact truncated icosahedron in Q(sqrt{5}). An Archimedean solid. Also known as the soccer ball.
Returns
Polytope - truncated_icosidodecahedron () → Polytope
- truncated_octahedron () → Polytope
Create truncated octahedron. An Archimedean solid. Also known as the 3-permutahedron.
Returns
Polytope - wythoff (type, rings) → Polytope
Produce the orbit polytope of a point under a Coxeter arrangement with exact coordinates, possibly in a qudratic extension field of the rationals
Parameters
String type single letter followed by rank representing the type of the arrangementSet rings indices of the hyperplanes corresponding to simple roots of the arrangement that the initial point should NOT lie on. You may specify just an integer or a perl array ref like [0,1] or [0..2].Options
Bool lattice Should the vertices of the orbit polytope be chosen to lie on the corresponding root lattice? default 0, which means that the vertices will instead be chosen to lie as symmetrically as possible.Returns
Polytope
Topologic cell complexes defined as quotients over polytopes modulo a discrete group.
- cs_quotient (P)
For a centrally symmetric polytope, divide out the central symmetry, i.e, identify diametrically opposite faces.
Parameters
Polytope P , centrally symmetricExample:> $P = cube(3);
> cs_quotient($P);
> print $P->CS_PERMUTATION;
7 6 5 4 3 2 1 0
The zeroth vertex gets identified with the seventh, the first with the sixth etc.
- cylinder_2 () → Polytope
Return a 2-dimensional cylinder obtained by identifying two opposite sides of a square.
Returns
Polytope Example:- To obtain a topological space homeomorphic to a cylinder, type
> $p = cylinder_2();
> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS;
2 3 0 1
> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS;
{0 2}
{1 3}
Thus, vertices 0,2 and vertices 1,3 are identified.> print $p->QUOTIENT_SPACE->FACES;
{{0} {1}}
{{0 1} {0 2} {1 3}}
{{0 1 2 3}}
Thus, after identification two vertices, three edges, and one two-dimensional face remain:> print $p->QUOTIENT_SPACE->F_VECTOR;
2 3 1
- davis_manifold () → Polytope
Return the 4-dimensional hyperbolic manifold obtained by Michael Davis
Returns
Polytope [Proceedings of the AMS, Vol. 93, No. 2 (Feb., 1985), pp. 325-328] by identifying opposite faces of the 120-cellExample:- The Davis manifold is the centrally symmetric quotient of the regular 210-cell:
> $d = davis_manifold();
> print $d->F_VECTOR;
600 1200 720 120
> print $d->QUOTIENT_SPACE->F_VECTOR;
300 600 360 60 1
- quarter_turn_manifold () → Polytope
Return the 3-dimensional Euclidean manifold obtained by identifying opposite faces of a 3-dimensional cube by a quarter turn. After identification, two classes of vertices remain.
Returns
Polytope Example:- To obtain a topological space homeomorphic to the quarter turn manifold, type
> $p = quarter_turn_manifold();
> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS;
5 7 4 6 2 0 3 1
6 2 1 5 7 3 0 4
To see which vertices are identified, type> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS;
{0 3 5 6}
{1 2 4 7}
Thus, two classes of vertices remain, with 0 and 1 being representatives. To see the faces remaining after identification, type> print $p->QUOTIENT_SPACE->FACES;
{{0} {1}}
{{0 1} {0 2} {0 4} {0 7}}
{{0 1 2 3} {0 1 4 5} {0 1 6 7}}
{{0 1 2 3 4 5 6 7}}
> print $p->QUOTIENT_SPACE->F_VECTOR;
2 4 3 1
- write_quotient_space_simplexity_ilp ()
outputs a linear program whose optimal value is a lower bound for the number of simplices necessary to triangulate the polytope in such a way that its symmetries respect the triangulation of the boundary.
These functions capture information of the object that is concerned with the action of permutation groups.
- cocircuit_equations_support_reps (points, gens, rirs, rmis) → Int
write the indices of the representatives of the support of the cocircuit equations to a file
Parameters
Matrix<Scalar> points Array<Array<Int>> gens the generators of the action of the symmetry groupArray<SetType> rirs representatives of interior ridge simplicesArray<SetType> rmis representatives of maximal interior simplicesOptions
String filename where large output should go to. 'filename=>"-"' writes to stdout.Returns
Int - combinatorial_symmetries (p) → group::PermutationAction
Compute the combinatorial symmetries (i.e., automorphisms of the face lattice) of a given polytope p. They are stored in terms of a GROUP.VERTICES_ACTION and a GROUP.FACETS_ACTION property in p, and the GROUP.VERTICES_ACTION is also returned.
Parameters
Polytope p Returns
group::PermutationAction the action of the combinatorial symmetry group on the verticesExample:- To get the vertex symmetry group of the square and print its generators, type the following:
> print combinatorial_symmetries(cube(2))->GENERATORS;
2 3 0 1
1 0 2 3
> $p = cube(2); combinatorial_symmetries($p);
> print $p->GROUP->VERTICES_ACTION->GENERATORS;
0 2 1 3
1 0 3 2
> print $p->GROUP->FACETS_ACTION->GENERATORS;
2 3 0 1
1 0 2 3
- combinatorial_symmetrized_cocircuit_equations (P, comps)
calculate a sparse representation of the cocircuit equations corresponding to a direct sum of isotypic components
- combinatorial_symmetrized_cocircuit_equations (P, rirs, rmis, comps) → Array<Pair<SetType, HashMap<SetType,Rational>>>
calculate the projection of the cocircuit equations to a direct sum of isotypic components and represent it combinatorially
Parameters
Cone P Array<SetType> rirs representatives of interior ridge simplicesArray<SetType> rmis representatives of maximal interior simplicesSet<Int> comps the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge.Options
String filename where large output should go to. 'filename=>"-"' writes to stdout.Returns
Array<Pair<SetType, HashMap<SetType,Rational>>> indexed_cocircuit_equations a list of interior ridge simplices together with the corresponding sparsely represented cocircuit equation - isotypic_configuration (P, i) → polytope::PointConfiguration<Float>
Given a polytope that has a matrix group acting on it, return the projections of the vertices to the i-th isotypic component C_i. If the input is a group with a permutation action a, regard a as acting on the unit basis vectors of the ambient space and return the projection of the unit basis vectors to the i-th isotypic component.
Parameters
Polytope P a polytope with a matrix action, or a group::Group g with a permutation actionInt i the index of the desired isotypic componentReturns
polytope::PointConfiguration<Float> Example:- Consider the symmetry group of the cyclic polytope c(4,10) in the Carathéodory realization.
> $p = cyclic_caratheodory(4,10,group=>1);
For i=4, we obtain a 10-gon:> print isotypic_configuration($p,4)->POINTS;
1 1 0
1 0.8090169944 0.5877852523
1 0.3090169944 0.9510565163
1 -0.3090169944 0.9510565163
1 -0.8090169944 0.5877852523
1 -1 0
1 -0.8090169944 -0.5877852523
1 -0.3090169944 -0.9510565163
1 0.3090169944 -0.9510565163
1 0.8090169944 -0.5877852523
Similarly, for i=5 we get two copies of a pentagon.
- lattice_automorphisms_smooth_polytope (P) → Array<Array<Int>>
Returns a generating set for the lattice automorphism group of a smooth polytope P by comparing lattice distances between vertices and facets.
Parameters
Polytope P the given polytopeReturns
Array<Array<Int>> the generating set for the lattice automorphism groupExample:> print lattice_automorphisms_smooth_polytope(cube(2));
2 3 0 1
1 0 3 2
0 2 1 3
- linear_symmetries ()
wrapper function to store the symmetry group in the parent object
Contained in extensionsympol
. - linear_symmetries (m) → group::Group
Use sympol to compute the linear symmetries of - the rows of a rational matrix m, or - the RAYS|VERTICES, FACETS, or POINTS of a rational cone or polytope C (whatever is available, in this order), or - the VECTORS|POINTS of a rational vector or point configuration P. Except for matrices, the action of the symmetry group is stored inside the parent object. In the case of cones, sympol might compute only a subset of the linear symmetry group. Sympol, and therefore this function, can only handle rational objects.
Contained in extensionsympol
.Parameters
Matrix m | Cone C | VectorConfiguration PReturns
group::Group the linear symmetry group, together with a PERMUTATION_ACTION, VERTEX_ACTION, FACETS_ACTION, or VECTOR_ACTIONExample:> $ls = linear_symmetries(cube(2)->VERTICES);
> print $ls->PERMUTATION_ACTION->GENERATORS;
0 2 1 3
3 1 2 0
2 3 0 1
> print linear_symmetries(cube(3)->VERTICES)->PERMUTATION_ACTION->GENERATORS;
0 4 2 6 1 5 3 7
0 1 4 5 2 3 6 7
7 6 5 4 3 2 1 0
2 6 0 4 3 7 1 5
> print linear_symmetries(cube(3))->FACETS_ACTION->GENERATORS;
1 0 2 3 4 5
0 1 3 2 4 5
2 3 0 1 4 5
0 1 2 3 5 4
0 1 4 5 2 3
- nestedOPGraph (gen_point, points, lattice_points, group, verbose) → ARRAY
Constructs the NOP-graph of an orbit polytope. It is used by the rule for the NOP_GRAPH.
Parameters
Vector gen_point the generating pointMatrix points the vertices of the orbit polytopeMatrix lattice_points the lattice points of the orbit polytopegroup::Group group the generating groupBool verbose print out additional informationReturns
ARRAY ($Graph, $lp_reps, $minInStartOrbit, \@core_point_reps, $CPindices) - orbit_polytope (input_point, a) → Polytope
Constructs the orbit polytope of a given point input_point with respect to a given group action a.
Parameters
Vector input_point the basis point of the orbit polytopegroup::PermutationAction a the action of a permutation group on the coordinates of the ambient spaceReturns
Polytope the orbit polytope of input_point w.r.t. the action aExample:- The orbit polytope of a set of points A in affine d-space is the convex hull of the images of A under the action of a group G on the affine space. polymake implements several variations of this concept. The most basic one is the convex hull of the orbit of a single point under a set of coordinate permutations. For example, consider the cyclic group C_6 that acts on 6-dimensional space by cyclically permuting the coordinates. This action is represented in polymake by group::cyclic_group(6)->PERMUTATION_ACTION. To compute the convex hull of cyclic shifts of the vector v = [1,6,0,5,-5,0,-5] in homogeneous coordinates, type
> $p = orbit_polytope(new Vector([1,6,0,5,-5,0,-5]), group::cyclic_group(6)->PERMUTATION_ACTION);
After this assignment, the orbit polytope is still in implicit form, and the only properties that are defined reside in GROUP->COORDINATE_ACTION:> print $p->GROUP->COORDINATE_ACTION->properties();
type: PermutationAction<Int, Rational> as Polytope<Rational>::GROUP::COORDINATE_ACTION
GENERATORS
1 2 3 4 5 0
INPUT_RAYS_GENERATORS
1 6 0 5 -5 0 -5
To calculate the vertices of the orbit polytope explicitly, say> print $p->VERTICES;
1 -5 0 -5 6 0 5
1 -5 6 0 5 -5 0
1 0 -5 6 0 5 -5
1 0 5 -5 0 -5 6
1 5 -5 0 -5 6 0
1 6 0 5 -5 0 -5
- orbit_polytope (input_points, a) → Polytope
Constructs the orbit polytope of a given set of points input_points with respect to a given group action a.
Parameters
Matrix input_points the basis points of the orbit polytopegroup::PermutationAction a the action of a permutation group on the coordinates of the ambient spaceReturns
Polytope the orbit polytope of input_points w.r.t. the action aExample:- To find the orbit of more than one point under a PermutationAction on the coordinates, say
> $p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), new group::PermutationAction(GENERATORS=>[ [1,2,3,4,5,0] ]));
> print $p->VERTICES;
1 -5 0 -5 6 0 5
1 -5 6 0 5 -5 0
1 0 -5 6 0 5 -5
1 0 5 -5 0 -5 6
1 5 -5 0 -5 6 0
1 6 0 5 -5 0 -5
1 1 2 3 4 5 6
1 2 3 4 5 6 1
1 3 4 5 6 1 2
1 4 5 6 1 2 3
1 5 6 1 2 3 4
1 6 1 2 3 4 5
- orbit_polytope (input_point, g) → Polytope
Constructs the orbit polytope of a given point input_point with respect to a given group action a.
Parameters
Vector input_point the basis point of the orbit polytopegroup::Group g a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient spaceReturns
Polytope the orbit polytope of input_point w.r.t. the action of gExample:- As a convenience function, you can also directly specify a group::Group that contains a PERMUTATION_ACTION:
> $p = orbit_polytope(new Vector([1,6,0,5,-5,0,-5]), group::cyclic_group(6));
Up to now, the orbit polytope is still in implicit form. To calculate the vertices explicitly, say> print $p->VERTICES;
1 -5 0 -5 6 0 5
1 -5 6 0 5 -5 0
1 0 -5 6 0 5 -5
1 0 5 -5 0 -5 6
1 5 -5 0 -5 6 0
1 6 0 5 -5 0 -5
- orbit_polytope (input_points, g) → Polytope
Constructs the orbit polytope of a given set of points input_points with respect to a given group action a.
Parameters
Matrix input_points the basis points of the orbit polytopegroup::Group g a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient spaceReturns
Polytope the orbit polytope of input_points w.r.t. the action of gExample:- As a convenience function, you can also directly specify a group::Group that contains a PERMUTATION_ACTION:
> $p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), group::cyclic_group(6));
> print $p->VERTICES;
1 -5 0 -5 6 0 5
1 -5 6 0 5 -5 0
1 0 -5 6 0 5 -5
1 0 5 -5 0 -5 6
1 5 -5 0 -5 6 0
1 6 0 5 -5 0 -5
1 1 2 3 4 5 6
1 2 3 4 5 6 1
1 3 4 5 6 1 2
1 4 5 6 1 2 3
1 5 6 1 2 3 4
1 6 1 2 3 4 5
- orbit_polytope (input_points, gens) → Polytope
Constructs the orbit polytope of a given set of points input_points with respect to a given set of generators gens.
Parameters
Matrix input_points the basis point of the orbit polytopeArray<Array<Int>> gens the generators of a permutation group that acts on the coordinates of the ambient spaceReturns
Polytope the orbit polytope of input_points w.r.t. the coordinate action generated by gensExample:- This is a variation where several points are given as the row of a matrix, and the permutation action on coordinates is given by explicitly listing the generators. In this example, the matrix has just one row, and there is just one generator.
> print orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5] ]), [ [1,2,3,4,5,0] ])->VERTICES;
1 -5 0 -5 6 0 5
1 -5 6 0 5 -5 0
1 0 -5 6 0 5 -5
1 0 5 -5 0 -5 6
1 5 -5 0 -5 6 0
1 6 0 5 -5 0 -5
- orbit_polytope <Scalar> (input_point, a) → Polytope
Constructs the orbit polytope of a given point input_point with respect to a given matrix group action a.
Type Parameters
Scalar S the underlying number typeParameters
Vector input_point the generating point of the orbit polytopegroup::MatrixActionOnVectors a the action of a matrix group on the coordinates of the ambient spaceReturns
Polytope the orbit polytope of input_point w.r.t. the action aExample:- polymake also supports orbit polytopes under the action of a group by matrices. To find the orbit of a point in the plane under the symmetry group of the square, say
> $p = orbit_polytope(new Vector([1,2,1]), cube(2, group=>1)->GROUP->MATRIX_ACTION);
> print $p->VERTICES;
1 -2 -1
1 -2 1
1 -1 -2
1 -1 2
1 1 -2
1 1 2
1 2 -1
1 2 1
- orbit_polytope <Scalar> (input_points, a) → Polytope
Constructs the orbit polytope of a given set of points input_points with respect to a given matrix group action a.
Type Parameters
Scalar S the underlying number typeParameters
Matrix<Scalar> input_points the generating points of the orbit polytopegroup::MatrixActionOnVectors<Scalar> a the action of a matrix group on the coordinates of the ambient spaceReturns
Polytope the orbit polytope of the input_points w.r.t. the action aExample:- To find the orbit of more than one point in the plane under the symmetry group of the square, say
> $p = orbit_polytope(new Matrix([ [1,2,1], [1,5/2,0] ]), cube(2, group=>1)->GROUP->MATRIX_ACTION);
> print $p->VERTICES;
1 -2 -1
1 -2 1
1 -1 -2
1 -1 2
1 1 -2
1 1 2
1 2 -1
1 2 1
1 -5/2 0
1 0 -5/2
1 0 5/2
1 5/2 0
- ortho_project (p) → Polytope
- representation_conversion_up_to_symmetry (c) → Pair
Computes the dual description of a polytope up to its linear symmetry group.
Contained in extensionsympol
.Parameters
Cone c the cone (or polytope) whose dual description is to be computed, equipped with a GROUPOptions
Bool v_to_h 1 (default) if converting V to H, false if converting H to VString method specifies sympol's method of ray computation via 'lrs' (default), 'cdd', 'beneath_beyond', 'ppl'Returns
Pair (Matrix<Rational> vertices/inequalities, Matrix<Rational> lineality/equations) - symmetrized_cocircuit_equations <Scalar> (P, comps)
calculate the projection of the cocircuit equations to a direct sum of isotypic components
Type Parameters
Scalar the underlying data typeParameters
Cone P or PointConfigurationSet<Int> comps the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge.Options
Bool reduce_rows Should we return only linearly independent equations? default: 1 - truncated_orbit_polytope (P, eps) → Polytope
Gives an implicit representation of the all-vertex truncation of an orbit polytope P, in which all vertices are cut off by hyperplanes at distance eps. The input polytope P must have a GROUP.COORDINATE_ACTION. The output is a polytope with a GROUP.COORDINATE_ACTION equipped with INEQUALITIES_GENERATORS.
These functions take a realized polytope and produce a new one by applying a suitable affine or projective transformation in order to obtain some special coordinate description but preserve the combinatorial type.
For example, before you can polarize an arbitrary polyhedron, it must be transformed to a combinatorially equivalent bounded polytope with the origin as a relatively interior point. It is achieved with the sequence orthantify - bound - center - polarize.
- ambient_lattice_normalization (p) → Polytope
Transform to a full-dimensional polytope while preserving the ambient lattice Z^n
Parameters
Polytope p the input polytope,Options
Bool store_transform store the reverse transformation as an attachementReturns
Polytope - the transformed polytope defined by its vertices. Facets are only written if available in p.Examples:- Consider a line segment embedded in 2-space containing three lattice points:
> $p = new Polytope(VERTICES=>[[1,0,0],[1,2,2]]);
> print ambient_lattice_normalization($p)->VERTICES;
1 0
1 2
The ambient lattice of the projection equals the intersection of the affine hull of $p with Z^2. - Another line segment containing only two lattice points:
> $p = new Polytope(VERTICES=>[[1,0,0],[1,1,2]]);
> $P = ambient_lattice_normalization($p,store_transform=>1);
> print $P->VERTICES;
1 0
1 1
To get the transformation, do the following:> $M = $P->get_attachment('REVERSE_LATTICE_PROJECTION');
> print $M;
1 0 0
0 1 2
> print $P->VERTICES * $M;
1 0 0
1 1 2
- 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 unit vectors. The origin (1,0,...,0) is fixed.
The input polyhedron should be POSITIVE; i.e. no negative coordinates.
Example:- Observe the transformation of a simple unbounded 2-polyhedron:
> $P = new Polytope(VERTICES=>[[1,0,0],[0,1,1],[0,0,1]]);
> print bound($P)->VERTICES;
1 0 0
1 1/2 1/2
1 0 1
As you can see, the far points are mapped to the hyperplane spanned by (1,1,0) and (1,0,1).
- 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).
Example:- Consider this triangle not containing the origin:
> $P = new Polytope(VERTICES => [[1,1,1],[1,2,1],[1,1,2]]);
> $origin = new Vector([1,0,0]);
> print $P->contains_in_interior($origin);
false
To create a translate that contains the origin, do this:> $PC = center($P);
> print $PC->contains_in_interior($origin);
true
This is what happened to the vertices:> print $PC->VERTICES;
1 -1/3 -1/3
1 2/3 -1/3
1 -1/3 2/3
There also exists a property to check whether a polytope is centered:> print $PC->CENTERED;
true
- 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 Example:- To orthantify the square, moving its first vertex to the origin, do this:
> $p = orthantify(cube(2),1);
> print $p->VERTICES;
1 2 0
1 0 0
1 2 2
1 0 2
- orthonormal_col_basis (M) → Matrix<Float>
Return an orthonormal column basis of the input matrix.
- orthonormal_row_basis (M) → Matrix<Float>
Return an orthonormal row basis of the input matrix.
- polarize (C) → Cone
This method takes either a polytope (1.) or a cone (2.) as input. 1. Given a bounded, centered, not necessarily full-dimensional polytope P, produce its polar with respect to the standard Euclidean scalar product. 2. Given a cone C produce its dual with respect to the standard Euclidean scalar product, i.e. all the vectors that evaluate positively on C. Note that the definition of the polar has changed after version 2.10: the polar is reflected in the origin to conform with cone polarization If P is not full-dimensional, the output will contain lineality orthogonal to the affine span of P. In particular, polarize() of a pointed polytope will always produce a full-dimensional polytope. If you want to compute the polar inside the affine hull you may use the pointed_part client afterwards.
Examples:- To save the polar of the square in the variable $p and then print its vertices, do this:
> $p = polarize(cube(2));
> print $p->VERTICES;
1 1 0
1 -1 0
1 0 1
1 0 -1
- To dualize the cone over a hexagon and print its rays, do this:
> $c = new Cone(INPUT_RAYS=>[[1,0,0],[1,1,0],[1,2,1],[1,2,2],[1,1,2],[1,0,1]]);
> $cd = polarize($c);
> print $cd->RAYS;
1 -1 1
0 0 1
0 1 0
1 1 -1
1 0 -1/2
1 -1/2 0
- revert (P) → Polytope
Apply a reverse transformation to a given polyhedron P. All transformation clients keep track of the polytope's history. They write or update the attachment REVERSE_TRANSFORMATION.
Applying revert to the transformed polytope reconstructs the original polytope.
Example:- The following translates the square and then reverts the transformation:
> $v = new Vector(1,2);
> $p = translate(cube(2),$v);
> print $p->VERTICES;
1 0 1
1 2 1
1 0 3
1 2 3
> $q = revert($p);
> print $q->VERTICES;
1 -1 -1
1 1 -1
1 -1 1
1 1 1
- scale (P, factor, store) → Polytope
Scale a polyhedron P by a given scaling parameter factor.
Parameters
Polytope P the polyhedron to be scaledScalar factor the scaling factorBool store stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.Returns
Polytope Example:- To scale the square by 23, do this:
> $p = scale(cube(2),23);
> print $p->VERTICES;
1 -23 -23
1 23 -23
1 -23 23
1 23 23
The transformation matrix is stored in an attachment:> print $p->get_attachment('REVERSE_TRANSFORMATION');
1 0 0
0 1/23 0
0 0 1/23
To reverse the transformation, you can use the revert function.> $q = revert($p);
> print $q->VERTICES;
1 -1 -1
1 1 -1
1 -1 1
1 1 1
- transform (P, trans, store) → Polytope
Transform a polyhedron P according to the linear transformation trans.
Parameters
Polytope P the polyhedron to be transformedMatrix trans the transformation matrixBool store stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.Returns
Polytope Example:- This translates the square by (23,23) and stores the transformation:
> $M = new Matrix([1,23,23],[0,1,0],[0,0,1]);
> $p = transform(cube(2),$M,1);
> print $p->VERTICES;
1 22 22
1 24 22
1 22 24
1 24 24
To retrieve the attached transformation, use this:> print $p->get_attachment('REVERSE_TRANSFORMATION');
1 -23 -23
0 1 0
0 0 1
Check out the revert function to learn how to undo the transformation. It might be more comfortable to use the translate function to achieve the same result.
- translate (P, trans, store) → Polytope
Translate a polyhedron P by a given translation vector trans.
Parameters
Polytope P the polyhedron to be translatedVector trans the translation vectorBool store stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.Returns
Polytope Example:- This translates the square by (23,23) and stores the transformation:
> $t = new Vector(23,23);
> $p = translate(cube(2),$t);
> print $p->VERTICES;
1 22 22
1 24 22
1 22 24
1 24 24
To retrieve the attached transformation, use this:> print $p->get_attachment('REVERSE_TRANSFORMATION');
1 -23 -23
0 1 0
0 0 1
Check out the revert function to learn how to undo the transformation.
- 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
These functions collect information about triangulations and other subdivisions of the object and properties usually computed from such, as the volume.
- barycentric_subdivision (c) → topaz::SimplicialComplex
Create a simplicial complex as a barycentric subdivision of a given cone or polytope. Each vertex in the new complex corresponds to a face in the old complex.
Parameters
Cone c input cone or polytopeOptions
Bool no_labels Do not generate VERTEX_LABELS from the faces of the original cone. default: 0Bool geometric_realization create a topaz::GeometricSimplicialComplex; default is trueReturns
topaz::SimplicialComplex - chirotope (P) → String
Compute the chirotope of a point or vector configuration using TOPCOM.
- chirotope (P) → String
Compute the chirotope of a point or vector configuration using polymake's native implementation.
- coherency_index (points, w1, w2)
- coherency_index (p1, p2)
- common_refinement (points, sub1, sub2, dim) → IncidenceMatrix
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 IncidenceMatrix sub1 first subdivisionIncidenceMatrix sub2 second subdivisionInt dim dimension of the point configurationReturns
IncidenceMatrix the common refinementExample:- A simple 2-dimensional set of points:
> $points = new Matrix<Rational>([[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,2,1]]);
Two different subdivisions...> $sub1 = new IncidenceMatrix([[0,1,2],[1,2,3,4]]);
> $sub2 = new IncidenceMatrix([[1,3,4],[0,1,2,3]]);
...and their common refinement:> print common_refinement($points,$sub1,$sub2,2);
{0 1 2}
{1 3 4}
{1 2 3}
- common_refinement (p1, p2) → Polytope
- delaunay_triangulation (V) → Array<Set<Int>>
Compute the Delaunay triangulation of the given SITES of a VoronoiPolyhedron 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).
Example:> $VD = new VoronoiPolyhedron(SITES=>[[1,1,1],[1,0,1],[1,-1,1],[1,1,-1],[1,0,-1],[1,-1,-1]]);
> $D = delaunay_triangulation($VD);
> print $D;
{0 1 3}
{1 3 4}
{1 2 4}
{2 4 5}
- fiber_polytope (pc, pc) → PointConfiguration
Computes the fiber polytope of a projection of point configurations P->Q via the GKZ secondary configuration.
Parameters
PointConfiguration pc (or Polytope) source point configuration or polytopePointConfiguration pc target point configurationReturns
PointConfiguration - fiber_polytope (pc, pc) → PointConfiguration
Computes the fiber polytope of a projection of point configurations P->Q via the GKZ secondary configuration.
Parameters
PointConfiguration pc (or Polytope) source point configuration or polytopePolytope pc target polytopeReturns
PointConfiguration - fiber_polytope (P, pi) → PointConfiguration
Computes the fiber polytope of a projection of point configurations P -pi-> Q via the GKZ secondary configuration.
Parameters
PointConfiguration P (or Polytope) source point configuration or polytopeMatrix pi the projection acting on PReturns
PointConfiguration - foldable_max_signature_ilp (d, points, volume, cocircuit_equations) → LinearProgram<Rational>
Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesRational volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
LinearProgram<Rational> an ILP that provides the result - foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → Integer
Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesRational volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
Integer the optimal value of an LP that provides a bound - interior_and_boundary_ridges (P) → Pair<Array<Set>,Array<Set>>
Find the (d-1)-dimensional simplices in the interior and in the boundary of a d-dimensional polytope or cone
Example:> print interior_and_boundary_ridges(cube(2));
<{0 3}
{1 2}
>
<{0 1}
{0 2}
{1 3}
{2 3}
>
- is_regular (points, subdiv) → Pair<Bool,Vector>
For a given subdivision subdiv of points tests if the subdivision is regular and if yes computes a weight vector inducing this subdivsion. The output is a pair of Bool and the weight vector. Options can be used to ensure properties of the resulting vector. The default is having 0 on all vertices of the first face of subdiv.
Parameters
Matrix points in homogeneous coordinatesArray<Set<Int> > subdiv Options
Matrix<Scalar> equations system of linear equation the cone is cut with.Set<Int> lift_to_zero gives only lifting functions lifting the designated vertices to 0Int lift_face_to_zero gives only lifting functions lifting all vertices of the designated face to 0Returns
Pair<Bool,Vector> Example:- A regular subdivision of the square, with the first cell lifted to zero:
> $points = cube(2)->VERTICES;
> print is_regular($points,[[0,1,3],[1,2,3]],lift_to_zero=>[0,1,3]);
1 <0 0 1 0>
- is_subdivision (points, faces)UNDOCUMENTEDExample:
- Two potential subdivisions of the square without innter points:
> $points = cube(2)->VERTICES;
> print is_subdivision($points,[[0,1,3],[1,2,3]],interior_points=>[ ]);
true
> print is_subdivision($points,[[0,1,2],[1,2]],interior_points=>[ ]);
false
- iterated_barycentric_subdivision (c, n) → topaz::SimplicialComplex
Create a simplicial complex as an iterated barycentric subdivision of a given cone or polytope.
Parameters
Cone c input cone or polytopeInt n how many times to subdivideOptions
Bool no_labels Do not generate VERTEX_LABELS from the faces of the original cone. default: 0Bool geometric_realization create a topaz::GeometricSimplicialComplex; default is falseReturns
topaz::SimplicialComplex - max_interior_simplices (P) → Array<Set>
Find the maximal interior simplices of a polytope P. Symmetries of P are NOT taken into account.
Example:> print max_interior_simplices(cube(2));
{0 1 2}
{0 1 3}
{0 2 3}
{1 2 3}
- max_interior_simplices (P) → Array<Set>
find the maximal interior simplices of a point configuration Symmetries of the configuration are NOT taken into account.
Example:- To calculate the maximal interior simplices of a point configuration, type
> $p=new PointConfiguration(POINTS=>[[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,1/2,1/2]]);
> print max_interior_simplices($p);
{0 1 2}
{0 1 3}
{0 1 4}
{0 2 3}
{0 2 4}
{1 2 3}
{1 3 4}
{2 3 4}
- mixed_volume (P1, P2, Pn) → SCALAR
- n_fine_triangulations (M, optimization) → Integer
Calculates the number of fine triangulations of a planar point configuration. This can be space intensive.
Victor Alvarez, Raimund Seidel: A Simple Aggregative Algorithm for Counting Triangulations of Planar Point Sets and Related Problems. In Proc. of the 29th Symposium on Computational Geometry (SoCG '13), pages 1-8, Rio de Janeiro, Brazil, 2013
Parameters
Matrix M in the plane (homogeneous coordinates)Bool optimization defaults to 1, where 1 includes optimization and 0 excludes itReturns
Integer number of fine triangulationsExample:- To print the number of possible fine triangulations of a square, do this:
> print n_fine_triangulations(cube(2)->VERTICES);
2
- placing_triangulation (Points) → Array<Set<Int>>
Compute the placing triangulation of the given point set using the beneath-beyond algorithm.
Parameters
Matrix Points the given point setOptions
Bool non_redundant whether it's already known that Points are non-redundantArray<Int> permutation placing order of Points, must be a valid permutation of (0..Points.rows()-1)Returns
Array<Set<Int>> Example:- To compute the placing triangulation of the square (of whose vertices we know that they're non-redundant), do this:
> $t = placing_triangulation(cube(2)->VERTICES, non_redundant=>1);
> print $t;
{0 1 2}
{1 2 3}
- points2metric (points) → Matrix
Define a metric by restricting the Euclidean distance function to a given set of points. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-norm is used instead (with exact computation).
Parameters
Matrix points Options
Bool max triggers the usage of the max-norm (exact computation)Bool l1 triggers the usage of the l1-norm (exact computation)Returns
Matrix Example:> print points2metric(cube(2)->VERTICES, max=>1);
0 2 2 2
2 0 2 2
2 2 0 2
2 2 2 0
- 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-norm is used instead (with exact computation).
Parameters
Polytope P Options
Bool max triggers the usage of the max-norm (exact computation)Returns
Matrix Example:> print poly2metric(cube(2), max=>1);
0 2 2 2
2 0 2 2
2 2 0 2
2 2 2 0
- 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 indicesReturns
Set<Set<Int>> A list of point sets that intersect positively the set S - quotient_space_simplexity_ilp (d, V, volume, cocircuit_equations) → LinearProgram
Set up an LP whose MINIMAL_VALUE is a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix V the input points or verticesScalar volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsOptions
String filename a name for a file in .lp format to store the linear programReturns
LinearProgram an LP that provides a lower bound - quotient_space_simplexity_lower_bound (d, V, volume, cocircuit_equations) → Integer
Calculate a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix V the input points or verticesScalar volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
Integer the optimal value of an LP that provides a lower bound - regularity_lp (points, subdiv) → Polytope<Scalar>
For a given subdivision subdiv of points determines a LinearProgram to decide whether the subdivision is regular. The output a Polytope with an attached LP. Options can be used to ensure properties of the resulting LP. The default is having 0 on all vertices of the first face of subdiv.
Parameters
Matrix points in homogeneous coordinatesArray<Set<Int> > subdiv Options
Matrix<Scalar> equations system of linear equation the cone is cut with.Set<Int> lift_to_zero gives only lifting functions lifting the designated vertices to 0Int lift_face_to_zero gives only lifting functions lifting all vertices of the designated face to 0Scalar epsilon minimum distance from all inequalitiesReturns
Polytope<Scalar> - regular_subdivision (points, weights) → Array<Set<Int>>
Compute a regular subdivision of the polytope obtained by lifting points to weights and taking the lower complex of the resulting polytope. If the weight is generic the output is a triangulation.
Example:- The following generates a regular subdivision of the square.
> $w = new Vector(2,23,2,2);
> $r = regular_subdivision(cube(2)->VERTICES,$w);
> print $r;
{0 2 3}
{0 1 3}
- secondary_polytope (pc) → PointConfiguration
Computes the GKZ secondary configuration of a point configuration via its chirotope.
- secondary_polytope (pc) → PointConfiguration
Computes the GKZ secondary configuration of a point configuration via its chirotope.
- simplexity_ilp (d, points, MIS, volume, cocircuit_equations) → LinearProgram
Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesArray<Set> MIS the representatives of maximal interior simplicesScalar volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
LinearProgram an LP that provides a lower bound - simplexity_ilp_with_angles (d, V, F, VIF, VIR, gens, MIS, volume, cocircuit_equations) → LinearProgram
Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix V the input points or verticesMatrix F the facets of the input polytopeIncidenceMatrix VIF the vertices-in-facets incidence matrixIncidenceMatrix VIR the vertices-in-ridges incidence matrixArray<Array<Int>> gens the generators of the symmetry groupArray<Set> MIS the (representative) maximal interior simplicesScalar volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
LinearProgram an LP that provides a lower bound - simplexity_lower_bound (d, points, volume, cocircuit_equations) → Integer
Calculate the LP relaxation lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesScalar volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
Integer the optimal value of an LP that provides a lower bound - 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 polyhedronReturns
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-1- and an l-1-dimensional simplex.
Parameters
Int k the number of vertices of the first simplexInt l the number of vertices of the second simplexReturns
Vector<Rational> Example:- The following creates the staircase triangulation of the product of the 2- and the 1-simplex.
> $w = staircase_weight(3,2);
> $p = product(simplex(2),simplex(1));
> $p->POLYTOPAL_SUBDIVISION(WEIGHTS=>$w);
> print $p->POLYTOPAL_SUBDIVISION->MAXIMAL_CELLS;
{0 2 4 5}
{0 2 3 5}
{0 1 3 5}
- symmetrized_foldable_max_signature_ilp (d, points, volume, generators, symmetrized_foldable_cocircuit_equations) → LinearProgram<Rational>
Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesRational volume the volume of the convex hullArray<Array<Int>> generators the generators of the symmetry groupSparseMatrix symmetrized_foldable_cocircuit_equations the matrix of symmetrized cocircuit equationsReturns
LinearProgram<Rational> an ILP that provides the result - symmetrized_foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → Integer
Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold
Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesRational volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
Integer the optimal value of an LP that provides a bound - topcom_all_triangulations (pc) → Array<Array<Set<Int>>>
Computes all triangulations of a point configuration via its chirotope.
- topcom_fine_and_connected_triangulations (pc) → Array<Array<Set<Int>>>
Computes all fine triangulations of a point configuration that are connected by bistellar flips to a fine seed triangulation. The triangulations are computed via the chirotope. If the input point configuration or polytope has a symmetry group, only fine triangulations up to symmetry will be computed.
Parameters
PointConfiguration pc or Polytope p input point configuration or polytopeReturns
Array<Array<Set<Int>>> - topcom_input_format (P) → String
This converts a polytope, cone or point configuration into a format that topcom understands
Example:- To convert a 2-cube without symmetries into topcom format, type
> print topcom_input_format(cube(2));
[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]
[]
If you also want the symmetry group, you can type> print topcom_input_format(cube(2,group=>1));
[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]
[[1,0,3,2],[0,2,1,3]]
- topcom_regular_and_connected_triangulations (pc) → Array<Array<Set<Int>>>
Computes all triangulations of a point configuration that are connected by bistellar flips to the regular triangulations. The triangulations are computed via the chirotope. If the input point configuration or polytope has a symmetry group, only triangulations up to symmetry will be computed.
Parameters
PointConfiguration pc or Polytope p input point configuration or polytopeReturns
Array<Array<Set<Int>>> - universal_polytope <Scalar> (PC) → Polytope
Calculate the universal polytope of a point configuration A. It is a 0/1 polytope with one vertex for every triangulation of A. Each coordinate of the ambient space corresponds to a simplex in the configuration.
Type Parameters
Scalar the underlying number typeParameters
PointConfiguration<Scalar> PC the point configurationReturns
Polytope Example:- To calculate the universal polytope of a point configuration, type
> $p=new PointConfiguration(POINTS=>[[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,1/2,1/2]]);
> print universal_polytope($p)->VERTICES;
1 0 1 0 1 0 0 0 0
1 1 0 0 0 0 1 0 0
1 0 0 1 0 1 0 1 1
Notice how the first vertex corresponds to the triangulation using all points, and the other ones to the triangulations that don't use the inner point.
- universal_polytope (P) → Polytope
Calculate the universal polytope U(P) of an input polytope P. If P has n vertices and dimension d, then U(P) is a 0/1-polytope in dimension binomial(n,d+1) whose vertices correspond to the full triangulations of P. Each coordinate of a particular vertex v indicates the presence or absence of a particular simplex in the triangulation corresponding to v, and the order of the simplices (and hence the interpretation of each coordinate of v) is the one given by the property MAX_INTERIOR_SIMPLICES. Because the number of triangulations of P is typically very large, the polytope U(P) is not constructed by enumerating triangulations, but instead in the inequality description afforded by the cocircuit equations, a volume equality, and non-negativity constraints for the coordinates.
Example:- Since the 2-dimensional cube (i.e., the square) has just two triangulations, its universal polytope is a segment embedded in dimension binomial(4,3) = 4. The cocircuit equations read as follows:
> print universal_polytope(cube(2))->EQUATIONS;
-8 4 4 4 4
(5) (2 -1) (3 1)
(5) (1 -1) (4 1)
- universal_polytope (P, reps, cocircuit_equations) → Polytope
Calculate the universal polytope of a polytope, point configuration or quotient manifold
Parameters
Polytope P the input polytopeArray<Set> reps the representatives of maximal interior simplicesSparseMatrix cocircuit_equations the matrix of cocircuit equationsReturns
Polytope
These functions are for 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.
- vlabels (vertices, wo_zero) → ARRAY
Creates vertex labels for visualization from the vertices of the polytope. The parameter wo_zero decides whether the entry at position 0 (homogenizing coordinate) is omitted (1) or included (0) in the label string."
Parameters
Matrix vertices the vertices of the polytopeBool wo_zero includes (0) or omits (1) the entry at position 0Returns
ARRAY a reference to an array of vertex label stringsExample:- This prints the vertex labels for the square with the origin as its center and side length 2, where we omit the leading 1:
> $l = vlabels(cube(2)->VERTICES,1);
> print join(', ', @{$l});
(-1,-1), (1,-1), (-1,1), (1,1)
Common Option Lists
These options are for visualization.
- schlegel_init
Initial properties of the Schlegel diagram to be displayed.
Options
Int FACET index of the projection facet, see Visual::SchlegelDiagram::FACETRational ZOOM zoom factor, see Visual::SchlegelDiagram::ZOOMVector FACET_POINT Vector INNER_POINT