There are various means to obtain new objects without having to type the data in a new file manually.
Application polytope defines many standard construction and transformation algorithms. Unfortunately, due
to the preliminary state of polymake reconstruction, we can't supply a uniform, comfortable function-like
interface to all of them. At the moment you still have to call the construction clients as separate
programs from the shell command line.
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.
Produce a d-dimensional cyclic polytope with n points.
Prototypical example of a neighborly polytope. Combinatorics completely known
due to Gale's evenness criterion. Coordinates are chosen on the trigonometric
moment curve.
Produce a d-dimensional cyclic polytope with n points.
Prototypical example of a neighborly polytope. Combinatorics completely known
due to Gale's evenness criterion. Coordinates are chosen on the moment curve.
Produces a d-dimensional Goldfarb cube if e<1/2 and g<=1/4e.
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.
Produce a (rounded) 2*k-dimensional k-cyclic polytope with n points.
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:
Warning: Some of the k-cyclic polytopes are not simplicial.
Since the components are rounded, this client 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
Produce a combinatorial description of a multiplex with parameters (d,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 Bayer et al.
[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].
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).
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.
factor_i gives the number of boxes in the i-th dimension.
Another important way of constructing polytopes is to modify an
already existing polytope.
Actually, these clients don't alter the input polytope
(it is forbidden in polymake), but create a new polytope object (file).
Many clients can at your choice either calculate the vertex or facet coordinates,
or constrain themselves on the purely combinatorial description of the
resulting polytope.
Make a bipyramid over a polyhedron.
The bipyramid is the convex hull of the input polyhedron P and two points v, v'
on both sides of the affine span of P. For bounded polyhedra, the projections
of v and v' to the affine span of P coincide with the vertex barycenter of P.
z and z' are distances between the vertex barycenter and v and v' respectively.
Default values are z=1 and z'=-z.
If the option -noc (no coordinates) is set, then only combinatorial
information is handled.
The option -relabel creates an additional section VERTEX_LABELS.
The vertices from the original polytope keep their labels;
the new vertices are labeled "Apex" and "Apex'".
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 P and P' at simple vertices v and v', respectively.
Up to an affine transformation one can assume that the orthogonal projections
of P and P' in direction v and v', respectively, are mutually congruent.
Any bijection b from the set of edges through v to the edges through v'
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. Default permutation is 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.
Create a Cayley embedding of two polytopes.
The vertices of the first polytope get an extra coordinate z,
and the vertices of the second one get z'.
Default values are z=1 and z'=-z.
The option -relabel creates an additional section VERTEX_LABELS.
The vertices of the first polytope inherit the original labels unchanged;
the vertex labels from the second polytope get a tick (') appended.
Extract the given facet of a polyhedron and write it as a new polyhedron.
n is the number of the chosen facet.
If the option -noc (no coordinates) is specified, only combinatorial description is
produced.
The option -relabel creates an additional section VERTEX_LABELS.
The vertices belonging to the extracted facet keep their labels from the original polytope.
Construct a new polytope as the mapping polytope of two
polytopes P and Q. The mapping polytope is the set of
all affine maps from R^p to R^q, that map P into Q.
The label of a new facet corresponding to v_1 and h_1 will
have the form "v_1*h_1$".
Make a prism over a polytope.
The prism is the product of the input polytope and the interval [z,z'].
The default interval is [0,1]. If z != 0, then z' defaults
to -z.
If the option -noc (no coordinates) is set, then only combinatorial information
is handled. The input polytope is assumed to be bounded.
The option -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.
Construct a new polytope as the product of two given ones.
Unbounded polyhedra are not allowed.
If the option -noc (no coordinates) is set, only combinatorial information is handled.
The option -relabel creates an additional section VERTEX_LABELS.
The label of a new vertex corresponding to v1 ⊕ v2 will
have the form "LABEL1*LABEL2".
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.
z is the distance between the vertex barycenter and v, default value is 1.
If the option -noc (no coordinates) is set, then only combinatorial
information is handled.
The option -relabel creates an additional section VERTEX_LABELS.
The vertices from the original polytope keep their labels;
the new top vertex is labeled "Apex".
Produce a polytope with n random points from the input polytope.
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.
A seed value for the random number generator can be specified.
Produce a polytope with n random vertices from input polytope.
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.
A seed value for the random number generator can be specified.
Stack a (simplicial or cubical) polytope over one or more of its facets.
For each specified facet, 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 keyword all means all facets of the original polytope.
Parameter lf 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 lf=0, the new vertex would lie
on the original facet. lf=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. Default value for lf is 1/2.
Alternatively, the option -noc (no coordinates) can be specified to produce a
pure combinatorial description of the resulting polytope.
The option -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.
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.
vertex is the number of the vertex to be cut off.
The keyword all means all vertices of the original polyhedron.
Parameter cf controls the exact location of the cutting hyperplane(s).
It should be a rational number from (0,1].
When cf=0, the hyperplane would go through the chosen vertex, thus cutting off nothing.
When cf=1, the hyperplane touches the nearest neighbor vertex of a polyhedron.
Default value for cf is 1/2.
Alternatively, the option -noc (no coordinates) can be specified to produce a
pure combinatorial description of the resulting polytope, which would correspond to
the cutoff factor 1/2.
The option -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.
Parameter cf controls the exact location of the cutting hyperplane.
It should be a rational number from (0,1).
By cf=0, the hyperplane would go through the chosen vertex, thus degenerating the vertex figure
to a single point. By cf=1, the hyperplane would touch the nearest neighbor vertex of a polyhedron.
Default value for cf is 1/2.
Alternatively, the option -noc (no coordinates) can be specified to produce a
pure combinatorial description.
The option -relabel creates an additional section VERTEX_LABELS.
The vertices inherit the labels from the corresponding neighbor vertices of the original polytope.
facet is the number of the `cutting edge' facet. The inclination of the bottom and top side facet
is controlled by z and z' paremeters, where z is the height of the projection of the old vertex
barycenter on the bottom side facet, and z' - on the top one.
Default heights are [0,1]; if only z is specified and non-zero, then z' defaults to -z.
The polytope must be bounded.
If the option -noc (no coordinates) is set, then only combinatorial information
is handled.
The option -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.
Construct a new polytope as the wreath product of two given ones.
Unbounded polyhedra are not allowed.
If the option -noc (no coordinates) is set, only combinatorial information is handled.
The option -relabel creates an additional section VERTEX_LABELS.
The label of a new vertex corresponding to v1 ⊕ v2 will
have the form "LABEL1*LABEL2".
These clients 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
@c orthantify - @c bound - @c center - @c polarize.
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 non-negative coordinates.
Make a polyhedron centered.
Apply a linear transformation to a polyhedron such that a relatively interior point
(preferably the vertex barycenter) is moved to the origin (1,0,...,0).
Make a polyhedron POSITIVE.
Apply an affine transformation to a polyhedron such that a vertex 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.
origin is the number of the vertex that will be moved to the origin
(1,0,...,0). Default is the first affine vertex of the polyhedron.
Apply a @see{reverse transformation} REVERSE_TRANSFORMATION to a given polyhedron.
All transformation clients keep track of the polytope's history.
They write or update the section REVERSE_TRANSFORMATION.
Applying revert to the transformed polytope re-constructs the original polyhedron.
Roughly speaking, the client reads the VERTICES of two polytopes and prints two
graphs in nauty format to stdout. Each of these graphs is a complete graph with
labeled edges, such that an edge e of the first graph has the same label as an
an edge f of the second one iff the vertices corresponding to e have the same
(squared) Euclidian distance as the vertices corresponding to f.
Since 'nauty' does not handle edge labels, the client splits each edge e of
the two graphs and adds a path of length l+1 to the 'split node', where
l is the label of the edge e.
Produce a random abstract objective function on a given simple polytope.
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 starting vertex. Also a seed value for the random
number generator may be given.
Compute the Steiner points of all faces of a polytope using a
randomized approximation of the angles.
-acceps is an accuracy parameter controlling the accuracy (
$10^{-eps} ) of the angles computed. The -seeds parameter
may be set to initialize the random calculation of the angles.
Compute the Steiner point of a polytope using a randomized approximation of the angles.
-acceps is an accuracy parameter controlling the accuracy (
10-eps ) of the angles computed. The -seeds parameter
may be set to initialize the random calculation of the angles.
Store the parameters of the Schlegel diagram in the file.
facet is the index of the facet the polytope is projected on.
This client puts the viewpoint always on the ray joining the vertex barycenter
of the polytope with the one of the chosen projection facet. Obviously, it should lie outside the polytope.
On the other side, the ray crosses the hyperplanes of the neighbor facets.
The viewpoint should lie closer to the projection facet than any of these crossing points;
otherwise the diagram will not be a valid polytopal complex any more.
However, in some rare cases all crossing points lie on the positive side of the projection facet;
then the range of the valid viewpoint positions is open.
zoom controls the exact position of the viewpoint within the valid range.
If specified, it should be a rational number between 0 and 1. The greater the zoom factor,
the larger appear the rear facets in the diagram.
Defaults are the first facet (index 0) and zoom factor 9/10.
Produce a zonotope from given vectors.
The zonotope is obtained as the iterated Minkowski sum of all intervals [-x,x],
where x ranges over the rows of a given matrix.
These clients are called by polymake automatically via the rules. They compute
some new properties of an object. You will hardly ever need to call them
directly. They are documented here first of all for the sake of completeness.
Compute the lenghts of all edges of a given graph with assigned coordinates for the nodes. If the -redirect option is set
then it is assumed that the graph has indices as node attributes which point into the coordinate section.
Create an embedding of the Hasse diagram as a layered graph.
The embedding algorithm tries to minimize the weighted sum of squares of edge lengths, starting
from a random distribution. The weights are relative to the fatness of the layers.
The y-space between the layers is constant; in the -primal mode the whole-lattice node is placed
on the top, in the -dual mode it is the empty node.
label_width_section should contain estimates (better upper bounds) of the label width of each
node. The computed layout guarantees that the distances between the nodes in a layer are at least equal to
the widest label in this layer.
Produce a 3-d embedding for the graph using the spring embedding algorithm
along the lines of
Thomas Fruchtermann and Edward Reingold:
Graph Drawing by Force-directed Placement.
Software Practice and Experience Vol. 21, 1129-1164 (1992), no. 11
The initial node coordinates are chosen randomly on the unit sphere.
The optional parameter seed controls the initial setting.
In the standard setting, the embedding algorithm tries to stretch all edges to the
same length. If you prefer different edge lengths, store them as the edge attributes
of the input graph, and put the -read-edge-weights option on the command line.
If the nodes already have an embedding in Rd and there is a linear objective function defined
in the coordinate space, it can be used to rearrange the 3-d embedding along the z-axis corresponding
to the objective function growth. This mode is enabled with option objective.
The embedding algorithm can be fine-tuned with several "black magic" options.
All of them take double values, which are multiplied with internal initial settings,
so all defaults are equal to 1.
scale enlarges the ideal edge length. balance changes the balance between the
edge contraction and node repulsion forces. inertion and viscosity affects how the nodes
are moved, and can be used to restrain oscillations. objective-factor changes the relative influence
of the linear objective function on the embedding. eps controls how far a point may move, to be
considered standing still.
Compute the sizes of all 2-faces of a simple polytope.
Since this algorithm does not require the complete face lattice, it is much faster
than the standard @client 2-face-sizes.
Compute the convex hull and the triangulation of the given point set
using the beneath-beyond algorithm.
The triangulation computed will be a placing one according to the order of the points
in the VERTICES or POINTS section. If you need an alternative order,
you can store it in some section (it should be a valid permutation of the integer
range 0 .. N_VERTICES-1) and specify its name as an additional command-line parameter.
Introduce artificial boundary facets (which are always vertical, i.e., last coordinate is zero) to allow
for bounded images of unbounded polyhedra (e.g., Voroni polyhedra). <bnd_percent> defaults to 10.
Direct the graph of a polytope according to a linear or abstract objective function.
The maximal and minimal values, which are attained by the objective function, as well
as the minimal and the maximal face are written into separate sections.
The optional "+" or "-" signals whether the graph is directed with increasing or
decreasing edges, respectively. By default, the edges are increasing.
Compute the dimension of the vector space built of points or hyperplanes.
mode may be -primal, -dual, or -rays.
If option -rays is specified, only far points (rays) are considered,
that is, the dimension of the far face is computed.
Rows of the incidence matrix correspond to the vectors of the first set, columns correspond to the second set.
Vector sets are encoded as rows of a matrix.
Two vectors are considered incident if their scalar product is exactly zero.
In primal mode it converts the V-representation to the H-representation,
in dual mode vice versa.
If the option -count is specified, only counts the facets rsp. vertices without storing them in a matrix.
-only-bounded in connection with -dual counts bounded vertices only.
Convert the combinatorial description of a 2-d or 3-d polytope
to the form suitable for visualization tools.
The rows of the vertex-facet incidence and the facet neighborhood matrices are rearranged
in the facet boundary counterclockwise traversal order, if seen from the outside of the polytope.
In dual mode, the notions of facets and vertices are interchanged.
Find an optimum of a linear objective function.
The method generalizes the behavior of the simplex algorithm,
but it relies on complete information about the solution polytope.
WARNING: this is not an efficient way to solve a linear program.
Calculate the transformation matrix for Schlegel diagram.
Polytope must be bounded and full dimensional.
The transformation matrix, when applied to the points of the polytope, will put them
on the projection facet, the latter will stay fixed. All calculations are made with
rational coordinates. The last step towards a ready-to-display
Schlegel diagram - an orthogonal transformation to Rd-1 - requires floating-point coordinates,
and is `outsourced' into a separate client, schlegel_vertices.
Given a 3-connected planar graph. If the corresponding polytope
contains a triangular facet (ie. the graph contains a non-
separating cycle of length 3), the client produces a realization
in R3.
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.
Compute the Voronoi polyhedron of a given set of points. The polyhedron is unbounded. Introduce artificial cut facets later
(e.g., for visualization); this must be done after the vertex have been computed.