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.
Specializations of Cone
- Cone<QuadraticExtension>
An affine cone with coordinates in a QuadraticExtension field realized in Rd.
Properties of Cone
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 matrix whose rows contain the cocircuit equations of P. The columns correspond to the MAX_INTERIOR_SIMPLICES.
Contained in extensionbundled:group
. - 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
- 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), ...
Contained in extensionbundled:group
. - 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.
- INTERIOR_RIDGE_SIMPLICES: common::Array<Set<Int>>
The (d-1)-dimensional simplices in the interior.
Contained in extensionbundled:group
. - MAX_BOUNDARY_SIMPLICES: common::Array<Set<Int>>
The boundary (d-1)-dimensional simplices of a cone of combinatorial dimension d
Contained in extensionbundled:group
. - MAX_INTERIOR_SIMPLICES: common::Array<Set<Int>>
The interior d-dimensional simplices of a cone of combinatorial dimension d
Contained in extensionbundled:group
.
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. N_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.
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)
- 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
- 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.
- 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 collect information about triangulations of the object and properties usually computed from such, as the volume.
- TRIANGULATION: topaz::GeometricSimplicialComplex
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: topaz::SimplicialComplex
Specialization of topaz::SimplicialComplex::BOUNDARY for Cone::TRIANGULATION
Properties of BOUNDARY
- FACET_TRIANGULATIONS: common::Array<Set<Int>>
For each facet the set of simplex indices of BOUNDARY that triangulate it.
- GKZ_VECTOR: common::Vector
GKZ-vector
See Chapter 7 in Gelfand, Kapranov, and Zelevinsky:Discriminants, Resultants and Multidimensional Determinants, Birkhäuser 1994 - REFINED_SPLITS: common::Set<Int>
The splits that are coarsenings of the current TRIANGULATION. If the triangulation is regular these form the unique split decomposition of the corresponding weight function.
These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.
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<List<Int>>
Reordered transposed RAYS_IN_FACETS. Dual to VIF_CYCLIC_NORMAL.
- NEIGHBOR_FACETS_CYCLIC_NORMAL: common::Array<List<Int>>
Reordered DUAL_GRAPH for 3d-cones. The neighbor facets are listed in the order corresponding to RIF_CYCLIC_NORMAL, so that the first two vertices in RIF_CYCLIC_NORMAL make up the ridge to the first neighbor facet and so on.
- NEIGHBOR_RAYS_CYCLIC_NORMAL: common::Array<List<Int>>
Reordered GRAPH. Dual to NEIGHBOR_FACETS_CYCLIC_NORMAL.
- 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 ()
The diameter of the DUAL_GRAPH
- DUAL_TRIANGLE_FREE ()
True if the DUAL_GRAPH contains no triangle
- TRIANGLE_FREE ()
True if the GRAPH contains no triangle
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 ()
- DUAL_CONNECTIVITY ()
Connectivity of the DUAL_GRAPH this is the minimum number of nodes that have to be removed from the DUAL_GRAPH to make it disconnected
- DUAL_EVEN ()
True if the DUAL_GRAPH is bipartite
- FACET_DEGREES () → Vector<Int>
Facet degrees of the polytope. The degree of a facet is the number of adjacent facets.
Returns
Vector<Int> - in the same order as FACETS - N_FLAGS (type ...)
Determine the number of flags of a given type. type must belong to {0,...,COMBINATORIAL_DIM-1}. Example: "N_FLAGS(0,3,4)" determines the entry f034 of the flag vector.
Parameters
Int type ... flag type - 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 ()
returns the dimension of the ambient space of the cone
- DIM ()
returns the geometric dimension of the cone (including the lineality space) for the dimension of the pointed part ask for COMBINATORIAL_DIM
These methods capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- HILBERT_BASIS () → Matrix<Integer>
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 ()
Difference of the black and white nodes if the DUAL_GRAPH is BIPARTITE. Otherwise -1.
Permutations of Cone
- FacetPerm
UNDOCUMENTED
Properties of FacetPerm
- VertexPerm
UNDOCUMENTED
Properties of VertexPerm
- 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
.
- derived from: Polytope<Rational>
A polytope all of whose vertex coordinates are integral.
Properties of LatticePolytope
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::Graph<Undirected>
Specialization of Polytope::GRAPH for LatticePolytope
Properties of GRAPH
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>
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>
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
These properties capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- EHRHART_POLYNOMIAL_COEFF: common::Vector<Rational>
The coefficients of the Ehrhart polynomial starting at the constant coefficient.
- FACET_VERTEX_LATTICE_DISTANCES: common::Matrix<Integer, NonSymmetric>
The entry (i,j) equals the lattice distance of vertex j from facet i.
- FACET_WIDTH: common::Integer
The maximal integral width of the polytope with respect to the facet normals.
- FACET_WIDTHS: common::Vector<Integer>
The integral width of the polytope with respect to each facet normal.
- GORENSTEIN: common::Bool
The polytope is Gorenstein if a dilation of the polytope is REFLEXIVE up to translation.
- GORENSTEIN_INDEX: common::Integer
If the polytope is GORENSTEIN then this is the multiple such that the polytope is REFLEXIVE.
- GORENSTEIN_VECTOR: common::Vector<Integer>
If the polytope is GORENSTEIN, then this is the unique interior lattice point in the multiple of the polytope that is REFLEXIVE.
- GROEBNER_BASIS: GroebnerBasis
The Groebner basis for the toric ideal associated to the lattice points in the polytope using any term order.
- LATTICE_BASIS: common::Matrix<Rational, NonSymmetric>
VERTICES are interpreted as coefficient vectors for this basis given in affine form assumed to the the standard basis if not explicitely specified.
- LATTICE_CODEGREE: common::Int
COMBINATORIAL_DIM+1-LATTICE_DEGREE or the smallest integer k such that k*P has an interior lattice point.
- LATTICE_EMPTY: common::Bool
True if the polytope contains no lattice points other than the vertices.
- NORMAL: common::Bool
The polytope is normal if the cone spanned by P x {1} is generated in height 1.
- SMOOTH: common::Bool
The polytope is smooth if the associated projective variety is smooth; the determinant of the edge directions is +/-1 at every vertex.
- TERMINAL: common::Bool
The polytope is terminal if there is exactly one interior lattice point and all other lattice points are vertices.
- VERY_AMPLE: common::Bool
The polytope is very ample if the Hilbert Basis of the cone spanned by the edge-directions of any vertex lies inside the polytope.
User Methods of LatticePolytope
These methods capture information that depends on the lattice structure of the cone. polymake always works with the integer lattice.
- FACET_POINT_LATTICE_DISTANCES (v) → Vector<Integer>
Vector containing the distances of a given point v from all facets
- POLYTOPE_IN_STD_BASIS (P) → Polytope<Rational>
returns a polytope in the integer lattice basis if a LATTICE_BASIS is given
- 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.
- 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.
- 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.
- MAXIMAL_FACE: common::Set<Int>
Indices of vertices at which the maximum of the objective function is attained.
- MAXIMAL_VALUE: LinearProgram::Scalar
Maximum value of the objective function. Negated if linear problem is unbounded.
- MAXIMAL_VERTEX: common::Vector
Coordinates of a (possibly not unique) affine vertex at which the maximum of the objective function is attained.
- RANDOM_EDGE_EPL: common::Vector<Rational>
Expected average path length for a simplex algorithm employing "random edge" pivoting strategy.
User Methods of LinearProgram
- VERTEX_IN_DEGREES ()
Array of in-degrees for all nodes of DIRECTED_GRAPH or numbers of objective decreasing edges at each vertex
- VERTEX_OUT_DEGREES ()
Array of out-degrees for all nodes of DIRECTED_GRAPH or numbers of objective increasing edges at each vertex
- Category: Symmetryderived from: SymmetricPolytope
A symmetric polytope defined as the convex hull of the orbit of a single point under a permutation group acting on coordinates.
Type Parameters
Scalar default: RationalProperties of OrbitPolytope
- 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 GEN_POINT with respect to the GENERATING_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
A matrix of representatives of all certifiers for GEN_POINT with respect to the GENERATING_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
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).
- 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: RationalProperties 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
Contained in extensionbundled:group
. - GRAPH: graph::Graph<Undirected>
Graph of the point configuration. Two points are adjacent if they lie in a common edge of the CONVEX_HULL.
- MAX_BOUNDARY_SIMPLICES: common::Array<Set<Int>>
Tells the full-dimensional simplices on the boundary that contain no points except for the vertices.
Contained in extensionbundled:group
. - MAX_INTERIOR_SIMPLICES: common::Array<Set<Int>>
Tells the full-dimensional simplices that contain no points except for the vertices.
Contained in extensionbundled:group
. - N_MAX_BOUNDARY_SIMPLICES: common::Int
Tells the number of MAX_BOUNDARY_SIMPLICES
Contained in extensionbundled:group
. - N_MAX_INTERIOR_SIMPLICES: common::Int
Tells the number of MAX_INTERIOR_SIMPLICES
Contained in extensionbundled:group
. - SIMPLEXITY_LOWER_BOUND: common::Int
A lower bound for the minimal number of simplices in a triangulation
Contained in extensionbundled:group
. - 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
The polytope being the convex hull of the point configuration.
Properties of CONVEX_HULL
These properties are for input only. They allow redundant information.
These properties collect information about triangulations of the object and properties usually computed from such, as the volume.
- POLYTOPAL_SUBDIVISION: fan::PolyhedralComplex
Polytopal Subdivision of the point configuration
Properties of POLYTOPAL_SUBDIVISION
- REFINED_SPLITS: common::Set<Int>
The splits that are coarsenings of the subdivision. If the subdivision is regular these form the unique split decomposition of the corresponding weight function.
- TRIANGULATION: topaz::GeometricSimplicialComplex
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: topaz::SimplicialComplex
Specialization of topaz::SimplicialComplex::BOUNDARY for PointConfiguration::TRIANGULATION
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 - 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
User Methods of PointConfiguration
These methods collect information about triangulations of the object and properties usually computed from such, as the volume.
- TRIANGULATION_SIGNS () → Array<Int>
For each simplex in the TRIANGULATION, this contains the sign of the determinant of its coordinate matrix, which is the orientation of the simplex.
Returns
Array<Int>
These methods are for visualization.
- VISUAL () → Visual::PointConfiguration
Visualize a point configuration.
- VISUAL_POINTS () → Visual::PointSet
Visualize the POINTS of a point configuration.
Options
option list: Visual::Polygons::decorations Returns
Visual::PointSet
- derived from: Cone
Not necessarily bounded or unbounded polyhedron. Nonetheless, the name "Polytope" is used for two reasons: Firstly, combinatorially we always deal with polytopes; see the description of VERTICES_IN_FACETS for details. The second reason is historical. We use homogeneous coordinates, which is why Polytope is derived from Cone. Note that a pointed polyhedron is projectively equivalent to a polytope. Scalar is the numeric data type used for the coordinates.
Specializations of Polytope
- 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<QuadraticExtension>
A pointed polyhedron with coordinates in a QuadraticExtension field realized in Rd.
Convex hull and related algorithms use exact quadratic extension fields for arithmetics.
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.
- ALTSHULER_DET: common::Integer
Let M be the vertex-facet incidence matrix, then the Altshulter determinant is defined as max{det(M ∗ MT), det(MT ∗ M)}.
- DUAL_BOUNDED_H_VECTOR: common::Vector<Integer>
h-vector of the bounded subcomplex, defined for not necessarily bounded polyhedra which are simple (as polyhedra, i.e., VERTEX_DEGREES on the FAR_FACE do not matter). Coincides with the reverse h-vector of the dual simplicial ball. Note that this vector will usually start with a number of zero entries.
- DUAL_H_VECTOR: common::Vector<Integer>
dual h-vector, defined via recursion on the face lattice of a polytope. Coincides for simple polytopes with the combinatorial definition of the h-vector via abstract objective functions.
- 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.
- 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.
- 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.
- FACETS_THRU_VERTICES: common::IncidenceMatrix<NonSymmetric>
transposed VERTICES_IN_FACETS Notice that this is a temporary property; it will not be stored in any file. Alias for property FACETS_THRU_RAYS.
- 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.
Contained in extensionbundled:group
. - GRAPH: graph::Graph<Undirected>
Specialization of Cone::GRAPH for Polytope
Properties of GRAPH
- EDGE_DIRECTIONS: common::EdgeMap
Difference of the vertices for each edge (only defined up to signs).
- G_VECTOR: common::Vector<Integer>
(Toric) g-vector, defined via the (generalized) h-vector as gi = hi - hi-1.
- 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.
- N_VERTEX_FACET_INC: common::Int
Number of pairs of incident vertices and facets. Alias for property N_RAY_FACET_INC.
- SIMPLEXITY_LOWER_BOUND: common::Int
A lower bound for the minimal number of simplices in a triangulation
Contained in extensionbundled:group
. - SUBRIDGE_SIZES: common::Map<Int, Int>
Lists for each occurring size (= number of incident facets or ridges) of a subridge how many there are.
- TWO_FACE_SIZES: common::Map<Int, Int>
Lists for each occurring size (= number of incident vertices or edges) of a 2-face how many there are.
- VERTEX_SIZES: common::Array<Int>
Number of incident facets for each vertex. Alias for property RAY_SIZES.
- VERTICES_IN_FACETS: common::IncidenceMatrix<NonSymmetric>
Vertex-facet incidence matrix, with rows corresponding to facets and columns to vertices. Vertices and facets are numbered from 0 to N_VERTICES-1 rsp. N_FACETS-1, according to their order in VERTICES rsp. FACETS.
This property is at the core of all combinatorial properties. It has the following semantics: (1) The combinatorics of an unbounded and pointed polyhedron is defined to be the combinatorics of the projective closure. (2) The combiantorics of an unbounded polyhedron which is not pointed is defined to be the combinatorics of the quotient modulo the lineality space. Therefore: VERTICES_IN_FACETS and each other property which is grouped under "Combinatorics" always refers to some polytope. Alias for property RAYS_IN_FACETS.
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 LINEAR_SPAN.
- CENTERED: common::Bool
True if (1, 0, 0, ...) is in the relative interior. If full-dimensional then polar to BOUNDED.
- 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.
- 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
- FACETS_THRU_POINTS: common::IncidenceMatrix<NonSymmetric>
similar to FACETS_THRU_VERTICES, but with POINTS instead of VERTICES Notice that this is a temporary property; it will not be stored in any file. Alias for property FACETS_THRU_INPUT_RAYS.
- INEQUALITIES_THRU_VERTICES: common::IncidenceMatrix<NonSymmetric>
transposed VERTICES_IN_INEQUALITIES Alias for property INEQUALITIES_THRU_RAYS.
- LATTICE: common::BoolOnly defined for Polytope<Rational>
This is the defining property: A polytope is lattice if each 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.
- POINTS_IN_FACETS: common::IncidenceMatrix<NonSymmetric>
Similar to VERTICES_IN_FACETS, but with columns corresponding to POINTS instead of VERTICES. This property is a byproduct of convex hull computation algorithms. It is discarded as soon as VERTICES_IN_FACETS is computed. Alias for property INPUT_RAYS_IN_FACETS.
- QUOTIENT_SPACE: QuotientSpace
A topological quotient space obtained from a polytope by identifying faces.
Contained in extensionbundled:group
. - 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.
- 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 RAY_SEPARATORS.
- 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 RAYS.
- VERTICES_IN_INEQUALITIES: common::IncidenceMatrix<NonSymmetric>
Similar to VERTICES_IN_FACETS, but with rows corresponding to INEQUALITIES instead of FACETS. This property is a byproduct of convex hull computation algorithms. It is discarded as soon as VERTICES_IN_FACETS is computed. Alias for property RAYS_IN_INEQUALITIES.
- 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.
- 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 INPUT_RAYS.
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.
- 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.
Everything in this group is defined for BOUNDED polytopes only.
- POLYTOPAL_SUBDIVISION: fan::PolyhedralComplex
Polytopal Subdivision of the polytope using only its vertices.
Properties of POLYTOPAL_SUBDIVISION
- REFINED_SPLITS: common::Set<Int>
The splits that are coarsenings of the subdivision. If the subdivision is regular these form the unique split decomposition of the corresponding weight function.
- 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.
- SQUARED_RELATIVE_VOLUMES: common::Array
Array of the squared relative k-dimensional volumes of the simplices in a triangulation of a d-dimensional polytope.
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: fan::PolyhedralComplex<Rational>
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::Graph<Undirected>
Specialization of fan::PolyhedralFan::GRAPH for Polytope::BOUNDED_COMPLEX
Properties of GRAPH
- EDGE_COLORS: common::EdgeMap<Undirected, Int>
Each edge indicates the maximal dimension of a bounded face containing it. Mainly used for visualization purposes.
- EDGE_DIRECTIONS: common::EdgeMap
Difference of the vertices for each edge (only defined up to signs).
- 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<List<Int>>
Reordered transposed VERTICES_IN_FACETS. Dual to VIF_CYCLIC_NORMAL. Alias for property FTR_CYCLIC_NORMAL.
- GALE_VERTICES: common::Matrix<Float, NonSymmetric>
Coordinates of points for an affine Gale diagram.
- NEIGHBOR_VERTICES_CYCLIC_NORMAL: common::Array<List<Int>>
Reordered GRAPH. Dual to NEIGHBOR_FACETS_CYCLIC_NORMAL. Alias for property NEIGHBOR_RAYS_CYCLIC_NORMAL.
- SCHLEGEL_DIAGRAM: SchlegelDiagram
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), you can create the labels automatically if you call the function with a relabel option. The exact format of the labels is dependent on the construction, and is described in the corresponding help topic.
- VIF_CYCLIC_NORMAL: common::Array<Array<Int>>
Reordered VERTICES_IN_FACETS for 2d and 3d-polytopes. Vertices are listed in the order of their appearance when traversing the facet border counterclockwise seen from outside of the polytope.
For a 2d-polytope (which is a closed polygon), lists all vertices in the border traversing order. Alias for property RIF_CYCLIC_NORMAL.
User Methods of Polytope
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 ()
Prettily print the cd-index given in CD_INDEX_COEFFICIENTS
- N_RIDGES ()
The number of ridges (faces of codimension 2) of the polytope equals the number of edges of the DUAL_GRAPH
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 ()
returns the dimension of the ambient space of the polytope
- contains (P, v) → Boolean
checks whether a given point is contained in a polytope
- contains_in_interior (P, v) → Boolean
checks whether a given point is contained in the strict interior of a polytope
- DIM ()
returns the dimension of the polytope
- 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>
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>
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 polytope. polymake always works with the integer lattice.
- LATTICE_POINTS () → Matrix<Integer>
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 - TRIANGULATION_SIGNS () → Array<Int>
For each simplex in the TRIANGULATION, contains the sign of the determinant of its coordinate matrix, telling about its orientation.
Returns
Array<Int>
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
Generate the Gale diagram of a d-polyhedron with at most d+4 vertices.
Returns
Visual::Gale - SCHLEGEL () → Visual::SchlegelDiagram
Create a Schlegel diagram and draw it.
Options
FIXME proj_facet decorations for the Edges of the projection 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::Polygons
- VISUAL_DUAL_FACE_LATTICE () → Visual::PolytopeLattice
Visualize the dual face lattice of a polyhedron as a multi-layer graph.
Options
Int seed random seed value for the node 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_TRIANGULATION_BOUNDARY () → Visual::Polygons
Visualize the TRIANGULATION_BOUNDARY of the polytope. Obsolete: the preferred procedure is to create a SimplicialComplex using the boundary_complex client of the application topaz and call its VISUAL method. FIXME: There is no boundary_complex in topaz.
Options
option list: Visual::Polygon::decorations Returns
Visual::Polygons
- 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::Graph<Directed>
Directed graph to define the propagated polytope. There is a (translation) vector assigned to each arc. We assume that this graph is acyclic with a unique sink.
Properties of SUM_PRODUCT_GRAPH
- Category: Symmetry
A topological quotient space obtained from a Polytope by identifying faces. This object will sit inside the polytope.
Contained in extensionbundled:group
.Properties of QuotientSpace
Properties defining a quotient space.
- IDENTIFICATION_GROUP: group::Group
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<Array<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<boost_dynamic_bitset>
The (d-1)-dimensional simplices in the interior.
- REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES: common::Array<boost_dynamic_bitset>
The boundary (d-1)-dimensional simplices of a cone of combinatorial dimension d
- REPRESENTATIVE_MAX_INTERIOR_SIMPLICES: common::Array<boost_dynamic_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
pm::perl::Hash proj_facet decoration for the edges of the projection faceoption list: Visual::Graph::decorations Returns
Visual::SchlegelDiagram
- Category: Symmetryderived from: Cone
A cone which is generated by a group and a generating set of inequalities (+equations) or input rays (+input_lineality). The cone is the intersection or the convex hull of all inequalities or input rays in the orbit of the generating set under the GENERATING_GROUP.
Type Parameters
Scalar default: RationalProperties of SymmetricCone
- GENERATING_GROUP: group::GroupOfCone
The group which generates the cone by being applied to some GEN_INPUT_RAYS (and GEN_INPUT_LINEALITY) or some GEN_INEQUALITIES (and GEN_EQUATIONS).
- GEN_EQUATIONS: common::Matrix
Some generating equations for (a subset of) the linear span of the symmetric cone. Redundancies are allowed.
Input section only.
- GEN_INEQUALITIES: common::Matrix
Some generating inequalities for the symmetric cone; redundancies are allowed.
Input section only. Ask for REPRESENTATIVE_FACETS if you want a list of representatives for the orbits of facets of a symmetric cone.
- GEN_INPUT_LINEALITY: common::Matrix
Some generating input rays for (a subset of) the lineality space of the symmetric cone. Redundancies are allowed.
Input section only.
- GEN_INPUT_RAYS: common::Matrix
Some generating input rays for the symmetric cone; redundancies are allowed.
Input section only. Ask for REPRESENTATIVE_RAYS if you want a list of representatives for the orbits of rays of a symmetric cone.
User Methods of SymmetricCone
- VISUAL_ORBIT_COLORED_GRAPH () → Visual::ConeGraph
Visualizes the graph of a symmetric cone: All nodes belonging to one orbit get the same color.
Options
option list: Visual::Graph::decorations Returns
Visual::ConeGraph
- Category: Symmetryderived from: SymmetricCone
A polytope which is generated by a group and a generating set of inequalities (+equations) or points (+input_lineality). The polytope is the intersection or the convex hull of all inequalities or points in the orbit of the generating set under the GENERATING_GROUP.
Type Parameters
Scalar default: RationalProperties of SymmetricPolytope
User Methods of SymmetricPolytope
- AMBIENT_DIM ()
must be copied (from common.rules) since SymmetricPolytope is derived from both objects, SymmetricCone and Polytope
- DIM ()
must be copied (from common.rules) since SymmetricPolytope is derived from both objects, SymmetricCone and Polytope
- derived from: Polytope
Bounded subcomplex of an unbounded polyhedron, which is associated with a finite metric space. The tight span is 1-dimensional if and only if the metric is tree-like. In this sense, the tight span captures the deviation of the metric from a tree-like one.
Properties of TightSpan
Properties of a TightSpan
- TAXA: common::Array<String>
Labels for the rows and columns of the METRIC space. Default TAXA are just consecutive numbers.
User Methods of TightSpan
These methods are for visualization.
- VISUAL_BOUNDED_GRAPH () → Visual::PolytopeGraph
Visualize the BOUNDED_COMPLEX.GRAPH of a tight span.
Options
Int seed random seed value for the string embedderoption list: Visual::Graph::decorations Returns
Visual::PolytopeGraph - VISUAL_SPLITS () → Visual::FiniteMetricSpace
Visualize the splits of a finite metric space (that is, a planar image of a tight span). Calls SplitsTree.
Returns
Visual::FiniteMetricSpace - VISUAL_TIGHT_SPAN () → Visual::Graph
This is a variation of Polytope::VISUAL_BOUNDED_GRAPH for the special case of a tight span. The vertices are embedded according to the METRIC, the others are hanged in between.
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.
These properties are for input only. They allow redundant information.
Properties which belong to the corresponding (oriented) matroid
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.
- Category: Visualization
Visualization of the point configuration.
User Methods of Visual::PointConfiguration
- POLYTOPAL_SUBDIVISION () → Visual::PointConfiguration
Visualize the POLYTOPAL_SUBDIVISION of a point configuration.
- TRIANGULATION () → Visual::PointConfiguration
Visualize the TRIANGULATION of a point configuration
- TRIANGULATION_BOUNDARY () → Visual::PointConfiguration
Draw the edges of the TRIANGULATION_BOUNDARY. The facets are made transparent.
- 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.
- LATTICE () → Visual::Polytope
Visualize the LATTICE_POINTS of a polytope
- LATTICE_COLORED () → Visual::Polytope
Visualize the LATTICE_POINTS of a polytope in different colors (interior / boundary / vertices)
- 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 - STEINER () → Visual::Polytope
Add the STEINER_POINTS to the 3-d visualization. The facets become transparent.
- TRIANGULATION (t) → Visual::Polytope
Add the triangulation to the drawing. The facets of the whole polytope become transparent.
You may specify any triangulation of the current polytope. Per default, the TRIANGULATION property is taken. (Currently there is only one possible alternative triangulation: TRIANGULATION_INT).
Hint: Use the method Method -> Effect -> Explode Group of Geometries of JavaView for better insight in the internal structure.
Parameters
Array<Set<Int>> t facets of the triangulationOptions
option list: Visual::Polygons::decorations Returns
Visual::Polytope - TRIANGULATION_BOUNDARY () → Visual::Polytope
Draw the edges of the TRIANGULATION_BOUNDARY. The facets are made transparent.
- 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
- 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 ()
UNDOCUMENTED
Options
option list: Visual::PointSet::decorations - 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 VoronoiDiagram becomes a derived class from Polytope<Scalar>.
Properties of VoronoiDiagram
- 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 VoronoiDiagram to produce proper iterated Voronoi diagrams.
- NN_CRUST_GRAPH: graph::Graph<Undirected>
Graph of the nearest neighbor crust, as defined in:
T. K. Dey and P. Kumar: A simple provable algorithm for curve reconstruction. Proc. 10th. Annu. ACM-SIAM Sympos. Discrete Alg., 1999, 893-894.
Polygonal reconstruction of a smooth planar curve from a finite set of samples. Sampling rate of <= 1/3 suffices.
- NN_GRAPH: graph::Graph<Undirected>
Graph of the nearest neighbors. This is a subgraph of NN_CRUST_GRAPH.
- SITES: common::Matrix
Coordinates of the sites in case the polyhedron is Voronoi. Sites must be pairwise distinct.
- 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 VoronoiDiagram
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.
Options
option list: Visual::Graph::decorations Returns
Visual::Container - VISUAL_NN_CRUST () → Visual::Container
Draw a Voronoi diagram, its dual graph and the nearest neighbor crust. Use the interactive features of the viewer to select.
Options
option list: Visual::Graph::decorations Returns
Visual::Container - VISUAL_VORONOI () → Visual::Container
Draw a Voronoi diagram and its dual. Use the interactive features of the viewer to select.
Options
option list: Visual::Graph::decorations Returns
Visual::Container
User Functions
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> - contraction (C, v)
Contract a vector configuration C along a specified vector v.
Parameters
VectorConfiguration C Int v index of the vector to contract - deletion (C, v)
Delete a specified vector v from a vector configuration C.
Parameters
VectorConfiguration C Int v index of the vector to delete - quotient_of_triangulation (T, G, R) → SparseVector
In a triangulation T, find the number of representatives of simplices wrt to G, and return the counts in the order indicated by the array R
Contained in extensionbundled:group
.Parameters
Array<Set> T the input triangulation,Array<Array<Int>> G the generators of the symmetry groupArray<Set> R the canonical lex-min representatives of the simplicesOptions
Bool foldable is the triangulation foldable?Returns
SparseVector V the number of times a simplex G-isomorphic to each representative in R occurs in T
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. 4 - equal_polyhedra (P1, P2) → Bool
- 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 permutations - included_polyhedra (P1, P2) → Bool
- isomorphic (P1, P2) → Bool
- 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
LatticePolytope P1 the first lattice polytopeLatticePolytope P2 the second lattice polytopeReturns
Bool 'true' if the polytopes are lattice equivalent, 'false' otherwise
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.
- 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
- 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 otherwise
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.
- 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
deg output in degrees rather than radians, default 0cone hyperplanes seen as linear hyperplanes, default 0Returns
Float - induced_lattice_basis (p) → Matrix<Integer>
Returns a basis of the affine lattice spanned by the vertices
- integer_points_bbox (P) → Matrix<Integer>
Enumerate all integer points in the given polytope by searching a bounding box.
- is_vertex (q, points) → Bool
Checks whether a given point q is a vertex of the polytope P generated by q and a set of other points points via solving a suitable LP (compare cdd redundancy check). Works without knowing the facets of P!
- minimal_vertex_angle (P) → Float
- normaliz_compute (C) → perl::ListReturn
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 extensionbundled:libnormaliz
.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 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
perl::ListReturn (degree one generators, Hilbert basis, Hilbert h-vector, Hilbert series, facets, linear_span, rays) (if they are requested) - 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 - steiner_point (P) → Vector
- 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
lattice_origin_is_vertex Bool 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
These functions provide tools from linear, integer and dicrete optimization. In particular, linear programs are defined here.
- core_point_algo (p, optLPvalue) → perl::ListReturn
Algorithm to solve highly symmetric integer linear programs (ILP). It is required that the group of the ILP induces the alternating or symmetric group on the set of coordinate directions. The linear objective function is the vector (0,1,1,..,1).
- core_point_algo_Rote (p, optLPvalue) → perl::ListReturn
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) → perl::ListReturn
Algorithm to solve symmetric linear programs (LP) of the form max ctx , c=(0,1,1,..,1) subject to the inequality system given by Inequalities. It is required that the symmetry group of the LP acts transitively on the coordinate directions.
Parameters
Matrix Inequalities the inequalities describing the feasible regionReturns
perl::ListReturn (optLPsolution,optLPvalue,feasible,max_bounded) - inner_point (points)
- lp2poly (file, testvec, prefix) → Polytope
Read a linear programming problem given in LP-Format (as used by cplex & Co.) and convert it to a Polytope<Scalar=Rational> object. By default Rational is used as coordinate type, but lp2poly<Float>("filename.lp") can be used to create a Polytope with Float coordinates.
WARNING The property FEASIBLE is NOT computed upon creation. This is done to avoid possibly long computation times before the object becomes available to the caller. This is NOT in keeping with standard practice in polymake, but after, all, these are linear programs and not polytopes.
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
Int nocheck Do not automatically compute FEASIBLE for the polytope (recommended for very large LPs)Returns
Polytope <Scalar=Rational> - 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 - 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) → Bool
Write the FACETS / INEQUALITIES and the LINEAR_SPAN / EQUATIONS 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 rowsReturns
Bool - 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> - rel_int_point (P)
Computes a relative interior point of a polyhedron P and stores it in P->REL_INT_POINT. The unbounded flag needs to be set to true if the polyhedron could be unbounded.
Parameters
Polytope P - separating_hyperplane (q, points) → ListReturn
Computes (the normal vector of) a hyperplane which separates a given point q from points via solving a suitable LP. The scalar product of the normal vector of the separating hyperplane and a point in points is greater or equal than 0 (same behavior as for facets!). If q is not a vertex of P=conv(points,q), the function returns a zero vector and sets answer to 'false'. Works without knowing the facets of P!
- separating_hyperplane_poly (p1, p2) → Vector
- 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> - write_foldable_max_signature_ilp (P, outfile_name)
- write_simplexity_ilp (P, outfile_name)
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 - violations (P, q) → Set
- 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 coefficientsScalar<Rational> s additional Parameter in the polynomialOptions
topaz::SimplicialComplex triangulation The triangulation of the pointset corresponding to the lifting functionRing ring the ring in which the polynomial should be - 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 coefficientsScalar<Rational> s additional Parameter in the polynomialOptions
topaz::SimplicialComplex triangulation The triangulation of the pointset corresponding to the lifting functionRing ring the ring in which the polynomial should be
Various constructions of cones.
- normal_cone (p, v, outer) → Cone
- 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.
- minkowski_sum (lambda, P1, mu, P2) → PointConfiguration
Produces the polytope lambda*P1+mu*P2, where * and + are scalar multiplication and Minkowski addition, respectively.
Polytope constructions which take graphs as input.
- cut_polytope (G) → 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 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 - 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.
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)
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 noc : don't compute the coordinates, purely combinatorial description is produced.Bool relabel copy the vertex labels from the original polytope, label the new vertices with "Apex" and "Apex'". - blending (P1, v1, P2, v2) → Polytope
Compute the blending of two polyhedra at simple vertices. This is a slightly less standard construction. A vertex is simple if its vertex figure is a simplex.
Moving a vertex v of a bounded polytope to infinity yields an unbounded polyhedron with all edges through v becoming mutually parallel rays. Do this to both input polytopes P1 and P2 at simple vertices v1 and v2, respectively. Up to an affine transformation one can assume that the orthogonal projections of P1 and P2 in direction v1 and v2, respectively, are mutually congruent.
Any bijection b from the set of edges through v1 to the edges through v2 uniquely defines a way of glueing the unbounded polyhedra to obtain a new bounded polytope, the blending with respect to b. The bijection is specified as a permutation of indices 0 1 2 etc. The default permutation is the identity.
The number of vertices of the blending is the sum of the numbers of vertices of the input polytopes minus 2. The number of facets is the sum of the numbers of facets of the input polytopes minus the dimension.
The resulting polytope is described only combinatorially.
- 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.
The option relabel creates an additional section VERTEX_LABELS.
- 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.
The option relabel creates an additional section VERTEX_LABELS.
- cayley_polytope (P_Array) → Polytope
Construct the cayley polytope of a set of pointed lattice polytopes contained in P_Array which is the convex hull of P1×e1, ..., Pk×ek where e1, ...,ek are the standard unit vectors in Rk. In this representation the last k coordinates always add up to 1. The option proj projects onto the complement of the last coordinate.
Parameters
Array<LatticePolytope> P_Array an array containing the lattice polytopes P1,...,PkOptions
Bool proj Returns
Polytope - cells_from_subdivision (P, cells) → Polytope<Scalar>
Extract the given cells of the subdivision of a polyhedron and write their union as a new polyhedron.
Parameters
Polytope<Scalar> P Set<Int> cells Options
Bool relabel copy the vertex labels from the original polytopeReturns
Polytope<Scalar> - cell_from_subdivision (P, cell) → Polytope
- conv (P_Array) → PropagatedPolytope
Construct a new polyhedron as the convex hull of the polyhedra given in P_Array.
- 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
- facet_to_infinity (i) → Polytope
- 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.
- join_polytopes (P1, P2) → Polytope
- lattice_bipyramid (P, v, v_prime, z, z_prime) → Polytope
Make a lattice bipyramid over a polyhedron. The bipyramid is the convex hull of the input polyhedron P and two points (v, z), (v_prime, z_prime) on both sides of the affine span of P.
Parameters
Polytope P Vector v basis point for the first 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 relabel copy the vertex labels from the original polytope, label the new vertices with "Apex" and "Apex'".Returns
Polytope - lattice_pyramid (P, z, v) → Polytope
Make a lattice pyramid over a polyhedron. The pyramid is the convex hull of the input polyhedron P and a point v outside the affine span of P.
- lawrence (P) → Cone
Create the Lawrence polytope Lambda(P) corresponding to P. If V is the matrix whose rows are the n vertices of P, then the vertices of Lambda(P) are the rows of the matrix ( V I_n ) ( 0_n I_n ). Lambda(P) has the property that Gale(Lambda(P)) = Gale(P) union -Gale(P).
- 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".
- minkowski_sum (P1, P2) → Polytope
- minkowski_sum (lambda, P1, mu, P2) → Polytope
- minkowski_sum_fukuda <Scalar> (summands) → Polytope<Scalar>
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. - 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 noc only combinatorial information is handledBool relabel creates an additional section VERTEX_LABELS; the bottom facet vertices get the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended.Returns
Polytope - product (P1, P2) → Polytope
Construct a new polytope as the product of two given polytopes P1 and P2.
- 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 - projection_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.
- 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.
- 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.
- 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 noc produces a pure combinatorial description (in contrast to lift)Bool relabel creates an additional section VERTEX_LABELS; New vertices get labels 'f(FACET_LABEL)' in the simplicial case, and 'f(FACET_LABEL)-NEIGHBOR_VERTEX_LABEL' in the cubical case.Returns
Polytope - stellar_all_faces (P, d) → Polytope
Perform a stellar subdivision of all proper faces, starting with the facets.
Parameter d specifies the lowest dimension of the faces to be divided. It can also be negative, then treated as the co-dimension. Default is 1, that is, the edges of the polytope.
- 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.
- truncation (P, trunc_vertices) → Polytope
Cut off one or more vertices of a polyhedron.
The exact location of the cutting hyperplane(s) can be controlled by the option cutoff, a rational number between 0 and 1. When cutoff=0, the hyperplane would go through the chosen vertex, thus cutting off nothing. When cutoff=1, the hyperplane touches the nearest neighbor vertex of a polyhedron.
Alternatively, the option noc (no coordinates) can be specified to produce a pure combinatorial description of the resulting polytope, which corresponds to the cutoff factor 1/2.
Parameters
Polytope P Set<Int> trunc_vertices the vertex/vertices to be cut off; A single vertex to be cut off is specified by its number. Several vertices can be passed in a Set or in an anonymous array of indices: [n1,n2,...] Special keyword All means that all vertices are to be cut off.Options
Scalar cutoff controls the exact location of the cutting hyperplane(s); rational number between 0 and 1; default value: 1/2Bool noc produces a pure combinatorial description (in contrast to cutoff)Bool relabel creates an additional section VERTEX_LABELS; New vertices get labels of the form 'LABEL1-LABEL2', where LABEL1 is the original label of the truncated vertex, and LABEL2 is the original label of its neighbor.Returns
Polytope - unirand (Polytope, n) → Polytope
Produce a polytope with n random points that are uniformly distributed within the given polytope P. P must be bounded and full-dimensional.
- vertex_figure (p, n) → 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 noc skip the coordinates computation, producing a pure combinatorial description.Bool relabel inherit vertex labels from the corresponding neighbor vertices of the original polytope.Returns
Polytope - wedge (P, facet, z, z_prime) → Polytope
Make a wedge from a polytope over the given facet. The polytope must be bounded. The inclination of the bottom and top side facet is controlled by z and z_prime, which are heights of the projection of the old vertex barycenter on the bottom and top side facet respectively.
Parameters
Polytope P , must be boundedInt facet the `cutting edge'.Scalar z default value is 0.Scalar z_prime default value is -z, or 1 if z==0.Options
Bool noc don't compute coordinates, pure combinatorial description is produced.Bool relabel create vertex labels: The bottom facet vertices obtain the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended.Returns
Polytope
With these clients you can create polytopes belonging to various parameterized families which occur frequently in polytope theory, as well as random polytopes with different models of randomness.
- associahedron (d) → Polytope
- binary_markov_graph (observation) → PropagatedPolytope
Defines a very simple graph for a polytope propagation related to a Hidden Markov Model. The propagated polytope is always a polygon. For a detailed description see
M. Joswig: Polytope propagation, in: Algebraic statistics and computational biologyby L. Pachter and B. Sturmfels (eds.), Cambridge, 2005. - binary_markov_graph (observation)
Parameters
String observation encoded as a string of "0" and "1". - constructible_n_gon () → 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 polytopeReturns
Polytope<Scalar> - 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 polytopeReturns
Polytope<Scalar> - cuboctahedron () → Polytope
- cyclic (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 (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.
- cyclic_caratheodory (d, n) → Polytope
- delpezzo (d, scale) → Polytope<Scalar>
Produce a d-dimensional del-Pezzo polytope. 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> - dodecahedron () → Polytope
- 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.
- fano_simplex (d) → Polytope
- goldfarb (d, e, g) → Polytope
Produces a d-dimensional Goldfarb cube if e<1/2 and g<=e/4. The Goldfarb cube is a combinatorial cube and yields a bad example for the Simplex Algorithm using the Shadow Vertex Pivoting Strategy. Here we use the description as a deformed product due to Amenta and Ziegler. For e<1/2 and g=0 we obtain the Klee-Minty cubes.
- hypersimplex (k, d) → Polytope
- 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> - icosahedron () → Polytope
- icosidodecahedron () → Polytope
- knapsack (b) → Polytope
Produce a knapsack polytope defined by one linear inequality (and non-negativity constraints).
- k_cyclic (n, s) → Polytope
Produce a (rounded) 2*k-dimensional k-cyclic polytope with n points, where k is the length of the input vector s. Special cases are the bicyclic (k=2) and tricyclic (k=3) polytopes. Only possible in even dimensions.
The parameters s_i can be specified as integer, floating-point, or rational numbers. The coordinates of the i-th point are taken as follows:
cos(s_1 * 2πi/n),sin(s_1 * 2πi/n),...cos(s_k * 2πi/n),sin(s_k * 2πi/n)Warning: Some of the k-cyclic polytopes are not simplicial. Since the components are rounded, this function might output a polytope which is not a k-cyclic polytope!
More information can be found in the following references:
P. Schuchert: "Matroid-Polytope und Einbettungen kombinatorischer Mannigfaltigkeiten",PhD thesis, TU Darmstadt, 1995.Z. Smilansky: "Bi-cyclic 4-polytopes",Isr. J. Math. 70, 1990, 82-92 - 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) → LatticePolytope
- perles_irrational_8_polytope () → Polytope
- permutahedron (d) → Polytope
- pile (sizes) → Polytope
Produce a (d+1)-dimensional polytope from a pile of cubes. Start with a d-dimensional pile of cubes. Take a generic convex function to lift this polytopal complex to the boundary of a (d+1)-polytope.
Parameters
Vector<Int> sizes a vector (s1,...,sd, where si specifies the number of boxes in the i-th dimension.Returns
Polytope - platonic_solids () → Array<Polytope<QuadraticExtension>>
Produce the list of all five Platonic solids with ascending number of vertices.
- pseudo_delpezzo (d, scale) → Polytope<Scalar>
Produce a d-dimensional del-Pezzo polytope. 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> - 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 (d, n) → Polytope
- regular_120_cell () → Polytope
- regular_24_cell () → Polytope
- regular_600_cell () → Polytope
- regular_simplex (d) → Polytope
- rhombicosidodecahedron () → Polytope
- rss_associahedron (l) → Polytope
Produce a polytope of constrained expansions in dimension l according to
Rote, Santos, and Streinu: Expansive motions and the polytope of pointed pseudo-triangulations.Discrete and computational geometry, 699--736, Algorithms Combin., 25, Springer, Berlin, 2003. - signed_permutahedron (d) → Polytope
- simplex (d, scale) → Polytope
- 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 - stable_set (G) → Polytope
- tetrahedron () → Polytope
- transportation (r, c) → Polytope
- truncated_cuboctahedron () → SymmetricPolytope
Create truncated cuboctahedron. An Archimedean solid. This is actually a misnomer. The actual truncation of a cuboctahedron is obtained as wythoff(B3,range(0,2)), which is rational and normally equivalent to this construction.
Contained in extensionbundled:group
.Returns
SymmetricPolytope - 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 - upper_bound_theorem (d, n) → 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
- zonotope <Scalar> (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.
Type Parameters
Scalar target coordinate typeParameters
Matrix<Scalar> M input points or vectorsOptions
Bool rows_are_points true if M are points instead of vectors; default trueReturns
Polytope<Scalar> the zonotope generated by the input points or vectors - zonotope_vertices_fukuda <Scalar> (M) → Polytope<Scalar>
Create a zonotope from a matrix whose rows are input points or vectors.
Type Parameters
Scalar Parameters
Matrix<Scalar> M Options
Bool centered_zonotope default 1Returns
Polytope<Scalar>
Functions producing big objects which are not contained in application polytope.
- coxeter_group (type) → group::GroupOfPolytope
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_*.
Parameters
String type the type of the Coxeter groupReturns
group::GroupOfPolytope the Coxeter group of type type - crosscut_complex (p) → SimplicialComplex
Produce the crosscut complex of the boundary of a 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.
Contained in extensionbundled:group
.Parameters
Polytope P , centrally symmetric - cylinder_2 () → Polytope
Return a 2-dimensional cylinder obtained by identifying two opposite sides of a square.
Contained in extensionbundled:group
.Returns
Polytope - 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.
Contained in extensionbundled:group
.Returns
Polytope - quotient_space_faces (P)
Find the faces of the quotient space represented by P and its IDENTIFICATION_GROUP.
Contained in extensionbundled:group
.Parameters
Polytope P - 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.
Contained in extensionbundled:group
.
These functions capture information of the object that is concerned with the action of permutation groups.
- alternating_group (degree, domain) → group::GroupOfPolytope
Constructs an alternating group of given degree. (See also group::alternating_group.)
Contained in extensionbundled:group
. - combinatorial_symmetries (poly, on_vertices) → group::GroupOfPolytope
Compute the combinatorial symmetries (i.e., automorphisms of the face lattice) of a given polytope poly. If on_vertices is set to 1, the function returns a GroupOfPolytope which acts on the vertices. If on_vertices is set to any other number, the function returns a GroupOfPolytope which acts on the facets of the polytope. If on_vertices is unspecified, both groups are returned.
Parameters
Polytope poly Int on_vertices specifies whether the returned group should act on vertices (1) or on facets (2)Returns
group::GroupOfPolytope the combinatorial symmetry group acting on the vertices or the facets depending on on_vertices or (group::GroupOfPolytope, group::GroupOfPolytope) = (group on vertices, group on facets) if //on_vertices is undefined - convert_coord_action (group, mat, dom_out) → group::Group
Converts the generators of a group acting on coordinates to generators of the corresponding group which acts on the rows of the given matrix mat. The parameter dom_out specifies whether mat describes vertices or facets.
Contained in extensionbundled:group
.Parameters
group::Group group input group acting on coordinatesMatrix mat vertices or facets of a polytopeInt dom_out OnRays(1) or OnFacets(2)Options
String name an optional name for the output groupReturns
group::Group a new group object with the generators induced on the new domain - convert_group_domain (group, VIF) → group::Group
Converts the generators of the input group from the domain onRays to generators on the domain onFacets, and vice versa.
Contained in extensionbundled:group
.Parameters
group::Group group IncidenceMatrix VIF the vertex-facet incidence matrix of the cone or polytopeOptions
String name an optional name for the output groupReturns
group::Group a new group object with the generators induced on the new domain - cyclic_group (degree, domain) → group::GroupOfPolytope
Constructs a cyclic group of given degree. (See also group::cyclic_group.)
Contained in extensionbundled:group
. - group_from_cyclic_notation0 (group, domain) → group::GroupOfPolytope
Constructs a group from a string with generators in cyclic notation. All numbers in the string are 0-based. Example: "(0,2)(1,3)"
Contained in extensionbundled:group
.Parameters
String group generators in cyclic notationInt domain of the polytope symmetry groupReturns
group::GroupOfPolytope - group_from_cyclic_notation1 (group, domain) → group::GroupOfPolytope
Constructs a group from a string with generators in cyclic notation. All numbers in the string are 1-based. Example: "(1,3)(2,4)"
Contained in extensionbundled:group
.Parameters
String group generators in cyclic notationInt domain of the polytope symmetry groupReturns
group::GroupOfPolytope - 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
LatticePolytope P the given polytopeReturns
Array<Array<Int>> the generating set for the lattice automorphism group - lex_min_representative (G, S) → Set
- linear_symmetries (c, dual) → group::GroupOfCone
Computes the linear symmetries of a given polytope p via 'sympol'. If the input is a cone, it may compute only a subgroup of the linear symmetry group.
Contained in extensionbundled:group
.Parameters
Cone c the cone (or polytope) whose linear symmetry group is to be computedBool dual true if group action on vertices, false if action on facetsReturns
group::GroupOfCone the linear symmetry group of p (or a subgroup if p is a cone) - 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::GroupOfPolytope group the generating groupBool verbose print out additional informationReturns
ARRAY ($Graph, $lp_reps, $minInStartOrbit, \@core_point_reps, $CPindices) - orbit_polytope (gen_point, group) → OrbitPolytope
Constructs the orbit polytope of a given point gen_point with respect to a given permutation group group.
Parameters
Vector<Rational> gen_point the basis point of the orbit polytopegroup::GroupOfPolytope group a group acting on coordinatesReturns
OrbitPolytope the orbit polytope of gen_point w.r.t. group - ortho_project (p) → Polytope
- representation_conversion_up_to_symmetry (c, a, dual, rayCompMethod) → perl::ListReturn
Computes the dual description of a polytope up to its linear symmetry group.
Contained in extensionbundled:group
.Parameters
Cone c the cone (or polytope) whose dual description is to be computedgroup::Group a symmetry group of the cone c (group::GroupOfCone or group::GroupOfPolytope)Bool dual true if V to H, false if H to VBool rayCompMethod specifies sympol's method of ray computation via lrs(0), cdd(1), beneath_and_beyond(2)Returns
perl::ListReturn list which contains success as bool, vertices/inequalities and lineality/equations as Matrix<Rational> - symmetric_group (degree, domain) → group::GroupOfPolytope
Constructs a symmetric group of given degree. (See also group::symmetric_group.)
Contained in extensionbundled:group
. - truncated_orbit_polytope (v, group, eps) → SymmetricPolytope
Constructs an orbit polytope of a given point v with respect to a given group group, in which all vertices are cut off by hyperplanes in distance eps
Contained in extensionbundled:group
.Parameters
Vector v point of which orbit polytope is to be constructedgroup::GroupOfPolytope group group for which orbit polytope is to be constructedRational eps scaled distance by which the vertices of the orbit polytope are to be cut offReturns
SymmetricPolytope the truncated orbit polytope - visualizeNOP (orb, colors_ref, trans_ref)
Visualizes all (nested) orbit polytopes contained in orb in one picture.
Parameters
OrbitPolytope orb the orbit polytopeScalar colors_ref the reference to an array of colorsScalar trans_ref the reference to an array of transparency values - visualizeNOPGraph (orb, filename)
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
OrbitPolytope orb the orbit polytopeString filename the filename for the 'dot' file
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
- bound (P) → Polytope
Make a positive polyhedron bounded. Apply a projective linear transformation to a polyhedron mapping the far hyperplane to the hyperplane spanned by the points (1,0,...,0,1,0,...). The origin (1,0,...,0) is fixed.
The input polyhedron should be POSITIVE; i.e. no negative coordinates.
- 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.
- polarize (C) → Cone
Given a bounded, centered, not necessarily full-dimensional polytope P, produce its polar with respect to the standard Euclidean scalar product. Note that the definition of the polar has changed after version 2.10: the polar is reflected in the origin to conform with cone 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.
- 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.
- transform (P, trans, store) → Polytope
- translate (P, trans, store) → Polytope
- 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) → 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.
- barycentric_subdivision (pc) → PointConfiguration
Create a simplicial complex as the barycentric subdivision of a given point configuration. Each vertex in the new complex corresponds to a face in the old complex.
Parameters
PointConfiguration pc input point configurationOptions
Bool relabel generate vertex labels from the faces of the original complex; default trueBool geometric_realization Returns
PointConfiguration - 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 refinement - common_refinement (p1, p2) → Polytope
- delaunay_triangulation (V) → Array<Set<Int>>
Compute the (a) Delaunay triangulation of the given SITES of a VoronoiDiagram V. If the sites are not in general position, the non-triangular facets of the Delaunay subdivision are triangulated (by applying the beneath-beyond algorithm).
- foldable_max_signature_ilp (d, points, volume, cocircuit_equations) → an
Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.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 equationsOptions
filename a name for a file in .lp format to store the linear programReturns
an ILP that provides the result - foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → the
Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.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
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
Contained in extensionbundled:group
. - 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> - is_subdivision (points, faces)
Checks whether faces forms a valid subdivision of points, where points is a set of points, and faces is a collection of subsets of (indices of) points. If the set of interior points of points is known, this set can be passed by assigning it to the option interior_points. If points are in convex position (i.e., if they are vertices of a polytope), the option interior_points should be set to [ ] (the empty set).
- iterated_barycentric_subdivision (c, how) → SimplicialComplex
- max_interior_simplices (P) → Array<Set>
Find the maximal interior simplices of a polytope P. Symmetries of P are NOT taken into account.
Contained in extensionbundled:group
. - max_interior_simplices (P)
find the maximal interior simplices of a point configuration that DO NOT contain any point in their closure, except for the vertices. Symmetries of the configuration are NOT taken into account.
Contained in extensionbundled:group
.Parameters
PointConfiguration P the input point configuration - max_interior_simplices_impl (P) → Array<Set>
Find the interior d-dimensional simplices of a polytope or cone of combinatorial dimension d
Contained in extensionbundled:group
. - max_metric (n) → Matrix
- metric2hyp_triang (FMS) → Polytope
- metric2splits (D) → Array<Pair<Set>>
Computes all non-trivial splits of a metric space D (encoded as a symmetric distance matrix).
- min_metric (n) → Matrix
- mixed_volume (P1, P2, Pn) → E
- placing_triangulation (Points, permutation) → Array<Set<Int>>
Compute the placing triangulation of the given point set using the beneath-beyond algorithm.
- points2metric (points) → Matrix
Define a metric by restricting the Euclidean distance function to a given set of points. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-nomr is used instead (with exact computation).
- poly2metric (P) → Matrix
Define a metric by restricting the Euclidean distance function to the vertex set of a given polytope P. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-nomr is used instead (with exact computation).
- 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) → an
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
Contained in extensionbundled:group
.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
filename a name for a file in .lp format to store the linear programReturns
an LP that provides a lower bound - quotient_space_simplexity_lower_bound (d, V, volume, cocircuit_equations) → the
Calculate a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.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
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.
- secondary_cone (points, subdiv) → Cone
For a given subdivision subdiv of points tests computes the corresponding secondary cone. If the subdivision is not regular, the cone will be the secondary cone of the finest regular coarsening of subdiv. (See option test_regularity) Options can be used to make the Cone POINTED.
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 0Bool test_regularity throws an exception if the subdivision is not regularReturns
Cone - simplexity_ilp (d, points, the, volume, cocircuit_equations) → an
Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesArray<Set> the representatives of maximal interior simplicesScalar volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsOptions
filename a name for a file in .lp format to store the linear programReturns
an LP that provides a lower bound - simplexity_ilp_with_angles (d, points, the, volume, cocircuit_equations) → an
Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.Parameters
Int d the dimension of the input polytope, point configuration or quotient manifoldMatrix points the input points or verticesArray<Set> the (representative) maximal interior simplicesScalar volume the volume of the convex hullSparseMatrix cocircuit_equations the matrix of cocircuit equationsOptions
filename a name for a file in .lp format to store the linear programReturns
an LP that provides a lower bound - simplexity_lower_bound (d, points, volume, cocircuit_equations) → the
Calculate the LP relaxation lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.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
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- and an l-dimensional simplex.
Parameters
Int k the dimension of the first simplexInt l the dimension of the second simplexReturns
Vector<Rational> - stellar_subdivision (pc, faces) → PointConfiguration
Computes the complex obtained by stellar subdivision of all faces of the TRIANGULATION of the PointConfiguration.
Parameters
PointConfiguration pc input point configurationArray<Set<Int>> faces list of faces to subdivideOptions
Bool no_labels : do not write any labelsReturns
PointConfiguration - symmetrized_foldable_max_signature_ilp (d, points, volume, generators, symmetrized_foldable_cocircuit_equations) → an
Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.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 equationsOptions
filename a name for a file in .lp format to store the linear programReturns
an ILP that provides the result - symmetrized_foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → the
Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold
Contained in extensionbundled:group
.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
the optimal value of an LP that provides a bound - thrackle_metric (n) → Matrix
Compute a metric such that the f-vector of its tight span is maximal among all metrics with n points. This metric can be interpreted as a lifting function for the thrackle triangulation (see de Loera, Sturmfels and Thomas: Groebner Basis and triangultaions of the second hypersimplex)
- tight_span (points, weight, full) → Polytope
Compute the tight span dual to the regular subdivision obtained by lifting points to weight and taking the lower complex of the resulting polytope.
- tight_span (P) → Polytope
Compute the tight span dual to the regular subdivision of a polytope P obtained by the WEIGHTS and taking the lower complex of the resulting polytope.
- topcom_all_fine_triangulations (pc) → Array<Array<Set<Int>>>
Compute all fine triangulations of a point configuration via its chirotope.
- topcom_all_triangulations (pc) → Array<Array<Set<Int>>>
Compute all triangulations of a point configuration via its chirotope.
- ts_max_metric (n) → TightSpan
- ts_min_metric (n) → TightSpan
- ts_thrackle_metric (n) → TightSpan
Compute a tight span of a metric such that its f-vector is maximal among all metrics with n points. This metric can be interpreted as a lifting function for the thrackle triangulation (see de Loera, Sturmfels and Thomas: Groebner Basis and triangultaions of the second hypersimplex)
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.
- splitstree (vis_obj ...)
Call wiki:external_software#SplitsTree with the given visual objects.
Parameters
Visual::Object vis_obj ... objects to displayOptions
String File "filename" or "AUTO" Only create a NEXUS format file, don't start the GUI.The.nex
suffix is automatically added to the file name.Specify AUTO if you want the filename be automatically derived from the drawing title.You can also use any expression allowed for theopen
function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe. - vlabels (vertices, wo_zero) → arrayref
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."
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