Library of commonly used, famous, or interesting polytopes

This module gathers several constructors of polytopes that can be reached through polytopes.<tab>. For example, here is the hypercube in dimension 5:

sage: polytopes.hypercube(5)
A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 32 vertices

The following constructions are available

Birkhoff_polytope()

associahedron()

bitruncated_six_hundred_cell()

buckyball()

cantellated_one_hundred_twenty_cell()

cantellated_six_hundred_cell()

cantitruncated_one_hundred_twenty_cell()

cantitruncated_six_hundred_cell()

cross_polytope()

cube()

cuboctahedron()

cyclic_polytope()

dodecahedron()

flow_polytope()

Gosset_3_21()

grand_antiprism()

great_rhombicuboctahedron()

hypercube()

hypersimplex()

icosahedron()

icosidodecahedron()

Kirkman_icosahedron()

octahedron()

omnitruncated_one_hundred_twenty_cell()

omnitruncated_six_hundred_cell()

one_hundred_twenty_cell()

parallelotope()

pentakis_dodecahedron()

permutahedron()

generalized_permutahedron()

rectified_one_hundred_twenty_cell()

rectified_six_hundred_cell()

regular_polygon()

rhombic_dodecahedron()

rhombicosidodecahedron()

runcinated_one_hundred_twenty_cell()

runcitruncated_one_hundred_twenty_cell()

runcitruncated_six_hundred_cell()

simplex()

six_hundred_cell()

small_rhombicuboctahedron()

snub_cube()

snub_dodecahedron()

tetrahedron()

truncated_cube()

truncated_dodecahedron()

truncated_icosidodecahedron()

truncated_tetrahedron()

truncated_octahedron()

truncated_one_hundred_twenty_cell()

truncated_six_hundred_cell()

twenty_four_cell()

class sage.geometry.polyhedron.library.Polytopes

Bases: object

A class of constructors for commonly used, famous, or interesting polytopes.

Birkhoff_polytope(n, backend=None)

Return the Birkhoff polytope with \(n!\) vertices.

The vertices of this polyhedron are the (flattened) \(n\) by \(n\) permutation matrices. So the ambient vector space has dimension \(n^2\) but the dimension of the polyhedron is \((n-1)^2\).

INPUT:

• n – a positive integer giving the size of the permutation matrices.

• backend – the backend to use to create the polytope.

See also

sage.matrix.matrix2.Matrix.as_sum_of_permutations() – return the current matrix as a sum of permutation matrices

EXAMPLES:

sage: b3 = polytopes.Birkhoff_polytope(3)
sage: b3.f_vector()
(1, 6, 15, 18, 9, 1)
sage: b3.ambient_dim(), b3.dim()
(9, 4)
sage: b3.is_lattice_polytope()
True
sage: p3 = b3.ehrhart_polynomial()     # optional - latte_int
sage: p3                               # optional - latte_int
1/8*t^4 + 3/4*t^3 + 15/8*t^2 + 9/4*t + 1
sage: [p3(i) for i in [1,2,3,4]]       # optional - latte_int
[6, 21, 55, 120]
sage: [len((i*b3).integral_points()) for i in [1,2,3,4]]
[6, 21, 55, 120]

sage: b4 = polytopes.Birkhoff_polytope(4)
sage: b4.n_vertices(), b4.ambient_dim(), b4.dim()
(24, 16, 9)

Gosset_3_21(backend=None)

Return the Gosset \(3_{21}\) polytope.

The Gosset \(3_{21}\) polytope is a uniform 7-polytope. It has 56 vertices, and 702 facets: \(126\) \(3_{11}\) and \(576\) \(6\)-simplex. For more information, see the Wikipedia article 3_21_polytope.

INPUT:

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: g = polytopes.Gosset_3_21(); g
A 7-dimensional polyhedron in ZZ^8 defined as the convex hull of 56 vertices
sage: g.f_vector() # not tested (~16s)
(1, 56, 756, 4032, 10080, 12096, 6048, 702, 1)

Kirkman_icosahedron(backend=None)

Return the Kirkman icosahedron.

The Kirkman icosahedron is a 3-polytope with integer coordinates: \((\pm 9, \pm 6, \pm 6)\), \((\pm 12, \pm 4, 0)\), \((0, \pm 12, \pm 8)\), \((\pm 6, 0, \pm 12)\). See [Fe2012] for more information.

INPUT:

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: ki = polytopes.Kirkman_icosahedron()
sage: ki.f_vector()
(1, 20, 38, 20, 1)

sage: ki.volume()
6528

sage: vertices = ki.vertices()
sage: edges = [[vector(edge[0]),vector(edge[1])] for edge in ki.bounded_edges()]
sage: edge_lengths = [norm(edge[0]-edge[1]) for edge in edges]
sage: sorted(set(edge_lengths))
[7, 8, 9, 11, 12, 14, 16]

bitruncated_six_hundred_cell(exact=True, backend=None)

Return the bitruncated 600-cell.

The bitruncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 3600 vertices. For more information see Wikipedia article Bitruncated 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcinated_six_hundred_cell(exact=True,backend='normaliz') # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices

buckyball(exact=True, base_ring=None, backend=None)

Return the bucky ball.

The bucky ball, also known as the truncated icosahedron is an Archimedean solid. It has 32 faces and 60 vertices.

See also

icosahedron()

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: bb = polytopes.buckyball()   # long time - 6secs                          # optional - sage.rings.number_field
sage: bb.f_vector()                # long time                                  # optional - sage.rings.number_field
(1, 60, 90, 32, 1)
sage: bb.base_ring()               # long time                                  # optional - sage.rings.number_field
Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?

A much faster implementation using floating point approximations:

sage: bb = polytopes.buckyball(exact=False)
sage: bb.f_vector()
(1, 60, 90, 32, 1)
sage: bb.base_ring()
Real Double Field

Its facets are 5 regular pentagons and 6 regular hexagons:

sage: sum(1 for f in bb.facets() if len(f.vertices()) == 5)
12
sage: sum(1 for f in bb.facets() if len(f.vertices()) == 6)
20

cantellated_one_hundred_twenty_cell(exact=True, backend=None)

Return the cantellated 120-cell.

The cantellated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 3600 vertices. For more information see Wikipedia article Cantellated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantellated_one_hundred_twenty_cell(backend='normaliz') # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices

cantellated_six_hundred_cell(exact=False, backend=None)

Return the cantellated 600-cell.

The cantellated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 3600 vertices. For more information see Wikipedia article Cantellated 600-cell.

Warning

The coordinates are inexact by default. The computation with inexact coordinates (using the backend 'cdd') issues a UserWarning on inconsistencies.

INPUT:

• exact - (boolean, default False) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantellated_six_hundred_cell() # not tested - very long time
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 3600 vertices

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.cantellated_six_hundred_cell(exact=True,backend='normaliz') # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices

cantitruncated_one_hundred_twenty_cell(exact=True, backend=None)

Return the cantitruncated 120-cell.

The cantitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Cantitruncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantitruncated_one_hundred_twenty_cell(exact=True,backend='normaliz') # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices

cantitruncated_six_hundred_cell(exact=True, backend=None)

Return the cantitruncated 600-cell.

The cantitruncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Cantitruncated 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantitruncated_six_hundred_cell(exact=True,backend='normaliz') # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices

cross_polytope(dim, backend=None)

Return a cross-polytope in dimension dim.

A cross-polytope is a higher dimensional generalization of the octahedron. It is the convex hull of the \(2d\) points \((\pm 1, 0, \ldots, 0)\), \((0, \pm 1, \ldots, 0)\), ldots, \((0, 0, \ldots, \pm 1)\). See the Wikipedia article Cross-polytope for more information.

INPUT:

• dim – integer. The dimension of the cross-polytope.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: four_cross = polytopes.cross_polytope(4)
sage: four_cross.f_vector()
(1, 8, 24, 32, 16, 1)
sage: four_cross.is_simple()
False

cube(intervals=None, backend=None)

Return the cube.

The cube is the Platonic solid that is obtained as the convex hull of the eight \(\pm 1\) vectors of length 3 (by default). Alternatively, the cube is the product of three intervals from intervals.

See also

hypercube()

INPUT:

• intervals – list (default=None). It takes the following possible inputs:

  • If the input is None (the default), returns the convex hull of the eight \(\pm 1\) vectors of length three.

  • 'zero_one' – (string). Return the \(0/1\)-cube.

  • a list of 3 lists of length 2. The cube will be a product of these three intervals.

• backend – the backend to use to create the polytope.

OUTPUT:

A cube as a polyhedron object.

EXAMPLES:

Return the \(\pm 1\)-cube:

sage: c = polytopes.cube()
sage: c
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: c.f_vector()
(1, 8, 12, 6, 1)
sage: c.volume()
8
sage: c.plot()  # optional - sage.plot
Graphics3d Object

Return the \(0/1\)-cube:

sage: cc = polytopes.cube(intervals ='zero_one')
sage: cc.vertices_list()
[[1, 0, 0],
 [1, 1, 0],
 [1, 1, 1],
 [1, 0, 1],
 [0, 0, 1],
 [0, 0, 0],
 [0, 1, 0],
 [0, 1, 1]]

cuboctahedron(backend=None)

Return the cuboctahedron.

The cuboctahedron is an Archimedean solid with 12 vertices and 14 faces dual to the rhombic dodecahedron. It can be defined as the convex hull of the twelve vertices \((0, \pm 1, \pm 1)\), \((\pm 1, 0, \pm 1)\) and \((\pm 1, \pm 1, 0)\). For more information, see the Wikipedia article Cuboctahedron.

INPUT:

• backend – the backend to use to create the polytope.

See also

rhombic_dodecahedron()

EXAMPLES:

sage: co = polytopes.cuboctahedron()
sage: co.f_vector()
(1, 12, 24, 14, 1)

Its facets are 8 triangles and 6 squares:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
8
sage: sum(1 for f in co.facets() if len(f.vertices()) == 4)
6

Some more computation:

sage: co.volume()
20/3
sage: co.ehrhart_polynomial()      # optional - latte_int
20/3*t^3 + 8*t^2 + 10/3*t + 1

cyclic_polytope(dim, n, base_ring=Rational Field, backend=None)

Return a cyclic polytope.

A cyclic polytope of dimension dim with n vertices is the convex hull of the points (t,t^2,...,t^dim) with \(t \in \{0,1,...,n-1\}\) . For more information, see the Wikipedia article Cyclic_polytope.

INPUT:

• dim – positive integer. the dimension of the polytope.

• n – positive integer. the number of vertices.

• base_ring – either QQ (default) or RDF.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: c = polytopes.cyclic_polytope(4,10)
sage: c.f_vector()
(1, 10, 45, 70, 35, 1)

dodecahedron(exact=True, base_ring=None, backend=None)

Return a dodecahedron.

The dodecahedron is the Platonic solid dual to the icosahedron().

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – (optional) the ring in which the coordinates will belong to. Note that this ring must contain \(\sqrt(5)\). If it is not provided and exact=True it will be the number field \(\QQ[\sqrt(5)]\) and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: d12 = polytopes.dodecahedron()                                                    # optional - sage.rings.number_field
sage: d12.f_vector()                                                                    # optional - sage.rings.number_field
(1, 20, 30, 12, 1)
sage: d12.volume()                                                                      # optional - sage.rings.number_field
-176*sqrt5 + 400
sage: numerical_approx(_)                                                               # optional - sage.rings.number_field
6.45203596003699

sage: d12 = polytopes.dodecahedron(exact=False)
sage: d12.base_ring()
Real Double Field

Here is an error with a field that does not contain \(\sqrt(5)\):

sage: polytopes.dodecahedron(base_ring=QQ)                              # optional - sage.symbolic
Traceback (most recent call last):
...
TypeError: unable to convert 1/4*sqrt(5) + 1/4 to a rational

static edge_polytope(backend=None)

Return the edge polytope of self.

The edge polytope (EP) of a Graph on \(n\) vertices is the polytope in \(\ZZ^{n}\) defined as the convex hull of \(e_i + e_j\) for each edge \((i, j)\). Here \(e_1, \dots, e_n\) denotes the standard basis.

INPUT:

• backend – string or None (default); the backend to use; see sage.geometry.polyhedron.constructor.Polyhedron()

EXAMPLES:

The EP of a \(4\)-cycle is a square:

sage: G = graphs.CycleGraph(4)
sage: P = G.edge_polytope(); P
A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices

The EP of a complete graph on \(4\) vertices is cross polytope:

sage: G = graphs.CompleteGraph(4)
sage: P = G.edge_polytope(); P
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
sage: P.is_combinatorially_isomorphic(polytopes.cross_polytope(3))
True

The EP of a graph is isomorphic to the subdirect sum of its connected components EPs:

sage: n = randint(3, 6)
sage: G1 = graphs.RandomGNP(n, 0.2)
sage: n = randint(3, 6)
sage: G2 = graphs.RandomGNP(n, 0.2)
sage: G = G1.disjoint_union(G2)
sage: P = G.edge_polytope()
sage: P1 = G1.edge_polytope()
sage: P2 = G2.edge_polytope()
sage: P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))
True

All trees on \(n\) vertices have isomorphic EPs:

sage: n = randint(4, 10)
sage: G1 = graphs.RandomTree(n)
sage: G2 = graphs.RandomTree(n)
sage: P1 = G1.edge_polytope()
sage: P2 = G2.edge_polytope()
sage: P1.is_combinatorially_isomorphic(P2)
True

However, there are still many different EPs:

sage: len(list(graphs(5)))
34
sage: polys = []
sage: for G in graphs(5):
....:     P = G.edge_polytope()
....:     for P1 in polys:
....:         if P.is_combinatorially_isomorphic(P1):
....:             break
....:     else:
....:         polys.append(P)
sage: len(polys)
19

static flow_polytope(edges=None, ends=None, backend=None)

Return the flow polytope of a digraph.

The flow polytope of a directed graph is the polytope consisting of all nonnegative flows on the graph with a given set \(S\) of sources and a given set \(T\) of sinks.

A flow on a directed graph \(G\) with a given set \(S\) of sources and a given set \(T\) of sinks means an assignment of a nonnegative real to each edge of \(G\) such that the flow is conserved in each vertex outside of \(S\) and \(T\), and there is a unit of flow entering each vertex in \(S\) and a unit of flow leaving each vertex in \(T\). These flows clearly form a polytope in the space of all assignments of reals to the edges of \(G\).

The polytope is empty unless the sets \(S\) and \(T\) are equinumerous.

By default, \(S\) is taken to be the set of all sources (i.e., vertices of indegree \(0\)) of \(G\), and \(T\) is taken to be the set of all sinks (i.e., vertices of outdegree \(0\)) of \(G\). If a different choice of \(S\) and \(T\) is desired, it can be specified using the optional ends parameter.

The polytope is returned as a polytope in \(\RR^m\), where \(m\) is the number of edges of the digraph self. The \(k\)-th coordinate of a point in the polytope is the real assigned to the \(k\)-th edge of self. The order of the edges is the one returned by self.edges(sort=True). If a different order is desired, it can be specified using the optional edges parameter.

The faces and volume of these polytopes are of interest. Examples of these polytopes are the Chan-Robbins-Yuen polytope and the Pitman-Stanley polytope [PS2002].

INPUT:

• edges – list (default: None); a list of edges of self. If not specified, the list of all edges of self is used with the default ordering of self.edges(sort=True). This determines which coordinate of a point in the polytope will correspond to which edge of self. It is also possible to specify a list which contains not all edges of self; this results in a polytope corresponding to the flows which are \(0\) on all remaining edges. Notice that the edges entered here must be in the precisely same format as outputted by self.edges(); so, if self.edges() outputs an edge in the form (1, 3, None), then (1, 3) will not do!

• ends – (optional, default: (self.sources(), self.sinks())) a pair \((S, T)\) of an iterable \(S\) and an iterable \(T\).

• backend – string or None (default); the backend to use; see sage.geometry.polyhedron.constructor.Polyhedron()

Note

Flow polytopes can also be built through the polytopes.<tab> object:

sage: polytopes.flow_polytope(digraphs.Path(5))
A 0-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex

EXAMPLES:

A commutative square:

sage: G = DiGraph({1: [2, 3], 2: [4], 3: [4]})
sage: fl = G.flow_polytope(); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 1, 0, 1), A vertex at (1, 0, 1, 0))

Using a different order for the edges of the graph:

sage: fl = G.flow_polytope(edges=G.edges(key=lambda x: x[0] - x[1])); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices
sage: fl.vertices()
(A vertex at (0, 1, 1, 0), A vertex at (1, 0, 0, 1))

A tournament on 4 vertices:

sage: H = digraphs.TransitiveTournament(4)
sage: fl = H.flow_polytope(); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 4 vertices
sage: fl.vertices()
(A vertex at (0, 0, 1, 0, 0, 0),
 A vertex at (0, 1, 0, 0, 0, 1),
 A vertex at (1, 0, 0, 0, 1, 0),
 A vertex at (1, 0, 0, 1, 0, 1))

Restricting to a subset of the edges:

sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),
....:                             (2, 3, None), (0, 3, None)])
sage: fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1), A vertex at (1, 1, 1, 0))

Using a different choice of sources and sinks:

sage: fl = H.flow_polytope(ends=([1], [3])); fl
A 1-dimensional polyhedron in QQ^6 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 0, 1), A vertex at (0, 0, 0, 0, 1, 0))
sage: fl = H.flow_polytope(ends=([0, 1], [3])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([3], [0])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([0, 1], [2, 3])); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 5 vertices
sage: fl.vertices()
(A vertex at (0, 0, 1, 1, 0, 0),
 A vertex at (0, 1, 0, 0, 1, 0),
 A vertex at (1, 0, 0, 2, 0, 1),
 A vertex at (1, 0, 0, 1, 1, 0),
 A vertex at (0, 1, 0, 1, 0, 1))
sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),
....:                             (2, 3, None), (0, 2, None),
....:                             (1, 3, None)],
....:                      ends=([0, 1], [2, 3])); fl
A 2-dimensional polyhedron in QQ^5 defined as the convex hull
of 4 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 1),
 A vertex at (1, 2, 1, 0, 0),
 A vertex at (1, 1, 0, 0, 1),
 A vertex at (0, 1, 1, 1, 0))

A digraph with one source and two sinks:

sage: Y = DiGraph({1: [2], 2: [3, 4]})
sage: Y.flow_polytope()
The empty polyhedron in QQ^3

A digraph with one vertex and no edge:

sage: Z = DiGraph({1: []})
sage: Z.flow_polytope()
A 0-dimensional polyhedron in QQ^0 defined as the convex hull
of 1 vertex

A digraph with multiple edges (trac ticket #28837):

sage: G = DiGraph([(0, 1), (0,1)], multiedges=True)
sage: G
Multi-digraph on 2 vertices
sage: P = G.flow_polytope()
sage: P
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: P.vertices()
(A vertex at (1, 0), A vertex at (0, 1))
sage: P.lines()
()

generalized_permutahedron(coxeter_type, point=None, exact=True, regular=False, backend=None)

Return the generalized permutahedron of type coxeter_type as the convex hull of the orbit of point in the fundamental cone.

This generalized permutahedron lies in the vector space used in the geometric representation, that is, in the default case, the dimension of generalized permutahedron equals the dimension of the space.

INPUT:

• coxeter_type – a Coxeter type; given as a pair [type,rank], where type is a letter and rank is the number of generators.

• point – a list (default: None); a point given by its coordinates in the weight basis. If None is given, the point \((1, 1, 1, \ldots)\) is used.

• exact - (boolean, default True) if False use floating point approximations instead of exact coordinates

• regular – boolean (default: False); whether to apply a linear transformation making the vertex figures isometric.

• backend – backend to use to create the polytope; (default: None)

EXAMPLES:

sage: perm_a3 = polytopes.generalized_permutahedron(['A',3]); perm_a3
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 24 vertices

You can put the starting point along the hyperplane of the first generator:

sage: perm_a3_011 = polytopes.generalized_permutahedron(['A',3],[0,1,1]); perm_a3_011
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
sage: perm_a3_110 = polytopes.generalized_permutahedron(['A',3],[1,1,0]); perm_a3_110
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
sage: perm_a3_110.is_combinatorially_isomorphic(perm_a3_011)
True
sage: perm_a3_101 = polytopes.generalized_permutahedron(['A',3],[1,0,1]); perm_a3_101
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
sage: perm_a3_110.is_combinatorially_isomorphic(perm_a3_101)
False
sage: perm_a3_011.f_vector()
(1, 12, 18, 8, 1)
sage: perm_a3_101.f_vector()
(1, 12, 24, 14, 1)

The usual output does not necessarily give a polyhedron with isometric vertex figures:

sage: perm_a2 = polytopes.generalized_permutahedron(['A',2])
sage: perm_a2.vertices()
(A vertex at (-1, -1),
 A vertex at (-1, 0),
 A vertex at (0, -1),
 A vertex at (0, 1),
 A vertex at (1, 0),
 A vertex at (1, 1))

It works also with Coxeter types that lead to non-rational coordinates:

sage: perm_b3 = polytopes.generalized_permutahedron(['B',3]); perm_b3  # long time                                      # optional - sage.rings.number_field
A 3-dimensional polyhedron
 in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3
defined as the convex hull of 48 vertices

Setting regular=True applies a linear transformation to get isometric vertex figures and the result is inscribed. This cannot be done using rational coordinates. We first do the computations using floating point approximations (RDF):

sage: perm_a2_inexact = polytopes.generalized_permutahedron(['A',2], exact=False)
sage: sorted(perm_a2_inexact.vertices())
[A vertex at (-1.0, -1.0),
 A vertex at (-1.0, 0.0),
 A vertex at (0.0, -1.0),
 A vertex at (0.0, 1.0),
 A vertex at (1.0, 0.0),
 A vertex at (1.0, 1.0)]

sage: perm_a2_inexact_reg = polytopes.generalized_permutahedron(['A',2], exact=False, regular=True)
sage: sorted(perm_a2_inexact_reg.vertices())
[A vertex at (-1.0, 0.0),
 A vertex at (-0.5, -0.8660254038),
 A vertex at (-0.5, 0.8660254038),
 A vertex at (0.5, -0.8660254038),
 A vertex at (0.5, 0.8660254038),
 A vertex at (1.0, 0.0)]

We can do the same computation using exact arithmetic with the field AA:

sage: perm_a2_reg = polytopes.generalized_permutahedron(['A',2], regular=True)                                          # optional - sage.rings.number_field
sage: V = sorted(perm_a2_reg.vertices()); V         # random                                                            # optional - sage.rings.number_field
[A vertex at (-1, 0),
 A vertex at (-1/2, -0.866025403784439?),
 A vertex at (-1/2, 0.866025403784439?),
 A vertex at (1/2, -0.866025403784439?),
 A vertex at (1/2, 0.866025403784439?),
 A vertex at (1.000000000000000?, 0.?e-18)]

Even though the numbers look like floating point approximations, the computation is actually exact. We can clean up the display a bit using exactify:

sage: for v in V:                                                                                                       # optional - sage.rings.number_field
....:     for x in v:
....:         x.exactify()
sage: V                                                                                                                 # optional - sage.rings.number_field
[A vertex at (-1, 0),
 A vertex at (-1/2, -0.866025403784439?),
 A vertex at (-1/2, 0.866025403784439?),
 A vertex at (1/2, -0.866025403784439?),
 A vertex at (1/2, 0.866025403784439?),
 A vertex at (1, 0)]
sage: perm_a2_reg.is_inscribed()                                                                                        # optional - sage.rings.number_field
True

Larger examples take longer:

sage: perm_a3_reg = polytopes.generalized_permutahedron(['A',3], regular=True); perm_a3_reg  # long time                # optional - sage.rings.number_field
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
sage: perm_a3_reg.is_inscribed()                                                             # long time                # optional - sage.rings.number_field
True
sage: perm_b3_reg = polytopes.generalized_permutahedron(['B',3], regular=True); perm_b3_reg  # not tested - long time (12sec on 64 bits).
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices

It is faster with the backend 'number_field', which internally uses an embedded number field instead of doing the computations directly with the base ring (AA):

sage: perm_a3_reg_nf = polytopes.generalized_permutahedron(                                                             # optional - sage.rings.number_field
....:    ['A',3], regular=True, backend='number_field'); perm_a3_reg_nf
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
sage: perm_a3_reg_nf.is_inscribed()                                                                                     # optional - sage.rings.number_field
True
sage: perm_b3_reg_nf = polytopes.generalized_permutahedron(                     # long time                             # optional - sage.rings.number_field
....:    ['B',3], regular=True, backend='number_field'); perm_b3_reg_nf
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices

It is even faster with the backend 'normaliz':

sage: perm_a3_reg_norm = polytopes.generalized_permutahedron(                                 # optional - pynormaliz
....:    ['A',3], regular=True, backend='normaliz'); perm_a3_reg_norm
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
sage: perm_a3_reg_norm.is_inscribed()                                                         # optional - pynormaliz
True
sage: perm_b3_reg_norm = polytopes.generalized_permutahedron(                                 # optional - pynormaliz
....:    ['B',3], regular=True, backend='normaliz'); perm_b3_reg_norm
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices

The speedups from using backend 'normaliz' allow us to go even further:

sage: perm_h3 = polytopes.generalized_permutahedron(['H',3], backend='normaliz')              # optional - pynormaliz
sage: perm_h3                                                                                 # optional - pynormaliz
A 3-dimensional polyhedron
 in (Number Field in a with defining polynomial x^2 - 5 with a = 2.236067977499790?)^3
 defined as the convex hull of 120 vertices
sage: perm_f4 = polytopes.generalized_permutahedron(['F',4], backend='normaliz')  # long time # optional - pynormaliz
sage: perm_f4                                                                     # long time # optional - pynormaliz
A 4-dimensional polyhedron
 in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^4
 defined as the convex hull of 1152 vertices

See also

• permutahedron()

• permutahedron()

grand_antiprism(exact=True, backend=None, verbose=False)

Return the grand antiprism.

The grand antiprism is a 4-dimensional non-Wythoffian uniform polytope. The coordinates were taken from http://eusebeia.dyndns.org/4d/gap. For more information, see the Wikipedia article Grand_antiprism.

Warning

The coordinates are exact by default. The computation with exact coordinates is not as fast as with floating point approximations. If you find this method to be too slow, consider using floating point approximations

INPUT:

• exact - (boolean, default True) if False use floating point approximations instead of exact coordinates

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: gap = polytopes.grand_antiprism()  # not tested - very long time
sage: gap                                # not tested - very long time
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
the convex hull of 100 vertices

Computation with the backend 'normaliz' is instantaneous:

sage: gap_norm = polytopes.grand_antiprism(backend='normaliz')  # optional - pynormaliz
sage: gap_norm                                                  # optional - pynormaliz
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
the convex hull of 100 vertices

Computation with approximated coordinates is also faster, but inexact:

sage: gap = polytopes.grand_antiprism(exact=False) # random
sage: gap
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 100 vertices
sage: gap.f_vector()
(1, 100, 500, 720, 320, 1)
sage: len(list(gap.bounded_edges()))
500

great_rhombicuboctahedron(exact=True, base_ring=None, backend=None)

Return the great rhombicuboctahedron.

The great rhombicuboctahedron (or truncated cuboctahedron) is an Archimedean solid with 48 vertices and 26 faces. For more information see the Wikipedia article Truncated_cuboctahedron.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: gr = polytopes.great_rhombicuboctahedron()  # long time ~ 3sec    # optional - sage.rings.number_field
sage: gr.f_vector()                               # long time           # optional - sage.rings.number_field
(1, 48, 72, 26, 1)

A faster implementation is obtained by setting exact=False:

sage: gr = polytopes.great_rhombicuboctahedron(exact=False)
sage: gr.f_vector()
(1, 48, 72, 26, 1)

Its facets are 4 squares, 8 regular hexagons and 6 regular octagons:

sage: sum(1 for f in gr.facets() if len(f.vertices()) == 4)
12
sage: sum(1 for f in gr.facets() if len(f.vertices()) == 6)
8
sage: sum(1 for f in gr.facets() if len(f.vertices()) == 8)
6

hypercube(dim, intervals=None, backend=None)

Return a hypercube of the given dimension.

The dim-dimensional hypercube is by default the convex hull of the \(2^{\text{dim}}\) \(\pm 1\) vectors of length dim. Alternatively, it is the product of dim line segments given in the intervals. For more information see the wikipedia article Wikipedia article Hypercube.

INPUT:

• dim – integer. The dimension of the hypercube.

• intervals – (default = None). It takes the following possible inputs:

  • If None (the default), it returns the \(\pm 1\)-cube of dimension dim.

  • 'zero_one' – (string). Return the \(0/1\)-cube.

  • a list of length dim. Its elements are pairs of numbers \((a,b)\) with \(a < b\). The cube will be the product of these intervals.

• backend – the backend to use to create the polytope.

EXAMPLES:

Create the \(\pm 1\)-hypercube of dimension 4:

sage: four_cube = polytopes.hypercube(4)
sage: four_cube.is_simple()
True
sage: four_cube.base_ring()
Integer Ring
sage: four_cube.volume()
16
sage: four_cube.ehrhart_polynomial()    # optional - latte_int
16*t^4 + 32*t^3 + 24*t^2 + 8*t + 1

Return the \(0/1\)-hypercube of dimension 4:

sage: z_cube = polytopes.hypercube(4,intervals = 'zero_one')
sage: z_cube.vertices()[0]
A vertex at (1, 0, 1, 1)
sage: z_cube.is_simple()
True
sage: z_cube.base_ring()
Integer Ring
sage: z_cube.volume()
1
sage: z_cube.ehrhart_polynomial()    # optional - latte_int
t^4 + 4*t^3 + 6*t^2 + 4*t + 1

Return the 4-dimensional combinatorial cube that is the product of [0,3]^4:

sage: t_cube = polytopes.hypercube(4, intervals = [[0,3]]*4)

Checking that t_cube is three times the previous \(0/1\)-cube:

sage: t_cube == 3 * z_cube
True

hypersimplex(dim, k, project=False, backend=None)

Return the hypersimplex in dimension dim and parameter k.

The hypersimplex \(\Delta_{d,k}\) is the convex hull of the vertices made of \(k\) ones and \(d-k\) zeros. It lies in the \(d-1\) hyperplane of vectors of sum \(k\). If you want a projected version to \(\RR^{d-1}\) (with floating point coordinates) then set project=True in the options.

See also

simplex()

INPUT:

• dim – the dimension

• n – the numbers (1,...,n) are permuted

• project – (boolean, default False) if True, the polytope is (isometrically) projected to a vector space of dimension dim-1. This operation turns the coordinates into floating point approximations and corresponds to the projection given by the matrix from zero_sum_projection().

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: h_4_2 = polytopes.hypersimplex(4, 2)
sage: h_4_2
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
sage: h_4_2.f_vector()
(1, 6, 12, 8, 1)
sage: h_4_2.ehrhart_polynomial()    # optional - latte_int
2/3*t^3 + 2*t^2 + 7/3*t + 1
sage: TestSuite(h_4_2).run()

sage: h_7_3 = polytopes.hypersimplex(7, 3, project=True)
sage: h_7_3
A 6-dimensional polyhedron in RDF^6 defined as the convex hull of 35 vertices
sage: h_7_3.f_vector()
(1, 35, 210, 350, 245, 84, 14, 1)
sage: TestSuite(h_7_3).run(skip=["_test_pyramid", "_test_lawrence"])

icosahedron(exact=True, base_ring=None, backend=None)

Return an icosahedron with edge length 1.

The icosahedron is one of the Platonic solids. It has 20 faces and is dual to the dodecahedron().

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – (optional) the ring in which the coordinates will belong to. Note that this ring must contain \(\sqrt(5)\). If it is not provided and exact=True it will be the number field \(\QQ[\sqrt(5)]\) and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: ico = polytopes.icosahedron()                                                 # optional - sage.rings.number_field
sage: ico.f_vector()                                                                # optional - sage.rings.number_field
(1, 12, 30, 20, 1)
sage: ico.volume()                                                                  # optional - sage.rings.number_field
5/12*sqrt5 + 5/4

Its non exact version:

sage: ico = polytopes.icosahedron(exact=False)
sage: ico.base_ring()
Real Double Field
sage: ico.volume() # known bug (trac 18214)
2.181694990...

A version using \(AA <sage.rings.qqbar.AlgebraicRealField>\):

sage: ico = polytopes.icosahedron(base_ring=AA)   # long time                       # optional - sage.rings.number_field
sage: ico.base_ring()                             # long time                       # optional - sage.rings.number_field
Algebraic Real Field
sage: ico.volume()                                # long time                       # optional - sage.rings.number_field
2.181694990624913?

Note that if base ring is provided it must contain the square root of \(5\). Otherwise you will get an error:

sage: polytopes.icosahedron(base_ring=QQ)                                           # optional - sage.symbolic
Traceback (most recent call last):
...
TypeError: unable to convert 1/4*sqrt(5) + 1/4 to a rational

icosidodecahedron(exact=True, backend=None)

Return the icosidodecahedron.

The Icosidodecahedron is a polyhedron with twenty triangular faces and twelve pentagonal faces. For more information see the Wikipedia article Icosidodecahedron.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: id = polytopes.icosidodecahedron()                                                # optional - sage.rings.number_field
sage: id.f_vector()                                                                     # optional - sage.rings.number_field
(1, 30, 60, 32, 1)

icosidodecahedron_V2(exact=True, base_ring=None, backend=None)

Return the icosidodecahedron.

The icosidodecahedron is an Archimedean solid. It has 32 faces and 30 vertices. For more information, see the Wikipedia article Icosidodecahedron.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: id = polytopes.icosidodecahedron_V2()   # long time - 6secs
sage: id.f_vector()                # long time
(1, 30, 60, 32, 1)
sage: id.base_ring()               # long time
Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?

A much faster implementation using floating point approximations:

sage: id = polytopes.icosidodecahedron_V2(exact=False)
sage: id.f_vector()
(1, 30, 60, 32, 1)
sage: id.base_ring()
Real Double Field

Its facets are 20 triangles and 12 regular pentagons:

sage: sum(1 for f in id.facets() if len(f.vertices()) == 3)
20
sage: sum(1 for f in id.facets() if len(f.vertices()) == 5)
12

octahedron(backend=None)

Return the octahedron.

The octahedron is a Platonic solid with 6 vertices and 8 faces dual to the cube. It can be defined as the convex hull of the six vertices \((0, 0, \pm 1)\), \((\pm 1, 0, 0)\) and \((0, \pm 1, 0)\). For more information, see the Wikipedia article Octahedron.

INPUT:

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.octahedron()
sage: co.f_vector()
(1, 6, 12, 8, 1)

Its facets are 8 triangles:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
8

Some more computation:

sage: co.volume()
4/3
sage: co.ehrhart_polynomial()      # optional - latte_int
4/3*t^3 + 2*t^2 + 8/3*t + 1

omnitruncated_one_hundred_twenty_cell(exact=True, backend=None)

Return the omnitruncated 120-cell.

The omnitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 14400 vertices. For more information see Wikipedia article Omnitruncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.omnitruncated_one_hundred_twenty_cell(backend='normaliz') # not tested - very long time ~10min
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 14400 vertices

omnitruncated_six_hundred_cell(exact=True, backend=None)

Return the omnitruncated 120-cell.

The omnitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 14400 vertices. For more information see Wikipedia article Omnitruncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.omnitruncated_one_hundred_twenty_cell(backend='normaliz') # not tested - very long time ~10min
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 14400 vertices

one_hundred_twenty_cell(exact=True, backend=None, construction='coxeter')

Return the 120-cell.

The 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 600 vertices and 120 facets. For more information see Wikipedia article 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

• construction – the construction to use (string, default ‘coxeter’); the other possibility is ‘as_permutahedron’.

` EXAMPLES:

The classical construction given by Coxeter in [Cox1969] is given by:

sage: polytopes.one_hundred_twenty_cell()                    # not tested - long time ~15 sec.
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
the convex hull of 600 vertices

The 'normaliz' is faster:

sage: P = polytopes.one_hundred_twenty_cell(backend='normaliz'); P  # optional - pynormaliz
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as the convex hull of 600 vertices

It is also possible to realize it using the generalized permutahedron of type \(H_4\):

sage: polytopes.one_hundred_twenty_cell(backend='normaliz',construction='as_permutahedron') # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 600 vertices

parallelotope(generators, backend=None)

Return the zonotope, or parallelotope, spanned by the generators.

The parallelotope is the multi-dimensional generalization of a parallelogram (2 generators) and a parallelepiped (3 generators).

INPUT:

• generators – a list of vectors of same dimension

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.parallelotope([ (1,0), (0,1) ])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: polytopes.parallelotope([[1,2,3,4],[0,1,0,7],[3,1,0,2],[0,0,1,0]])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices

sage: K = QuadraticField(2, 'sqrt2')
sage: sqrt2 = K.gen()
sage: P = polytopes.parallelotope([ (1,sqrt2), (1,-1) ]); P
A 2-dimensional polyhedron in (Number Field in sqrt2 with defining
polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^2 defined as
the convex hull of 4 vertices

pentakis_dodecahedron(exact=True, base_ring=None, backend=None)

Return the pentakis dodecahedron.

The pentakis dodecahedron (orkisdodecahedron) is a face-regular, vertex-uniform polytope dual to the truncated icosahedron. It has 60 facets and 32 vertices. See the Wikipedia article Pentakis_dodecahedron for more information.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: pd = polytopes.pentakis_dodecahedron()    # long time - ~10 sec
sage: pd.n_vertices()                           # long time
32
sage: pd.n_inequalities()                       # long time
60

A much faster implementation is obtained when setting exact=False:

sage: pd = polytopes.pentakis_dodecahedron(exact=False)
sage: pd.n_vertices()
32
sage: pd.n_inequalities()
60

The 60 are triangles:

sage: all(len(f.vertices()) == 3 for f in pd.facets())
True

permutahedron(n, project=False, backend=None)

Return the standard permutahedron of (1,…,n).

The permutahedron (or permutohedron) is the convex hull of the permutations of \(\{1,\ldots,n\}\) seen as vectors. The edges between the permutations correspond to multiplication on the right by an elementary transposition in the SymmetricGroup.

If we take the graph in which the vertices correspond to vertices of the polyhedron, and edges to edges, we get the BubbleSortGraph().

INPUT:

• n – integer

• project – (boolean, default False) if True, the polytope is (isometrically) projected to a vector space of dimension dim-1. This operation turns the coordinates into floating point approximations and corresponds to the projection given by the matrix from zero_sum_projection().

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: perm4 = polytopes.permutahedron(4)
sage: perm4
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 24 vertices
sage: perm4.is_lattice_polytope()
True
sage: perm4.ehrhart_polynomial()   # optional - latte_int
16*t^3 + 15*t^2 + 6*t + 1

sage: perm4 = polytopes.permutahedron(4, project=True)
sage: perm4
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
sage: perm4.plot()  # optional - sage.plot
Graphics3d Object
sage: perm4.graph().is_isomorphic(graphs.BubbleSortGraph(4))
True

As both Hrepresentation an Vrepresentation are known, the permutahedron can be set up with both using the backend field. The following takes very very long time to recompute, e.g. with backend ppl:

sage: polytopes.permutahedron(8, backend='field')  # (~1s)
A 7-dimensional polyhedron in QQ^8 defined as the convex hull of 40320 vertices
sage: polytopes.permutahedron(9, backend='field')  # not tested (memory consumption)  # (~5s)
A 8-dimensional polyhedron in QQ^9 defined as the convex hull of 362880 vertices

See also

• BubbleSortGraph()

rectified_one_hundred_twenty_cell(exact=True, backend=None)

Return the rectified 120-cell.

The rectified 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 1200 vertices. For more information see Wikipedia article Rectified 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.rectified_one_hundred_twenty_cell(backend='normaliz') # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 1200 vertices

rectified_six_hundred_cell(exact=True, backend=None)

Return the rectified 600-cell.

The rectified 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 720 vertices. For more information see Wikipedia article Rectified 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.rectified_six_hundred_cell(backend='normaliz') # not tested - long time ~14sec
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 720 vertices

regular_polygon(n, exact=True, base_ring=None, backend=None)

Return a regular polygon with \(n\) vertices.

INPUT:

• n – a positive integer, the number of vertices.

• exact – (boolean, default True) if False floating point numbers are used for coordinates.

• base_ring – a ring in which the coordinates will lie. It is None by default. If it is not provided and exact is True then it will be the field of real algebraic number, if exact is False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: octagon = polytopes.regular_polygon(8)                                               # optional - sage.rings.number_field
sage: octagon                                                                              # optional - sage.rings.number_field
A 2-dimensional polyhedron in AA^2 defined as the convex hull of 8 vertices
sage: octagon.n_vertices()                                                                 # optional - sage.rings.number_field
8
sage: v = octagon.volume()                                                                 # optional - sage.rings.number_field
sage: v                                                                                    # optional - sage.rings.number_field
2.828427124746190?
sage: v == 2*QQbar(2).sqrt()                                                               # optional - sage.rings.number_field
True

Its non exact version:

sage: polytopes.regular_polygon(3, exact=False).vertices()
(A vertex at (0.0, 1.0),
 A vertex at (0.8660254038, -0.5),
 A vertex at (-0.8660254038, -0.5))
sage: polytopes.regular_polygon(25, exact=False).n_vertices()
25

rhombic_dodecahedron(backend=None)

Return the rhombic dodecahedron.

The rhombic dodecahedron is a polytope dual to the cuboctahedron. It has 14 vertices and 12 faces. For more information see the Wikipedia article Rhombic_dodecahedron.

INPUT:

• backend – the backend to use to create the polytope.

See also

cuboctahedron()

EXAMPLES:

sage: rd = polytopes.rhombic_dodecahedron()
sage: rd.f_vector()
(1, 14, 24, 12, 1)

Its facets are 12 quadrilaterals (not all identical):

sage: sum(1 for f in rd.facets() if len(f.vertices()) == 4)
12

Some more computations:

sage: p = rd.ehrhart_polynomial()    # optional - latte_int
sage: p                              # optional - latte_int
16*t^3 + 12*t^2 + 4*t + 1
sage: [p(i) for i in [1,2,3,4]]      # optional - latte_int
[33, 185, 553, 1233]
sage: [len((i*rd).integral_points()) for i in [1,2,3,4]]
[33, 185, 553, 1233]

rhombicosidodecahedron(exact=True, base_ring=None, backend=None)

Return the rhombicosidodecahedron.

The rhombicosidodecahedron is an Archimedean solid. It has 62 faces and 60 vertices. For more information, see the Wikipedia article Rhombicosidodecahedron.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: rid = polytopes.rhombicosidodecahedron()   # long time - 6secs
sage: rid.f_vector()                # long time
(1, 60, 120, 62, 1)
sage: rid.base_ring()               # long time
Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?

A much faster implementation using floating point approximations:

sage: rid = polytopes.rhombicosidodecahedron(exact=False)
sage: rid.f_vector()
(1, 60, 120, 62, 1)
sage: rid.base_ring()
Real Double Field

Its facets are 20 triangles, 30 squares and 12 pentagons:

sage: sum(1 for f in rid.facets() if len(f.vertices()) == 3)
20
sage: sum(1 for f in rid.facets() if len(f.vertices()) == 4)
30
sage: sum(1 for f in rid.facets() if len(f.vertices()) == 5)
12

runcinated_one_hundred_twenty_cell(exact=False, backend=None)

Return the runcinated 120-cell.

The runcinated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 2400 vertices. For more information see Wikipedia article Runcinated 120-cell.

Warning

The coordinates are inexact by default. The computation with inexact coordinates (using the backend 'cdd') issues a UserWarning on inconsistencies.

INPUT:

• exact - (boolean, default False) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcinated_one_hundred_twenty_cell(exact=False) # not tested - very long time
doctest:warning ...  UserWarning: This polyhedron data is
numerically complicated; cdd could not convert between the inexact
V and H representation without loss of data. The resulting object
might show inconsistencies.
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 2400 vertices

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.runcinated_one_hundred_twenty_cell(exact=True,backend='normaliz') # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 2400 vertices

runcitruncated_one_hundred_twenty_cell(exact=False, backend=None)

Return the runcitruncated 120-cell.

The runcitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Runcitruncated 120-cell.

Warning

The coordinates are inexact by default. The computation with inexact coordinates (using the backend 'cdd') issues a UserWarning on inconsistencies.

INPUT:

• exact - (boolean, default False) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcitruncated_one_hundred_twenty_cell(exact=False) # not tested - very long time
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.runcitruncated_one_hundred_twenty_cell(exact=True,backend='normaliz') # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices

runcitruncated_six_hundred_cell(exact=True, backend=None)

Return the runcitruncated 600-cell.

The runcitruncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Runcitruncated 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcitruncated_six_hundred_cell(backend='normaliz') # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of
7200 vertices

simplex(dim=3, project=False, base_ring=None, backend=None)

Return the dim dimensional simplex.

The \(d\)-simplex is the convex hull in \(\RR^{d+1}\) of the standard basis \((1,0,\ldots,0)\), \((0,1,\ldots,0)\), ldots, \((0,0,\ldots,1)\). For more information, see the Wikipedia article Simplex.

INPUT:

• dim – The dimension of the simplex, a positive integer.

• project – (boolean, default False) if True, the polytope is (isometrically) projected to a vector space of dimension dim-1. This corresponds to the projection given by the matrix from zero_sum_projection(). By default, this operation turns the coordinates into floating point approximations (see base_ring).

• base_ring – the base ring to use to create the polytope. If project is False, this defaults to \(\ZZ\). Otherwise, it defaults to RDF.

• backend – the backend to use to create the polytope.

See also

tetrahedron()

EXAMPLES:

sage: s5 = polytopes.simplex(5)
sage: s5
A 5-dimensional polyhedron in ZZ^6 defined as the convex hull of 6 vertices
sage: s5.f_vector()
(1, 6, 15, 20, 15, 6, 1)

sage: s5 = polytopes.simplex(5, project=True)
sage: s5
A 5-dimensional polyhedron in RDF^5 defined as the convex hull of 6 vertices

Its volume is \(\sqrt{d+1} / d!\):

sage: s5 = polytopes.simplex(5, project=True)
sage: s5.volume()      # abs tol 1e-10
0.0204124145231931
sage: sqrt(6.) / factorial(5)
0.0204124145231931

sage: s6 = polytopes.simplex(6, project=True)
sage: s6.volume()      # abs tol 1e-10
0.00367465459870082
sage: sqrt(7.) / factorial(6)
0.00367465459870082

Computation in algebraic reals:

sage: s3 = polytopes.simplex(3, project=True, base_ring=AA)                     # optional - sage.rings.number_field
sage: s3.volume() == sqrt(3+1) / factorial(3)                                   # optional - sage.rings.number_field
True

six_hundred_cell(exact=False, backend=None)

Return the standard 600-cell polytope.

The 600-cell is a 4-dimensional regular polytope. In many ways this is an analogue of the icosahedron.

Warning

The coordinates are not exact by default. The computation with exact coordinates takes a huge amount of time.

INPUT:

• exact - (boolean, default False) if True use exact coordinates instead of floating point approximations

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: p600 = polytopes.six_hundred_cell()
sage: p600
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 120 vertices
sage: p600.f_vector()  # long time ~2sec
(1, 120, 720, 1200, 600, 1)

Computation with exact coordinates is currently too long to be useful:

sage: p600 = polytopes.six_hundred_cell(exact=True) # not tested - very long time
sage: len(list(p600.bounded_edges()))               # not tested - very long time
720

small_rhombicuboctahedron(exact=True, base_ring=None, backend=None)

Return the (small) rhombicuboctahedron.

The rhombicuboctahedron is an Archimedean solid with 24 vertices and 26 faces. See the Wikipedia article Rhombicuboctahedron for more information.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: sr = polytopes.small_rhombicuboctahedron()                    # optional - sage.rings.number_field
sage: sr.f_vector()                                                 # optional - sage.rings.number_field
(1, 24, 48, 26, 1)
sage: sr.volume()                                                   # optional - sage.rings.number_field
80/3*sqrt2 + 32

The faces are \(8\) equilateral triangles and \(18\) squares:

sage: sum(1 for f in sr.facets() if len(f.vertices()) == 3)         # optional - sage.rings.number_field
8
sage: sum(1 for f in sr.facets() if len(f.vertices()) == 4)         # optional - sage.rings.number_field
18

Its non exact version:

sage: sr = polytopes.small_rhombicuboctahedron(False)
sage: sr
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of
24 vertices
sage: sr.f_vector()
(1, 24, 48, 26, 1)

snub_cube(exact=False, base_ring=None, backend=None, verbose=False)

Return a snub cube.

The snub cube is an Archimedean solid. It has 24 vertices and 38 faces. For more information see the Wikipedia article Snub_cube.

The constant \(z\) used in constructing this polytope is the reciprocal of the tribonacci constant, that is, the solution of the equation \(x^3 + x^2 + x - 1 = 0\). See Wikipedia article Generalizations_of_Fibonacci_numbers#Tribonacci_numbers.

INPUT:

• exact – (boolean, default False) if True use exact coordinates instead of floating point approximations

• base_ring – the field to use. If None (the default), construct the exact number field needed (if exact is True) or default to RDF (if exact is True).

• backend – the backend to use to create the polytope. If None (the default), the backend will be selected automatically.

EXAMPLES:

sage: sc_inexact = polytopes.snub_cube(exact=False); sc_inexact                 # optional - sage.groups
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
sage: sc_inexact.f_vector()                                                     # optional - sage.groups
(1, 24, 60, 38, 1)
sage: sc_exact = polytopes.snub_cube(exact=True)          # long time           # optional - sage.groups sage.rings.number_field
sage: sc_exact.f_vector()                                 # long time           # optional - sage.groups sage.rings.number_field
(1, 24, 60, 38, 1)
sage: sorted(sc_exact.vertices())                         # long time           # optional - sage.groups sage.rings.number_field
[A vertex at (-1, -z, -z^2),
 A vertex at (-1, -z^2, z),
 A vertex at (-1, z^2, -z),
 A vertex at (-1, z, z^2),
 A vertex at (-z, -1, z^2),
 A vertex at (-z, -z^2, -1),
 A vertex at (-z, z^2, 1),
 A vertex at (-z, 1, -z^2),
 A vertex at (-z^2, -1, -z),
 A vertex at (-z^2, -z, 1),
 A vertex at (-z^2, z, -1),
 A vertex at (-z^2, 1, z),
 A vertex at (z^2, -1, z),
 A vertex at (z^2, -z, -1),
 A vertex at (z^2, z, 1),
 A vertex at (z^2, 1, -z),
 A vertex at (z, -1, -z^2),
 A vertex at (z, -z^2, 1),
 A vertex at (z, z^2, -1),
 A vertex at (z, 1, z^2),
 A vertex at (1, -z, z^2),
 A vertex at (1, -z^2, -z),
 A vertex at (1, z^2, z),
 A vertex at (1, z, -z^2)]
sage: sc_exact.is_combinatorially_isomorphic(sc_inexact)  # long time           # optional - sage.groups sage.rings.number_field
True

snub_dodecahedron(base_ring=None, backend=None, verbose=False)

Return the snub dodecahedron.

The snub dodecahedron is an Archimedean solid. It has 92 faces and 60 vertices. For more information, see the Wikipedia article Snub_dodecahedron.

INPUT:

• base_ring – the ring in which the coordinates will belong to. If it is not provided it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

Only the backend using the optional normaliz package can construct the snub dodecahedron in reasonable time:

sage: sd = polytopes.snub_dodecahedron(base_ring=AA, backend='normaliz') # optional - pynormaliz, long time
sage: sd.f_vector()                                                      # optional - pynormaliz, long time
(1, 60, 150, 92, 1)
sage: sd.base_ring()                                                     # optional - pynormaliz, long time
Algebraic Real Field

Its facets are 80 triangles and 12 pentagons:

sage: sum(1 for f in sd.facets() if len(f.vertices()) == 3)              # optional - pynormaliz, long time
80
sage: sum(1 for f in sd.facets() if len(f.vertices()) == 5)              # optional - pynormaliz, long time
12

static symmetric_edge_polytope(backend=None)

Return the symmetric edge polytope of self.

The symmetric edge polytope (SEP) of a Graph on \(n\) vertices is the polytope in \(\ZZ^{n}\) defined as the convex hull of \(e_i - e_j\) and \(e_j - e_i\) for each edge \((i, j)\). Here \(e_1, \dots, e_n\) denotes the standard basis.

INPUT:

• backend – string or None (default); the backend to use; see sage.geometry.polyhedron.constructor.Polyhedron()

EXAMPLES:

The SEP of a \(4\)-cycle is a cube:

sage: G = graphs.CycleGraph(4)
sage: P = G.symmetric_edge_polytope(); P
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 8 vertices
sage: P.is_combinatorially_isomorphic(polytopes.cube())
True

The SEP of a complete graph on \(4\) vertices is a cuboctahedron:

sage: G = graphs.CompleteGraph(4)
sage: P = G.symmetric_edge_polytope(); P
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 12 vertices
sage: P.is_combinatorially_isomorphic(polytopes.cuboctahedron())
True

The SEP of a graph with edges on \(n\) vertices has dimension \(n\) minus the number of connected components:

sage: n = randint(5, 12)
sage: G = Graph()
sage: while not G.num_edges():
....:     G = graphs.RandomGNP(n, 0.2)
sage: P = G.symmetric_edge_polytope()
sage: P.ambient_dim() == n
True
sage: P.dim() == n - G.connected_components_number()
True

The SEP of a graph is isomorphic to the subdirect sum of its connected components SEP’s:

sage: n = randint(3, 6)
sage: G1 = graphs.RandomGNP(n, 0.2)
sage: n = randint(3, 6)
sage: G2 = graphs.RandomGNP(n, 0.2)
sage: G = G1.disjoint_union(G2)
sage: P = G.symmetric_edge_polytope()
sage: P1 = G1.symmetric_edge_polytope()
sage: P2 = G2.symmetric_edge_polytope()
sage: P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))
True

All trees on \(n\) vertices have isomorphic SEPs:

sage: n = randint(4, 10)
sage: G1 = graphs.RandomTree(n)
sage: G2 = graphs.RandomTree(n)
sage: P1 = G1.symmetric_edge_polytope()
sage: P2 = G2.symmetric_edge_polytope()
sage: P1.is_combinatorially_isomorphic(P2)
True

However, there are still many different SEPs:

sage: len(list(graphs(5)))
34
sage: polys = []
sage: for G in graphs(5):
....:     P = G.symmetric_edge_polytope()
....:     for P1 in polys:
....:         if P.is_combinatorially_isomorphic(P1):
....:             break
....:     else:
....:         polys.append(P)
sage: len(polys)
25

A non-trivial example of two graphs with isomorphic SEPs:

sage: G1 = graphs.CycleGraph(4)
sage: G1.add_edges([[0, 5], [5, 2], [1, 6], [6, 2]])
sage: G2 = copy(G1)
sage: G1.add_edges([[2, 7], [7, 3]])
sage: G2.add_edges([[0, 7], [7, 3]])
sage: G1.is_isomorphic(G2)
False
sage: P1 = G1.symmetric_edge_polytope()
sage: P2 = G2.symmetric_edge_polytope()
sage: P1.is_combinatorially_isomorphic(P2)
True

Apparently, glueing two graphs together on a vertex gives isomorphic SEPs:

sage: n = randint(3, 7)
sage: g1 = graphs.RandomGNP(n, 0.2)
sage: g2 = graphs.RandomGNP(n, 0.2)
sage: G = g1.disjoint_union(g2)
sage: H = copy(G)
sage: G.merge_vertices(((0, randrange(n)), (1, randrange(n))))
sage: H.merge_vertices(((0, randrange(n)), (1, randrange(n))))
sage: PG = G.symmetric_edge_polytope()
sage: PH = H.symmetric_edge_polytope()
sage: PG.is_combinatorially_isomorphic(PH)
True

tetrahedron(backend=None)

Return the tetrahedron.

The tetrahedron is a Platonic solid with 4 vertices and 4 faces dual to itself. It can be defined as the convex hull of the 4 vertices \((0, 0, 0)\), \((1, 1, 0)\), \((1, 0, 1)\) and \((0, 1, 1)\). For more information, see the Wikipedia article Tetrahedron.

INPUT:

• backend – the backend to use to create the polytope.

See also

simplex()

EXAMPLES:

sage: co = polytopes.tetrahedron()
sage: co.f_vector()
(1, 4, 6, 4, 1)

Its facets are 4 triangles:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
4

Some more computation:

sage: co.volume()
1/3
sage: co.ehrhart_polynomial()      # optional - latte_int
1/3*t^3 + t^2 + 5/3*t + 1

truncated_cube(exact=True, base_ring=None, backend=None)

Return the truncated cube.

The truncated cube is an Archimedean solid with 24 vertices and 14 faces. It can be defined as the convex hull of the 24 vertices \((\pm x, \pm 1, \pm 1), (\pm 1, \pm x, \pm 1), (\pm 1, \pm 1, \pm x)\) where \(x = \sqrt(2) - 1\). For more information, see the Wikipedia article Truncated_cube.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\sqrt{2}]\) and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.truncated_cube()                                               # optional - sage.rings.number_field
sage: co.f_vector()                                                                 # optional - sage.rings.number_field
(1, 24, 36, 14, 1)

Its facets are 8 triangles and 6 octogons:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)                         # optional - sage.rings.number_field
8
sage: sum(1 for f in co.facets() if len(f.vertices()) == 8)                         # optional - sage.rings.number_field
6

Some more computation:

sage: co.volume()                                                                   # optional - sage.rings.number_field
56/3*sqrt2 - 56/3

truncated_dodecahedron(exact=True, base_ring=None, backend=None)

Return the truncated dodecahedron.

The truncated dodecahedron is an Archimedean solid. It has 32 faces and 60 vertices. For more information, see the Wikipedia article Truncated dodecahedron.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: td = polytopes.truncated_dodecahedron()
sage: td.f_vector()
(1, 60, 90, 32, 1)
sage: td.base_ring()
Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?

Its facets are 20 triangles and 12 regular decagons:

sage: sum(1 for f in td.facets() if len(f.vertices()) == 3)
20
sage: sum(1 for f in td.facets() if len(f.vertices()) == 10)
12

The faster implementation using floating point approximations does not fully work unfortunately, see https://github.com/cddlib/cddlib/pull/7 for a detailed discussion of this case:

sage: td = polytopes.truncated_dodecahedron(exact=False) # random
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
sage: td.f_vector()
Traceback (most recent call last):
...
ValueError: not all vertices are intersections of facets
sage: td.base_ring()
Real Double Field

truncated_icosidodecahedron(exact=True, base_ring=None, backend=None)

Return the truncated icosidodecahedron.

The truncated icosidodecahedron is an Archimedean solid. It has 62 faces and 120 vertices. For more information, see the Wikipedia article Truncated_icosidodecahedron.

INPUT:

• exact – (boolean, default True) If False use an approximate ring for the coordinates.

• base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: ti = polytopes.truncated_icosidodecahedron()   # long time
sage: ti.f_vector()                # long time
(1, 120, 180, 62, 1)
sage: ti.base_ring()               # long time
Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?

The implementation using floating point approximations is much faster:

sage: ti = polytopes.truncated_icosidodecahedron(exact=False) # random
sage: ti.f_vector()
(1, 120, 180, 62, 1)
sage: ti.base_ring()
Real Double Field

Its facets are 30 squares, 20 hexagons and 12 decagons:

sage: sum(1 for f in ti.facets() if len(f.vertices()) == 4)
30
sage: sum(1 for f in ti.facets() if len(f.vertices()) == 6)
20
sage: sum(1 for f in ti.facets() if len(f.vertices()) == 10)
12

truncated_octahedron(backend=None)

Return the truncated octahedron.

The truncated octahedron is an Archimedean solid with 24 vertices and 14 faces. It can be defined as the convex hull off all the permutations of \((0, \pm 1, \pm 2)\). For more information, see the Wikipedia article Truncated_octahedron.

This is also known as the permutohedron of dimension 3.

INPUT:

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.truncated_octahedron()
sage: co.f_vector()
(1, 24, 36, 14, 1)

Its facets are 6 squares and 8 hexagons:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 4)
6
sage: sum(1 for f in co.facets() if len(f.vertices()) == 6)
8

Some more computation:

sage: co.volume()
32
sage: co.ehrhart_polynomial()      # optional - latte_int
32*t^3 + 18*t^2 + 6*t + 1

truncated_one_hundred_twenty_cell(exact=True, backend=None)

Return the truncated 120-cell.

The truncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 2400 vertices. For more information see Wikipedia article Truncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

• exact - (boolean, default True) if True use exact coordinates instead of floating point approximations.

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.truncated_one_hundred_twenty_cell(backend='normaliz') # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 2400 vertices

truncated_six_hundred_cell(exact=False, backend=None)

Return the truncated 600-cell.

The truncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 1440 vertices. For more information see Wikipedia article Truncated 600-cell.

Warning

The coordinates are not exact by default. The computation with exact coordinates takes a huge amount of time.

INPUT:

• exact - (boolean, default False) if True use exact coordinates instead of floating point approximations

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.truncated_six_hundred_cell() # not tested - long time
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 1440 vertices

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.truncated_six_hundred_cell(exact=True,backend='normaliz') # not tested - long time ~16sec
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 1440 vertices

truncated_tetrahedron(backend=None)

Return the truncated tetrahedron.

The truncated tetrahedron is an Archimedean solid with 12 vertices and 8 faces. It can be defined as the convex hull off all the permutations of \((\pm 1, \pm 1, \pm 3)\) with an even number of minus signs. For more information, see the Wikipedia article Truncated_tetrahedron.

INPUT:

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.truncated_tetrahedron()
sage: co.f_vector()
(1, 12, 18, 8, 1)

Its facets are 4 triangles and 4 hexagons:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
4
sage: sum(1 for f in co.facets() if len(f.vertices()) == 6)
4

Some more computation:

sage: co.volume()
184/3
sage: co.ehrhart_polynomial()      # optional - latte_int
184/3*t^3 + 28*t^2 + 26/3*t + 1

twenty_four_cell(backend=None)

Return the standard 24-cell polytope.

The 24-cell polyhedron (also called icositetrachoron or octaplex) is a regular polyhedron in 4-dimension. For more information see the Wikipedia article 24-cell.

INPUT:

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: p24 = polytopes.twenty_four_cell()
sage: p24.f_vector()
(1, 24, 96, 96, 24, 1)
sage: v = next(p24.vertex_generator())
sage: for adj in v.neighbors(): print(adj)
A vertex at (-1/2, -1/2, -1/2, 1/2)
A vertex at (-1/2, -1/2, 1/2, -1/2)
A vertex at (-1, 0, 0, 0)
A vertex at (-1/2, 1/2, -1/2, -1/2)
A vertex at (0, -1, 0, 0)
A vertex at (0, 0, -1, 0)
A vertex at (0, 0, 0, -1)
A vertex at (1/2, -1/2, -1/2, -1/2)

sage: p24.volume()
2

zonotope(generators, backend=None)

Return the zonotope, or parallelotope, spanned by the generators.

The parallelotope is the multi-dimensional generalization of a parallelogram (2 generators) and a parallelepiped (3 generators).

INPUT:

• generators – a list of vectors of same dimension

• backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.parallelotope([ (1,0), (0,1) ])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: polytopes.parallelotope([[1,2,3,4],[0,1,0,7],[3,1,0,2],[0,0,1,0]])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices

sage: K = QuadraticField(2, 'sqrt2')
sage: sqrt2 = K.gen()
sage: P = polytopes.parallelotope([ (1,sqrt2), (1,-1) ]); P
A 2-dimensional polyhedron in (Number Field in sqrt2 with defining
polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^2 defined as
the convex hull of 4 vertices

sage.geometry.polyhedron.library.gale_transform_to_polytope(vectors, base_ring=None, backend=None)

Return the polytope associated to the list of vectors forming a Gale transform.

This function is the inverse of gale_transform() up to projective transformation.

INPUT:

• vectors – the vectors of the Gale transform

• base_ring – string (default: \(None\)); the base ring to be used for the construction

• backend – string (default: \(None\)); the backend to use to create the polytope

Note

The order of the input vectors will not be preserved.

If the center of the (input) vectors is the origin, the function is much faster and might give a nicer representation of the polytope.

If this is not the case, the vectors will be scaled (each by a positive scalar) accordingly to obtain the polytope.

See also

:func`~sage.geometry.polyhedron.library.gale_transform_to_primal`.

EXAMPLES:

sage: from sage.geometry.polyhedron.library import gale_transform_to_polytope
sage: points = polytopes.octahedron().gale_transform()
sage: points
((0, -1), (-1, 0), (1, 1), (1, 1), (-1, 0), (0, -1))
sage: P = gale_transform_to_polytope(points); P
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices
sage: P.vertices()
(A vertex at (-1, 0, 0),
 A vertex at (0, -1, 0),
 A vertex at (0, 0, -1),
 A vertex at (0, 0, 1),
 A vertex at (0, 1, 0),
 A vertex at (1, 0, 0))

One can specify the base ring:

sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)]).vertices()
(A vertex at (-25, 0, 0),
 A vertex at (-15, 50, -60),
 A vertex at (0, -25, 0),
 A vertex at (0, 0, -25),
 A vertex at (16, -35, 54),
 A vertex at (24, 10, 31))
sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)],
....:     base_ring=RDF).vertices()
(A vertex at (-0.64, 1.4, -2.16),
 A vertex at (-0.96, -0.4, -1.24),
 A vertex at (0.6, -2.0, 2.4),
 A vertex at (1.0, 0.0, 0.0),
 A vertex at (0.0, 1.0, 0.0),
 A vertex at (0.0, 0.0, 1.0))

One can also specify the backend:

sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)],
....:     backend='field').backend()
'field'
sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)],
....:     backend='cdd', base_ring=RDF).backend()
'cdd'

A gale transform corresponds to a polytope if and only if every oriented (linear) hyperplane has at least two vectors on each side. See Theorem 6.19 of [Zie2007]. If this is not the case, one of two errors is raised.

If there is such a hyperplane with no vector on one side, the vectors are not totally cyclic:

sage: gale_transform_to_polytope([(0,1), (1,1), (1,0), (-1,0)])
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic

If every hyperplane has at least one vector on each side, then the gale transform corresponds to a point configuration. It corresponds to a polytope if and only if this point configuration is convex and if and only if every hyperplane contains at least two vectors of the gale transform on each side.

If this is not the case, an error is raised:

sage: gale_transform_to_polytope([(0,1), (1,1), (1,0), (-1,-1)])
Traceback (most recent call last):
...
ValueError: the gale transform does not correspond to a polytope

sage.geometry.polyhedron.library.gale_transform_to_primal(vectors, base_ring=None, backend=None)

Return a point configuration dual to a totally cyclic vector configuration.

This is the dehomogenized vector configuration dual to the input. The dual vector configuration is acyclic and can therefore be dehomogenized as the input is totally cyclic.

INPUT:

• vectors – the ordered vectors of the Gale transform

• base_ring – string (default: \(None\)); the base ring to be used for the construction

• backend – string (default: \(None\)); the backend to be use to construct a polyhedral, used internally in case the center is not the origin, see Polyhedron()

OUTPUT: An ordered point configuration as list of vectors.

Note

If the center of the (input) vectors is the origin, the function is much faster and might give a nicer representation of the point configuration.

If this is not the case, the vectors will be scaled (each by a positive scalar) accordingly.

ALGORITHM:

Step 1: If the center of the (input) vectors is not the origin, we do an appropriate transformation to make it so.

Step 2: We add a row of ones on top of Matrix(vectors). The right kernel of this larger matrix is the dual configuration space, and a basis of this space provides the dual point configuration.

More concretely, the dual vector configuration (inhomogeneous) is obtained by taking a basis of the right kernel of Matrix(vectors). If the center of the (input) vectors is the origin, there exists a basis of the right kernel of the form [[1], [V]], where [1] represents a row of ones. Then, V is a dehomogenization and thus the dual point configuration.

To extend [1] to a basis of Matrix(vectors), we add a row of ones to Matrix(vectors) and calculate a basis of the right kernel of the obtained matrix.

REFERENCES:

For more information, see Section 6.4 of [Zie2007] or Definition 2.5.1 and Definition 4.1.35 of [DLRS2010].

See also

:func`~sage.geometry.polyhedron.library.gale_transform_to_polytope`.

EXAMPLES:

sage: from sage.geometry.polyhedron.library import gale_transform_to_primal
sage: points = ((0, -1), (-1, 0), (1, 1), (1, 1), (-1, 0), (0, -1))
sage: gale_transform_to_primal(points)
[(0, 0, 1), (0, 1, 0), (1, 0, 0), (-1, 0, 0), (0, -1, 0), (0, 0, -1)]

One can specify the base ring:

sage: p = [(1,1), (-1,-1), (1,0), (-1,0), (1,-1), (-2,1)]
sage: gtpp = gale_transform_to_primal(p); gtpp
[(16, -35, 54),
 (24, 10, 31),
 (-15, 50, -60),
 (-25, 0, 0),
 (0, -25, 0),
 (0, 0, -25)]
sage: (matrix(RDF, gtpp)/25 +
....:  matrix(gale_transform_to_primal(p, base_ring=RDF))).norm() < 1e-15
True

One can also specify the backend to be used internally:

sage: gale_transform_to_primal(p, backend='field')
[(48, -71, 88),
 (84, -28, 99),
 (-77, 154, -132),
 (-55, 0, 0),
 (0, -55, 0),
 (0, 0, -55)]
sage: gale_transform_to_primal(p, backend='normaliz') # optional - pynormaliz
[(16, -35, 54),
 (24, 10, 31),
 (-15, 50, -60),
 (-25, 0, 0),
 (0, -25, 0),
 (0, 0, -25)]

The input vectors should be totally cyclic:

sage: gale_transform_to_primal([(0,1), (1,0), (1,1), (-1,0)])
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic

sage: gale_transform_to_primal(
....:     [(1,1,0), (-1,-1,0), (1,0,0),
....:      (-1,0,0), (1,-1,0), (-2,1,0)], backend='field')
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic

sage.geometry.polyhedron.library.project_points(*points, **kwds)

Projects a set of points into a vector space of dimension one less.

INPUT:

• points… – the points to project.

• base_ring – (defaults to RDF if keyword is None or not provided in kwds) the base ring to use.

The projection is isometric to the orthogonal projection on the hyperplane made of zero sum vector. Hence, if the set of points have all equal sums, then their projection is isometric (as a set of points).

The projection used is the matrix given by zero_sum_projection().

EXAMPLES:

sage: from sage.geometry.polyhedron.library import project_points
sage: project_points([2,-1,3,2])          # abs tol 1e-15
[(2.1213203435596424, -2.041241452319315, -0.577350269189626)]
sage: project_points([1,2,3],[3,3,5])     # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892), (0.0, -1.6329931618554523)]

These projections are compatible with the restriction. More precisely, given a vector \(v\), the projection of \(v\) restricted to the first \(i\) coordinates will be equal to the projection of the first \(i+1\) coordinates of \(v\):

sage: project_points([1,2])    # abs tol 1e-15
[(-0.7071067811865475)]
sage: project_points([1,2,3])  # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892)]
sage: project_points([1,2,3,4])     # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892, -1.7320508075688776)]
sage: project_points([1,2,3,4,0])   # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892, -1.7320508075688776, 2.23606797749979)]

Check that it is (almost) an isometry:

sage: V = list(map(vector, IntegerVectors(n=5, length=3)))              # optional - sage.combinat
sage: P = project_points(*V)                                            # optional - sage.combinat
sage: for i in range(21):                                               # optional - sage.combinat
....:     for j in range(21):
....:         assert abs((V[i]-V[j]).norm() - (P[i]-P[j]).norm()) < 0.00001

Example with exact computation:

sage: V = [ vector(v) for v in IntegerVectors(n=4, length=2) ]          # optional - sage.combinat
sage: P = project_points(*V, base_ring=AA)                              # optional - sage.combinat sage.rings.number_field
sage: for i in range(len(V)):                                           # optional - sage.combinat sage.rings.number_field
....:     for j in range(len(V)):
....:         assert (V[i]-V[j]).norm() == (P[i]-P[j]).norm()

sage.geometry.polyhedron.library.zero_sum_projection(d, base_ring=None)

Return a matrix corresponding to the projection on the orthogonal of \((1,1,\ldots,1)\) in dimension \(d\).

The projection maps the orthonormal basis \((1,-1,0,\ldots,0) / \sqrt(2)\), \((1,1,-1,0,\ldots,0) / \sqrt(3)\), ldots, \((1,1,\ldots,1,-1) / \sqrt(d)\) to the canonical basis in \(\RR^{d-1}\).

OUTPUT:

A matrix of dimensions \((d-1)\times d\) defined over base_ring (default: RDF).

EXAMPLES:

sage: from sage.geometry.polyhedron.library import zero_sum_projection
sage: zero_sum_projection(2)
[ 0.7071067811865475 -0.7071067811865475]
sage: zero_sum_projection(3)
[ 0.7071067811865475 -0.7071067811865475                 0.0]
[ 0.4082482904638631  0.4082482904638631 -0.8164965809277261]

Exact computation in AA:

sage: zero_sum_projection(3, base_ring=AA)                              # optional - sage.rings.number_field
[ 0.7071067811865475? -0.7071067811865475?                    0]
[ 0.4082482904638630?  0.4082482904638630? -0.8164965809277260?]