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 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).
d is the dimension of the polytope to be built, n is the dimension of the equivalent cube.
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 si can be specified as integer, floating-point, or rational numbers.
The coordinates of the i-th point are taken as follows:
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.
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+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.
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.
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.
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.
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".
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.
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'".
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".
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.
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 mapping polytope of two
polytopes P and Q. The mapping polytope is the set of
all affine maps from Rp to Rq, that map P into Q.
The label of a new facet corresponding to v1 and h1 will
have the form "v1*h1".
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.
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.
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.
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.
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.
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.
Orthogonally project a polyhedron to a coordinate subspace.
The subspace the polyhedron is projected on is given by the coordinate indices ki.
The dash argument inverts the coordinate list. If no coordinates are specified the polytope is
projected by omitting "redundant" columns, 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.
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.
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
orthantify - p_bound - center - 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 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.
-----
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.
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).
Implements the reduction of polytope congruence 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
Writes the scaling factor to the given result section. Zero means non-congruent polytopes.
If no result section is specified, prints the scaling factor on the standard output.
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.
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. If the input vectors are in general
position VERTICES and FACETS are written, otherwise POINTS and INEQUALITIES
Compute the Steiner points of all faces of a polytope using a
randomized approximation of the angles.
eps is an accuracy parameter controlling the accuracy
( 10-eps ) of the angles computed. The s 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.
-acc is an accuracy parameter controlling the accuracy (10-eps )
of the angles computed. The -seed parameter
may be set to initialize the random calculation of the angles.
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.
Define a metric by restricting the Euclidean distance function to the vertex set of a polytope.
Due to floating point computations (sqrt is used) the metric defined may not be exact.
Given a generic finite metric space, construct the associated (i.e. dual) triangulation of the hypersimplex.
The newly created object is of type RationalPolytope.
Defines a very simple graph for a polytope propagation related to a Hidden Markov Model.
The propagated polytope is always a polygon.
For a detailed description see
M. Joswig: Polytope propagation, in: Algebraic statistics and computational biology
by L. Pachter and B. Sturmfels (eds.), Cambridge, 2005.
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.
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 subgraph induced by a given set of nodes.
The nodes are labeled with the original node indices, unless nol option is specified.
If compl option is specified, the complement of the subgraph_nodes_section is used to
select the subgraph nodes.
Determine whether two given graphs are isomorphic.
The answer is written as a boolean property result_section of the first file.
If the result section is omitted, prints the node permutation to the standard output.
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.
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.
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 or abstract 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 -z-ordering.
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. -z-factor changes the relative influence
of the objective function on the embedding. -eps controls how far a point may move, to be
considered standing still.
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.
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.
Determine whether two given polytopes are combinatorially isomorphic.
If the second argument is -self-dual, checks the first polytope for being isomorphic to its own dual.
The answer is written as a boolean property result_section of the first file.
If the result section is omitted, prints the vertex and facet permutations to the standard output.
Computes the SPLITS of a polytope, i. e. those hyperplanes
which cut the polytope in two parts such that one gets a subdivision
without new vertices. The splits are normalized by dividing by the first
non-zero entry.
If the polytope is not fulldimensional the first entries are set two zero,
however by additionally giving a section with a set of integers one forces
the program to set these entries to zero.
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.
Apply a reverse transformation some section of a polyhedron.
All transformation clients keep track of the polytope's history.
They write or update the section REVERSE_TRANSFORMATION.
Only one section in the input polyhedron is reverted and written in the output polyhedron.
The parameters "-primal" and "-dual" state if the section contains point-like or
hyperplane-like content.
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 @see 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.
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.
Compute a relative interior point of a polyhedron. The option unbounded
has to be set if the polyhedron may be unbounded. The option affinehull
assumes that the affine hull of the polyhedron is still computed.
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 option -inverse directs the graph with decreasing instead of increasing edges.
If the option -generic is set ties will be broken by lexicographical ordering.
Create a FRAMEWORK by combining a graph with coordinates given in <graph_section> and <coordinate_section>.
The <coordinate_section> is given in homogeneous coordinates.
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.
Polygonal reconstruction of a smooth curve from a finite set of samples.
Sampling rate of <= 1/3 suffices.
If -nnonly flag is set only the subgraph of nearest neighbors is computed.
T. K. Dey and P. Kumar: A simple provable algorithm for curve reconstruction.
Proc. 10th. Annu. ACM-SIAM Sympos. Discrete Alg., 1999, 893-894.
Introduce artificial boundary facets (which are always vertical, i.e., last coordinate is zero) to allow
for bounded images of unbounded polyhedra (e.g., Voronoi polyhedra). -offset defaults to 10%.
By default all directions are bounded. If the option -voronoi is set, the last direction is left unbounded.
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.
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.
Compute the bounded graph of an unbounded polyhedron and assign to each edge the maximal dimension of a face containing it.
In the case of tight spans there are a priori upper bounds due to Mike Develin.
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.
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.
Compute the INFINITESIMAL_MOTIONS of a bar and joint framework from its RIGIDITY_MATRIX.
Further this client computes the expansive patterns of the motions and the number of degrees of
freedom.