application: polytope

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

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

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

imports from: common, graph
uses: group, ideal, topaz

Objects

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 cocircuits
      Returns
      SparseMatrix<Rational>
    •  
      cocircuit_equations (C, interior_ridge_simplices, interior_simplices) → SparseMatrix<Int>

      A matrix whose rows contain the cocircuit equations of a cone C with respect to a list of interior ridge simplices symmetries of the cone are NOT taken into account

      Parameters
      ConeC
      Array<Set>interior_ridge_simplices
      interior codimension 1 simplices
      Array<Set>interior_simplices
      interior simplices of maximal dimension
      Options
      Stringfilename
      where to write the output (default empty)
      Boolreduce_rows
      whether to perform row reduction (default 1)
      Intlog_frequency
      how often to print log messages
      Returns
      SparseMatrix<Int>
    •  
      cocircuit_equation_of_ridge (C, rho) → HashMap<Set,Rational>

      The cocircuit equations of a cone C corresponding to some interior ridge rho with respect to a list of interior simplices symmetries of the cone are NOT taken into account

      Parameters
      ConeC
      Setrho
      the interior ridge
      Returns
      HashMap<Set,Rational>
    •  
      codegree <Scalar> (P)

      Calculate the codegree of a cone or polytope P. This is the maximal positive integer c such that every subset of size < c lies in a common facet of conv P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.

      Type Parameters
      Scalar
      the underlying number type,
      Parameters
      ConeP

      Example:
      • To find the codegree of the 3-cube, type> print codegree(cube(3)); 1
    •  
      codegree <Scalar> (P)

      Calculate the codegree of a point configuration P. This is the maximal positive integer c such that every subset of size < c lies in a common facet of conv P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.

      Type Parameters
      Scalar
      the underlying number type,
      Parameters
      PointConfigurationP
    •  
      contraction (C, v)

      Contract a vector configuration C along a specified vector v.

      Parameters
      VectorConfigurationC
      Intv
      index of the vector to contract
    •  
      degree <Scalar> (P)

      Calculate the degree of a cone, polytope or point configuration P. This is the maximal dimension of an interior face of P, where an interior face is a subset of the points of P whose convex hull does not lie on the boundary of P. Moreover, the relation degree(P) + codegree(P) = dim(P) + 1 holds.

      Type Parameters
      Scalar
      the underlying number type,
      Parameters
      PointConfigurationP
      (or Cone or Polytope)

      Example:
      • To find the degree of the 3-cube, type> print degree(cube(3)); 3
    •  
      deletion (C, v)

      Delete a specified vector v from a vector configuration C.

      Parameters
      VectorConfigurationC
      Intv
      index of the vector to delete
  •  

    Functions based on graph isomorphisms.

    •  
      congruent (P1, P2) → Scalar

      Check whether two given polytopes P1 and P2 are congruent, i.e. whether there is an affine isomorphism between them that is induced by a (possibly scaled) orthogonal matrix. Returns the scale factor, or 0 if the polytopes are not congruent.

      We are using the reduction of the congruence problem (for arbitrary point sets) to the graph isomorphism problem due to:

      Akutsu, T.: On determining the congruence of point sets in `d` dimensions.
      Comput. Geom. Theory Appl. 9, 247--256 (1998), no. 4
      Parameters
      PolytopeP1
      the first polytope
      PolytopeP2
      the second polytope
      Returns
      Scalar
      the square of the scale factor or 0 if the polytopes are not congruent

      Example:
      • Let's first consider an isosceles triangle and its image of the reflection in the origin:> $t = simplex(2);> $tr = simplex(2,-1); Those two are congruent:> print congruent($t,$tr); 1 If we scale one of them, we get a factor:> print congruent(scale($t,2),$tr); 4 But if we instead take a triangle that is not isosceles, we get a negative result.> $tn = new Polytope(VERTICES => [[1,0,0],[1,2,0],[1,0,1]]);> print congruent($t,$tn); 0
    •  
      equal_polyhedra (P1, P2) → Bool

      UNDOCUMENTED
      Parameters
      PolytopeP1
      the first polytope
      PolytopeP2
      the second polytope
      Options
      Boolverbose
      Prints information on the difference between P1 and P2 if they are not equal.
      Returns
      Bool
      true if the two polyhedra are equal, false otherwise

      Example:
      • > $p = new Polytope(VERTICES => [[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]]);> print equal_polyhedra($p,cube(2)); true To see why two polytopes are unequal, try this:> print equal_polyhedra($p,cube(3),verbose => 1); Cones/Polytopes do no live in the same ambient space. false> print equal_polyhedra($p,simplex(2),verbose => 1); Inequality 1 -1 -1 not satisfied by point 1 1 1. false
    •  
      find_facet_vertex_permutations (P1, P2) → Pair<Array<Int>, Array<Int>>

      Find the permutations of facets and vertices which maps the cone or polyhedron P1 to P2. The facet permutation is the first component, the vertex permutation is the second component of the return value.

      Only the combinatorial isomorphism is considered. If the polytopes are not isomorphic, an exception is thrown.

      Parameters
      ConeP1
      the first cone/polytope
      ConeP2
      the second cone/polytope
      Returns
      Pair<Array<Int>, Array<Int>>
      the facet and the vertex permutations

      Example:
      • To print the vertex permutation that maps the 3-simplex to its mirror image, type this:> $p = find_facet_vertex_permutations(simplex(3),scale(simplex(3),-1));> print $p->first; 1 2 3 0
    •  
      included_polyhedra (P1, P2) → Bool

      UNDOCUMENTED
      Parameters
      PolytopeP1
      the first polytope
      PolytopeP2
      the second polytope
      Options
      Boolverbose
      Prints information on the difference between P1 and P2 if none is included in the other.
      Returns
      Bool
      'true' if P1 is included in P2, 'false' otherwise

      Example:
      • > print included_polyhedra(simplex(3),cube(3)); true To see in what way the two polytopes differ, try this:> print included_polyhedra(cube(2),cube(3),verbose=>1); Cones/Polytopes do no live in the same ambient space. false
    •  
      isomorphic (P1, P2) → Bool

      Check whether the face lattices of two cones or polytopes are isomorphic. The problem is reduced to graph isomorphism of the vertex-facet incidence graphs.

      Parameters
      ConeP1
      the first cone/polytope
      ConeP2
      the second cone/polytope
      Returns
      Bool
      'true' if the face lattices are isomorphic, 'false' otherwise

      Example:
      • The following compares the standard 2-cube with a polygon generated as the convex hull of five points. The return value is true since both polygons are quadrangles.> $p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]);> print isomorphic(cube(2),$p); true
    •  
      lattice_isomorphic_smooth_polytopes (P1, P2) → Bool

      Tests whether two smooth lattice polytopes are lattice equivalent by comparing lattice distances between vertices and facets.

      Parameters
      PolytopeP1
      the first lattice polytope
      PolytopeP2
      the second lattice polytope
      Returns
      Bool
      'true' if the polytopes are lattice equivalent, 'false' otherwise

      Example:
      • > $t = new Vector(2,2);> print lattice_isomorphic_smooth_polytopes(cube(2),translate(cube(2),$t)); true
  •  

    These functions are for checking the consistency of some properties.

    •  
      check_inc (points, hyperplanes, sign, verbose) → Bool

      Check coordinate data. For each pair of vectors from two given matrices their inner product must satisfy the given relation.

      Parameters
      Matrixpoints
      Matrixhyperplanes
      Stringsign
      composed of one or two characters from [-+0], representing the allowed domain of the vector inner products.
      Boolverbose
      print all products violating the required relation
      Returns
      Bool
      'true' if all relations are satisfied, 'false' otherwise

      Example:
      • Let's check which vertices of the square lie in its zeroth facet:> $H = cube(2)->FACETS->minor([0],All);> print check_inc(cube(2)->VERTICES,$H,'0',1); <1,0> ( 1 1 -1 ) * [ 1 1 0 ] == 2 <3,0> ( 1 1 1 ) * [ 1 1 0 ] == 2 #points==4, #hyperplanes==1, -:0, 0:2, +:2, total:4 false Thus, the first and third vertex don't lie on the hyperplane defined by the facet but on the positive side of it, and the remaining two lie on the hyperplane.
    •  
      check_poly (VIF) → Polytope

      Try to check whether a given vertex-facet incidence matrix VIF defines a polytope. Note that a successful certification by check_poly is not sufficient to determine whether an incidence matrix actually defines a polytope. Think of it as a plausibility check.

      Parameters
      IncidenceMatrixVIF
      Options
      Booldual
      transposes the incidence matrix
      Boolverbose
      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.

      Parameters
      PolytopeP
      the given polytope
      Returns
      Bool
      'true' if the Moebius strip edges form such a Moebius strip, 'false' otherwise
    •  
      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
      PolytopeP
      the given polytope
      Options
      Boolverbose
      print details
      Returns
      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

      Parameters
      PolytopeP
      source object
      Returns
      Matrix<Float>
      the dehomogenized vertices converted to Float

      Example:
      • > print cube(2,1/2)->VERTICES; 1 -1/2 -1/2 1 1/2 -1/2 1 -1/2 1/2 1 1/2 1/2> print affine_float_coords(cube(2,1/2)); -0.5 -0.5 0.5 -0.5 -0.5 0.5 0.5 0.5
    •  
      convert_to <Coord> (c) → Cone<Coord>

      Creates a new Cone object with different coordinate type target coordinate type Coord must be specified in angle brackets e.g. $new_cone = convert_to<Coord>($cone)

      Type Parameters
      Coord
      target coordinate type
      Parameters
      Conec
      the input cone
      Returns
      Cone<Coord>
      a new cone object or C itself it has the requested type
    •  
      convert_to <Coord> (P) → Polytope<Coord>

      provide a Polytope object with desired coordinate type

      Type Parameters
      Coord
      target coordinate type
      Parameters
      PolytopeP
      source object
      Returns
      Polytope<Coord>
      P if it already has the requested type, a new object otherwise

      Example:
      • > print cube(2)->type->full_name; Polytope<Rational>> $pf = convert_to<Float>(cube(2));> print $pf->type->full_name; Polytope<Float>
  •  

    Tight spans and their connections to polyhedral geometry

  •  

    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.

      Parameters
      PolytopeP
      Options
      Floateps
      controls the accuracy of the angles computed
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Matrix
    •  
      center_distance (p) → Float

      Compute the mean or median distance of the VERTICES to the VERTEX_BARYCENTER.

      Parameters
      Polytopep
      Options
      Boolmedian
      use median instead of arithmetic mean
      Returns
      Float
    •  
      circuit_completions (L, R) → Array<Set>

      Given two matrices L (n x d) and R (m x d) such that (L/R) has rank r, select all (r+1-n)-subsets C of rows of R such that (L,S) or (S,L) is a circuit. Optionally, if d > r, a basis H for the orthogonal span of the affine hull of (L/R) may be given.

      Parameters
      MatrixL
      MatrixR
      Options
      MatrixH
      Returns
      Array<Set>

      Example:
      • Divide the vertex set of the 3-cube into a body diagonal L and six remaining vertices R. To find the subsets of R that complete L to a circuit, type> $c = cube(3);> $L = $c->VERTICES->minor([0,7],All);> $R = $c->VERTICES->minor([1,2,3,4,5,6],All);> print circuit_completions($L,$R); {0 1 3} {2 4 5}
    •  
      containing_normal_cone (P, q) → Set

      Return the vertices of the face of P whose normal cone contains a point q.

      Parameters
      ConeP
      Vectorq
      Returns
      Set

      Example:
      • To find the face whose normal cone contains a given point, type> $p = new Polytope(VERTICES=>[[1,-1,0],[1,0,-1],[1,0,1],[1,100,0]]);> print containing_normal_cone($p, new Vector([1,1,2])); {2 3}
    •  
      containing_outer_cone (P, q) → Set

      Return the vertices of the face of P whose outer cone contains a point q.

      Parameters
      PolytopeP
      Vectorq
      Returns
      Set

      Example:
      • To find the face whose outer cone contains a given point, type> print containing_outer_cone(cube(3), new Vector([1,2,2,2])); {7}
    •  
      dihedral_angle (H1, H2) → Float

      Compute the dihedral angle between two (oriented) affine or linear hyperplanes.

      Parameters
      Vector<Scalar>H1
      : first hyperplane
      Vector<Scalar>H2
      : second hyperplane
      Options
      Booldeg
      output in degrees rather than radians, default is false
      Boolcone
      hyperplanes seen as linear hyperplanes, default is false
      Returns
      Float

      Example:
      • > $H1 = new Vector(1,5,5);> $H2 = new Vector(1,-5,5);> print dihedral_angle($H1,$H2,deg=>1); 90
    •  
      induced_lattice_basis (p) → Matrix<Integer>

      Returns a basis of the affine lattice spanned by the vertices

      Parameters
      Polytopep
      the input polytope
      Returns
      Matrix<Integer>
      - the lattice basis.

      Example:
      • The vertices of the 2-simplex span all of Z^2...> print induced_lattice_basis(simplex(2)); 0 1 0 0 0 1 ...but if we scale it with 2, we get only every second lattice point.> print induced_lattice_basis(scale(simplex(2),2)); 0 2 0 0 0 2
    •  
      integer_points_bbox (P) → Matrix<Integer>

      Enumerate all integer points in the given polytope by searching a bounding box.


      Example:
      • > $p = new Polytope(VERTICES=>[[1,13/10,1/2],[1,1/5,6/5],[1,1/10,-3/2],[1,-7/5,1/5]]);> print integer_points_bbox($p); 1 0 -1 1 -1 0 1 0 0 1 1 0 1 0 1
    •  
      minimal_vertex_angle (P) → Float

      Computes the minimal angle between two vertices of the input polytope P.

      Parameters
      PolytopeP
      Returns
      Float

      Example:
      • > print minimal_vertex_angle(simplex(3)); 3.14159265358979
    •  
      normaliz_compute (C) → List

      Compute degree one elements, Hilbert basis or Hilbert series of a cone C with libnormaliz Hilbert series and Hilbert h-vector depend on the given grading and will not work unless C is HOMOGENEOUS or a MONOID_GRADING is set

      Contained in extension libnormaliz.
      Parameters
      ConeC
      Options
      Boolfrom_facets
      supply facets instead of rays to normaliz
      Booldegree_one_generators
      compute the generators of degree one, i.e. lattice points of the polytope
      Boolhilbert_basis
      compute Hilbert basis of the cone C
      Boolh_star_vector
      compute Hilbert h-vector of the cone C
      Boolhilbert_series
      compute Hilbert series of the monoid
      Boolehrhart_quasi_polynomial
      compute Ehrhart quasi polynomial of a polytope
      Boolfacets
      compute support hyperplanes (=FACETS,LINEAR_SPAN)
      Boolrays
      compute extreme rays (=RAYS)
      Booldual_algorithm
      use the dual algorithm by Pottier
      Boolskip_long
      do not try to use long coordinates first
      Boolverbose
      libnormaliz debug output
      Returns
      List
      (Matrix<Integer> degree one generators, Matrix<Integer> Hilbert basis, Vector<Integer> Hilbert h-vector, RationalFunction Hilbert series, Matrix<Rational> facets, Matrix<Rational> linear_span, Matrix<Rational> rays) (only requested items)
    •  
      occluding_cone (P, F) → Cone

      For a face F of a cone or polytope P, return the polyhedral cone C such that taking the convex hull of P and any point in C destroys the face F

      Parameters
      ConeP
      SetF
      Returns
      Cone

      Example:
      • To find the occluding cone of an edge of the 3-cube, type> $c=occluding_cone(cube(3), [0,1]);> print $c->FACETS; -1 0 -1 0 -1 0 0 -1
    •  
      print_face_lattice (VIF, dual)

      Write the face lattice of a vertex-facet incidence matrix VIF to stdout. If dual is set true the face lattice of the dual is printed.

      Parameters
      IncidenceMatrixVIF
      Booldual

      Example:
      • To get a nice representation of the squares face lattice, do this:> print_face_lattice(cube(2)->VERTICES_IN_FACETS); FACE_LATTICE [ -1 : 4 ] {{0 1} {0 2} {1 3} {2 3}} [ -2 : 4 ] {{0} {1} {2} {3}}
    •  
      separable (q, P) → Bool

      Checks whether there exists a hyperplane separating a given point q from a polytope/cone P by solving a suitable LP. If true, q is a vertex of the polytope defined by q and the vertices of P. To get the separating hyperplane, use separating_hyperplane. Works without knowing the facets of P!

      Parameters
      Vectorq
      the vertex (candidate) which is to be separated from P
      ConeP
      the polytope/cone from which q is to be separated
      Options
      Boolstrong
      Test for strong separability. default: true
      Returns
      Bool
      'true' if q is separable from p

      Example:
      • > $q = cube(2)->VERTICES->row(0);> print separable(cube(2), $q, strong=>0); true
    •  
      steiner_point (P) → Vector

      Compute the Steiner point of a polyhedron P using a randomized approximation of the angles.

      Parameters
      PolytopeP
      Options
      Floateps
      controls the accuracy of the angles computed
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Vector
    •  
      violations (P, q) → Set

      Check which relations, if any, are violated by a point.

      Parameters
      ConeP
      Vectorq
      Options
      Stringsection
      Which section of P to test against q
      Intviolating_criterion
      has the options: +1 (positive values violate; this is the default), 0 (*non*zero values violate), -1 (negative values violate)
      Returns
      Set

      Example:
      • This calculates and prints the violated equations defining a square with the origin as its center and side length 2 with respect to a certain point:> $p = cube(2);> $v = new Vector([1,2,2]);> $S = violations($p,$v);> print $S; {1 3}
    •  
      visible_facet_indices (P, q) → Set

      Return the indices of all facets that are visible from a point q.

      Parameters
      ConeP
      Vectorq
      Returns
      Set

      Example:
      • This prints the facets of a square with the origin as its center and side length 2 that are visible from a certain point:> $p = cube(2);> $v = new Vector([1,2,2]);> map { print $p->VERTICES_IN_FACETS->[$_], "\n" } @{visible_facet_indices($p,$v)}; {1 3} {2 3}
    •  
      visible_face_indices (P, q) → Set

      Return the indices (in the HASSE_DIAGRAM) of all faces that are visible from a point q.

      Parameters
      ConeP
      Vectorq
      Returns
      Set

      Example:
      • This prints the faces of a square with the origin as its center and side length 2 that are visible from a certain point:> $p = cube(2);> $v = new Vector([1,2,2]);> map { print $p->HASSE_DIAGRAM->FACES->[$_], "\n" } @{visible_face_indices($p,$v)}; {} {1} {2} {3} {1 3} {2 3}
    •  
      zonotope_tiling_lattice (P) → AffineLattice

      Calculates a generating set for a tiling lattice for P, i.e., a lattice L such that P + L tiles the affine span of P.

      Parameters
      PolytopeP
      the zonotope
      Options
      Boollattice_origin_is_vertex
      true if the origin of the tiling lattice should be a vertex of P; default false, ie, the origin will be the barycenter of P
      Returns
      AffineLattice

      Example:
      • This determines a tiling lattice for a parallelogram with the origin as its vertex barycenter and prints it base vectors:> $M = new Matrix([[1,1,0],[1,1,1]]);> $p = zonotope($M);> $A = zonotope_tiling_lattice($p);> print $A->BASIS; 0 -1 -1 0 0 1
  •  

    These functions provide tools from linear, integer and dicrete optimization. In particular, linear programs are defined here.

    •  
      ball_lifting_lp (c, facet_index, conv_eps) → Polytope

      Computes the inequalities and the linear objective for an LP to lift a simplicial d-ball embedded starshaped in Rd.

      Contained in extension local.
      Parameters
      topaz::GeometricSimplicialComplexc
      Intfacet_index
      index of the facet to be lifted
      Rationalconv_eps
      some epsilon > 0
      Returns
      Polytope
    •  
      core_point_algo (p, optLPvalue) → List

      Algorithm to solve highly symmetric integer linear programs (ILP). It is required that the group of the ILP induces the alternating or symmetric group on the set of coordinate directions. The linear objective function is the vector (0,1,1,..,1).

      Parameters
      Polytopep
      RationaloptLPvalue
      optimal value of LP approximation
      Options
      Boolverbose
      Returns
      List
      (Vector<Rational> optimal solution, Rational optimal value) may be empty
    •  
      core_point_algo_Rote (p, optLPvalue) → List

      Version of core_point_algo with improved running time (according to a suggestion by G. Rote). The core_point_algo is an algorithm to solve highly symmetric integer linear programs (ILP). It is required that the group of the ILP induces the alternating or symmetric group on the set of coordinate directions. The linear objective function is the vector (0,1,1,..,1).

      Parameters
      Polytopep
      RationaloptLPvalue
      optimal value of LP approximation
      Options
      Boolverbose
      Returns
      List
      (Vector<Rational> optimal solution, Rational optimal value) may be empty
    •  
      find_transitive_lp_sol (Inequalities) → List

      Algorithm to solve symmetric linear programs (LP) of the form max ctx , c=(0,1,1,..,1) subject to the inequality system given by Inequalities. It is required that the symmetry group of the LP acts transitively on the coordinate directions.

      Parameters
      MatrixInequalities
      the inequalities describing the feasible region
      Returns
      List
      (Vector<Rational> optimal solution, Rational optimal value, Bool feasible, Bool max_bounded)

      Example:
      • Consider the LP described by the facets of the 3-cube:> @sol=find_transitive_lp_sol(cube(3)->FACETS);> print $_, "\n" for @sol; 1 1 1 1 3 true true The optimal solution is [1,1,1,1], its value under c is 3, and the LP is feasible and bounded in direction of c.
    •  
      inner_point (points) → Vector

      Compute a true inner point of a convex hull of the given set of points.

      Parameters
      Matrixpoints
      Returns
      Vector

      Example:
      • To print an inner point of the square, do this:> print inner_point(cube(2)->VERTICES); 1 -1/3 -1/3
    •  
      lp2poly <Scalar> (file, testvec, prefix) → Polytope<Scalar>

      Read a linear programming problem given in LP-Format (as used by cplex & Co.) and convert it to a Polytope<Scalar> object.

      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.

      Type Parameters
      Scalar
      coordinate type of the resulting polytope; default is Rational.
      Parameters
      Stringfile
      filename of a linear programming problem in LP-Format
      Vectortestvec
      If present, after reading in each line of the LP it is checked whether testvec fulfills it
      Stringprefix
      If testvec is present, all variables in the LP file are assumed to have the form $prefix$i
      Options
      Intnocheck
      Do not automatically compute FEASIBLE for the polytope (recommended for very large LPs)
      Returns
      Polytope<Scalar>
    •  
      poly2lp (P, LP, maximize, file)

      Convert a polymake description of a polyhedron to LP format (as used by CPLEX and other linear problem solvers) and write it to standard output or to a file. If LP comes with an attachment 'INTEGER_VARIABLES' (of type Array<Bool>), the output will contain an additional section 'GENERAL', allowing for IP computations in CPLEX. If the polytope is not FEASIBLE, the function will throw a runtime error.

      Parameters
      PolytopeP
      LinearProgramLP
      default value: P->LP
      Boolmaximize
      produces a maximization problem; default value: 0 (minimize)
      Stringfile
      default value: standard output
    •  
      poly2porta (p, file)

      take a rational polytope and write a porta input file (.ieq or .poi)

      Parameters
      Polytope<Rational>p
      Stringfile
      filename for the porta file (.ieq or .poi) or an open IO handle
      Options
      Boolprimal
      true if points should be written, false if inequalities should be written (default is true)
    •  
      porta2poly (file) → Polytope<Rational>

      Read an .ieq or .poi file (porta input) or .poi.ieq or .ieq.poi (porta output) and convert it to a Polytope<Rational> object

      Parameters
      Stringfile
      filename of a porta file (.ieq or .poi)
      Returns
      Polytope<Rational>
    •  
      print_constraints (C)

      Write the FACETS / INEQUALITIES and the LINEAR_SPAN / EQUATIONS (if present) of a polytope P or cone C in a readable way. COORDINATE_LABELS are adopted if present.

      Parameters
      Cone<Scalar>C
      the given polytope or cone
      Options
      Array<String>ineq_labels
      changes the labels of the inequality rows
      Array<String>eq_labels
      changes the labels of the equation rows

      Example:
      • The following prints the facet inequalities of the square, changing the labels.> print_constraints(cube(2),ineq_labels=>['zero','one','two','three']); Facets: zero: x1 >= -1 one: -x1 >= -1 two: x2 >= -1 three: -x2 >= -1
    •  
      random_edge_epl (G) → Vector<Rational>

      Computes a vector containing the expected path length to the maximum for each vertex of a directed graph G. The random edge pivot rule is applied.

      Parameters
      Graph<Directed>G
      a directed graph
      Returns
      Vector<Rational>
    •  
      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
      PolytopeP
      a simple polytope
      Intstart
      the index of the starting vertex; default value: random
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Vector<Rational>
    •  
      separating_hyperplane (q, points) → Vector

      Computes (the normal vector of) a hyperplane which separates a given point q from points via solving a suitable LP. The scalar product of the normal vector of the separating hyperplane and a point in points is greater or equal than 0 (same behavior as for facets!). If q is not a vertex of P=conv(points,q), the function throws an infeasible exception. Works without knowing the facets of P!

      Parameters
      Vectorq
      the vertex (candidate) which is to be separated from points
      Matrixpoints
      the points from which q is to be separated
      Returns
      Vector
      sep_hyp

      Example:
      • The following stores the result in the List @r and then prints the answer and a description of the hyperplane separating the zeroth vertex of the square from the others.> $q = cube(2)->VERTICES->row(0);> $points = cube(2)->VERTICES->minor(sequence(1,3),All);> print separating_hyperplane($q,$points); 0 1/2 1/2
    •  
      separating_hyperplane (p1, p2) → Vector

      Computes (the normal vector of) a hyperplane which separates two given polytopes p1 and p2 if possible. Works by solving a linear program, not by facet enumeration.

      Parameters
      Polytopep1
      the first polytope, will be on the positive side of the separating hyperplane
      Polytopep2
      the second polytope
      Options
      Boolstrong
      If this is set to true, the resulting hyperplane will be strongly separating, i.e. it wont touch either of the polytopes. If such a plane does not exist, an exception will be thrown. default: true
      Returns
      Vector
      a hyperplane separating p1 from p2
    •  
      totally_dual_integral (inequalities) → Bool

      Checks weather a given system of inequalities is totally dual integral or not. The inequalities should describe a full dimensional polyhedron

      Parameters
      Matrixinequalities
      Returns
      Bool

      Example:
      • > print totally_dual_integral(cube(2)->FACETS); true
    •  
      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
      PolytopeP
      LinearProgramLP
      Options
      RGBmin
      the minimal RGB value
      RGBmax
      the maximal RGB value
      Returns
      Array<RGB>

      Example:
      • This calculates a vertex coloring with respect to a linear program. For a better visualization, we also set the vertex thickness to 2.> $p = cube(3);> $p->LP(LINEAR_OBJECTIVE=>[0,1,2,3]);> $v = vertex_colors($p,$p->LP);> $p->VISUAL(VertexColor=>$v,VertexThickness=>2);
    •  
      write_foldable_max_signature_ilp (P, outfile_name)

      construct a linear program whose optimal value is an upper bound for the algebraic signature of a triangulation of P. This is the absolute value of the difference of normalized volumes of black minus white simplices (counting only those with odd normalized volume) in a triangulation of P whose dual graph is bipartite. If P has a GROUP, it will be used to construct the linear program.

      Parameters
      PolytopeP
      Stringoutfile_name

      Examples:
      • For the 0/1 2-cube without a GROUP, the foldable max signature lp is computed as follows:> write_foldable_max_signature_ilp(cube(2,0)); MINIMIZE obj: +1 x1 -1 x2 +1 x3 -1 x4 +1 x5 -1 x6 +1 x7 -1 x8 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 ie4: +1 x5 >= 0 ie5: +1 x6 >= 0 ie6: +1 x7 >= 0 ie7: +1 x8 >= 0 ie8: -1 x1 -1 x2 >= -1 ie9: -1 x3 -1 x4 >= -1 ie10: -1 x5 -1 x6 >= -1 ie11: -1 x7 -1 x8 >= -1 eq0: -1 x4 +1 x5 = 0 eq1: +1 x3 -1 x6 = 0 eq2: -1 x2 +1 x7 = 0 eq3: +1 x1 -1 x8 = 0 eq4: +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +1 x7 +1 x8 = 2 BOUNDS x1 free x2 free x3 free x4 free x5 free x6 free x7 free x8 free GENERAL x1 x2 x3 x4 x5 x6 x7 x8 END There are eight variables, one for each possible black or white maximal interior simplex. The optimal value of this LP is zero, because any triangulation has exactly one black and one white simplex of odd normalized volume. Notice that the objective function becomes empty for cube(2), because in the +1/-1 cube, each simplex has even volume.
      • For the 0/1 3-cube, we use a GROUP property:> write_foldable_max_signature_ilp(cube(3,0,group=>1)); MINIMIZE obj: +1 x1 -1 x2 +1 x3 -1 x4 +1 x5 -1 x6 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 ie4: +1 x5 >= 0 ie5: +1 x6 >= 0 ie6: +1 x7 >= 0 ie7: +1 x8 >= 0 ie8: -1 x1 -1 x2 >= -8 ie9: -1 x3 -1 x4 >= -24 ie10: -1 x5 -1 x6 >= -24 ie11: -1 x7 -1 x8 >= -2 eq0: +2 x3 -2 x4 +2 x5 -2 x6 = 0 eq1: -2 x3 +2 x4 -2 x5 +2 x6 = 0 eq2: -6 x2 +6 x5 +24 x7 = 0 eq3: -6 x1 +6 x6 +24 x8 = 0 eq4: +1 x1 +1 x2 +1 x3 +1 x4 +1 x5 +1 x6 +2 x7 +2 x8 = 6 BOUNDS x1 free x2 free x3 free x4 free x5 free x6 free x7 free x8 free GENERAL x1 x2 x3 x4 x5 x6 x7 x8 END There are again 8 variables, but now they correspond to the black and white representatives of the four symmetry classes of maximal interior simplices. The optimal value of this linear program is 4, because the most imbalanced triangulation is the one with 5 simplices, in which the volume of the big interior simplex is even and doesn't get counted in the objective function.
    •  
      write_simplexity_ilp (P)

      construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P.

      Parameters
      PolytopeP
      Options
      Stringoutfile_name
      . If the string is '-' (as is the default), the linear program is printed to STDOUT.

      Example:
      • To print the linear program for the 2-dimensional cube, write> write_simplexity_ilp(cube(2)); MINIMIZE obj: +1 x1 +1 x2 +1 x3 +1 x4 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 eq0: +4 x1 +4 x2 +4 x3 +4 x4 = 8 eq1: -1 x2 +1 x3 = 0 eq2: -1 x1 +1 x4 = 0 BOUNDS x1 free x2 free x3 free x4 free GENERAL x1 x2 x3 x4 END
    •  
      write_simplexity_ilp_with_angles (P, outfile_name)

      construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P, and that takes into account the angle constraint around codimension 2 faces. The first set of variables correspond to possible maximal internal simplices, the second set to the simplices of codimension 2. See the source file polytope/src/symmetrized_codim_2_angle_sums.cc for details.

      Parameters
      PolytopeP
      Stringoutfile_name

      Example:
      • To print the linear program for the 2-dimensional cube, write> write_simplexity_ilp_with_angles(cube(2)); MINIMIZE obj: +1 x1 +1 x2 +1 x3 +1 x4 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 ie4: +1 x5 >= 0 ie5: +1 x6 >= 0 ie6: +1 x7 >= 0 ie7: +1 x8 >= 0 eq0: -1 x2 +1 x3 = 0 eq1: -1 x1 +1 x4 = 0 eq2: +0.5 x1 +0.25 x2 +0.2500000000000001 x3 -0.5 x5 = 0 eq3: +0.25 x1 +0.5 x3 +0.2500000000000001 x4 -0.5 x6 = 0 eq4: +0.25 x1 +0.5 x2 +0.2500000000000001 x4 -0.5 x7 = 0 eq5: +0.25 x2 +0.2500000000000001 x3 +0.5 x4 -0.5 x8 = 0 eq6: +1 x5 = 1 eq7: +1 x6 = 1 eq8: +1 x7 = 1 eq9: +1 x8 = 1 eq10: +4 x1 +4 x2 +4 x3 +4 x4 = 8 BOUNDS x1 free x2 free x3 free x4 free x5 free x6 free x7 free x8 free GENERAL x1 x2 x3 x4 x5 x6 x7 x8 END
    •  
      write_symmetrized_simplexity_ilp (P, isotypic_components, outfile_name)

      construct a linear program whose optimal value is a lower bound for the minimal number of simplices in a triangulation of P. The symmetry group of P is taken into account, in that the variables in the linear program are projections of the indicator variables of the maximal interior simplices to a given direct sum of isotypic components of the symmetry group of P acting on these simplices.

      Parameters
      PolytopeP
      Set<Int>isotypic_components
      the set of indices of isotypic components to project to; default [0]
      Stringoutfile_name
      . Setting this to '-' (as is the default) prints the LP to stdout.

      Example:
      • For the 3-cube, the symmetrized LP for isotypic component 0 reads as follows:> write_symmetrized_simplexity_ilp(cube(3,group=>1)); MINIMIZE obj: +1 x1 +1 x2 +1 x3 +1 x4 Subject To ie0: +1 x1 >= 0 ie1: +1 x2 >= 0 ie2: +1 x3 >= 0 ie3: +1 x4 >= 0 eq0: +8 x1 +8 x2 +8 x3 +16 x4 = 48 eq1: -6 x1 +6 x3 +24 x4 = 0 BOUNDS x1 free x2 free x3 free x4 free GENERAL x1 x2 x3 x4 END The interpretation is as follows: The variables x1,...,x4 correspond to the representatives of interior simplices:> print cube(3,group=>1)->GROUP->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES; {0 1 2 4} {0 1 2 5} {0 1 2 7} {0 3 5 6} The solution (x1,x2,x3,x4) = (4,0,0,1) of the LP says that in a minimal triangulation of the 3-cube, there are 4 simplices in the same symmetry class as {0,1,2,4}, and one in the class of {0,3,5,6}.
  •  

    Special purpose functions.

    •  
      edge_orientable (P)

      Checks whether a 2-cubical polytope P is edge-orientable (in the sense of Hetyei), that means that there exits an orientation of the edges such that for each 2-face the opposite edges point in the same direction. It produces the certificates EDGE_ORIENTATION if the polytope is edge-orientable, or MOEBIUS_STRIP_EDGES otherwise. In the latter case, the output can be checked with the client validate_moebius_strip.

      Parameters
      PolytopeP
      the given 2-cubical polytope
    •  
      face_pair (P, S) → Pair<Set,Set>

      For a given set S of rays compute the smallest face F of a cone P containing them all; see also face.

      Parameters
      ConeP
      SetS
      Returns
      Pair<Set,Set>
      where the first is the set of vertices of F, while the second is the set of facets containing F.

      Example:
      • computes the dimension of the face of the 3-cube which is spanned by the vertices 0 and 1> $c=cube(3);> print rank($c->VERTICES->minor(face_pair($c,[0,1])->first(),All))-1; 1
    •  
      lawrence_matrix (M) → Matrix

      UNDOCUMENTED
      Parameters
      MatrixM
      Create the Lawrence matrix Lambda(M) corresponding to M. If M has n rows and d columns, then Lambda(M) equals ( M I_n ) ( 0_{n,d} I_n ).
      Returns
      Matrix
    •  
      matroid_indices_of_hypersimplex_vertices () → Set<Int>

      For a given matroid return the bases as a subset of the vertices of the hypersimplex

      Options
      matroid::Matroidm
      the matroid
      Returns
      Set<Int>
    •  
      m_sequence (h) → Bool

      Test if the given vector is an M-sequence.

      Parameters
      Vector<Int>h
      Returns
      Bool

      Example:
      • The h-vector of a simplicial or simple polytope is an M-sequence.> print m_sequence(cyclic(7,23)->H_VECTOR); true
    •  
      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 points
      Vector<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 space
      Vector<Int>lambda
      height function on lattice points
      Array<Rational>coeff
      coefficients
      Rationals
      additional Parameter in the polynomial
      Options
      topaz::SimplicialComplextriangulation
      The triangulation of the pointset corresponding to the lifting function
    •  
      wronski_system (M, lambda, coeff_array, s)

      Returns a Wronski system of a topaz::FOLDABLE triangulation of a lattice polytope

      Parameters
      Matrix<Int>M
      points (in homogeneous coordinates); affinely span the space
      Vector<Int>lambda
      height function on lattice points
      Array<Array<Rational>>coeff_array
      coefficients
      Rationals
      additional Parameter in the polynomial
      Options
      topaz::SimplicialComplextriangulation
      The triangulation of the pointset corresponding to the lifting function
  •  

    Various constructions of cones.

    •  
      inner_cone (p, F) → Cone

      Computes the inner cone of p at a face F (or a vertex v).

      Parameters
      Conep
      Set<Int>F
      (or Int v) vertex indices which are not contained in the far face
      Options
      Boolouter
      Make it point outside the polytope? Default value is 0 (= point inside)
      Boolattach
      Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity)
      Returns
      Cone

      Examples:
      • To compute the inner cone at a vertex of the 3-cube, do this:> $c = inner_cone(cube(3), 1);> print $c->RAYS; -1 0 0 0 1 0 0 0 1
      • To compute the inner cone along an edge of the 3-cube, and make it point outside the polytope, do this:> print inner_cone(cube(3), [0,1], outer=>1)->RAYS; 0 0 -1 0 -1 0
      • If you want to attach the cone to the polytope, specify the corresponding option:> print normal_cone(cube(3), [0,1], attach=>1)->RAYS; 1 -1 -1 -1 1 1 -1 -1 0 0 1 0 0 0 0 1
    •  
      normal_cone (p, F) → Cone

      Computes the normal cone of p at a face F (or vertex v). By default this is the inner normal cone.

      Parameters
      PointConfigurationp
      Set<Int>F
      (or Int v) point indices which are not contained in the far face
      Options
      Boolouter
      Calculate outer normal cone? Default value is 0 (= inner)
      Boolattach
      Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity)
      Returns
      Cone

      Example:
      • To compute the outer normal cone of a doubled 2-cube, do this:> $v = cube(2)->VERTICES;> $p = new PointConfiguration(POINTS=>($v/$v));> print normal_cone($p, 4, outer=>1)->RAYS; 0 -1 -1 0
    •  
      normal_cone (p, F) → Cone

      Computes the normal cone of p at a face F (or a vertex v). By default this is the inner normal cone.

      Parameters
      Conep
      Set<Int>F
      (or Int v) vertex indices which are not contained in the far face
      Options
      Boolouter
      Calculate outer normal cone? Default value is 0 (= inner)
      Boolattach
      Attach the cone to F? Default 0 (ie, return the cone inside the hyperplane at infinity)
      Returns
      Cone

      Examples:
      • To compute the outer normal cone at a vertex of the 3-cube, do this:> $c = normal_cone(cube(3), 0, outer=>1);> print $c->RAYS; -1 0 0 0 -1 0 0 0 -1
      • To compute the outer normal cone along an edge of the 3-cube, do this:> print normal_cone(cube(3), [0,1], outer=>1)->RAYS; 0 -1 0 0 0 -1
      • If you want to attach the cone to the polytope, specify the corresponding option:> print normal_cone(cube(3), [0,1], outer=>1, attach=>1)->RAYS; 1 -1 -1 -1 1 1 -1 -1 0 0 -1 0 0 0 0 -1
    •  
      recession_cone (P) → Cone<Scalar>

      retuns the recession cone (tail cone, characteristic cone) of a polytope

      Parameters
      Polytope<Scalar>P
      polytope
      Returns
      Cone<Scalar>
    •  
      subcone (C) → Cone

      Make a subcone from a cone.

      Parameters
      ConeC
      the input cone
      Options
      Boolno_labels
      Do not create RAY_LABELS. default: 0
      Returns
      Cone
  •  

    Constructing a point configuration, either from scratch or from existing objects.

    •  
      minkowski_sum (P1, P2) → PointConfiguration

      Produces the Minkowski sum of P1 and P2.


      Example:
      • > $P1 = new PointConfiguration(POINTS=>simplex(2)->VERTICES);> $P2 = new PointConfiguration(POINTS=>[[1,1,1],[1,-1,1],[1,1,-1],[1,-1,-1],[1,0,0]]);> $m = minkowski_sum($P1,$P2);> print $m->POINTS; 1 1 1 1 -1 1 1 1 -1 1 -1 -1 1 0 0 1 2 1 1 0 1 1 2 -1 1 0 -1 1 1 0 1 1 2 1 -1 2 1 1 0 1 -1 0 1 0 1
    •  
      minkowski_sum (lambda, P1, mu, P2) → PointConfiguration

      Produces the polytope lambda*P1+mu*P2, where * and + are scalar multiplication and Minkowski addition, respectively.


      Example:
      • > $P1 = new PointConfiguration(POINTS=>simplex(2)->VERTICES);> $P2 = new PointConfiguration(POINTS=>[[1,1,1],[1,-1,1],[1,1,-1],[1,-1,-1],[1,0,0]]);> $m = minkowski_sum(1,$P1,3,$P2);> print $m->POINTS; 1 3 3 1 -3 3 1 3 -3 1 -3 -3 1 0 0 1 4 3 1 -2 3 1 4 -3 1 -2 -3 1 1 0 1 3 4 1 -3 4 1 3 -2 1 -3 -2 1 0 1
  •  

    Polytope constructions which take graphs as input.

    •  
      flow_polytope <Scalar> (G, Arc_Bounds, source, sink) → Polytope

      Produces the flow polytope of a directed Graph G=(V,E) with a given source and sink. The flow polytope has the following outer description: forall v in V-{source, sink}: sum_{e in E going into v} x_e - sum_{e in E going out of v} x_e = 0

      sum_{e in E going into source} x_e - sum_{e in E going out of source} x_e <= 0

      sum_{e in E going into sink} x_e - sum_{e in E going out of sink} x_e >= 0

      forall e in E: x_e <= given bound on edge e

      Type Parameters
      Scalar
      Parameters
      Graph<Directed>G
      EdgeMap<Directed, Scalar>Arc_Bounds
      Intsource
      Intsink
      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
      Intsource
      Intsink
      Returns
      Polytope
    •  
      fractional_cut_polytope (G) → Polytope

      Cut polytope of an undirected graph.

      Parameters
      GraphG
      Returns
      Polytope
    •  
      fractional_matching_polytope (G) → Polytope

      Matching polytope of an undirected graph.

      Parameters
      GraphG
      Returns
      Polytope
    •  
      tutte_lifting (G) → Polytope

      Let G be 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.

      Parameters
      GraphG
      Returns
      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.

      Parameters
      Matrixencoding
      weighted digraph
      Returns
      polytope::Polytope
  •  

    Polytope constructions which take other big objects as input.

    •  
      billera_lee (H) → Polytope

      Produces a simplicial polytope whose H-vector is the given input vector. The G-vector coming from the given vector must be an M-sequence. This is an implementation of the algorithm described in the paper "A Proof of the Sufficiency of McMullen’s Conditions of Simplicial Convex Polytopes" by Louis Billera and Carl Lee, DOI: 10.1016/0097-3165(81)90058-3

      Parameters
      Vector<Integer>H
      Returns
      Polytope

      Example:
      • > $p = billera_lee([1,5,15,15,5,1]);> print $p->H_VECTOR; 1 5 15 15 5 1
  •  

    An important way of constructing polytopes is to modify an already existing polytope.

    Actually, these functions don't alter the input polytope (it is forbidden in polymake), but create a new polytope object.

    Many functions can at your choice either calculate the vertex or facet coordinates, or constrain themselves on the purely combinatorial description of the resulting polytope.

    •  
      bipyramid (P, z, z_prime) → Polytope

      Make a bipyramid over a pointed polyhedron. The bipyramid is the convex hull of the input polyhedron P and two points (v, z), (v, z_prime) on both sides of the affine span of P. For bounded polyhedra, the apex projections v to the affine span of P coincide with the vertex barycenter of P.

      Parameters
      PolytopeP
      Scalarz
      distance between the vertex barycenter and the first apex, default value is 1.
      Scalarz_prime
      distance between the vertex barycenter and the second apex, default value is -z.
      Options
      Boolno_coordinates
      : don't compute the coordinates, purely combinatorial description is produced.
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new vertices with "Apex" and "Apex'".
      Returns
      Polytope

      Example:
      • Here's a way to construct the 3-dimensional cross polytope:> $p = bipyramid(bipyramid(cube(1)));> print equal_polyhedra($p,cross(3)); true
    •  
      blending (P1, v1, P2, v2) → Polytope

      Compute the blending of two polyhedra at simple vertices. This is a slightly less standard construction. A vertex is simple if its vertex figure is a simplex.

      Moving a vertex v of a bounded polytope to infinity yields an unbounded polyhedron with all edges through v becoming mutually parallel rays. Do this to both input polytopes P1 and P2 at simple vertices v1 and v2, respectively. Up to an affine transformation one can assume that the orthogonal projections of P1 and P2 in direction v1 and v2, respectively, are mutually congruent.

      Any bijection b from the set of edges through v1 to the edges through v2 uniquely defines a way of glueing the unbounded polyhedra to obtain a new bounded polytope, the blending with respect to b. The bijection is specified as a permutation of indices 0 1 2 etc. The default permutation is the identity.

      The number of vertices of the blending is the sum of the numbers of vertices of the input polytopes minus 2. The number of facets is the sum of the numbers of facets of the input polytopes minus the dimension.

      The resulting polytope is described only combinatorially.

      Parameters
      PolytopeP1
      Intv1
      the index of the first vertex
      PolytopeP2
      Intv2
      the index of the second vertex
      Options
      Array<Int>permutation
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytopes. default: 0
      Returns
      Polytope

      Example:
      • The following gives the smallest EVEN 3-polytope which is not a zonotope.> $c = cube(3); $bc = blending($c,0,$c,0);> print $bc->EVEN true> print $bc->F_VECTOR 14 21 9
    •  
      cayley_embedding (P_0, P_1, t_0, t_1) → Polytope

      Create a Cayley embedding of two polytopes (one of them must be pointed). The vertices of the first polytope P_0 get embedded to (t_0,0) and the vertices of the second polytope P_1 to (0,t_1).

      Default values are t_0=t_1=1.

      Parameters
      PolytopeP_0
      the first polytope
      PolytopeP_1
      the second polytope
      Scalart_0
      the extra coordinate for the vertices of P_0
      Scalart_1
      the extra coordinate for the vertices of P_1
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0
      Returns
      Polytope
    •  
      cayley_embedding (A) → Polytope

      Create a Cayley embedding of an array (P1,...,Pm) of polytopes. All polytopes must have the same dimension, at least one of them must be pointed, and all must be defined over the same number type. Each vertex v of the i-th polytope is embedded to v|t_i e_i, where t_i is the i-th entry of the optional array t.

      Parameters
      Array<Polytope>A
      the input polytopes
      Options
      Array<Scalar>factors
      array of scaling factors for the Cayley embedding; defaults to the all-1 vector
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0
      Returns
      Polytope
    •  
      cayley_polytope (P_Array) → Polytope

      Construct the cayley polytope of a set of pointed lattice polytopes contained in P_Array which is the convex hull of P1×e1, ..., Pk×ek where e1, ...,ek are the standard unit vectors in Rk. In this representation the last k coordinates always add up to 1. The option proj projects onto the complement of the last coordinate.

      Parameters
      Array<Polytope>P_Array
      an array containing the lattice polytopes P1,...,Pk
      Options
      Boolproj
      Returns
      Polytope
    •  
      cells_from_subdivision (P, cells) → Polytope<Scalar>

      Extract the given cells of the subdivision of a polyhedron and create a new polyhedron that has as vertices the vertices of the cells.

      Parameters
      Polytope<Scalar>P
      Set<Int>cells
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0
      Returns
      Polytope<Scalar>

      Example:
      • First we create a nice subdivision for a small polytope:> $p = new Polytope(VERTICES=>[[1,0,0],[1,0,1],[1,1,0],[1,1,1],[1,3/2,1/2]]);> $p->POLYTOPAL_SUBDIVISION(MAXIMAL_CELLS=>[[0,1,3],[1,2,3],[2,3,4]]); Then we create the polytope that has as vertices the vertices from cell 1 and 2, while keeping their labels.> $c = cells_from_subdivision($p,[1,2]);> print $c->VERTICES; 1 0 1 1 1 0 1 1 1 1 3/2 1/2> print $c->VERTEX_LABELS; 1 2 3 4
    •  
      cell_from_subdivision (P, cell) → Polytope

      Extract the given cell of the subdivision of a polyhedron and write it as a new polyhedron.

      Parameters
      PolytopeP
      Intcell
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0
      Returns
      Polytope

      Example:
      • First we create a nice subdivision for our favourite 2-polytope, the square:> $p = cube(2);> $p->POLYTOPAL_SUBDIVISION(MAXIMAL_CELLS=>[[0,1,3],[1,2,3]]); Then we extract the [1,2,3]-cell, copying the vertex labels.> $c = cell_from_subdivision($p,1);> print $c->VERTICES; 1 1 -1 1 -1 1 1 1 1> print $c->VERTEX_LABELS; 1 2 3
    •  
      conv (P_Array) → PropagatedPolytope

      Construct a new polyhedron as the convex hull of the polyhedra given in P_Array.

      Parameters
      Array<Polytope>P_Array
      Returns
      PropagatedPolytope

      Example:
      • > $p = conv([cube(2,1,0),cube(2,6,5)]);> print $p->VERTICES; 1 0 0 1 1 0 1 0 1 1 6 5 1 5 6 1 6 6
    •  
      dual_linear_program (P, maximize) → Polytope

      Produces the dual linear program for a given linear program of the form min {cx | Ax >= b, Bx = d}. Here (A,b) are given by the FACETS (or the INEQAULITIES), and (B,d) are given by the AFFINE_HULL (or by the EQUATIONS) of the polytope P, while the objective function c comes from an LP subobject.

      Parameters
      PolytopeP
      = {x | Ax >= b, Bx = d}
      Boolmaximize
      tells if the primal lp is a maximization problem. Default value is 0 (= minimize)
      Returns
      Polytope
    •  
      edge_middle (P) → Polytope

      Produce the convex hull of all edge middle points of some polytope P. The polytope must be BOUNDED.

      Parameters
      PolytopeP
      Returns
      Polytope
    •  
      face (P, S) → Cone

      For a given set S of rays compute the smallest face F of a cone P containing them all; see also face_pair.

      Parameters
      ConeP
      SetS
      Options
      Boolno_coordinates
      don't copy the coordinates, produce purely combinatorial description.
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0
      Returns
      Cone

      Example:
      • To create a cone from the vertices of the zeroth facet of the 3-cube, type this:> $p = face(cube(3),[0,1]);
    •  
      facet (P, facet) → Cone

      Extract the given facet of a polyhedron and write it as a new polyhedron.

      Parameters
      ConeP
      Intfacet
      Options
      Boolno_coordinates
      don't copy the coordinates, produce purely combinatorial description.
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0
      Returns
      Cone

      Example:
      • To create a cone from the vertices of the zeroth facet of the 3-cube, type this:> $p = facet(cube(3),0);
    •  
      facet_to_infinity (P, i) → Polytope

      Make an affine transformation such that the i-th facet is transformed to infinity

      Parameters
      PolytopeP
      Inti
      the facet index
      Returns
      Polytope

      Example:
      • This generates the polytope that is the positive quadrant in 2-space:> $q = new Polytope(VERTICES=>[[1,-1,-1],[1,0,1],[1,1,0]]);> $pf = facet_to_infinity($q,2);> print $pf->VERTICES; 0 -1 -1 0 0 1 1 0 1
    •  
      free_sum (P1, P2) → Polytope

      Construct a new polyhedron as the free sum of two given bounded ones.

      Parameters
      PolytopeP1
      PolytopeP2
      Options
      Boolforce_centered
      if the input polytopes must be centered. Defaults to true.
      Boolno_coordinates
      produces a pure combinatorial description. Defaults to false.
      Returns
      Polytope

      Example:
      • > $p = free_sum(cube(2),cube(2));> print $p->VERTICES; 1 -1 -1 0 0 1 1 -1 0 0 1 -1 1 0 0 1 1 1 0 0 1 0 0 -1 -1 1 0 0 1 -1 1 0 0 -1 1 1 0 0 1 1
    •  
      free_sum_decomposition (P) → Array<Polytope>

      Decompose a given polytope into the free sum of smaller ones

      Parameters
      PolytopeP
      Returns
      Array<Polytope>
    •  
      free_sum_decomposition_indices (P) → Array<Set>

      Decompose a given polytope into the free sum of smaller ones, and return the vertex indices of the summands

      Parameters
      PolytopeP
      Returns
      Array<Set>

      Example:
      • > $p = free_sum(cube(1),cube(1));> print $p->VERTICES; 1 -1 0 1 1 0 1 0 -1 1 0 1> print free_sum_decomposition_indices($p); {0 1} {2 3}
    •  
      gc_closure (P) → Polytope

      Produces the gomory-chvatal closure of a full dimensional polyhedron

      Parameters
      PolytopeP
      Returns
      Polytope
    •  
      integer_hull (P) → Polytope

      Produces the integer hull of a polyhedron

      Parameters
      PolytopeP
      Returns
      Polytope

      Example:
      • > $p = new Polytope(VERTICES=>[[1,13/10,1/2],[1,1/5,6/5],[1,1/10,-3/2],[1,-7/5,1/5]]);> $ih = integer_hull($p);> print $ih->VERTICES; 1 -1 0 1 0 -1 1 0 1 1 1 0
    •  
      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.

      Parameters
      ConeC ...
      polyhedra and cones to be intersected
      Returns
      Cone

      Example:
      • > $p = intersection(cube(2), cross(2,3/2));> print $p->VERTICES; 1 -1/2 1 1 -1 1/2 1 1/2 1 1 1 1/2 1 1/2 -1 1 1 -1/2 1 -1/2 -1 1 -1 -1/2
    •  
      join_polytopes (P1, P2) → Polytope

      Construct a new polyhedron as the join of two given bounded ones.

      Parameters
      PolytopeP1
      PolytopeP2
      Options
      Boolno_coordinates
      produces a pure combinatorial description.
      Boolgroup
      Compute the canonical group induced by the groups on P1 and P2 Throws an exception if the GROUPs of the input polytopes are not provided. default 0
      Returns
      Polytope

      Example:
      • To join two squares, use this:> $p = join_polytopes(cube(2),cube(2));> print $p->VERTICES; 1 -1 -1 -1 0 0 1 1 -1 -1 0 0 1 -1 1 -1 0 0 1 1 1 -1 0 0 1 0 0 1 -1 -1 1 0 0 1 1 -1 1 0 0 1 -1 1 1 0 0 1 1 1
    •  
      lattice_bipyramid (P, v, v_prime, z, z_prime) → Polytope

      Make a lattice bipyramid over a polyhedron. The bipyramid is the convex hull of the input polyhedron P and two points (v, z), (v_prime, z_prime) on both sides of the affine span of P.

      Parameters
      PolytopeP
      Vectorv
      basis point for the first apex
      Vectorv_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.
      Rationalz
      height for the first apex, default value is 1
      Rationalz_prime
      height for the second apex, default value is -z
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new vertices with "Apex" and "Apex'".
      Returns
      Polytope

      Example:
      • To create the bipyramid over a square and keep the vertex labels, do this:> $p = lattice_bipyramid(cube(2),new Vector(1,0,0));> print $p->VERTICES; 1 -1 -1 0 1 1 -1 0 1 -1 1 0 1 1 1 0 1 0 0 1 1 0 0 -1> print $p->VERTEX_LABELS; 0 1 2 3 Apex Apex'
    •  
      lattice_pyramid (P, z, v) → Polytope

      Make a lattice pyramid over a polyhedron. The pyramid is the convex hull of the input polyhedron P and a point v outside the affine span of P.

      Parameters
      PolytopeP
      Rationalz
      the height for the apex (v,z), default value is 1.
      Vectorv
      the lattice point to use as apex, default is the first vertex of P.
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new top vertex with "Apex".
      Returns
      Polytope

      Example:
      • To create the pyramid of height 5 over a square and keep the vertex labels, do this:> $p = lattice_pyramid(cube(2),5,new Vector(1,0,0));> print $p->VERTICES; 1 -1 -1 0 1 1 -1 0 1 -1 1 0 1 1 1 0 1 0 0 5> print $p->VERTEX_LABELS; 0 1 2 3 Apex
    •  
      lawrence (P) → Cone

      Create the Lawrence polytope Lambda(P) corresponding to P. Lambda(P) has the property that Gale(Lambda(P)) = Gale(P) union -Gale(P).

      Parameters
      ConeP
      an input cone or polytope
      Returns
      Cone
      the Lawrence cone or polytope to P
    •  
      make_totally_dual_integral (P) → Polytope

      Produces a polyhedron with an totally dual integral inequality formulation of a full dimensional polyhedron

      Parameters
      PolytopeP
      Returns
      Polytope
    •  
      mapping_polytope (P1, P2) → Polytope

      Construct a new polytope as the mapping polytope of two polytopes P1 and P2. The mapping polytope is the set of all affine maps from Rp to Rq, that map P1 into P2.

      The label of a new facet corresponding to v1 and h1 will have the form "v1*h1".

      Parameters
      PolytopeP1
      PolytopeP2
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0
      Returns
      Polytope
    •  
      minkowski_sum (P1, P2) → Polytope

      Produces the Minkowski sum of P1 and P2.

      Parameters
      PolytopeP1
      PolytopeP2
      Returns
      Polytope

      Example:
      • The following stores the minkowski sum of a square and a triangle in the variable $p and then prints its vertices.> $p = minkowski_sum(cube(2),simplex(2));> print $p->VERTICES; 1 -1 -1 1 2 -1 1 -1 2 1 2 1 1 1 2
    •  
      minkowski_sum (lambda, P1, mu, P2) → Polytope

      Produces the polytope lambda*P1+mu*P2, where * and + are scalar multiplication and Minkowski addition, respectively.

      Parameters
      Scalarlambda
      PolytopeP1
      Scalarmu
      PolytopeP2
      Returns
      Polytope

      Example:
      • The following stores the minkowski sum of a scaled square and a triangle in the variable $p and then prints its vertices.> $p = minkowski_sum(2,cube(2),1,simplex(2));> print $p->VERTICES; 1 -2 -2 1 3 -2 1 -2 3 1 3 2 1 2 3
    •  
      minkowski_sum_fukuda (summands) → Polytope<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.

      Example:
      • > $p = minkowski_sum_fukuda([cube(2),simplex(2),cross(2)]);> print $p->VERTICES; 1 3 -1 1 3 1 1 -1 -2 1 1 3 1 -1 3 1 2 -2 1 -2 2 1 -2 -1
    •  
      mixed_integer_hull (P, int_coords) → Polytope

      Produces the mixed integer hull of a polyhedron

      Parameters
      PolytopeP
      Array<Int>int_coords
      the coordinates to be integral;
      Returns
      Polytope
    •  
      pointed_part (P) → Polytope

      Produces the pointed part of a polyhedron

      Parameters
      PolytopeP
      Returns
      Polytope

      Example:
      • > $p = new Polytope(POINTS=>[[1,0,0],[1,0,1],[1,1,0],[1,1,1],[0,1,0],[0,0,1]]);> $pp = pointed_part($p);> print $pp->VERTICES; 1 0 0 0 1 0 0 0 1
    •  
      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
      PolytopeP
      the input polytope
      Scalarz1
      the left endpoint of the interval; default value: -1
      Scalarz2
      the right endpoint of the interval; default value: -z1
      Options
      Boolgroup
      Compute the canonical group induced by the group on P with an extra generator swapping the upper and lower copy. throws an exception if GROUP of P is not provided. default 0
      Boolno_coordinates
      only combinatorial information is handled
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 the bottom facet vertices get the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended.
      Returns
      Polytope

      Example:
      • The following saves the prism over the square and the interval [-2,2] to the variable $p, and then prints a nice representation of its vertices.> $p = prism(cube(2),-2);> print rows_labeled($p->VERTICES,$p->VERTEX_LABELS); 0:1 -1 -1 -2 1:1 1 -1 -2 2:1 -1 1 -2 3:1 1 1 -2 0':1 -1 -1 2 1':1 1 -1 2 2':1 -1 1 2 3':1 1 1 2
    •  
      product (P1, P2) → Polytope

      Construct a new polytope as the product of two given polytopes P1 and P2. As little additional properties of the input polytopes as possible are computed. You can control this behaviour using the option flags.

      Parameters
      PolytopeP1
      PolytopeP2
      Options
      Boolno_coordinates
      only combinatorial information is handled
      Boolno_vertices
      do not compute vertices
      Boolno_facets
      do not compute facets
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytopes, if present. the label of a new vertex corresponding to v1 ⊕ v2 will have the form LABEL_1*LABEL_2. default: 0
      Boolgroup
      Compute the canonical group of the product, as induced by the groups on FACETS of VERTICES of P1 and P2. If neither FACETS_ACTION nor VERTICES_ACTION of the GROUPs of the input polytopes are provided, an exception is thrown. default 0
      Returns
      Polytope

      Example:
      • The following builds the product of a square and an interval, without computing vertices of neither the input nor the output polytopes.> $p = product(cube(2),cube(1), no_vertices=>1);
    •  
      projection (P, indices) → Cone

      Orthogonally project a pointed polyhedron to a coordinate subspace.

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

      Parameters
      ConeP
      Array<Int>indices
      Options
      Boolrevert
      inverts the coordinate list
      Boolnofm
      suppresses Fourier-Motzkin elimination
      Returns
      Cone

      Example:
      • project the 3-cube along the first coordinate, i.e. to the subspace spanned by the second and third coordinate:> $p = projection(cube(3),[1],revert=>1);> print $p->VERTICES; 1 1 -1 1 1 1 1 -1 1 1 -1 -1
    •  
      projection_preimage (P_Array) → Cone

      Construct a new polyhedron that projects to a given array of polyhedra. If the n polyhedra are d_1, d_2, ..., d_n-dimensional and all have m vertices, the resulting polyhedron is (d_1+...+d_n)-dimensional, has m vertices, and the projection to the i-th d_i coordinates gives the i-th input polyhedron.

      Parameters
      Array<Cone>P_Array
      Returns
      Cone

      Example:
      • > $p = projection_preimage(cube(2),cube(2));> print $p->VERTICES; 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 1 1 1 1 1
    •  
      project_full (P) → Cone

      Orthogonally project a polyhedron to a coordinate subspace such that redundant columns are omitted, i.e., the projection becomes full-dimensional without changing the combinatorial type. The client scans for all coordinate sections and produces proper output from each. If a description in terms of inequalities is found, the client performs Fourier-Motzkin elimination unless the nofm option is set. Setting the nofm option is useful if the corank of the projection is large; in this case the number of inequalities produced grows quickly.

      Parameters
      ConeP
      Options
      Boolnofm
      suppresses Fourier-Motzkin elimination
      Boolno_labels
      Do not copy VERTEX_LABELS to the projection. default: 0
      Returns
      Cone
    •  
      pyramid (P, z) → Polytope

      Make a pyramid over a polyhedron. The pyramid is the convex hull of the input polyhedron P and a point v outside the affine span of P. For bounded polyhedra, the projection of v to the affine span of P coincides with the vertex barycenter of P.

      Parameters
      PolytopeP
      Scalarz
      is the distance between the vertex barycenter and v, default value is 1.
      Options
      Boolgroup
      compute the group induced by the GROUP of P and leaving the apex fixed. throws an exception if GROUP of P is not provided. default 0
      Boolno_coordinates
      don't compute new coordinates, produce purely combinatorial description.
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 label the new top vertex with "Apex".
      Returns
      Polytope

      Example:
      • The following saves the pyramid of height 2 over the square to the variable $p. The vertices are relabeled.> $p = pyramid(cube(2),2); To print the vertices and vertex labels of the newly generated pyramid, do this:> print $p->VERTICES; 1 -1 -1 0 1 1 -1 0 1 -1 1 0 1 1 1 0 1 0 0 2> print $p->VERTEX_LABELS; 0 1 2 3 Apex
    •  
      rand_inner_points (P, n) → Polytope

      Produce a polytope with n random points from the input polytope P. Each generated point is a convex linear combination of the input vertices with uniformly distributed random coefficients. Thus, the output points can't in general be expected to be distributed uniformly within the input polytope; cf. unirand for this. The polytope must be BOUNDED.

      Parameters
      PolytopeP
      the input polytope
      Intn
      the number of random points
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Polytope
    •  
      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.

      Parameters
      MatrixV
      the vertices of a polytope
      Intn
      the number of random points
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Matrix
    •  
      spherize (P) → Polytope

      Project all vertices of a polyhedron P on the unit sphere. P must be CENTERED and BOUNDED.

      Parameters
      PolytopeP
      Returns
      Polytope

      Example:
      • The following scales the 2-dimensional cross polytope by 23 and then projects it back onto the unit circle.> $p = scale(cross(2),23);> $s = spherize($p);> print $s->VERTICES; 1 1 0 1 -1 0 1 0 1 1 0 -1
    •  
      stack (P, stack_facets) → Polytope

      Stack a (simplicial or cubical) polytope over one or more of its facets.

      For each facet of the polytope P specified in stack_facets, the barycenter of its vertices is lifted along the normal vector of the facet. In the simplicial case, this point is directly added to the vertex set, thus building a pyramid over the facet. In the cubical case, this pyramid is truncated by a hyperplane parallel to the original facet at its half height. This way, the property of being simplicial or cubical is preserved in both cases.

      The option lift controls the exact coordinates of the new vertices. It should be a rational number between 0 and 1, which expresses the ratio of the distance between the new vertex and the stacked facet, to the maximal possible distance. When lift=0, the new vertex would lie on the original facet. lift=1 corresponds to the opposite extremal case, where the new vertex hit the hyperplane of some neighbor facet. As an additional restriction, the new vertex can't lie further from the facet as the vertex barycenter of the whole polytope. Alternatively, the option noc (no coordinates) can be specified to produce a pure combinatorial description of the resulting polytope.

      Parameters
      PolytopeP
      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
      Rationallift
      controls the exact coordinates of the new vertices; rational number between 0 and 1; default value: 1/2
      Boolno_coordinates
      produces a pure combinatorial description (in contrast to lift)
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 New vertices get labels 'f(FACET_LABEL)' in the simplicial case, and 'f(FACET_LABEL)-NEIGHBOR_VERTEX_LABEL' in the cubical case.
      Returns
      Polytope

      Example:
      • To generate a cubical polytope by stacking all facets of the 3-cube to height 1/4, do this:> $p = stack(cube(3),All,lift=>1/4);
    •  
      stellar_all_faces (P, d) → Polytope

      Perform a stellar subdivision of all proper faces, starting with the facets.

      Parameter d specifies the lowest dimension of the faces to be divided. It can also be negative, then treated as the co-dimension. Default is 1, that is, the edges of the polytope.

      Parameters
      PolytopeP
      , must be bounded
      Intd
      the lowest dimension of the faces to be divided; negative values: treated as the co-dimension; default value: 1.
      Returns
      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.

      Parameters
      PolytopeP
      , must be bounded
      Array<Set<Int>>in_faces
      Returns
      Polytope
    •  
      tensor (P1, P2) → Polytope

      Construct a new polytope as the convex hull of the tensor products of the vertices of two polytopes P1 and P2. Unbounded polyhedra are not allowed. Does depend on the vertex coordinates of the input.

      Parameters
      PolytopeP1
      PolytopeP2
      Returns
      Polytope

      Example:
      • The following creates the tensor product polytope of two squares and then prints its vertices.> $p = tensor(cube(2),cube(2));> print $p->VERTICES; 1 1 1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1
    •  
      truncation (P, trunc_vertices) → Polytope

      Cut off one or more vertices of a polyhedron.

      The exact location of the cutting hyperplane(s) can be controlled by the option cutoff, a rational number between 0 and 1. When cutoff=0, the hyperplane would go through the chosen vertex, thus cutting off nothing. When cutoff=1, the hyperplane touches the nearest neighbor vertex of a polyhedron.

      Alternatively, the option no_coordinates can be specified to produce a pure combinatorial description of the resulting polytope, which corresponds to the cutoff factor 1/2.

      Parameters
      PolytopeP
      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
      Scalarcutoff
      controls the exact location of the cutting hyperplane(s); rational number between 0 and 1; default value: 1/2
      Boolno_coordinates
      produces a pure combinatorial description (in contrast to cutoff)
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 New vertices get labels of the form 'LABEL1-LABEL2', where LABEL1 is the original label of the truncated vertex, and LABEL2 is the original label of its neighbor.
      Returns
      Polytope

      Example:
      • To truncate the second vertex of the square at 1/4, try this:> $p = truncation(cube(2),2,cutoff=>1/4);> print $p->VERTICES; 1 -1 -1 1 1 -1 1 1 1 1 -1 1/2 1 -1/2 1
    •  
      unirand (P, n) → Polytope

      Produce a polytope with n random points that are uniformly distributed within the given polytope P. P must be bounded and full-dimensional.

      Parameters
      PolytopeP
      Intn
      the number of random points
      Options
      Boolboundary
      forces the points to lie on the boundary of the given polytope
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Polytope

      Examples:
      • This produces a polytope as the convex hull of 5 random points in the square with the origin as its center and side length 2:> $p = unirand(cube(2),5);
      • This produces a polytope as the convex hull of 5 random points on the boundary of the square with the origin as its center and side length 2:> $p = unirand(cube(2),5,boundary=>1);
    •  
      vertex_figure (p, n) → Polytope

      Construct the vertex figure of the vertex n of a polyhedron. The vertex figure is dual to a facet of the dual polytope.

      Parameters
      Polytopep
      Intn
      number of the chosen vertex
      Options
      Scalarcutoff
      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.
      Boolno_coordinates
      skip the coordinates computation, producing a pure combinatorial description.
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytope. default: 0 by default, the labels are produced from the corresponding neighbor vertices of the original polytope.
      Returns
      Polytope

      Example:
      • This produces a vertex figure of one vertex of a 3-dimensional cube with the origin as its center and side length 2. The result is a 2-simplex.> $p = vertex_figure(cube(3),5);> print $p->VERTICES; 1 1 -1 0 1 0 -1 1 1 1 0 1
    •  
      wedge (P, facet, z, z_prime) → Polytope

      Make a wedge from a polytope over the given facet. The polytope must be bounded. The inclination of the bottom and top side facet is controlled by z and z_prime, which are heights of the projection of the old vertex barycenter on the bottom and top side facet respectively.

      Parameters
      PolytopeP
      , must be bounded
      Intfacet
      the `cutting edge'.
      Rationalz
      default value is 0.
      Rationalz_prime
      default value is -z, or 1 if z==0.
      Options
      Boolno_coordinates
      don't compute coordinates, pure combinatorial description is produced.
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytopes. default: 0 By default, the vertices get labelled as follows: The bottom facet vertices obtain the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended.
      Returns
      Polytope

      Example:
      • This produces the wedge from a square (over the facet 0), which yields a prism over a triangle:> $p = wedge(cube(2),0);> print $p->VERTICES; 1 -1 -1 0 1 1 -1 0 1 -1 1 0 1 1 1 0 1 1 -1 2 1 1 1 2
    •  
      wreath (P1, P2) → Polytope

      Construct a new polytope as the wreath product of two input polytopes P1, P2. P1 and P2 have to be BOUNDED.

      Parameters
      PolytopeP1
      PolytopeP2
      Options
      Booldual
      invokes the computation of the dual wreath product
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytopes. default: 0 the label of a new vertex corresponding to v1 ⊕ v2 will have the form LABEL_1*LABEL_2.
      Returns
      Polytope
  •  

    With these clients you can create polytopes belonging to various parameterized families which occur frequently in polytope theory, as well as several kinds of random polytopes. Regular polytopes and their friends are listed separately.

    •  
      associahedron (d) → Polytope

      Produce a d-dimensional associahedron (or Stasheff polytope). We use the facet description given in Ziegler's book on polytopes, section 9.2.

      Parameters
      Intd
      the dimension
      Options
      Boolgroup
      Compute the combinatorial symmetry group of the polytope. It has two generators, as it is induced by the symmetry group of an d+3-gon, the dihedral group of degree d+3. See arXiv 1109.5544v2 for details.
      Returns
      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 biology
      by L. Pachter and B. Sturmfels (eds.), Cambridge, 2005.
      Parameters
      Array<Bool>observation
      Returns
      PropagatedPolytope
    •  
      binary_markov_graph (observation)

      Parameters
      Stringobservation
      encoded as a string of "0" and "1".
    •  
      birkhoff (n, even) → Polytope

      Constructs the Birkhoff polytope of dimension n2. It is the polytope of nxn stochastic matrices (encoded as n2 row vectors), thus matrices with non-negative entries whose row and column entries sum up to one. Its vertices are the permutation matrices.

      Parameters
      Intn
      Booleven
      Defaults to '0'. Set this to '1' to get vertices only for even permutation matrices.
      Options
      Boolgroup
      add the symmetry group induced by the symmetric group to the resulting polytope
      Returns
      Polytope
    •  
      cyclic (d, n) → Polytope<Rational>

      Produce a d-dimensional cyclic polytope with n points. Prototypical example of a neighborly polytope. Combinatorics completely known due to Gale's evenness criterion. Coordinates are chosen on the (spherical) moment curve at integer steps from start, or 0 if unspecified. If spherical is true the vertices lie on the sphere with center (1/2,0,...,0) and radius 1/2. In this case (the necessarily positive) parameter start defaults to 1.

      Parameters
      Intd
      the dimension
      Intn
      the number of points
      Options
      Intstart
      defaults to 0 (or to 1 if spherical)
      Boolspherical
      defaults to false
      Returns
      Polytope<Rational>

      Example:
      • To create the 2-dimensional cyclic polytope with 6 points on the sphere, starting at 3:> $p = cyclic(2,6,start=>3,spherical=>1);> print $p->VERTICES; 1 1/10 3/10 1 1/17 4/17 1 1/26 5/26 1 1/37 6/37 1 1/50 7/50 1 1/65 8/65
    •  
      cyclic_caratheodory (d, n) → Polytope

      Produce a d-dimensional cyclic polytope with n points. Prototypical example of a neighborly polytope. Combinatorics completely known due to Gale's evenness criterion. Coordinates are chosen on the trigonometric moment curve. For cyclic polytopes from other curves, see polytope::cyclic.

      Parameters
      Intd
      the dimension. Required to be even.
      Intn
      the number of points
      Options
      Boolgroup
      add a symmetry group description. If 0 (default), the return type is Polytope<Rational>, else Polytope<Float> so that the matrices corresponding to the symmetry action may be approximated
      Returns
      Polytope
    •  
      delpezzo (d, scale) → Polytope<Scalar>

      Produce a d-dimensional del-Pezzo polytope, which is the convex hull of the cross polytope together with the all-ones and minus all-ones vector.

      All coordinates are +/- scale or 0.

      Parameters
      Intd
      the dimension
      Scalarscale
      the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.
      Returns
      Polytope<Scalar>
    •  
      dwarfed_cube (d) → Polytope

      Produce a d-dimensional dwarfed cube.

      Parameters
      Intd
      the dimension
      Returns
      Polytope
    •  
      dwarfed_product_polygons (d, s) → Polytope

      Produce a d-dimensional dwarfed product of polygons of size s.

      Parameters
      Intd
      the dimension
      Ints
      the size
      Returns
      Polytope
    •  
      explicit_zonotope (zones) → Polytope

      Produce the POINTS of a zonotope as the iterated Minkowski sum of all intervals [-x,x], where x ranges over the rows of the input matrix zones.

      Parameters
      Matrixzones
      the input vectors
      Options
      Boolrows_are_points
      the rows of the input matrix represent affine points(true, default) or linear vectors(false)
      Returns
      Polytope

      Example:
      • > $M = new Matrix([1,1],[1,-1]);> $p = explicit_zonotope($M,rows_are_points=>0);> print $p->VERTICES; 1 2 0 1 0 -2 1 0 2 1 -2 0
    •  
      fano_simplex (d) → Polytope

      Produce a Fano d-simplex.

      Parameters
      Intd
      the dimension
      Options
      Boolgroup
      Returns
      Polytope

      Example:
      • To create the 2-dimensional fano simplex and compute its symmetry group, type this: and print ints generators, do this:> $p = fano_simplex(2,group=>1);> print $p->GROUP->RAYS_ACTION->GENERATORS; 1 0 2 2 0 1
    •  
      fractional_knapsack (b) → Polytope

      Produce a knapsack polytope defined by one linear inequality (and non-negativity constraints).

      Parameters
      Vector<Rational>b
      linear inequality
      Returns
      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.

      Parameters
      Intd
      the dimension
      Scalare
      Scalarg
      Returns
      Polytope
    •  
      goldfarb_sit (d, eps, delta) → Polytope

      Produces a d-dimensional variation of the Klee-Minty cube if eps<1/2 and delta<=1/2. This Klee-Minty cube is scaled in direction x_(d-i) by (eps*delta)^i. This cube is a combinatorial cube and yields a bad example for the Simplex Algorithm using the 'steepest edge' Pivoting Strategy. Here we use a scaled description of the construction of Goldfarb and Sit.

      Parameters
      Intd
      the dimension
      Scalareps
      Scalardelta
      Returns
      Polytope
    •  
      hypersimplex (k, d) → Polytope

      Produce the hypersimplex Δ(k,d), that is the the convex hull of all 0/1-vector in Rd with exactly k 1s. Note that the output is never full-dimensional.

      Parameters
      Intk
      number of 1s
      Intd
      ambient dimension
      Options
      Boolgroup
      Boolno_vertices
      do not compute vertices
      Boolno_facets
      do not compute facets
      Boolno_vif
      do not compute vertices in facets
      Returns
      Polytope

      Example:
      • This creates the hypersimplex in dimension 4 with vertices with exactly two 1-entries and computes its symmetry group:> $h = hypersimplex(2,4,group=>1);
    •  
      hypertruncated_cube <Scalar> (d, k, lambda) → Polytope<Scalar>

      Produce a d-dimensional hypertruncated cube. With symmetric linear objective function (0,1,1,...,1).

      Type Parameters
      Scalar
      Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.
      Parameters
      Intd
      the dimension
      Scalark
      cutoff parameter
      Scalarlambda
      scaling of extra vertex
      Returns
      Polytope<Scalar>
    •  
      klee_minty_cube (d, e) → Polytope

      Produces a d-dimensional Klee-Minty-cube if e<1/2. Uses the goldfarb client with g=0.

      Parameters
      Intd
      the dimension
      Scalare
      Returns
      Polytope
    •  
      k_cyclic (n, s) → Polytope

      Produce a (rounded) 2*k-dimensional k-cyclic polytope with n points, where k is the length of the input vector s. Special cases are the bicyclic (k=2) and tricyclic (k=3) polytopes. Only possible in even dimensions.

      The parameters s_i can be specified as integer, floating-point, or rational numbers. The coordinates of the i-th point are taken as follows:

      cos(s_1 * 2πi/n),
      sin(s_1 * 2πi/n),
      ...
      cos(s_k * 2πi/n),
      sin(s_k * 2πi/n)

      Warning: Some of the k-cyclic polytopes are not simplicial. Since the components are rounded, this function might output a polytope which is not a k-cyclic polytope!

      More information can be found in the following references:

      P. Schuchert: "Matroid-Polytope und Einbettungen kombinatorischer Mannigfaltigkeiten",
      PhD thesis, TU Darmstadt, 1995.
      Z. Smilansky: "Bi-cyclic 4-polytopes",
      Isr. J. Math. 70, 1990, 82-92
      Parameters
      Intn
      the number of points
      Vectors
      s=(s_1,...,s_k)
      Returns
      Polytope

      Example:
      • To produce a (not exactly) regular pentagon, type this:> $p = k_cyclic(5,[1]);
    •  
      lecture_hall_simplex (d) → Polytope

      Produce a lecture hall d-simplex.

      Parameters
      Intd
      the dimension
      Options
      Boolgroup
      Returns
      Polytope

      Example:
      • To create the 2-dimensional lecture hall simplex and compute its symmetry group, type this:> $p = lecture_hall_simplex(2, group=>1);> print $p->GROUP->RAYS_ACTION->GENERATORS; 1 0 2 2 0 1
    •  
      long_and_winding (r) → Polytope<PuiseuxFraction<Max, Rational, Rational> >

      Produce polytope in dimension 2r with 3r+2 facets such that the total curvature of the central path is at least Omega(2^r). This establishes a counter-example to a continuous analog of the Hirsch conjecture by Deza, Terlaky and Zinchenko, Adv. Mech. Math. 17 (2009). The same construction (written in a slightly different form) and its analysis can be found in Allamigeon, Benchimol, Gaubert and Joswig, arXiv:1405.4161 See also perturbed_long_and_winding.

      Parameters
      Intr
      defining parameter
      Options
      Rationaleval_ratio
      parameter for evaluating the puiseux rational functions
      Inteval_exp
      to evaluate at eval_ratio^eval_exp, default: 1
      Floateval_float
      parameter for evaluating the puiseux rational functions
      Returns
      Polytope<PuiseuxFraction<Max, Rational, Rational> >

      Examples:
      • This yields a 4-polytope over the field of Puiseux fractions.> $p = long_and_winding(2);
      • This yields a rational 4-polytope with the same combinatorics.> $p = long_and_winding(2,eval_ratio=>2);
    •  
      max_GC_rank (d) → Polytope

      Produce a d-dimensional polytope of maximal Gomory-Chvatal rank Omega(d/log(d)), integrally infeasible. With symmetric linear objective function (0,1,1..,1). Construction due to Pokutta and Schulz.

      Parameters
      Intd
      the dimension
      Returns
      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.
      Parameters
      Intd
      the dimension
      Intn
      Returns
      Polytope
    •  
      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).
      Parameters
      Intd
      dimension of the polytope
      Intn
      dimension of the equivalent cube
      Returns
      Polytope
    •  
      newton (p) → Polytope<Rational>

      Produce the Newton polytope of a polynomial p.


      Example:
      • Create the newton polytope of 1+x^2+y like so:> local_var_names<Polynomial>(qw(x y)); $p=new Polynomial('1+x^2+y');> $n = newton($p);> print $n->VERTICES; 1 0 0 1 0 1 1 2 0
    •  
      n_gon (n, r, alpha_0) → Polytope

      Produce a regular n-gon. All vertices lie on a circle of radius r. The radius defaults to 1.

      Parameters
      Intn
      the number of vertices
      Rationalr
      the radius (defaults to 1)
      Rationalalpha_0
      the initial angle divided by pi (defaults to 0)
      Options
      Boolgroup
      Returns
      Polytope

      Example:
      • To store the regular pentagon in the variable $p and calculate its symmetry group, do this:> $p = n_gon(5,group=>1);> print $p->GROUP->RAYS_ACTION->GENERATORS; 0 4 3 2 1 1 2 3 4 0
    •  
      perles_irrational_8_polytope () → Polytope

      Create an 8-dimensional polytope without rational realizations due to Perles

      Returns
      Polytope
    •  
      permutahedron (d) → Polytope

      Produce a d-dimensional permutahedron. The vertices correspond to the elements of the symmetric group of degree d+1.

      Parameters
      Intd
      the dimension
      Options
      Boolgroup
      Returns
      Polytope

      Example:
      • To create the 3-permutahedron and also compute its symmetry group, do this:> $p = permutahedron(3,group=>1);> print $p->GROUP->COORDINATE_ACTION->GENERATORS; 1 0 2 3 3 0 1 2
    •  
      perturbed_long_and_winding (r) → Polytope<PuiseuxFraction<Max, Rational, Rational> >

      Produce polytope in dimension 2r with 3r+2 facets such that the total curvature of the central path is at least Omega(2^r). This is a perturbed version of long_and_winding, which yields simple polytopes.

      Parameters
      Intr
      defining parameter
      Options
      Rationaleval_ratio
      parameter for evaluating the puiseux rational functions
      Inteval_exp
      to evaluate at eval_ratio^eval_exp, default: 1
      Floateval_float
      parameter for evaluating the puiseux rational functions
      Returns
      Polytope<PuiseuxFraction<Max, Rational, Rational> >

      Example:
      • This yields a simple 4-polytope over the field of Puiseux fractions.> $p = perturbed_long_and_winding(2);
    •  
      pile (sizes) → Polytope

      Produce a (d+1)-dimensional polytope from a pile of cubes. Start with a d-dimensional pile of cubes. Take a generic convex function to lift this polytopal complex to the boundary of a (d+1)-polytope.

      Parameters
      Vector<Int>sizes
      a vector (s1,...,sd, where si specifies the number of boxes in the i-th dimension.
      Returns
      Polytope
    •  
      pseudo_delpezzo (d, scale) → Polytope<Scalar>

      Produce a d-dimensional del-Pezzo polytope, which is the convex hull of the cross polytope together with the all-ones vector.

      All coordinates are +/- scale or 0.

      Parameters
      Intd
      the dimension
      Scalarscale
      the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.
      Returns
      Polytope<Scalar>
    •  
      rand01 (d, n) → Polytope

      Produce a d-dimensional 0/1-polytope with n random vertices. Uniform distribution.

      Parameters
      Intd
      the dimension
      Intn
      the number of random vertices
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Polytope
    •  
      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.

      Parameters
      Intd
      the dimension of the box
      Intn
      the number of random points
      Intb
      the size of the box
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Polytope
    •  
      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.

      Parameters
      Intd
      the dimension
      Intn
      the number of vertices
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Polytope
    •  
      rand_metric <Scalar> (n) → Matrix

      Produce an n-point metric with random distances. The values are uniformily distributed in [1,2].

      Type Parameters
      Scalar
      element type of the result matrix
      Parameters
      Intn
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Matrix
    •  
      rand_metric_int <Scalar> (n) → Matrix

      Produce an n-point metric with random distances. The values are uniformily distributed in [1,2].

      Type Parameters
      Scalar
      element type of the result matrix
      Parameters
      Intn
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Matrix
    •  
      rand_sphere (d, n) → Polytope

      Produce a d-dimensional polytope with n random vertices uniformly distributed on the unit sphere.

      Parameters
      Intd
      the dimension
      Intn
      the number of random vertices
      Options
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Intprecision
      Number of bits for MPFR sphere approximation
      Returns
      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.
      Parameters
      Intl
      ambient dimension
      Returns
      Polytope
    •  
      signed_permutahedron (d) → Polytope

      Produce a d-dimensional signed permutahedron.

      Parameters
      Intd
      the dimension
      Options
      Boolgroup
      Returns
      Polytope
    •  
      simplex (d, scale) → Polytope

      Produce the standard d-simplex. Combinatorially equivalent to a regular polytope corresponding to the Coxeter group of type Ad-1. Optionally, the simplex can be scaled by the parameter scale.

      Parameters
      Intd
      the dimension
      Scalarscale
      default value: 1
      Options
      Boolgroup
      Returns
      Polytope

      Examples:
      • To print the vertices (in homogeneous coordinates) of the standard 2-simplex, i.e. a right-angled isoceles triangle, type this:> print simplex(2)->VERTICES; (3) (0 1) 1 1 0 1 0 1 The first row vector is sparse and encodes the origin.
      • To create a 3-simplex and also calculate its symmetry group, type this:> simplex(3, group=>1);
    •  
      stable_set (G) → Polytope

      Produces the stable set polytope from an undirected graph G=(V,E). The stable set Polytope has the following inequalities: x_i + x_j <= 1 forall {i,j} in E x_i >= 0 forall i in V x_i <= 1 forall i in V with deg(i)=0

      Parameters
      GraphG
      Returns
      Polytope
    •  
      transportation (r, c) → Polytope

      Produce the transportation polytope from two vectors r of length m and c of length n, i.e. all positive m×n Matrizes with row sums equal to r and column sums equal to c.

      Parameters
      Vectorr
      Vectorc
      Returns
      Polytope
    •  
      upper_bound_theorem (d, n) → Polytope

      Produce combinatorial data common to all simplicial d-polytopes with n vertices with the maximal number of facets as given by McMullen's Upper-Bound-Theorem. Essentially this lets you read off all possible entries of the H_VECTOR and the F_VECTOR.

      Parameters
      Intd
      the dimension
      Intn
      the number of points
      Returns
      Polytope

      Example:
      • This produces the combinatorial data as mentioned above for 5 points in dimension 3 and prints the h-vector:> $p = upper_bound_theorem(3,5);> print $p->H_VECTOR; 1 2 2 1
    •  
      zonotope (M) → Polytope<Scalar>

      Create a zonotope from a matrix whose rows are input points or vectors.

      This method merely defines a Polytope object with the property ZONOTOPE_INPUT_POINTS.

      Parameters
      Matrix<Scalar>M
      input points or vectors
      Options
      Boolrows_are_points
      true if M are points instead of vectors; default true
      Boolcentered
      true if output should be centered; default true
      Returns
      Polytope<Scalar>
      the zonotope generated by the input points or vectors

      Examples:
      • The following produces a parallelogram with the origin as its vertex barycenter:> $M = new Matrix([[1,1,0],[1,1,1]]);> $p = zonotope($M);> print $p->VERTICES; 1 0 -1/2 1 0 1/2 1 -1 -1/2 1 1 1/2
      • The following produces a parallelogram with the origin being a vertex (not centered case):> $M = new Matrix([[1,1,0],[1,1,1]]);> $p = zonotope($M,centered=>0);> print $p->VERTICES; 1 1 0 1 0 0 1 1 1 1 2 1
    •  
      zonotope_vertices_fukuda (M) → Matrix<E>

      Create the vertices of a zonotope from a matrix whose rows are input points or vectors.

      Parameters
      Matrix<Scalar>M
      Options
      Boolcentered_zonotope
      default 1
      Returns
      Matrix<E>

      Example:
      • The following stores the vertices of a parallelogram with the origin as its vertex barycenter and prints them:> $M = new Matrix([[1,1,0],[1,1,1]]);> print zonotope_vertices_fukuda($M); 1 0 -1/2 1 0 1/2 1 -1 -1/2 1 1 1/2
  •  

    A way of constructing vector configurations is to modify an already existing vector configuration.

    •  
      free_sum (P1, P2) → VectorConfiguration

      Construct the free sum of two vector configurations.

      Parameters
      VectorConfigurationP1
      VectorConfigurationP2
      Options
      Boolforce_centered
      if the input polytopes must be centered. Defaults to true.
      Boolno_coordinates
      produces a pure combinatorial description. Defaults to false.
      Returns
      VectorConfiguration
    •  
      projection <Scalar> (P, indices) → VectorConfiguration

      Orthogonally project a vector configuration to a coordinate subspace.

      The subspace the VectorConfiguration P is projected on is given by indices in the set indices. The option revert inverts the coordinate list.

      Type Parameters
      Scalar
      coordinate type
      Parameters
      VectorConfigurationP
      Array<Int>indices
      Options
      Boolrevert
      inverts the coordinate list
      Returns
      VectorConfiguration
    •  
      projection_preimage <Scalar> (P_Array) → VectorConfiguration

      Construct a new vector configuration that projects to a given array of vector configurations If the n vector configurations are d_1, d_2, ..., d_n-dimensional and all have m vectors, the resulting vector configuration is (d_1+...+d_n)-dimensional, has m vectors, and the projection to the i-th d_i coordinates gives the i-th input vector configuration.

      Type Parameters
      Scalar
      coordinate type
      Parameters
      Array<VectorConfiguration>P_Array
      Returns
      VectorConfiguration
    •  
      project_full <Scalar> (P) → VectorConfiguration

      Orthogonally project a vector configuration to a coordinate subspace such that redundant columns are omitted, i.e., the projection becomes full-dimensional without changing the combinatorial type.

      Type Parameters
      Scalar
      coordinate type
      Parameters
      VectorConfigurationP
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS to the projection. default: 0
      Returns
      VectorConfiguration
    •  
      project_out <Scalar> (V, B) → VectorConfiguration

      Project a vector configuration V along the subspace with the given basis B. The result is still expressed in the original ambient basis. If V is a PointConfiguration and the first column of B is zero, the result is a PointConfiguration, else a VectorConfiguration.

      Type Parameters
      Scalar
      coordinate type
      Parameters
      VectorConfigurationV
      MatrixB
      a matrix whose rows contain the basis of the space to be projected out
      Returns
      VectorConfiguration
    •  
      project_out <Scalar> (C, B) → Cone

      Project a Cone C along the subspace with the given basis B The result is still expressed in the original ambient basis. If V is a Polytope and the first column of B is zero, the result is a Polytope, else a Cone.

      Type Parameters
      Scalar
      coordinate type
      Parameters
      ConeC
      MatrixB
      a matrix whose rows contain the basis of the space to be projected out
      Returns
      Cone
    •  
      project_to <Scalar> (V, B) → VectorConfiguration

      Project a vector configuration V to the subspace with a given basis B and express the result in that basis. A boolean flag make_affine (by default undef) determines whether the resulting coordinates acquire an extra leading '1'. The return type is a VectorConfiguration, unless (i) P is a PointConfiguration, (ii) the first column of B is zero, (iii) make_affine is not 0, in which case it is a PointConfiguration. The return type depends on the input: (1) If V is a VectorConfiguration, the result is also a VectorConfiguration. (2a) If V is a PointConfiguration and all rows in B start with a 0, the result is a PointConfiguration. If, furthermore, make_affine is undef, it is set to 1. (2b) If V is a PointConfiguration and some row of B has a non-zero first entry, the result is a VectorConfiguration. The reasoning here is that B having a zero first column or not influences the hyperplane at infinity.

      Type Parameters
      Scalar
      coordinate type
      Parameters
      VectorConfigurationV
      MatrixB
      a matrix whose rows contain the basis of the image space
      Options
      Boolmake_affine
      . If undef (default), apply the above reasoning. If 1 (0), unconditionally (don't) add leading 1's.
      Returns
      VectorConfiguration
      or PointConfiguration
    •  
      project_to <Scalar> (C, B) → Cone

      Project a Polytope or Cone to the subspace with a given basis, and express the result in that basis A boolean flag make_affine (by default undef) determines whether the resulting coordinates acquire an extra leading '1'. The return type is a Cone, unless (i) P is a Polytope, (ii) the first column of B is zero, (iii) make_affine is not 0, in which case it is a Polytope. If make_affine is undef and (ii) is true, make_affine is set to 1. The reasoning here is that B having a zero first column or not influences the hyperplane at infinity.

      Type Parameters
      Scalar
      coordinate type
      Parameters
      ConeC
      MatrixB
      a matrix whose rows contain the basis of the image space
      Returns
      Cone
      or Polytope
  •  

    Functions producing big objects which are not contained in application polytope.

  •  

    This includes the Platonic solids and their generalizations into two directions. In dimension 3 there are the Archimedean, Catalan and Johnson solids. In higher dimensions there are the simplices, the cubes, the cross polytopes and three other regular 4-polytopes.

    •  
      archimedean_solid (s) → Polytope

      Create Archimedean solid of the given name. Some polytopes are realized with floating point numbers and thus not exact; Vertex-facet-incidences are correct in all cases.

      Parameters
      Strings
      the name of the desired Archimedean solid
      Possible values:
      'truncated_tetrahedron'
      Truncated tetrahedron. Regular polytope with four triangular and four hexagonal facets.
      'cuboctahedron'
      Cuboctahedron. Regular polytope with eight triangular and six square facets.
      'truncated_cube'
      Truncated cube. Regular polytope with eight triangular and six octagonal facets.
      'truncated_octahedron'
      Truncated Octahedron. Regular polytope with six square and eight hexagonal facets.
      'rhombicuboctahedron'
      Rhombicuboctahedron. Regular polytope with eight triangular and 18 square facets.
      'truncated_cuboctahedron'
      Truncated Cuboctahedron. Regular polytope with 12 square, eight hexagonal and six octagonal facets.
      'snub_cube'
      Snub Cube. Regular polytope with 32 triangular and six square facets. The vertices are realized as floating point numbers. This is a chiral polytope.
      'icosidodecahedron'
      Icosidodecahedon. Regular polytope with 20 triangular and 12 pentagonal facets.
      'truncated_dodecahedron'
      Truncated Dodecahedron. Regular polytope with 20 triangular and 12 decagonal facets.
      'truncated_icosahedron'
      Truncated Icosahedron. Regular polytope with 12 pentagonal and 20 hexagonal facets.
      'rhombicosidodecahedron'
      Rhombicosidodecahedron. Regular polytope with 20 triangular, 30 square and 12 pentagonal facets.
      'truncated_icosidodecahedron'
      Truncated Icosidodecahedron. Regular polytope with 30 square, 20 hexagonal and 12 decagonal facets.
      'snub_dodecahedron'
      Snub Dodecahedron. Regular polytope with 80 triangular and 12 pentagonal facets. The vertices are realized as floating point numbers. This is a chiral polytope.
      Returns
      Polytope

      Example:
      • To show the mirror image of the snub cube use:> scale(archimedean_solid('snub_cube'),-1)->VISUAL;
    •  
      catalan_solid (s) → Polytope

      Create Catalan solid of the given name. Some polytopes are realized with floating point numbers and thus not exact; Vertex-facet-incidences are correct in all cases.

      Parameters
      Strings
      the name of the desired Catalan solid
      Possible values:
      'triakis_tetrahedron'
      Triakis Tetrahedron. Dual polytope to the Truncated Tetrahedron, made of 12 isosceles triangular facets.
      'triakis_octahedron'
      Triakis Octahedron. Dual polytope to the Truncated Cube, made of 24 isosceles triangular facets.
      'rhombic_dodecahedron'
      Rhombic dodecahedron. Dual polytope to the cuboctahedron, made of 12 rhombic facets.
      'tetrakis_hexahedron'
      Tetrakis hexahedron. Dual polytope to the truncated octahedron, made of 24 isosceles triangluar facets.
      'disdyakis_dodecahedron'
      Disdyakis dodecahedron. Dual polytope to the truncated cuboctahedron, made of 48 scalene triangular facets.
      'pentagonal_icositetrahedron'
      Pentagonal Icositetrahedron. Dual polytope to the snub cube, made of 24 irregular pentagonal facets. The vertices are realized as floating point numbers.
      'pentagonal_hexecontahedron'
      Pentagonal Hexecontahedron. Dual polytope to the snub dodecahedron, made of 60 irregular pentagonal facets. The vertices are realized as floating point numbers.
      'rhombic_triacontahedron'
      Rhombic triacontahedron. Dual polytope to the icosidodecahedron, made of 30 rhombic facets.
      'triakis_icosahedron'
      Triakis icosahedron. Dual polytope to the icosidodecahedron, made of 30 rhombic facets.
      'deltoidal_icositetrahedron'
      Deltoidal Icositetrahedron. Dual polytope to the rhombicubaoctahedron, made of 24 kite facets.
      'pentakis_dodecahedron'
      Pentakis dodecahedron. Dual polytope to the truncated icosahedron, made of 60 isosceles triangular facets.
      'deltoidal_hexecontahedron'
      Deltoidal hexecontahedron. Dual polytope to the rhombicosidodecahedron, made of 60 kite facets.
      'disdyakis_triacontahedron'
      Disdyakis triacontahedron. Dual polytope to the truncated icosidodecahedron, made of 120 scalene triangular facets.
      Returns
      Polytope
    •  
      cross <Scalar> (d, scale) → Polytope<Scalar>

      Produce a d-dimensional cross polytope. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.

      All coordinates are +/- scale or 0.

      Type Parameters
      Scalar
      Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.
      Parameters
      Intd
      the dimension
      Scalarscale
      the absolute value of each non-zero vertex coordinate. Needs to be positive. The default value is 1.
      Options
      Boolgroup
      add a symmetry group description to the resulting polytope
      Boolcharacter_table
      add the character table to the symmetry group description, if 0<d<7; default 1
      Returns
      Polytope<Scalar>

      Example:
      • To create the 3-dimensional cross polytope, type> $p = cross(3); Check out it's vertices and volume:> print $p->VERTICES; 1 1 0 0 1 -1 0 0 1 0 1 0 1 0 -1 0 1 0 0 1 1 0 0 -1> print cross(3)->VOLUME; 4/3 If you rather had a bigger one, type> $p_scaled = cross(3,2);> print $p_scaled->VOLUME; 32/3 To also calculate the symmetry group, do this:> $p = cross(3,group=>1); You can then print the generators of this group like this:> print $p->GROUP->RAYS_ACTION->GENERATORS; 1 0 2 3 4 5 2 3 0 1 4 5 0 1 4 5 2 3
    •  
      cube <Scalar> (d, x_up, x_low) → Polytope<Scalar>

      Produce a d-dimensional cube. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.

      The bounding hyperplanes are xi <= x_up and xi >= x_low.

      Type Parameters
      Scalar
      Coordinate type of the resulting polytope. Unless specified explicitly, deduced from the type of bound values, defaults to Rational.
      Parameters
      Intd
      the dimension
      Scalarx_up
      upper bound in each dimension
      Scalarx_low
      lower bound in each dimension
      Options
      Boolgroup
      add a symmetry group description to the resulting polytope
      Boolcharacter_table
      add the character table to the symmetry group description, if 0<d<7; default 1
      Returns
      Polytope<Scalar>

      Examples:
      • This yields a +/-1 cube of dimension 3 and stores it in the variable $c.> $c = cube(3);
      • This stores a standard unit cube of dimension 3 in the variable $c.> $c = cube(3,0);
      • This prints the area of a square with side length 4 translated to have its vertex barycenter at [5,5]:> print cube(2,7,3)->VOLUME; 16
    •  
      cuboctahedron () → Polytope

      Create cuboctahedron. An Archimedean solid.

      Returns
      Polytope
    •  
      dodecahedron () → Polytope

      Create exact regular dodecahedron in Q(sqrt{5}). A Platonic solid.

      Returns
      Polytope
    •  
      icosahedron () → Polytope

      Create exact regular icosahedron in Q(sqrt{5}). A Platonic solid.

      Returns
      Polytope
    •  
      icosidodecahedron () → Polytope

      Create exact icosidodecahedron in Q(sqrt{5}). An Archimedean solid.

      Returns
      Polytope
    •  
      johnson_solid (n) → Polytope

      Create Johnson solid number n, where 1 <= n <= 92. A Johnson solid is a 3-polytope all of whose facets are regular polygons. Some are realized with floating point numbers and thus not exact; yet VERTICES_IN_FACETS is correct in all cases.

      Parameters
      Intn
      the index of the desired Johnson polytope
      Returns
      Polytope
    •  
      johnson_solid (s) → Polytope

      Create Johnson solid with the given name. A Johnson solid is a 3-polytope all of whose facets are regular polygons. Some are realized with floating point numbers and thus not exact; yet VERTICES_IN_FACETS is correct in all cases.

      Parameters
      Strings
      the name of the desired Johnson polytope
      Possible values:
      'square_pyramid'
      Square pyramid with regular facets. Johnson solid J1.
      'pentagonal_pyramid'
      Pentagonal pyramid with regular facets. Johnson solid J2.
      'triangular_cupola'
      Triangular cupola with regular facets. Johnson solid J3.
      'square_cupola'
      Square cupola with regular facets. Johnson solid J4.
      'pentagonal_cupola'
      Pentagonal cupola with regular facets. Johnson solid J5.
      'pentagonal_rotunda'
      Pentagonal rotunda with regular facets. Johnson solid J6.
      'elongated_triangular_pyramid'
      Elongated triangular pyramid with regular facets. Johnson solid J7.
      'elongated_square_pyramid'
      Elongated square pyramid with regular facets. Johnson solid J8.
      'elongated_pentagonal_pyramid'
      Elongated pentagonal pyramid with regular facets. Johnson solid J9. The vertices are realized as floating point numbers.
      'gyroelongated_square_pyramid'
      Gyroelongated square pyramid with regular facets. Johnson solid J10. The vertices are realized as floating point numbers.
      'gyroelongated_pentagonal_pyramid'
      Gyroelongated pentagonal pyramid with regular facets. Johnson solid J11.
      'triangular_bipyramid'
      Triangular bipyramid with regular facets. Johnson solid J12.
      'pentagonal_bipyramid'
      Pentagonal bipyramid with regular facets. Johnson solid J13. The vertices are realized as floating point numbers.
      'elongated_triangular_bipyramid'
      Elongated triangular bipyramid with regular facets. Johnson solid J14.
      'elongated_square_bipyramid'
      Elongated square bipyramid with regular facets. Johnson solid J15.
      'elongated_pentagonal_bipyramid'
      Elongated pentagonal bipyramid with regular facets. Johnson solid J16. The vertices are realized as floating point numbers.
      'gyroelongated_square_bipyramid'
      Gyroelongted square bipyramid with regular facets. Johnson solid J17. The vertices are realized as floating point numbers.
      'elongated_triangular_cupola'
      Elongted triangular cupola with regular facets. Johnson solid J18. The vertices are realized as floating point numbers.
      'elongated_square_cupola'
      Elongted square cupola with regular facets. Johnson solid J19.
      'elongated_pentagonal_cupola'
      Elongted pentagonal cupola with regular facets. Johnson solid J20 The vertices are realized as floating point numbers.
      'elongated_pentagonal_rotunda'
      Elongated pentagonal rotunda with regular facets. Johnson solid J21. The vertices are realized as floating point numbers.
      'gyroelongated_triangular_cupola'
      Gyroelongted triangular cupola with regular facets. Johnson solid J22. The vertices are realized as floating point numbers.
      'gyroelongated_square_cupola'
      Gyroelongted square cupola with regular facets. Johnson solid J23. The vertices are realized as floating point numbers.
      'gyroelongated_pentagonal_cupola'
      Gyroelongted pentagonal cupola with regular facets. Johnson solid J24. The vertices are realized as floating point numbers.
      'gyroelongated_pentagonal_rotunda'
      Gyroelongted pentagonal rotunda with regular facets. Johnson solid J25. The vertices are realized as floating point numbers.
      'gyrobifastigium'
      Gyrobifastigium with regular facets. Johnson solid J26.
      'triangular_orthobicupola'
      Triangular orthobicupola with regular facets. Johnson solid J27.
      'square_orthobicupola'
      Square orthobicupola with regular facets. Johnson solid J28.
      'square_gyrobicupola'
      Square gyrobicupola with regular facets. Johnson solid J29.
      'pentagonal_orthobicupola'
      Pentagonal orthobicupola with regular facets. Johnson solid J30. The vertices are realized as floating point numbers.
      'pentagonal_gyrobicupola'
      Pentagonal gyrobicupola with regular facets. Johnson solid J31. The vertices are realized as floating point numbers.
      'pentagonal_orthocupolarotunda'
      Pentagonal orthocupolarotunda with regular facets. Johnson solid J32. The vertices are realized as floating point numbers.
      'pentagonal_gyrocupolarotunda'
      Pentagonal gyrocupolarotunda with regular facets. Johnson solid J33. The vertices are realized as floating point numbers.
      'pentagonal_orthobirotunda'
      Pentagonal orthobirotunda with regular facets. Johnson solid J32. The vertices are realized as floating point numbers.
      'elongated_triangular_orthbicupola'
      Elongated triangular orthobicupola with regular facets. Johnson solid J35. The vertices are realized as floating point numbers.
      'elongated_triangular_gyrobicupola'
      Elongated triangular gyrobicupola with regular facets. Johnson solid J36. The vertices are realized as floating point numbers.
      'elongated_square_gyrobicupola'
      Elongated square gyrobicupola with regular facets. Johnson solid J37.
      'elongated_pentagonal_orthobicupola'
      Elongated pentagonal orthobicupola with regular facets. Johnson solid J38. The vertices are realized as floating point numbers.
      'elongated_pentagonal_gyrobicupola'
      Elongated pentagonal gyrobicupola with regular facets. Johnson solid J39. The vertices are realized as floating point numbers.
      'elongated_pentagonal_orthocupolarotunda'
      Elongated pentagonal orthocupolarotunda with regular facets. Johnson solid J40. The vertices are realized as floating point numbers.
      'elongated_pentagonal_gyrocupolarotunda'
      Elongated pentagonal gyrocupolarotunda with regular facets. Johnson solid J41. The vertices are realized as floating point numbers.
      'elongated_pentagonal_orthobirotunda'
      Elongated pentagonal orthobirotunda with regular facets. Johnson solid J42. The vertices are realized as floating point numbers.
      'elongated_pentagonal_gyrobirotunda'
      Elongated pentagonal gyrobirotunda with regular facets. Johnson solid J43. The vertices are realized as floating point numbers.
      'gyroelongated_triangular_bicupola'
      Gyroelongated triangular bicupola with regular facets. Johnson solid J44. The vertices are realized as floating point numbers.
      'elongated_square_bicupola'
      Elongated square bicupola with regular facets. Johnson solid J45. The vertices are realized as floating point numbers.
      'gyroelongated_pentagonal_bicupola'
      Gyroelongated pentagonal bicupola with regular facets. Johnson solid J46. The vertices are realized as floating point numbers.
      'gyroelongated_pentagonal_cupolarotunda'
      Gyroelongated pentagonal cupolarotunda with regular facets. Johnson solid J47. The vertices are realized as floating point numbers.
      'gyroelongated_pentagonal_birotunda'
      Gyroelongated pentagonal birotunda with regular facets. Johnson solid J48. The vertices are realized as floating point numbers.
      'augmented_triangular_prism'
      Augmented triangular prism with regular facets. Johnson solid J49. The vertices are realized as floating point numbers.
      'biaugmented_triangular_prism'
      Biaugmented triangular prism with regular facets. Johnson solid J50. The vertices are realized as floating point numbers.
      'triaugmented_triangular_prism'
      Triaugmented triangular prism with regular facets. Johnson solid J51. The vertices are realized as floating point numbers.
      'augmented_pentagonal_prism'
      Augmented prantagonal prism with regular facets. Johnson solid J52. The vertices are realized as floating point numbers.
      'biaugmented_pentagonal_prism'
      Augmented pentagonal prism with regular facets. Johnson solid J53. The vertices are realized as floating point numbers.
      'augmented_hexagonal_prism'
      Augmented hexagonal prism with regular facets. Johnson solid J54. The vertices are realized as floating point numbers.
      'parabiaugmented_hexagonal_prism'
      Parabiaugmented hexagonal prism with regular facets. Johnson solid J55. The vertices are realized as floating point numbers.
      'metabiaugmented_hexagonal_prism'
      Metabiaugmented hexagonal prism with regular facets. Johnson solid J56. The vertices are realized as floating point numbers.
      'triaugmented_hexagonal_prism'
      triaugmented hexagonal prism with regular facets. Johnson solid J57. The vertices are realized as floating point numbers.
      'augmented_dodecahedron'
      Augmented dodecahedron with regular facets. Johnson solid J58. The vertices are realized as floating point numbers.
      'parabiaugmented_dodecahedron'
      Parabiaugmented dodecahedron with regular facets. Johnson solid J59. The vertices are realized as floating point numbers.
      'metabiaugmented_dodecahedron'
      Metabiaugmented dodecahedron with regular facets. Johnson solid J60. The vertices are realized as floating point numbers.
      'triaugmented_dodecahedron'
      Triaugmented dodecahedron with regular facets. Johnson solid J61. The vertices are realized as floating point numbers.
      'metabidiminished_icosahedron'
      Metabidiminished icosahedron with regular facets. Johnson solid J62.
      'tridiminished_icosahedron'
      Tridiminished icosahedron with regular facets. Johnson solid J63.
      'augmented_tridiminished_icosahedron'
      Augmented tridiminished icosahedron with regular facets. Johnson solid J64. The vertices are realized as floating point numbers.
      'augmented_truncated_tetrahedron'
      Augmented truncated tetrahedron with regular facets. Johnson solid J65.
      'augmented_truncated_cube'
      Augmented truncated cube with regular facets. Johnson solid J66.
      'biaugmented_truncated_cube'
      Biaugmented truncated cube with regular facets. Johnson solid J67.
      'augmented_truncated_dodecahedron'
      Augmented truncated dodecahedron with regular facets. Johnson solid J68. The vertices are realized as floating point numbers.
      'parabiaugmented_truncated_dodecahedron'
      Parabiaugmented truncated dodecahedron with regular facets. Johnson solid J69. The vertices are realized as floating point numbers.
      'metabiaugmented_truncated_dodecahedron'
      Metabiaugmented truncated dodecahedron with regular facets. Johnson solid J70. The vertices are realized as floating point numbers.
      'triaugmented_truncated_dodecahedron'
      Triaugmented truncated dodecahedron with regular facets. Johnson solid J71. The vertices are realized as floating point numbers.
      'gyrate_rhombicosidodecahedron'
      Gyrate rhombicosidodecahedron with regular facets. Johnson solid J72. The vertices are realized as floating point numbers.
      'parabigyrate_rhombicosidodecahedron'
      Parabigyrate rhombicosidodecahedron with regular facets. Johnson solid J73. The vertices are realized as floating point numbers.
      'metabigyrate_rhombicosidodecahedron'
      Metabigyrate rhombicosidodecahedron with regular facets. Johnson solid J74. The vertices are realized as floating point numbers.
      'trigyrate_rhombicosidodecahedron'
      Trigyrate rhombicosidodecahedron with regular facets. Johnson solid J75. The vertices are realized as floating point numbers.
      'diminished_rhombicosidodecahedron'
      Diminished rhombicosidodecahedron with regular facets. Johnson solid J76.
      'paragyrate_diminished_rhombicosidodecahedron'
      Paragyrate diminished rhombicosidodecahedron with regular facets. Johnson solid J77. The vertices are realized as floating point numbers.
      'metagyrate_diminished_rhombicosidodecahedron'
      Metagyrate diminished rhombicosidodecahedron with regular facets. Johnson solid J78. The vertices are realized as floating point numbers.
      'bigyrate_diminished_rhombicosidodecahedron'
      Bigyrate diminished rhombicosidodecahedron with regular facets. Johnson solid J79. The vertices are realized as floating point numbers.
      'parabidiminished_rhombicosidodecahedron'
      Parabidiminished rhombicosidodecahedron with regular facets. Johnson solid J80.
      'metabidiminished_rhombicosidodecahedron'
      Metabidiminished rhombicosidodecahedron with regular facets. Johnson solid J81.
      'gyrate_bidiminished_rhombicosidodecahedron'
      Gyrate bidiminished rhombicosidodecahedron with regular facets. Johnson solid J82. The vertices are realized as floating point numbers.
      'tridiminished_rhombicosidodecahedron'
      Tridiminished rhombicosidodecahedron with regular facets. Johnson solid J83.
      'snub_disphenoid'
      Snub disphenoid with regular facets. Johnson solid J84. The vertices are realized as floating point numbers.
      'snub_square_antisprim'
      Snub square antiprism with regular facets. Johnson solid J85. The vertices are realized as floating point numbers.
      'sphenocorona'
      Sphenocorona with regular facets. Johnson solid J86. The vertices are realized as floating point numbers.
      'augmented_sphenocorona'
      Augmented sphenocorona with regular facets. Johnson solid J87. The vertices are realized as floating point numbers.
      'sphenomegacorona'
      Sphenomegacorona with regular facets. Johnson solid J88. The vertices are realized as floating point numbers.
      'hebesphenomegacorona'
      Hebesphenomegacorona with regular facets. Johnson solid J89. The vertices are realized as floating point numbers.
      'disphenocingulum'
      Disphenocingulum with regular facets. Johnson solid J90. The vertices are realized as floating point numbers.
      'bilunabirotunda'
      Bilunabirotunda with regular facets. Johnson solid J91.
      'triangular_hebesphenorotunda'
      Triangular hebesphenorotunda with regular facets. Johnson solid J92.
      Returns
      Polytope
    •  
      octahedron () → Polytope

      Produce a regular octahedron, which is the same as the 3-dimensional cross polytope.

      Returns
      Polytope
    •  
      platonic_solid (s) → Polytope

      Create Platonic solid of the given name.

      Parameters
      Strings
      the name of the desired Platonic solid
      Possible values:
      'tetrahedron'
      Tetrahedron. Regular polytope with four triangular facets.
      'cube'
      Cube. Regular polytope with six square facets.
      'octahedron'
      Octahedron. Regular polytope with eight triangular facets.
      'dodecahedron'
      Dodecahedron. Regular polytope with 12 pentagonal facets.
      'icosahedron'
      Icosahedron. Regular polytope with 20 triangular facets.
      Returns
      Polytope
    •  
      reduced (t, x, s, h, r) → Polytope<Rational>

      Produce a 3-dimensional reduced polytope (for suitably chosen parameters). That is, a polytope of constant width which does not properly contain a subpolytope of the same width. Construction due to Bernardo González Merino, Thomas Jahn, Alexandr Polyanskii and Gerd Wachsmuth, arXiv:1701.08629


      Example:
      • These values yield a reduced 3-polytope (approximately). The width equals 1.> $r = reduced(0.55, 0.6176490959800, 0.1351384931026, 0.0984300252409, 0.3547183586709);
    •  
      regular_120_cell () → Polytope

      Create exact regular 120-cell in Q(sqrt{5}).

      Returns
      Polytope
    •  
      regular_24_cell () → Polytope

      Create regular 24-cell.

      Returns
      Polytope
    •  
      regular_600_cell () → Polytope

      Create exact regular 600-cell in Q(sqrt{5}).

      Returns
      Polytope
    •  
      regular_simplex (d) → Polytope

      Produce a regular d-simplex embedded in R^d with edge length sqrt(2).

      Parameters
      Intd
      the dimension
      Options
      Boolgroup
      Returns
      Polytope

      Examples:
      • To print the vertices (in homogeneous coordinates) of the regular 2-simplex, i.e. an equilateral triangle, type this:> print regular_simplex(2)->VERTICES; 1 1 0 1 0 1 1 1/2-1/2r3 1/2-1/2r3 The polytopes cordinate type is QuadraticExtension<Rational>, thus numbers that can be represented as a + b*sqrt(c) with Rational numbers a, b and c. The last row vectors entrys thus represent the number 1/2*(1-sqrt(3)).
      • To store a regular 3-simplex in the variable $s and also calculate its symmetry group, type this:> $s = regular_simplex(3, group=>1); You can then print the groups generators like so:> print $s->GROUP->RAYS_ACTION->GENERATORS; 1 0 2 3 3 0 1 2
    •  
      rhombicosidodecahedron () → Polytope

      Create exact rhombicosidodecahedron in Q(sqrt{5}). An Archimedean solid.

      Returns
      Polytope
    •  
      rhombicuboctahedron () → Polytope

      Create rhombicuboctahedron. An Archimedean solid.

      Returns
      Polytope
    •  
      root_system (type) → VectorConfiguration

      Produce the root systems of the Coxeter arrangement of a given type The roots lie at infinity to facilitate reflecting in them.

      Parameters
      Stringtype
      the type of the Coxeter arrangement, for example A4 or E8
      Returns
      VectorConfiguration
    •  
      simple_roots_type_A (index) → SparseMatrix

      Produce the simple roots of the Coxeter arrangement of type A Indices are taken w.r.t. the Dynkin diagram 0 ---- 1 ---- ... ---- n-1 Note that the roots lie at infinity to facilitate reflecting in them, and are normalized to length sqrt{2}.

      Parameters
      Intindex
      of the arrangement (3, 4, etc)
      Returns
      SparseMatrix
    •  
      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}.

      Parameters
      Intindex
      of the arrangement (3, 4, etc)
      Returns
      SparseMatrix
    •  
      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}.

      Parameters
      Intindex
      of the arrangement (3, 4, etc)
      Returns
      SparseMatrix
    •  
      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}.

      Parameters
      Intindex
      of the arrangement (3, 4, etc)
      Returns
      SparseMatrix
    •  
      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.

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

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

    •  
      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

    •  
      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

    •  
      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

    •  
      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}

    •  
      tetrahedron () → Polytope

      Create regular tetrahedron. A Platonic solid.

      Returns
      Polytope
    •  
      truncated_cube () → Polytope

      Create truncated cube. An Archimedean solid.

      Returns
      Polytope
    •  
      truncated_cuboctahedron () → Polytope

      Create truncated cuboctahedron. An Archimedean solid. This is actually a misnomer. The actual truncation of a cuboctahedron is normally equivalent to this construction, but has two different edge lengths. This construction has regular 2-faces.

      Returns
      Polytope
    •  
      truncated_dodecahedron () → Polytope

      Create exact truncated dodecahedron in Q(sqrt{5}). An Archimedean solid.

      Returns
      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

      Create exact truncated icosidodecahedron in Q(sqrt{5}). An Archimedean solid.

      Returns
      Polytope
    •  
      truncated_octahedron () → Polytope

      Create truncated octahedron. An Archimedean solid. Also known as the 3-permutahedron.

      Returns
      Polytope
    •  
      wythoff (type, rings) → Polytope

      Produce the orbit polytope of a point under a Coxeter arrangement with exact coordinates, possibly in a qudratic extension field of the rationals

      Parameters
      Stringtype
      single letter followed by rank representing the type of the arrangement
      Setrings
      indices of the hyperplanes corresponding to simple roots of the arrangement that the initial point should NOT lie on. You may specify just an integer or a perl array ref like [0,1] or [0..2].
      Options
      Boollattice
      Should the vertices of the orbit polytope be chosen to lie on the corresponding root lattice? default 0, which means that the vertices will instead be chosen to lie as symmetrically as possible.
      Returns
      Polytope
  •  

    Topologic cell complexes defined as quotients over polytopes modulo a discrete group.

    •  
      cs_quotient (P)

      For a centrally symmetric polytope, divide out the central symmetry, i.e, identify diametrically opposite faces.

      Parameters
      PolytopeP
      , centrally symmetric

      Example:
      • > $P = cube(3);> cs_quotient($P);> print $P->CS_PERMUTATION; 7 6 5 4 3 2 1 0 The zeroth vertex gets identified with the seventh, the first with the sixth etc.
    •  
      cylinder_2 () → Polytope

      Return a 2-dimensional cylinder obtained by identifying two opposite sides of a square.

      Returns
      Polytope

      Example:
      • To obtain a topological space homeomorphic to a cylinder, type> $p = cylinder_2();> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS; 2 3 0 1> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS; {0 2} {1 3} Thus, vertices 0,2 and vertices 1,3 are identified.> print $p->QUOTIENT_SPACE->FACES; {{0} {1}} {{0 1} {0 2} {1 3}} {{0 1 2 3}} Thus, after identification two vertices, three edges, and one two-dimensional face remain:> print $p->QUOTIENT_SPACE->F_VECTOR; 2 3 1
    •  
      davis_manifold () → Polytope

      Return the 4-dimensional hyperbolic manifold obtained by Michael Davis

      Returns
      Polytope
      [Proceedings of the AMS, Vol. 93, No. 2 (Feb., 1985), pp. 325-328] by identifying opposite faces of the 120-cell

      Example:
      • The Davis manifold is the centrally symmetric quotient of the regular 210-cell:> $d = davis_manifold();> print $d->F_VECTOR; 600 1200 720 120> print $d->QUOTIENT_SPACE->F_VECTOR; 300 600 360 60 1
    •  
      quarter_turn_manifold () → Polytope

      Return the 3-dimensional Euclidean manifold obtained by identifying opposite faces of a 3-dimensional cube by a quarter turn. After identification, two classes of vertices remain.

      Returns
      Polytope

      Example:
      • To obtain a topological space homeomorphic to the quarter turn manifold, type> $p = quarter_turn_manifold();> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS; 5 7 4 6 2 0 3 1 6 2 1 5 7 3 0 4 To see which vertices are identified, type> print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS; {0 3 5 6} {1 2 4 7} Thus, two classes of vertices remain, with 0 and 1 being representatives. To see the faces remaining after identification, type> print $p->QUOTIENT_SPACE->FACES; {{0} {1}} {{0 1} {0 2} {0 4} {0 7}} {{0 1 2 3} {0 1 4 5} {0 1 6 7}} {{0 1 2 3 4 5 6 7}}> print $p->QUOTIENT_SPACE->F_VECTOR; 2 4 3 1
    •  
      write_quotient_space_simplexity_ilp ()

      outputs a linear program whose optimal value is a lower bound for the number of simplices necessary to triangulate the polytope in such a way that its symmetries respect the triangulation of the boundary.

  •  

    These functions capture information of the object that is concerned with the action of permutation groups.

    •  
      cocircuit_equations_support_reps (points, gens, rirs, rmis) → Int

      write the indices of the representatives of the support of the cocircuit equations to a file

      Parameters
      Matrix<Scalar>points
      Array<Array<Int>>gens
      the generators of the action of the symmetry group
      Array<SetType>rirs
      representatives of interior ridge simplices
      Array<SetType>rmis
      representatives of maximal interior simplices
      Options
      Stringfilename
      where large output should go to. 'filename=>"-"' writes to stdout.
      Returns
      Int
    •  
      combinatorial_symmetries (p) → group::PermutationAction

      Compute the combinatorial symmetries (i.e., automorphisms of the face lattice) of a given polytope p. They are stored in terms of a GROUP.VERTICES_ACTION and a GROUP.FACETS_ACTION property in p, and the GROUP.VERTICES_ACTION is also returned.

      Parameters
      Polytopep
      Returns
      group::PermutationAction
      the action of the combinatorial symmetry group on the vertices

      Example:
      • To get the vertex symmetry group of the square and print its generators, type the following:> print combinatorial_symmetries(cube(2))->GENERATORS; 2 3 0 1 1 0 2 3> $p = cube(2); combinatorial_symmetries($p);> print $p->GROUP->VERTICES_ACTION->GENERATORS; 0 2 1 3 1 0 3 2> print $p->GROUP->FACETS_ACTION->GENERATORS; 2 3 0 1 1 0 2 3
    •  
      combinatorial_symmetrized_cocircuit_equations (P, comps)

      calculate a sparse representation of the cocircuit equations corresponding to a direct sum of isotypic components

      Parameters
      ConeP
      Set<Int>comps
      the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge.
    •  
      combinatorial_symmetrized_cocircuit_equations (P, rirs, rmis, comps) → Array<Pair<SetType, HashMap<SetType,Rational>>>

      calculate the projection of the cocircuit equations to a direct sum of isotypic components and represent it combinatorially

      Parameters
      ConeP
      Array<SetType>rirs
      representatives of interior ridge simplices
      Array<SetType>rmis
      representatives of maximal interior simplices
      Set<Int>comps
      the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge.
      Options
      Stringfilename
      where large output should go to. 'filename=>"-"' writes to stdout.
      Returns
      Array<Pair<SetType, HashMap<SetType,Rational>>>
      indexed_cocircuit_equations a list of interior ridge simplices together with the corresponding sparsely represented cocircuit equation
    •  
      isotypic_configuration (P, i) → polytope::PointConfiguration<Float>

      Given a polytope that has a matrix group acting on it, return the projections of the vertices to the i-th isotypic component C_i. If the input is a group with a permutation action a, regard a as acting on the unit basis vectors of the ambient space and return the projection of the unit basis vectors to the i-th isotypic component.

      Parameters
      PolytopeP
      a polytope with a matrix action, or a group::Group g with a permutation action
      Inti
      the index of the desired isotypic component
      Returns
      polytope::PointConfiguration<Float>

      Example:
      • Consider the symmetry group of the cyclic polytope c(4,10) in the Carathéodory realization.> $p = cyclic_caratheodory(4,10,group=>1); For i=4, we obtain a 10-gon:> print isotypic_configuration($p,4)->POINTS; 1 1 0 1 0.8090169944 0.5877852523 1 0.3090169944 0.9510565163 1 -0.3090169944 0.9510565163 1 -0.8090169944 0.5877852523 1 -1 0 1 -0.8090169944 -0.5877852523 1 -0.3090169944 -0.9510565163 1 0.3090169944 -0.9510565163 1 0.8090169944 -0.5877852523 Similarly, for i=5 we get two copies of a pentagon.
    •  
      lattice_automorphisms_smooth_polytope (P) → Array<Array<Int>>

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

      Parameters
      PolytopeP
      the given polytope
      Returns
      Array<Array<Int>>
      the generating set for the lattice automorphism group

      Example:
      • > print lattice_automorphisms_smooth_polytope(cube(2)); 2 3 0 1 1 0 3 2 0 2 1 3
    •  
      linear_symmetries ()

      wrapper function to store the symmetry group in the parent object

      Contained in extension sympol.
    •  
      linear_symmetries (m) → group::Group

      Use sympol to compute the linear symmetries of - the rows of a rational matrix m, or - the RAYS|VERTICES, FACETS, or POINTS of a rational cone or polytope C (whatever is available, in this order), or - the VECTORS|POINTS of a rational vector or point configuration P. Except for matrices, the action of the symmetry group is stored inside the parent object. In the case of cones, sympol might compute only a subset of the linear symmetry group. Sympol, and therefore this function, can only handle rational objects.

      Contained in extension sympol.
      Parameters
      Matrixm
      | Cone C | VectorConfiguration P
      Returns
      group::Group
      the linear symmetry group, together with a PERMUTATION_ACTION, VERTEX_ACTION, FACETS_ACTION, or VECTOR_ACTION

      Example:
      • > $ls = linear_symmetries(cube(2)->VERTICES);> print $ls->PERMUTATION_ACTION->GENERATORS; 0 2 1 3 3 1 2 0 2 3 0 1> print linear_symmetries(cube(3)->VERTICES)->PERMUTATION_ACTION->GENERATORS; 0 4 2 6 1 5 3 7 0 1 4 5 2 3 6 7 7 6 5 4 3 2 1 0 2 6 0 4 3 7 1 5> print linear_symmetries(cube(3))->FACETS_ACTION->GENERATORS; 1 0 2 3 4 5 0 1 3 2 4 5 2 3 0 1 4 5 0 1 2 3 5 4 0 1 4 5 2 3
    •  
      nestedOPGraph (gen_point, points, lattice_points, group, verbose) → ARRAY

      Constructs the NOP-graph of an orbit polytope. It is used by the rule for the NOP_GRAPH.

      Parameters
      Vectorgen_point
      the generating point
      Matrixpoints
      the vertices of the orbit polytope
      Matrixlattice_points
      the lattice points of the orbit polytope
      group::Groupgroup
      the generating group
      Boolverbose
      print out additional information
      Returns
      ARRAY
      ($Graph, $lp_reps, $minInStartOrbit, \@core_point_reps, $CPindices)
    •  
      orbit_polytope (input_point, a) → Polytope

      Constructs the orbit polytope of a given point input_point with respect to a given group action a.

      Parameters
      Vectorinput_point
      the basis point of the orbit polytope
      group::PermutationActiona
      the action of a permutation group on the coordinates of the ambient space
      Returns
      Polytope
      the orbit polytope of input_point w.r.t. the action a

      Example:
      • The orbit polytope of a set of points A in affine d-space is the convex hull of the images of A under the action of a group G on the affine space. polymake implements several variations of this concept. The most basic one is the convex hull of the orbit of a single point under a set of coordinate permutations. For example, consider the cyclic group C_6 that acts on 6-dimensional space by cyclically permuting the coordinates. This action is represented in polymake by group::cyclic_group(6)->PERMUTATION_ACTION. To compute the convex hull of cyclic shifts of the vector v = [1,6,0,5,-5,0,-5] in homogeneous coordinates, type> $p = orbit_polytope(new Vector([1,6,0,5,-5,0,-5]), group::cyclic_group(6)->PERMUTATION_ACTION); After this assignment, the orbit polytope is still in implicit form, and the only properties that are defined reside in GROUP->COORDINATE_ACTION:> print $p->GROUP->COORDINATE_ACTION->properties(); type: PermutationAction<Int, Rational> as Polytope<Rational>::GROUP::COORDINATE_ACTION GENERATORS 1 2 3 4 5 0 INPUT_RAYS_GENERATORS 1 6 0 5 -5 0 -5 To calculate the vertices of the orbit polytope explicitly, say> print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5
    •  
      orbit_polytope (input_points, a) → Polytope

      Constructs the orbit polytope of a given set of points input_points with respect to a given group action a.

      Parameters
      Matrixinput_points
      the basis points of the orbit polytope
      group::PermutationActiona
      the action of a permutation group on the coordinates of the ambient space
      Returns
      Polytope
      the orbit polytope of input_points w.r.t. the action a

      Example:
      • To find the orbit of more than one point under a PermutationAction on the coordinates, say> $p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), new group::PermutationAction(GENERATORS=>[ [1,2,3,4,5,0] ]));> print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5 1 1 2 3 4 5 6 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 1 2 3 1 5 6 1 2 3 4 1 6 1 2 3 4 5
    •  
      orbit_polytope (input_point, g) → Polytope

      Constructs the orbit polytope of a given point input_point with respect to a given group action a.

      Parameters
      Vectorinput_point
      the basis point of the orbit polytope
      group::Groupg
      a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient space
      Returns
      Polytope
      the orbit polytope of input_point w.r.t. the action of g

      Example:
      • As a convenience function, you can also directly specify a group::Group that contains a PERMUTATION_ACTION:> $p = orbit_polytope(new Vector([1,6,0,5,-5,0,-5]), group::cyclic_group(6)); Up to now, the orbit polytope is still in implicit form. To calculate the vertices explicitly, say> print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5
    •  
      orbit_polytope (input_points, g) → Polytope

      Constructs the orbit polytope of a given set of points input_points with respect to a given group action a.

      Parameters
      Matrixinput_points
      the basis points of the orbit polytope
      group::Groupg
      a group with a PERMUTATION_ACTION that acts on the coordinates of the ambient space
      Returns
      Polytope
      the orbit polytope of input_points w.r.t. the action of g

      Example:
      • As a convenience function, you can also directly specify a group::Group that contains a PERMUTATION_ACTION:> $p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), group::cyclic_group(6));> print $p->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5 1 1 2 3 4 5 6 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 1 2 3 1 5 6 1 2 3 4 1 6 1 2 3 4 5
    •  
      orbit_polytope (input_points, gens) → Polytope

      Constructs the orbit polytope of a given set of points input_points with respect to a given set of generators gens.

      Parameters
      Matrixinput_points
      the basis point of the orbit polytope
      Array<Array<Int>>gens
      the generators of a permutation group that acts on the coordinates of the ambient space
      Returns
      Polytope
      the orbit polytope of input_points w.r.t. the coordinate action generated by gens

      Example:
      • This is a variation where several points are given as the row of a matrix, and the permutation action on coordinates is given by explicitly listing the generators. In this example, the matrix has just one row, and there is just one generator.> print orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5] ]), [ [1,2,3,4,5,0] ])->VERTICES; 1 -5 0 -5 6 0 5 1 -5 6 0 5 -5 0 1 0 -5 6 0 5 -5 1 0 5 -5 0 -5 6 1 5 -5 0 -5 6 0 1 6 0 5 -5 0 -5
    •  
      orbit_polytope <Scalar> (input_point, a) → Polytope

      Constructs the orbit polytope of a given point input_point with respect to a given matrix group action a.

      Type Parameters
      Scalar
      S the underlying number type
      Parameters
      Vectorinput_point
      the generating point of the orbit polytope
      group::MatrixActionOnVectorsa
      the action of a matrix group on the coordinates of the ambient space
      Returns
      Polytope
      the orbit polytope of input_point w.r.t. the action a

      Example:
      • polymake also supports orbit polytopes under the action of a group by matrices. To find the orbit of a point in the plane under the symmetry group of the square, say> $p = orbit_polytope(new Vector([1,2,1]), cube(2, group=>1)->GROUP->MATRIX_ACTION);> print $p->VERTICES; 1 -2 -1 1 -2 1 1 -1 -2 1 -1 2 1 1 -2 1 1 2 1 2 -1 1 2 1
    •  
      orbit_polytope <Scalar> (input_points, a) → Polytope

      Constructs the orbit polytope of a given set of points input_points with respect to a given matrix group action a.

      Type Parameters
      Scalar
      S the underlying number type
      Parameters
      Matrix<Scalar>input_points
      the generating points of the orbit polytope
      group::MatrixActionOnVectors<Scalar>a
      the action of a matrix group on the coordinates of the ambient space
      Returns
      Polytope
      the orbit polytope of the input_points w.r.t. the action a

      Example:
      • To find the orbit of more than one point in the plane under the symmetry group of the square, say> $p = orbit_polytope(new Matrix([ [1,2,1], [1,5/2,0] ]), cube(2, group=>1)->GROUP->MATRIX_ACTION);> print $p->VERTICES; 1 -2 -1 1 -2 1 1 -1 -2 1 -1 2 1 1 -2 1 1 2 1 2 -1 1 2 1 1 -5/2 0 1 0 -5/2 1 0 5/2 1 5/2 0
    •  
      ortho_project (p) → Polytope

      Projects a symmetric polytope in R4 cap H1,k to R3. (See also the polymake extension 'tropmat' by S. Horn.)

      Parameters
      Polytopep
      the symmetric polytope to be projected
      Returns
      Polytope
      the image of p in R3
    •  
      representation_conversion_up_to_symmetry (c) → Pair

      Computes the dual description of a polytope up to its linear symmetry group.

      Contained in extension sympol.
      Parameters
      Conec
      the cone (or polytope) whose dual description is to be computed, equipped with a GROUP
      Options
      Boolv_to_h
      1 (default) if converting V to H, false if converting H to V
      Stringmethod
      specifies sympol's method of ray computation via 'lrs' (default), 'cdd', 'beneath_beyond', 'ppl'
      Returns
      Pair
      (Matrix<Rational> vertices/inequalities, Matrix<Rational> lineality/equations)
    •  
      symmetrized_cocircuit_equations <Scalar> (P, comps)

      calculate the projection of the cocircuit equations to a direct sum of isotypic components

      Type Parameters
      Scalar
      the underlying data type
      Parameters
      ConeP
      or PointConfiguration
      Set<Int>comps
      the list of indices of the isotypic components to project to; default [0], which amounts to summing all cocircuit equations corresponding to the orbit of each ridge.
      Options
      Boolreduce_rows
      Should we return only linearly independent equations? default: 1
    •  
      truncated_orbit_polytope (P, eps) → Polytope

      Gives an implicit representation of the all-vertex truncation of an orbit polytope P, in which all vertices are cut off by hyperplanes at distance eps. The input polytope P must have a GROUP.COORDINATE_ACTION. The output is a polytope with a GROUP.COORDINATE_ACTION equipped with INEQUALITIES_GENERATORS.

      Parameters
      PolytopeP
      the input polytope
      Scalareps
      scaled distance by which the vertices of the orbit polytope are to be cut off
      Returns
      Polytope
      the truncated orbit polytope
  •  

    These functions take a realized polytope and produce a new one by applying a suitable affine or projective transformation in order to obtain some special coordinate description but preserve the combinatorial type.

    For example, before you can polarize an arbitrary polyhedron, it must be transformed to a combinatorially equivalent bounded polytope with the origin as a relatively interior point. It is achieved with the sequence orthantify - bound - center - polarize.

    •  
      ambient_lattice_normalization (p) → Polytope

      Transform to a full-dimensional polytope while preserving the ambient lattice Z^n

      Parameters
      Polytopep
      the input polytope,
      Options
      Boolstore_transform
      store the reverse transformation as an attachement
      Returns
      Polytope
      - the transformed polytope defined by its vertices. Facets are only written if available in p.

      Examples:
      • Consider a line segment embedded in 2-space containing three lattice points:> $p = new Polytope(VERTICES=>[[1,0,0],[1,2,2]]);> print ambient_lattice_normalization($p)->VERTICES; 1 0 1 2 The ambient lattice of the projection equals the intersection of the affine hull of $p with Z^2.
      • Another line segment containing only two lattice points:> $p = new Polytope(VERTICES=>[[1,0,0],[1,1,2]]);> $P = ambient_lattice_normalization($p,store_transform=>1);> print $P->VERTICES; 1 0 1 1 To get the transformation, do the following:> $M = $P->get_attachment('REVERSE_LATTICE_PROJECTION');> print $M; 1 0 0 0 1 2> print $P->VERTICES * $M; 1 0 0 1 1 2
    •  
      bound (P) → Polytope

      Make a positive polyhedron bounded. Apply a projective linear transformation to a polyhedron mapping the far hyperplane to the hyperplane spanned by the unit vectors. The origin (1,0,...,0) is fixed.

      The input polyhedron should be POSITIVE; i.e. no negative coordinates.

      Parameters
      PolytopeP
      a positive polyhedron
      Returns
      Polytope

      Example:
      • Observe the transformation of a simple unbounded 2-polyhedron:> $P = new Polytope(VERTICES=>[[1,0,0],[0,1,1],[0,0,1]]);> print bound($P)->VERTICES; 1 0 0 1 1/2 1/2 1 0 1 As you can see, the far points are mapped to the hyperplane spanned by (1,1,0) and (1,0,1).
    •  
      center (P) → Polytope

      Make a polyhedron centered. Apply a linear transformation to a polyhedron P such that a relatively interior point (preferably the vertex barycenter) is moved to the origin (1,0,...,0).

      Parameters
      PolytopeP
      Returns
      Polytope

      Example:
      • Consider this triangle not containing the origin:> $P = new Polytope(VERTICES => [[1,1,1],[1,2,1],[1,1,2]]);> $origin = new Vector([1,0,0]);> print $P->contains_in_interior($origin); false To create a translate that contains the origin, do this:> $PC = center($P);> print $PC->contains_in_interior($origin); true This is what happened to the vertices:> print $PC->VERTICES; 1 -1/3 -1/3 1 2/3 -1/3 1 -1/3 2/3 There also exists a property to check whether a polytope is centered:> print $PC->CENTERED; true
    •  
      orthantify (P, v) → Polytope

      Make a polyhedron POSITIVE. Apply an affine transformation to a polyhedron such that the vertex v is mapped to the origin (1,0,...,0) and as many facets through this vertex as possible are mapped to the bounding facets of the first orthant.

      Parameters
      PolytopeP
      Intv
      vertex to be moved to the origin. By default it is the first affine vertex of the polyhedron.
      Returns
      Polytope

      Example:
      • To orthantify the square, moving its first vertex to the origin, do this:> $p = orthantify(cube(2),1);> print $p->VERTICES; 1 2 0 1 0 0 1 2 2 1 0 2
    •  
      orthonormal_col_basis (M) → Matrix<Float>

      Return an orthonormal column basis of the input matrix.

      Parameters
      Matrix<Scalar>M
      the input matrix
      Returns
      Matrix<Float>
    •  
      orthonormal_row_basis (M) → Matrix<Float>

      Return an orthonormal row basis of the input matrix.

      Parameters
      Matrix<Scalar>M
      the input matrix
      Returns
      Matrix<Float>
    •  
      polarize (C) → Cone

      This method takes either a polytope (1.) or a cone (2.) as input. 1. Given a bounded, centered, not necessarily full-dimensional polytope P, produce its polar with respect to the standard Euclidean scalar product. 2. Given a cone C produce its dual with respect to the standard Euclidean scalar product, i.e. all the vectors that evaluate positively on C. Note that the definition of the polar has changed after version 2.10: the polar is reflected in the origin to conform with cone polarization If P is not full-dimensional, the output will contain lineality orthogonal to the affine span of P. In particular, polarize() of a pointed polytope will always produce a full-dimensional polytope. If you want to compute the polar inside the affine hull you may use the pointed_part client afterwards.

      Parameters
      ConeC
      Options
      Boolno_coordinates
      only combinatorial information is handled
      Returns
      Cone

      Examples:
      • To save the polar of the square in the variable $p and then print its vertices, do this:> $p = polarize(cube(2));> print $p->VERTICES; 1 1 0 1 -1 0 1 0 1 1 0 -1
      • To dualize the cone over a hexagon and print its rays, do this:> $c = new Cone(INPUT_RAYS=>[[1,0,0],[1,1,0],[1,2,1],[1,2,2],[1,1,2],[1,0,1]]);> $cd = polarize($c);> print $cd->RAYS; 1 -1 1 0 0 1 0 1 0 1 1 -1 1 0 -1/2 1 -1/2 0
    •  
      revert (P) → Polytope

      Apply a reverse transformation to a given polyhedron P. All transformation clients keep track of the polytope's history. They write or update the attachment REVERSE_TRANSFORMATION.

      Applying revert to the transformed polytope reconstructs the original polytope.

      Parameters
      PolytopeP
      a (transformed) polytope
      Returns
      Polytope
      the original polytope

      Example:
      • The following translates the square and then reverts the transformation:> $v = new Vector(1,2);> $p = translate(cube(2),$v);> print $p->VERTICES; 1 0 1 1 2 1 1 0 3 1 2 3> $q = revert($p);> print $q->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1
    •  
      scale (P, factor, store) → Polytope

      Scale a polyhedron P by a given scaling parameter factor.

      Parameters
      PolytopeP
      the polyhedron to be scaled
      Scalarfactor
      the scaling factor
      Boolstore
      stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.
      Returns
      Polytope

      Example:
      • To scale the square by 23, do this:> $p = scale(cube(2),23);> print $p->VERTICES; 1 -23 -23 1 23 -23 1 -23 23 1 23 23 The transformation matrix is stored in an attachment:> print $p->get_attachment('REVERSE_TRANSFORMATION'); 1 0 0 0 1/23 0 0 0 1/23 To reverse the transformation, you can use the revert function.> $q = revert($p);> print $q->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1
    •  
      transform (P, trans, store) → Polytope

      Transform a polyhedron P according to the linear transformation trans.

      Parameters
      PolytopeP
      the polyhedron to be transformed
      Matrixtrans
      the transformation matrix
      Boolstore
      stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.
      Returns
      Polytope

      Example:
      • This translates the square by (23,23) and stores the transformation:> $M = new Matrix([1,23,23],[0,1,0],[0,0,1]);> $p = transform(cube(2),$M,1);> print $p->VERTICES; 1 22 22 1 24 22 1 22 24 1 24 24 To retrieve the attached transformation, use this:> print $p->get_attachment('REVERSE_TRANSFORMATION'); 1 -23 -23 0 1 0 0 0 1 Check out the revert function to learn how to undo the transformation. It might be more comfortable to use the translate function to achieve the same result.
    •  
      translate (P, trans, store) → Polytope

      Translate a polyhedron P by a given translation vector trans.

      Parameters
      PolytopeP
      the polyhedron to be translated
      Vectortrans
      the translation vector
      Boolstore
      stores the reverse transformation as an attachment (REVERSE_TRANSFORMATION); default value: 1.
      Returns
      Polytope

      Example:
      • This translates the square by (23,23) and stores the transformation:> $t = new Vector(23,23);> $p = translate(cube(2),$t);> print $p->VERTICES; 1 22 22 1 24 22 1 22 24 1 24 24 To retrieve the attached transformation, use this:> print $p->get_attachment('REVERSE_TRANSFORMATION'); 1 -23 -23 0 1 0 0 0 1 Check out the revert function to learn how to undo the transformation.
    •  
      vertex_lattice_normalization (p) → Polytope

      Transform to a full-dimensional polytope while preserving the lattice spanned by vertices induced lattice of new vertices = Z^dim

      Parameters
      Polytopep
      the input polytope,
      Options
      Boolstore_transform
      store the reverse transformation as an attachement
      Returns
      Polytope
      - the transformed polytope defined by its vertices. Facets are only written if available in p.
  •  

    These functions collect information about triangulations and other subdivisions of the object and properties usually computed from such, as the volume.

    •  
      barycentric_subdivision (c) → topaz::SimplicialComplex

      Create a simplicial complex as a barycentric subdivision of a given cone or polytope. Each vertex in the new complex corresponds to a face in the old complex.

      Parameters
      Conec
      input cone or polytope
      Options
      Boolno_labels
      Do not generate VERTEX_LABELS from the faces of the original cone. default: 0
      Boolgeometric_realization
      create a topaz::GeometricSimplicialComplex; default is true
      Returns
      topaz::SimplicialComplex
    •  
      chirotope (P) → String

      Compute the chirotope of a polytope using TOPCOM.

      Parameters
      PolytopeP
      Returns
      String
    •  
      chirotope (P) → String

      Compute the chirotope of a point or vector configuration using TOPCOM.

      Parameters
      VectorConfigurationP
      Returns
      String
    •  
      chirotope (P) → String

      Compute the chirotope of a polytope using polymake's native implementation.

      Parameters
      PolytopeP
      Returns
      String
    •  
      chirotope (P) → String

      Compute the chirotope of a point or vector configuration using polymake's native implementation.

      Parameters
      VectorConfigurationP
      Returns
      String
    •  
      coherency_index (p1, p2, points, w1, w2)

      DOC_FIXME: Incomprehensible description! Computes the coherency index of w1 w.r.t. w2

      Contained in extension local.
      Parameters
      Polytopep1
      Polytopep2
      Matrixpoints
      Vectorw1
      Vectorw2
    •  
      coherency_index (points, w1, w2)

      DOC_FIXME: Incomprehensible description! Computes the coherency index of w1 w.r.t. w2

      Contained in extension local.
      Parameters
      Matrixpoints
      Vectorw1
      Vectorw2
    •  
      coherency_index (p1, p2)

      DOC_FIXME: Erroneous description! w1 is not a parameter here! Computes the coherency index of p1 w.r.t. p2

      Contained in extension local.
      Parameters
      Polytopep1
      Polytopep2
    •  
      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
      Matrixpoints
      IncidenceMatrixsub1
      first subdivision
      IncidenceMatrixsub2
      second subdivision
      Intdim
      dimension of the point configuration
      Returns
      IncidenceMatrix
      the common refinement

      Example:
      • A simple 2-dimensional set of points:> $points = new Matrix<Rational>([[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,2,1]]); Two different subdivisions...> $sub1 = new IncidenceMatrix([[0,1,2],[1,2,3,4]]);> $sub2 = new IncidenceMatrix([[1,3,4],[0,1,2,3]]); ...and their common refinement:> print common_refinement($points,$sub1,$sub2,2); {0 1 2} {1 3 4} {1 2 3}
    •  
      common_refinement (p1, p2) → Polytope

      Computes the common refinement of two subdivisions of the same polytope p1, p2. It is assumed that there exists a common refinement of the two subdivisions. It is not checked if p1 and p2 are indeed the same!

      Parameters
      Polytopep1
      Polytopep2
      Returns
      Polytope
    •  
      delaunay_triangulation (V) → Array<Set<Int>>

      Compute the Delaunay triangulation of the given SITES of a VoronoiPolyhedron V. If the sites are not in general position, the non-triangular facets of the Delaunay subdivision are triangulated (by applying the beneath-beyond algorithm).


      Example:
      • > $VD = new VoronoiPolyhedron(SITES=>[[1,1,1],[1,0,1],[1,-1,1],[1,1,-1],[1,0,-1],[1,-1,-1]]);> $D = delaunay_triangulation($VD);> print $D; {0 1 3} {1 3 4} {1 2 4} {2 4 5}
    •  
      fiber_polytope (pc, pc) → PointConfiguration

      Computes the fiber polytope of a projection of point configurations P->Q via the GKZ secondary configuration.

      Parameters
      PointConfigurationpc
      (or Polytope) source point configuration or polytope
      PointConfigurationpc
      target point configuration
      Returns
      PointConfiguration
    •  
      fiber_polytope (pc, pc) → PointConfiguration

      Computes the fiber polytope of a projection of point configurations P->Q via the GKZ secondary configuration.

      Parameters
      PointConfigurationpc
      (or Polytope) source point configuration or polytope
      Polytopepc
      target polytope
      Returns
      PointConfiguration
    •  
      fiber_polytope (P, pi) → PointConfiguration

      Computes the fiber polytope of a projection of point configurations P -pi-> Q via the GKZ secondary configuration.

      Parameters
      PointConfigurationP
      (or Polytope) source point configuration or polytope
      Matrixpi
      the projection acting on P
      Returns
      PointConfiguration
    •  
      foldable_max_signature_ilp (d, points, volume, cocircuit_equations) → LinearProgram<Rational>

      Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      Matrixpoints
      the input points or vertices
      Rationalvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      LinearProgram<Rational>
      an ILP that provides the result
    •  
      foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → Integer

      Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      Matrixpoints
      the input points or vertices
      Rationalvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      Integer
      the optimal value of an LP that provides a bound
    •  
      interior_and_boundary_ridges (P) → Pair<Array<Set>,Array<Set>>

      Find the (d-1)-dimensional simplices in the interior and in the boundary of a d-dimensional polytope or cone

      Parameters
      PolytopeP
      the input polytope or cone
      Returns
      Pair<Array<Set>,Array<Set>>

      Example:
      • > print interior_and_boundary_ridges(cube(2)); <{0 3} {1 2} > <{0 1} {0 2} {1 3} {2 3} >
    •  
      is_regular (points, subdiv) → Pair<Bool,Vector>

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

      Parameters
      Matrixpoints
      in homogeneous coordinates
      Array<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 0
      Intlift_face_to_zero
      gives only lifting functions lifting all vertices of the designated face to 0
      Returns
      Pair<Bool,Vector>

      Example:
      • A regular subdivision of the square, with the first cell lifted to zero:> $points = cube(2)->VERTICES;> print is_regular($points,[[0,1,3],[1,2,3]],lift_to_zero=>[0,1,3]); 1 <0 0 1 0>
    •  
      is_subdivision (points, faces)

      UNDOCUMENTED
      Parameters
      Matrixpoints
      Array<Set<Int>>faces
      Options
      Set<Int>interior_points

      Example:
      • Two potential subdivisions of the square without innter points:> $points = cube(2)->VERTICES;> print is_subdivision($points,[[0,1,3],[1,2,3]],interior_points=>[ ]); true> print is_subdivision($points,[[0,1,2],[1,2]],interior_points=>[ ]); false
    •  
      iterated_barycentric_subdivision (c, n) → topaz::SimplicialComplex

      Create a simplicial complex as an iterated barycentric subdivision of a given cone or polytope.

      Parameters
      Conec
      input cone or polytope
      Intn
      how many times to subdivide
      Options
      Boolno_labels
      Do not generate VERTEX_LABELS from the faces of the original cone. default: 0
      Boolgeometric_realization
      create a topaz::GeometricSimplicialComplex; default is false
      Returns
      topaz::SimplicialComplex
    •  
      max_interior_simplices (P) → Array<Set>

      Find the maximal interior simplices of a polytope P. Symmetries of P are NOT taken into account.

      Parameters
      PolytopeP
      the input polytope
      Returns
      Array<Set>

      Example:
      • > print max_interior_simplices(cube(2)); {0 1 2} {0 1 3} {0 2 3} {1 2 3}
    •  
      max_interior_simplices (P) → Array<Set>

      find the maximal interior simplices of a point configuration Symmetries of the configuration are NOT taken into account.

      Parameters
      PointConfigurationP
      the input point configuration
      Returns
      Array<Set>

      Example:
      • To calculate the maximal interior simplices of a point configuration, type> $p=new PointConfiguration(POINTS=>[[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,1/2,1/2]]);> print max_interior_simplices($p); {0 1 2} {0 1 3} {0 1 4} {0 2 3} {0 2 4} {1 2 3} {1 3 4} {2 3 4}
    •  
      mixed_volume (P1, P2, Pn) → Scalar

      Produces the mixed volume of polytopes P1,P2,...,Pn.

      Parameters
      Polytope<Scalar>P1
      first polytope
      Polytope<Scalar>P2
      second polytope
      Polytope<Scalar>Pn
      last polytope
      Returns
      Scalar
      mixed volume

      Example:
      • > print mixed_volume(cube(2),simplex(2)); 4
    •  
      n_triangulations (M, optimization) → Integer

      Calculates the number of triangulations of a planar point configuration. This can be space intensive.

      Victor Alvarez, Raimund Seidel: A Simple Aggregative Algorithm for Counting Triangulations of Planar Point Sets and Related Problems. In Proc. of the 29th Symposium on Computational Geometry (SoCG '13), pages 1-8, Rio de Janeiro, Brazil, 2013

      Parameters
      MatrixM
      in the plane (homogeneous coordinates)
      Booloptimization
      defaults to 1, where 1 includes optimization and 0 excludes it
      Returns
      Integer
      number of triangulations

      Example:
      • To print the number of possible triangulations of a square, do this:> print n_triangulations(cube(2)->VERTICES); 2
    •  
      placing_triangulation (Points) → Array<Set<Int>>

      Compute the placing triangulation of the given point set using the beneath-beyond algorithm.

      Parameters
      MatrixPoints
      the given point set
      Options
      Boolnon_redundant
      whether it's already known that Points are non-redundant
      Array<Int>permutation
      placing order of Points, must be a valid permutation of (0..Points.rows()-1)
      Returns
      Array<Set<Int>>

      Example:
      • To compute the placing triangulation of the square (of whose vertices we know that they're non-redundant), do this:> $t = placing_triangulation(cube(2)->VERTICES, non_redundant=>1);> print $t; {0 1 2} {1 2 3}
    •  
      points2metric (points) → Matrix

      Define a metric by restricting the Euclidean distance function to a given set of points. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-norm is used instead (with exact computation).

      Parameters
      Matrixpoints
      Options
      Boolmax
      triggers the usage of the max-norm (exact computation)
      Booll1
      triggers the usage of the l1-norm (exact computation)
      Returns
      Matrix

      Example:
      • > print points2metric(cube(2)->VERTICES, max=>1); 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0
    •  
      poly2metric (P) → Matrix

      Define a metric by restricting the Euclidean distance function to the vertex set of a given polytope P. Due to floating point computations (sqrt is used) the metric defined may not be exact. If the option max or l1 is set to true the max-norm or l1-norm is used instead (with exact computation).

      Parameters
      PolytopeP
      Options
      Boolmax
      triggers the usage of the max-norm (exact computation)
      Returns
      Matrix

      Example:
      • > print poly2metric(cube(2), max=>1); 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0
    •  
      positive_circuits (or, S) → Set<Set<Int>>

      returns all sets of points that form a circuit with the given list of points

      Parameters
      Polytopeor
      PointConfiguration P
      Set<Int>S
      subset of point indices
      Returns
      Set<Set<Int>>
      A list of point sets that intersect positively the set S
    •  
      quotient_space_simplexity_ilp (d, V, volume, cocircuit_equations) → LinearProgram

      Set up an LP whose MINIMAL_VALUE is a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      MatrixV
      the input points or vertices
      Scalarvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Options
      Stringfilename
      a name for a file in .lp format to store the linear program
      Returns
      LinearProgram
      an LP that provides a lower bound
    •  
      quotient_space_simplexity_lower_bound (d, V, volume, cocircuit_equations) → Integer

      Calculate a lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      MatrixV
      the input points or vertices
      Scalarvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      Integer
      the optimal value of an LP that provides a lower bound
    •  
      regularity_lp (points, subdiv) → Polytope<Scalar>

      For a given subdivision subdiv of points determines a LinearProgram to decide whether the subdivision is regular. The output a Polytope with an attached LP. Options can be used to ensure properties of the resulting LP. The default is having 0 on all vertices of the first face of subdiv.

      Parameters
      Matrixpoints
      in homogeneous coordinates
      Array<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 0
      Intlift_face_to_zero
      gives only lifting functions lifting all vertices of the designated face to 0
      Scalarepsilon
      minimum distance from all inequalities
      Returns
      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.

      Parameters
      Matrixpoints
      Vectorweights
      Returns
      Array<Set<Int>>

      Example:
      • The following generates a regular subdivision of the square.> $w = new Vector(2,23,2,2);> $r = regular_subdivision(cube(2)->VERTICES,$w);> print $r; {0 2 3} {0 1 3}
    •  
      secondary_polytope (pc) → PointConfiguration

      Computes the GKZ secondary configuration of a point configuration via its chirotope.

      Parameters
      PointConfigurationpc
      input point configuration
      Returns
      PointConfiguration
    •  
      secondary_polytope (pc) → PointConfiguration

      Computes the GKZ secondary configuration of a point configuration via its chirotope.

      Parameters
      Polytopepc
      input polytope
      Returns
      PointConfiguration
    •  
      simplexity_ilp (d, points, MIS, volume, cocircuit_equations) → LinearProgram

      Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      Matrixpoints
      the input points or vertices
      Array<Set>MIS
      the representatives of maximal interior simplices
      Scalarvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      LinearProgram
      an LP that provides a lower bound
    •  
      simplexity_ilp_with_angles (d, V, F, VIF, VIR, gens, MIS, volume, cocircuit_equations) → LinearProgram

      Set up an ILP whose MINIMAL_VALUE is the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      MatrixV
      the input points or vertices
      MatrixF
      the facets of the input polytope
      IncidenceMatrixVIF
      the vertices-in-facets incidence matrix
      IncidenceMatrixVIR
      the vertices-in-ridges incidence matrix
      Array<Array<Int>>gens
      the generators of the symmetry group
      Array<Set>MIS
      the (representative) maximal interior simplices
      Scalarvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      LinearProgram
      an LP that provides a lower bound
    •  
      simplexity_lower_bound (d, points, volume, cocircuit_equations) → Integer

      Calculate the LP relaxation lower bound for the minimal number of simplices needed to triangulate a polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      Matrixpoints
      the input points or vertices
      Scalarvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      Integer
      the optimal value of an LP that provides a lower bound
    •  
      splits (V, G, F, dimension) → Matrix

      Computes the SPLITS of a polytope. The splits are normalized by dividing by the first non-zero entry. If the polytope is not fulldimensional the first entries are set to zero unless coords are specified.

      Parameters
      MatrixV
      vertices of the polytope
      GraphG
      graph of the polytope
      MatrixF
      facets of the polytope
      Intdimension
      of the polytope
      Options
      Set<Int>coords
      entries that should be set to zero
      Returns
      Matrix
    •  
      splits_in_subdivision (vertices, subdivision, splits) → Set<Int>

      Tests which of the splits of a polyhedron are coarsenings of the given subdivision.

      Parameters
      Matrixvertices
      the vertices of the polyhedron
      Array<Set<Int>>subdivision
      a subdivision of the polyhedron
      Matrixsplits
      the splits of the polyhedron
      Returns
      Set<Int>
    •  
      split_compatibility_graph (splits, P) → Graph

      DOC_FIXME: Incomprehensible description! Computes the compatibility graph among the splits of a polytope P.

      Parameters
      Matrixsplits
      the splits given by split equations
      PolytopeP
      the input polytope
      Returns
      Graph
    •  
      split_polyhedron (P) → Polytope

      Computes the split polyhedron of a full-dimensional polyhdron P.

      Parameters
      PolytopeP
      Returns
      Polytope
    •  
      staircase_weight (k, l) → Vector<Rational>

      Gives a weight vector for the staircase triangulation of the product of a k-1- and an l-1-dimensional simplex.

      Parameters
      Intk
      the number of vertices of the first simplex
      Intl
      the number of vertices of the second simplex
      Returns
      Vector<Rational>

      Example:
      • The following creates the staircase triangulation of the product of the 2- and the 1-simplex.> $w = staircase_weight(3,2);> $p = product(simplex(2),simplex(1));> $p->POLYTOPAL_SUBDIVISION(WEIGHTS=>$w);> print $p->POLYTOPAL_SUBDIVISION->MAXIMAL_CELLS; {0 2 4 5} {0 2 3 5} {0 1 3 5}
    •  
      symmetrized_foldable_max_signature_ilp (d, points, volume, generators, symmetrized_foldable_cocircuit_equations) → LinearProgram<Rational>

      Set up an ILP whose MAXIMAL_VALUE is the maximal signature of a foldable triangulation of a polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      Matrixpoints
      the input points or vertices
      Rationalvolume
      the volume of the convex hull
      Array<Array<Int>>generators
      the generators of the symmetry group
      SparseMatrixsymmetrized_foldable_cocircuit_equations
      the matrix of symmetrized cocircuit equations
      Returns
      LinearProgram<Rational>
      an ILP that provides the result
    •  
      symmetrized_foldable_max_signature_upper_bound (d, points, volume, cocircuit_equations) → Integer

      Calculate the LP relaxation upper bound to the maximal signature of a foldable triangulation of polytope, point configuration or quotient manifold

      Parameters
      Intd
      the dimension of the input polytope, point configuration or quotient manifold
      Matrixpoints
      the input points or vertices
      Rationalvolume
      the volume of the convex hull
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      Integer
      the optimal value of an LP that provides a bound
    •  
      topcom_all_triangulations (pc) → Array<Array<Set<Int>>>

      Computes all triangulations of a point configuration via its chirotope.

      Parameters
      PointConfigurationpc
      input point configuration
      Returns
      Array<Array<Set<Int>>>
    •  
      topcom_fine_and_connected_triangulations (pc) → Array<Array<Set<Int>>>

      Computes all fine triangulations of a point configuration that are connected by bistellar flips to a fine seed triangulation. The triangulations are computed via the chirotope. If the input point configuration or polytope has a symmetry group, only fine triangulations up to symmetry will be computed.

      Parameters
      PointConfigurationpc
      or Polytope p input point configuration or polytope
      Returns
      Array<Array<Set<Int>>>
    •  
      topcom_input_format (P) → String

      This converts a polytope, cone or point configuration into a format that topcom understands

      Parameters
      ConeP
      (or PointConfiguration)
      Returns
      String

      Example:
      • To convert a 2-cube without symmetries into topcom format, type> print topcom_input_format(cube(2)); [[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]] [] If you also want the symmetry group, you can type> print topcom_input_format(cube(2,group=>1)); [[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]] [[1,0,3,2],[0,2,1,3]]
    •  
      topcom_regular_and_connected_triangulations (pc) → Array<Array<Set<Int>>>

      Computes all triangulations of a point configuration that are connected by bistellar flips to the regular triangulations. The triangulations are computed via the chirotope. If the input point configuration or polytope has a symmetry group, only triangulations up to symmetry will be computed.

      Parameters
      PointConfigurationpc
      or Polytope p input point configuration or polytope
      Returns
      Array<Array<Set<Int>>>
    •  
      universal_polytope <Scalar> (PC) → Polytope

      Calculate the universal polytope of a point configuration A. It is a 0/1 polytope with one vertex for every triangulation of A. Each coordinate of the ambient space corresponds to a simplex in the configuration.

      Type Parameters
      Scalar
      the underlying number type
      Parameters
      PointConfiguration<Scalar>PC
      the point configuration
      Returns
      Polytope

      Example:
      • To calculate the universal polytope of a point configuration, type> $p=new PointConfiguration(POINTS=>[[1,0,0],[1,1,0],[1,0,1],[1,1,1],[1,1/2,1/2]]);> print universal_polytope($p)->VERTICES; 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 Notice how the first vertex corresponds to the triangulation using all points, and the other ones to the triangulations that don't use the inner point.
    •  
      universal_polytope (P) → Polytope

      Calculate the universal polytope U(P) of an input polytope P. If P has n vertices and dimension d, then U(P) is a 0/1-polytope in dimension binomial(n,d+1) whose vertices correspond to the full triangulations of P. Each coordinate of a particular vertex v indicates the presence or absence of a particular simplex in the triangulation corresponding to v, and the order of the simplices (and hence the interpretation of each coordinate of v) is the one given by the property MAX_INTERIOR_SIMPLICES. Because the number of triangulations of P is typically very large, the polytope U(P) is not constructed by enumerating triangulations, but instead in the inequality description afforded by the cocircuit equations, a volume equality, and non-negativity constraints for the coordinates.

      Parameters
      PolytopeP
      the input polytope
      Returns
      Polytope

      Example:
      • Since the 2-dimensional cube (i.e., the square) has just two triangulations, its universal polytope is a segment embedded in dimension binomial(4,3) = 4. The cocircuit equations read as follows:> print universal_polytope(cube(2))->EQUATIONS; -8 4 4 4 4 (5) (2 -1) (3 1) (5) (1 -1) (4 1)
    •  
      universal_polytope (P, reps, cocircuit_equations) → Polytope

      Calculate the universal polytope of a polytope, point configuration or quotient manifold

      Parameters
      PolytopeP
      the input polytope
      Array<Set>reps
      the representatives of maximal interior simplices
      SparseMatrixcocircuit_equations
      the matrix of cocircuit equations
      Returns
      Polytope
  •  

    These functions are for visualization.

    •  
      bounding_box (V, surplus_k, voronoi) → Matrix

      Introduce artificial boundary facets (which are always vertical, i.e., the last coordinate is zero) to allow for bounded images of unbounded polyhedra (e.g. Voronoi polyhedra). If the voronoi flag is set, the last direction is left unbounded.

      Parameters
      MatrixV
      vertices that should be in the box
      Scalarsurplus_k
      size of the bounding box relative to the box spanned by V
      Boolvoronoi
      useful for visualizations of Voronoi diagrams that do not have enough vertices default value is 0.
      Returns
      Matrix
    •  
      vlabels (vertices, wo_zero) → ARRAY

      Creates vertex labels for visualization from the vertices of the polytope. The parameter wo_zero decides whether the entry at position 0 (homogenizing coordinate) is omitted (1) or included (0) in the label string."

      Parameters
      Matrixvertices
      the vertices of the polytope
      Boolwo_zero
      includes (0) or omits (1) the entry at position 0
      Returns
      ARRAY
      a reference to an array of vertex label strings

      Example:
      • This prints the vertex labels for the square with the origin as its center and side length 2, where we omit the leading 1:> $l = vlabels(cube(2)->VERTICES,1);> print join(', ', @{$l}); (-1,-1), (1,-1), (-1,1), (1,1)

Common Option Lists