Base class for polyhedra¶
-
class
sage.geometry.polyhedron.base.
Polyhedron_base
(parent, Vrep, Hrep, **kwds)¶ Bases:
sage.structure.element.Element
Base class for Polyhedron objects
INPUT:
parent
– the parent, an instance ofPolyhedra
.Vrep
– a list[vertices, rays, lines]
orNone
. The V-representation of the polyhedron. IfNone
, the polyhedron is determined by the H-representation.Hrep
– a list[ieqs, eqns]
orNone
. The H-representation of the polyhedron. IfNone
, the polyhedron is determined by the V-representation.
Only one of
Vrep
orHrep
can be different fromNone
.TESTS:
sage: p = Polyhedron() sage: TestSuite(p).run()
-
Hrep_generator
()¶ Return an iterator over the objects of the H-representation (inequalities or equations).
EXAMPLES:
sage: p = polytopes.hypercube(3) sage: next(p.Hrep_generator()) An inequality (0, 0, -1) x + 1 >= 0
-
Hrepresentation
(index=None)¶ Return the objects of the H-representation. Each entry is either an inequality or a equation.
INPUT:
index
– either an integer orNone
.
OUTPUT:
The optional argument is an index running from
0
toself.n_Hrepresentation()-1
. If present, the H-representation object at the given index will be returned. Without an argument, returns the list of all H-representation objects.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p.Hrepresentation(0) An inequality (0, 0, -1) x + 1 >= 0 sage: p.Hrepresentation(0) == p.Hrepresentation() [0] True
-
Hrepresentation_space
()¶ Return the linear space containing the H-representation vectors.
OUTPUT:
A free module over the base ring of dimension
ambient_dim()
+ 1.EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]]) sage: poly_test.Hrepresentation_space() Ambient free module of rank 5 over the principal ideal domain Integer Ring
-
Minkowski_difference
(other)¶ Return the Minkowski difference.
Minkowski subtraction can equivalently be defined via Minkowski addition (see
Minkowski_sum()
) or as set-theoretic intersection via\[X \ominus Y = (X^c \oplus Y)^c = \cap_{y\in Y} (X-y)\]where superscript-“c” means the complement in the ambient vector space. The Minkowski difference of convex sets is convex, and the difference of polyhedra is again a polyhedron. We only consider the case of polyhedra in the following. Note that it is not quite the inverse of addition. In fact:
- \((X+Y)-Y = X\) for any polyhedra \(X\), \(Y\).
- \((X-Y)+Y \subseteq X\)
- \((X-Y)+Y = X\) if and only if Y is a Minkowski summand of X.
INPUT:
other
– aPolyhedron_base
.
OUTPUT:
The Minkowski difference of
self
andother
. Also known as Minkowski subtraction ofother
fromself
.EXAMPLES:
sage: X = polytopes.hypercube(3) sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1), (0,1,0), (1,0,0)]) / 2 sage: (X+Y)-Y == X True sage: (X-Y)+Y < X True
The polyhedra need not be full-dimensional:
sage: X2 = Polyhedron(vertices=[(-1,-1,0),(1,-1,0),(-1,1,0),(1,1,0)]) sage: Y2 = Polyhedron(vertices=[(0,0,0), (0,1,0), (1,0,0)]) / 2 sage: (X2+Y2)-Y2 == X2 True sage: (X2-Y2)+Y2 < X2 True
Minus sign is really an alias for
Minkowski_difference()
sage: four_cube = polytopes.hypercube(4) sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]]) sage: four_cube - four_simplex A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices sage: four_cube.Minkowski_difference(four_simplex) == four_cube - four_simplex True
Coercion of the base ring works:
sage: poly_spam = Polyhedron([[3,4,5,2],[1,0,0,1],[0,0,0,0],[0,4,3,2],[-3,-3,-3,-3]], base_ring=ZZ) sage: poly_eggs = Polyhedron([[5,4,5,4],[-4,5,-4,5],[4,-5,4,-5],[0,0,0,0]], base_ring=QQ) / 100 sage: poly_spam - poly_eggs A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 5 vertices
TESTS:
sage: X = polytopes.hypercube(2) sage: Y = Polyhedron(vertices=[(1,1)]) sage: (X-Y).Vrepresentation() (A vertex at (0, -2), A vertex at (0, 0), A vertex at (-2, 0), A vertex at (-2, -2)) sage: Y = Polyhedron(vertices=[(1,1), (0,0)]) sage: (X-Y).Vrepresentation() (A vertex at (0, -1), A vertex at (0, 0), A vertex at (-1, 0), A vertex at (-1, -1)) sage: X = X + Y # now Y is a Minkowski summand of X sage: (X+Y)-Y == X True sage: (X-Y)+Y == X True
-
Minkowski_sum
(other)¶ Return the Minkowski sum.
Minkowski addition of two subsets of a vector space is defined as
\[X \oplus Y = \cup_{y\in Y} (X+y) = \cup_{x\in X, y\in Y} (x+y)\]See
Minkowski_difference()
for a partial inverse operation.INPUT:
other
– aPolyhedron_base
.
OUTPUT:
The Minkowski sum of
self
andother
.EXAMPLES:
sage: X = polytopes.hypercube(3) sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1/2), (0,1/2,0), (1/2,0,0)]) sage: X+Y A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 13 vertices sage: four_cube = polytopes.hypercube(4) sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]]) sage: four_cube + four_simplex A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 36 vertices sage: four_cube.Minkowski_sum(four_simplex) == four_cube + four_simplex True sage: poly_spam = Polyhedron([[3,4,5,2],[1,0,0,1],[0,0,0,0],[0,4,3,2],[-3,-3,-3,-3]], base_ring=ZZ) sage: poly_eggs = Polyhedron([[5,4,5,4],[-4,5,-4,5],[4,-5,4,-5],[0,0,0,0]], base_ring=QQ) sage: poly_spam + poly_spam + poly_eggs A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 12 vertices
-
Vrep_generator
()¶ Returns an iterator over the objects of the V-representation (vertices, rays, and lines).
EXAMPLES:
sage: p = polytopes.cyclic_polytope(3,4) sage: vg = p.Vrep_generator() sage: next(vg) A vertex at (0, 0, 0) sage: next(vg) A vertex at (1, 1, 1)
-
Vrepresentation
(index=None)¶ Return the objects of the V-representation. Each entry is either a vertex, a ray, or a line.
See
sage.geometry.polyhedron.constructor
for a definition of vertex/ray/line.INPUT:
index
– either an integer orNone
.
OUTPUT:
The optional argument is an index running from
0
to \(self.n_Vrepresentation()-1`\). If present, the V-representation object at the given index will be returned. Without an argument, returns the list of all V-representation objects.EXAMPLES:
sage: p = polytopes.simplex(4, project=True) sage: p.Vrepresentation(0) A vertex at (0.7071067812, 0.4082482905, 0.2886751346, 0.2236067977) sage: p.Vrepresentation(0) == p.Vrepresentation() [0] True
-
Vrepresentation_space
()¶ Return the ambient vector space.
OUTPUT:
A free module over the base ring of dimension
ambient_dim()
.EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]]) sage: poly_test.Vrepresentation_space() Ambient free module of rank 4 over the principal ideal domain Integer Ring sage: poly_test.ambient_space() is poly_test.Vrepresentation_space() True
-
adjacency_matrix
()¶ Return the binary matrix of vertex adjacencies.
EXAMPLES:
sage: polytopes.simplex(4).vertex_adjacency_matrix() [0 1 1 1 1] [1 0 1 1 1] [1 1 0 1 1] [1 1 1 0 1] [1 1 1 1 0]
The rows and columns of the vertex adjacency matrix correspond to the
Vrepresentation()
objects: vertices, rays, and lines. The \((i,j)\) matrix entry equals \(1\) if the \(i\)-th and \(j\)-th V-representation object are adjacent.Two vertices are adjacent if they are the endpoints of an edge, that is, a one-dimensional face. For unbounded polyhedra this clearly needs to be generalized and we define two V-representation objects (see
sage.geometry.polyhedron.constructor
) to be adjacent if they together generate a one-face. There are three possible combinations:- Two vertices can bound a finite-length edge.
- A vertex and a ray can generate a half-infinite edge starting at the vertex and with the direction given by the ray.
- A vertex and a line can generate an infinite edge. The position of the vertex on the line is arbitrary in this case, only its transverse position matters. The direction of the edge is given by the line generator.
For example, take the half-plane:
sage: half_plane = Polyhedron(ieqs=[(0,1,0)]) sage: half_plane.Hrepresentation() (An inequality (1, 0) x + 0 >= 0,)
Its (non-unique) V-representation consists of a vertex, a ray, and a line. The only edge is spanned by the vertex and the line generator, so they are adjacent:
sage: half_plane.Vrepresentation() (A line in the direction (0, 1), A ray in the direction (1, 0), A vertex at (0, 0)) sage: half_plane.vertex_adjacency_matrix() [0 0 1] [0 0 0] [1 0 0]
In one dimension higher, that is for a half-space in 3 dimensions, there is no one-dimensional face. Hence nothing is adjacent:
sage: Polyhedron(ieqs=[(0,1,0,0)]).vertex_adjacency_matrix() [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
EXAMPLES:
In a bounded polygon, every vertex has precisely two adjacent ones:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(P.adjacency_matrix().row(v.index()), v)) (0, 1, 0, 1) A vertex at (0, 1) (1, 0, 1, 0) A vertex at (1, 0) (0, 1, 0, 1) A vertex at (3, 0) (1, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)], ....: rays=[(0,1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(P.adjacency_matrix().row(v.index()), v)) (0, 1, 0, 0, 1) A ray in the direction (0, 1) (1, 0, 1, 0, 0) A vertex at (0, 1) (0, 1, 0, 1, 0) A vertex at (1, 0) (0, 0, 1, 0, 1) A vertex at (3, 0) (1, 0, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two V-representation objects (which can now be vertices or rays). The two rays are not adjacent to each other:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)], ....: rays=[(0,1), (1,1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(P.adjacency_matrix().row(v.index()), v)) (0, 1, 0, 0, 0) A ray in the direction (0, 1) (1, 0, 1, 0, 0) A vertex at (0, 1) (0, 1, 0, 0, 1) A vertex at (1, 0) (0, 0, 0, 0, 1) A ray in the direction (1, 1) (0, 0, 1, 1, 0) A vertex at (3, 0)
-
affine_hull
()¶ Return the affine hull.
Each polyhedron is contained in some smallest affine subspace (possibly the entire ambient space). The affine hull is the same polyhedron but thought of as a full-dimensional polyhedron in this subspace.
OUTPUT:
A full-dimensional polyhedron.
EXAMPLES:
sage: triangle = Polyhedron([(1,0,0), (0,1,0), (0,0,1)]); triangle A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices sage: triangle.affine_hull() A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: half3d = Polyhedron(vertices=[(3,2,1)], rays=[(1,0,0)]) sage: half3d.affine_hull().Vrepresentation() (A ray in the direction (1), A vertex at (3))
TESTS:
sage: Polyhedron([(2,3,4)]).affine_hull() A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex
-
ambient_dim
()¶ Return the dimension of the ambient space.
EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]]) sage: poly_test.ambient_dim() 4
-
ambient_space
()¶ Return the ambient vector space.
OUTPUT:
A free module over the base ring of dimension
ambient_dim()
.EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]]) sage: poly_test.Vrepresentation_space() Ambient free module of rank 4 over the principal ideal domain Integer Ring sage: poly_test.ambient_space() is poly_test.Vrepresentation_space() True
-
barycentric_subdivision
(subdivision_frac=None)¶ Return the barycentric subdivision of a compact polyhedron.
DEFINITION:
The barycentric subdivision of a compact polyhedron is a standard way to triangulate its faces in such a way that maximal faces correspond to flags of faces of the starting polyhedron (i.e. a maximal chain in the face lattice of the polyhedron). As a simplicial complex, this is known as the order complex of the face lattice of the polyhedron.
REFERENCE:
See Wikipedia article Barycentric_subdivision Section 6.6, Handbook of Convex Geometry, Volume A, edited by P.M. Gruber and J.M. Wills. 1993, North-Holland Publishing Co..
INPUT:
subdivision_frac
– number. Gives the proportion how far the new vertices are pulled out of the polytope. Default is \(\frac{1}{3}\) and the value should be smaller than \(\frac{1}{2}\). The subdivision is computed on the polar polyhedron.
OUTPUT:
A Polyhedron object, subdivided as described above.
EXAMPLES:
sage: P = polytopes.hypercube(3) sage: P.barycentric_subdivision() A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 26 vertices sage: P = Polyhedron(vertices=[[0,0,0],[0,1,0],[1,0,0],[0,0,1]]) sage: P.barycentric_subdivision() A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 14 vertices sage: P = Polyhedron(vertices=[[0,1,0],[0,0,1],[1,0,0]]) sage: P.barycentric_subdivision() A 2-dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices sage: P = polytopes.regular_polygon(4, base_ring=QQ) sage: P.barycentric_subdivision() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 8 vertices
TESTS:
sage: P.barycentric_subdivision(1/2) Traceback (most recent call last): ... ValueError: The subdivision fraction should be between 0 and 1/2. sage: P = Polyhedron(ieqs=[[1,0,1],[0,1,0],[1,0,0],[0,0,1]]) sage: P.barycentric_subdivision() Traceback (most recent call last): ... ValueError: The polytope has to be compact. sage: P = Polyhedron(vertices=[[0,0,0],[0,1,0],[1,0,0],[0,0,1]], backend='field') sage: P.barycentric_subdivision() A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 14 vertices
-
base_extend
(base_ring, backend=None)¶ Return a new polyhedron over a larger field.
INPUT:
base_ring
– the new base ring.backend
– the new backend, seePolyhedron()
.
OUTPUT:
The same polyhedron, but over a larger base ring.
EXAMPLES:
sage: P = Polyhedron(vertices=[(1,0), (0,1)], rays=[(1,1)], base_ring=ZZ); P A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices and 1 ray sage: P.base_extend(QQ) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray sage: P.base_extend(QQ) == P True
-
base_ring
()¶ Return the base ring.
OUTPUT:
The ring over which the polyhedron is defined. Must be a sub-ring of the reals to define a polyhedron, in particular comparison must be defined. Popular choices are
ZZ
(the ring of integers, lattice polytope),QQ
(exact arithmetic using gmp),RDF
(double precision floating-point arithmetic), orAA
(real algebraic field).
EXAMPLES:
sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]]) sage: triangle.base_ring() == ZZ True
-
bipyramid
()¶ Return a polyhedron that is a bipyramid over the original.
EXAMPLES:
sage: octahedron = polytopes.cross_polytope(3) sage: cross_poly_4d = octahedron.bipyramid() sage: cross_poly_4d.n_vertices() 8 sage: q = [list(v) for v in cross_poly_4d.vertex_generator()] sage: q [[-1, 0, 0, 0], [0, -1, 0, 0], [0, 0, -1, 0], [0, 0, 0, -1], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]]
Now check that bipyramids of cross-polytopes are cross-polytopes:
sage: q2 = [list(v) for v in polytopes.cross_polytope(4).vertex_generator()] sage: [v in q2 for v in q] [True, True, True, True, True, True, True, True]
-
bounded_edges
()¶ Return the bounded edges (excluding rays and lines).
OUTPUT:
A generator for pairs of vertices, one pair per edge.
EXAMPLES:
sage: p = Polyhedron(vertices=[[1,0],[0,1]], rays=[[1,0],[0,1]]) sage: [ e for e in p.bounded_edges() ] [(A vertex at (0, 1), A vertex at (1, 0))] sage: for e in p.bounded_edges(): print(e) (A vertex at (0, 1), A vertex at (1, 0))
-
bounding_box
(integral=False)¶ Return the coordinates of a rectangular box containing the non-empty polytope.
INPUT:
integral
– Boolean (default:False
). Whether to only allow integral coordinates in the bounding box.
OUTPUT:
A pair of tuples
(box_min, box_max)
wherebox_min
are the coordinates of a point bounding the coordinates of the polytope from below andbox_max
bounds the coordinates from above.EXAMPLES:
sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box() ((1/3, 1/3), (2/3, 2/3)) sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box(integral=True) ((0, 0), (1, 1)) sage: polytopes.buckyball(exact=False).bounding_box() ((-0.8090169944, -0.8090169944, -0.8090169944), (0.8090169944, 0.8090169944, 0.8090169944))
-
cdd_Hrepresentation
()¶ Write the inequalities/equations data of the polyhedron in cdd’s H-representation format.
See also
write_cdd_Hrepresentation()
– export the polyhedron as a H-representation to a file.OUTPUT: a string
EXAMPLES:
sage: p = polytopes.hypercube(2) sage: print(p.cdd_Hrepresentation()) H-representation begin 4 3 rational 1 1 0 1 0 1 1 -1 0 1 0 -1 end sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]],base_ring=AA) sage: triangle.base_ring() Algebraic Real Field sage: triangle.cdd_Hrepresentation() Traceback (most recent call last): ... TypeError: The base ring must be ZZ, QQ, or RDF
-
cdd_Vrepresentation
()¶ Write the vertices/rays/lines data of the polyhedron in cdd’s V-representation format.
See also
write_cdd_Vrepresentation()
– export the polyhedron as a V-representation to a file.OUTPUT: a string
EXAMPLES:
sage: q = Polyhedron(vertices = [[1,1],[0,0],[1,0],[0,1]]) sage: print(q.cdd_Vrepresentation()) V-representation begin 4 3 rational 1 0 0 1 0 1 1 1 0 1 1 1 end
-
center
()¶ Return the average of the vertices.
See also
representative_point()
.OUTPUT:
The center of the polyhedron. All rays and lines are ignored. Raises a
ZeroDivisionError
for the empty polytope.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p = p + vector([1,0,0]) sage: p.center() (1, 0, 0)
-
combinatorial_automorphism_group
()¶ Computes the combinatorial automorphism group of the vertex graph of the polyhedron.
OUTPUT:
A
PermutationGroup
that is isomorphic to the combinatorial automorphism group is returned.Note that in Sage, permutation groups always act on positive integers while
self.Vrepresentation()
is indexed by nonnegative integers. The indexing of the permutation group is chosen to be shifted by+1
. That is,i
in the permutation group corresponds to the V-representation objectself.Vrepresentation(i-1)
.EXAMPLES:
sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)]) sage: quadrangle.combinatorial_automorphism_group() Permutation Group with generators [(2,3), (1,2)(3,4)] sage: quadrangle.restricted_automorphism_group() Permutation Group with generators [()]
Permutations can only exchange vertices with vertices, rays with rays, and lines with lines:
sage: P = Polyhedron(vertices=[(1,0,0), (1,1,0)], rays=[(1,0,0)], lines=[(0,0,1)]) sage: P.combinatorial_automorphism_group() Permutation Group with generators [(3,4)]
-
contains
(point)¶ Test whether the polyhedron contains the given
point
.See also
interior_contains()
andrelative_interior_contains()
.INPUT:
point
– coordinates of a point (an iterable).
OUTPUT:
Boolean.
EXAMPLES:
sage: P = Polyhedron(vertices=[[1,1],[1,-1],[0,0]]) sage: P.contains( [1,0] ) True sage: P.contains( P.center() ) # true for any convex set True
As a shorthand, one may use the usual
in
operator:sage: P.center() in P True sage: [-1,-1] in P False
The point need not have coordinates in the same field as the polyhedron:
sage: ray = Polyhedron(vertices=[(0,0)], rays=[(1,0)], base_ring=QQ) sage: ray.contains([sqrt(2)/3,0]) # irrational coordinates are ok True sage: a = var('a') sage: ray.contains([a,0]) # a might be negative! False sage: assume(a>0) sage: ray.contains([a,0]) True sage: ray.contains(['hello', 'kitty']) # no common ring for coordinates False
The empty polyhedron needs extra care, see trac ticket #10238:
sage: empty = Polyhedron(); empty The empty polyhedron in ZZ^0 sage: empty.contains([]) False sage: empty.contains([0]) # not a point in QQ^0 False sage: full = Polyhedron(vertices=[()]); full A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex sage: full.contains([]) True sage: full.contains([0]) False
-
convex_hull
(other)¶ Return the convex hull of the set-theoretic union of the two polyhedra.
INPUT:
other
– aPolyhedron
.
OUTPUT:
The convex hull.
EXAMPLES:
sage: a_simplex = polytopes.simplex(3, project=True) sage: verts = a_simplex.vertices() sage: verts = [[x[0]*3/5+x[1]*4/5, -x[0]*4/5+x[1]*3/5, x[2]] for x in verts] sage: another_simplex = Polyhedron(vertices = verts) sage: simplex_union = a_simplex.convex_hull(another_simplex) sage: simplex_union.n_vertices() 7
-
dilation
(scalar)¶ Return the dilated (uniformly stretched) polyhedron.
INPUT:
scalar
– A scalar, not necessarily inbase_ring()
.
OUTPUT:
The polyhedron dilated by that scalar, possibly coerced to a bigger field.
EXAMPLES:
sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in srange(2,6)]) sage: next(p.vertex_generator()) A vertex at (2, 4, 8) sage: p2 = p.dilation(2) sage: next(p2.vertex_generator()) A vertex at (4, 8, 16) sage: p.dilation(2) == p * 2 True
TESTS:
Dilation of empty polyhedrons works, see trac ticket #14987:
sage: p = Polyhedron(ambient_dim=2); p The empty polyhedron in ZZ^2 sage: p.dilation(3) The empty polyhedron in ZZ^2 sage: p = Polyhedron(vertices=[(1,1)], rays=[(1,0)], lines=[(0,1)]) sage: (-p).rays() (A ray in the direction (-1, 0),) sage: (-p).lines() (A line in the direction (0, 1),) sage: (0*p).rays() () sage: (0*p).lines() ()
-
dim
()¶ Return the dimension of the polyhedron.
OUTPUT:
-1 if the polyhedron is empty, otherwise a non-negative integer.
EXAMPLES:
sage: simplex = Polyhedron(vertices = [[1,0,0,0],[0,0,0,1],[0,1,0,0],[0,0,1,0]]) sage: simplex.dim() 3 sage: simplex.ambient_dim() 4
The empty set is a special case (trac ticket #12193):
sage: P1=Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]]) sage: P2=Polyhedron(vertices=[[2,0,0],[0,2,0],[0,0,2]]) sage: P12 = P1.intersection(P2) sage: P12 The empty polyhedron in ZZ^3 sage: P12.dim() -1
-
dimension
()¶ Return the dimension of the polyhedron.
OUTPUT:
-1 if the polyhedron is empty, otherwise a non-negative integer.
EXAMPLES:
sage: simplex = Polyhedron(vertices = [[1,0,0,0],[0,0,0,1],[0,1,0,0],[0,0,1,0]]) sage: simplex.dim() 3 sage: simplex.ambient_dim() 4
The empty set is a special case (trac ticket #12193):
sage: P1=Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]]) sage: P2=Polyhedron(vertices=[[2,0,0],[0,2,0],[0,0,2]]) sage: P12 = P1.intersection(P2) sage: P12 The empty polyhedron in ZZ^3 sage: P12.dim() -1
-
edge_truncation
(cut_frac=None)¶ Return a new polyhedron formed from two points on each edge between two vertices.
INPUT:
cut_frac
– integer. how deeply to cut into the edge.- Default is \(\frac{1}{3}\).
OUTPUT:
A Polyhedron object, truncated as described above.
EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: trunc_cube = cube.edge_truncation() sage: trunc_cube.n_vertices() 24 sage: trunc_cube.n_inequalities() 14
-
equation_generator
()¶ Return a generator for the linear equations satisfied by the polyhedron.
EXAMPLES:
sage: p = polytopes.regular_polygon(8,base_ring=RDF) sage: p3 = Polyhedron(vertices = [x+[0] for x in p.vertices()], base_ring=RDF) sage: next(p3.equation_generator()) An equation (0.0, 0.0, 1.0) x + 0.0 == 0
-
equations
()¶ Return all linear constraints of the polyhedron.
OUTPUT:
A tuple of equations.
EXAMPLES:
sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]]) sage: test_p.equations() (An equation (1, 1, 1, 1) x - 10 == 0,)
-
equations_list
()¶ Return the linear constraints of the polyhedron. As with inequalities, each constraint is given as [b -a1 -a2 ... an] where for variables x1, x2,..., xn, the polyhedron satisfies the equation b = a1*x1 + a2*x2 + ... + an*xn.
Note
It is recommended to use
equations()
orequation_generator()
instead to iterate over the list ofEquation
objects.EXAMPLES:
sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]]) sage: test_p.equations_list() [[-10, 1, 1, 1, 1]]
-
f_vector
()¶ Return the f-vector.
OUTPUT:
Returns a vector whose
i
-th entry is the number ofi
-dimensional faces of the polytope.EXAMPLES:
sage: p = Polyhedron(vertices=[[1, 2, 3], [1, 3, 2], ... [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [0, 0, 0]]) sage: p.f_vector() (1, 7, 12, 7, 1)
-
face_lattice
()¶ Return the face-lattice poset.
OUTPUT:
A
FinitePoset
. Elements are given asPolyhedronFace
.In the case of a full-dimensional polytope, the faces are pairs (vertices, inequalities) of the spanning vertices and corresponding saturated inequalities. In general, a face is defined by a pair (V-rep. objects, H-rep. objects). The V-representation objects span the face, and the corresponding H-representation objects are those inequalities and equations that are saturated on the face.
The bottom-most element of the face lattice is the “empty face”. It contains no V-representation object. All H-representation objects are incident.
The top-most element is the “full face”. It is spanned by all V-representation objects. The incident H-representation objects are all equations and no inequalities.
In the case of a full-dimensional polytope, the “empty face” and the “full face” are the empty set (no vertices, all inequalities) and the full polytope (all vertices, no inequalities), respectively.
ALGORITHM:
For a full-dimensional polytope, the basic algorithm is described in
Hasse_diagram_from_incidences()
. There are three generalizations of [KP2002] necessary to deal with more general polytopes, corresponding to the extra H/V-representation objects:- Lines are removed before calling
Hasse_diagram_from_incidences()
, and then added back to each face V-representation except for the “empty face”. - Equations are removed before calling
Hasse_diagram_from_incidences()
, and then added back to each face H-representation. - Rays: Consider the half line as an example. The
V-representation objects are a point and a ray, which we can
think of as a point at infinity. However, the point at
infinity has no inequality associated to it, so there is
only one H-representation object alltogether. The face
lattice does not contain the “face at infinity”. This means
that in
Hasse_diagram_from_incidences()
, one needs to drop faces with V-representations that have no matching H-representation. In addition, one needs to ensure that every non-empty face contains at least one vertex.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: square.face_lattice() Finite poset containing 10 elements with distinguished linear extension sage: list(_) [<>, <0>, <1>, <2>, <3>, <0,1>, <0,2>, <2,3>, <1,3>, <0,1,2,3>] sage: poset_element = _[6] sage: a_face = poset_element sage: a_face <0,2> sage: a_face.dim() 1 sage: set(a_face.ambient_Vrepresentation()) == ... set([square.Vrepresentation(0), square.Vrepresentation(2)]) True sage: a_face.ambient_Vrepresentation() (A vertex at (-1, -1), A vertex at (1, -1)) sage: a_face.ambient_Hrepresentation() (An inequality (0, 1) x + 1 >= 0,)
A more complicated example:
sage: c5_10 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5] for i in range(1,11)]) sage: c5_10_fl = c5_10.face_lattice() sage: [len(x) for x in c5_10_fl.level_sets()] [1, 10, 45, 100, 105, 42, 1]
Note that if the polyhedron contains lines then there is a dimension gap between the empty face and the first non-empty face in the face lattice:
sage: line = Polyhedron(vertices=[(0,)], lines=[(1,)]) sage: [ fl.dim() for fl in line.face_lattice() ] [-1, 1]
TESTS:
sage: c5_20 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5] ... for i in range(1,21)]) sage: c5_20_fl = c5_20.face_lattice() # long time sage: [len(x) for x in c5_20_fl.level_sets()] # long time [1, 20, 190, 580, 680, 272, 1] sage: polytopes.hypercube(2).face_lattice().plot() Graphics object consisting of 27 graphics primitives sage: level_sets = polytopes.cross_polytope(2).face_lattice().level_sets() sage: level_sets[0], level_sets[-1] ([<>], [<0,1,2,3>])
Various degenerate polyhedra:
sage: Polyhedron(vertices=[[0,0,0],[1,0,0],[0,1,0]]).face_lattice().level_sets() [[<>], [<0>, <1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]] sage: Polyhedron(vertices=[(1,0,0),(0,1,0)], rays=[(0,0,1)]).face_lattice().level_sets() [[<>], [<1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]] sage: Polyhedron(rays=[(1,0,0),(0,1,0)], vertices=[(0,0,1)]).face_lattice().level_sets() [[<>], [<0>], [<0,1>, <0,2>], [<0,1,2>]] sage: Polyhedron(rays=[(1,0),(0,1)], vertices=[(0,0)]).face_lattice().level_sets() [[<>], [<0>], [<0,1>, <0,2>], [<0,1,2>]] sage: Polyhedron(vertices=[(1,),(0,)]).face_lattice().level_sets() [[<>], [<0>, <1>], [<0,1>]] sage: Polyhedron(vertices=[(1,0,0),(0,1,0)], lines=[(0,0,1)]).face_lattice().level_sets() [[<>], [<0,1>, <0,2>], [<0,1,2>]] sage: Polyhedron(lines=[(1,0,0)], vertices=[(0,0,1)]).face_lattice().level_sets() [[<>], [<0,1>]] sage: Polyhedron(lines=[(1,0),(0,1)], vertices=[(0,0)]).face_lattice().level_sets() [[<>], [<0,1,2>]] sage: Polyhedron(lines=[(1,0)], rays=[(0,1)], vertices=[(0,0)]) ... .face_lattice().level_sets() [[<>], [<0,1>], [<0,1,2>]] sage: Polyhedron(vertices=[(0,)], lines=[(1,)]).face_lattice().level_sets() [[<>], [<0,1>]] sage: Polyhedron(lines=[(1,0)], vertices=[(0,0)]).face_lattice().level_sets() [[<>], [<0,1>]]
REFERENCES:
[KP2002] Volker Kaibel and Marc E. Pfetsch, “Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences”, Computational Geometry: Theory and Applications, Volume 23, Issue 3 (November 2002), 281-290. Available at http://portal.acm.org/citation.cfm?id=763203 and free of charge at http://arxiv.org/abs/math/0106043 - Lines are removed before calling
-
faces
(face_dimension)¶ Return the faces of given dimension
INPUT:
face_dimension
– integer. The dimension of the faces whose representation will be returned.
OUTPUT:
A tuple of
PolyhedronFace
. Seeface
for details. The order random but fixed.EXAMPLES:
Here we find the vertex and face indices of the eight three-dimensional facets of the four-dimensional hypercube:
sage: p = polytopes.hypercube(4) sage: p.faces(3) (<0,1,2,3,4,5,6,7>, <0,1,2,3,8,9,10,11>, <0,1,4,5,8,9,12,13>, <0,2,4,6,8,10,12,14>, <2,3,6,7,10,11,14,15>, <8,9,10,11,12,13,14,15>, <4,5,6,7,12,13,14,15>, <1,3,5,7,9,11,13,15>) sage: face = p.faces(3)[0] sage: face.ambient_Hrepresentation() (An inequality (1, 0, 0, 0) x + 1 >= 0,) sage: face.vertices() (A vertex at (-1, -1, -1, -1), A vertex at (-1, -1, -1, 1), A vertex at (-1, -1, 1, -1), A vertex at (-1, -1, 1, 1), A vertex at (-1, 1, -1, -1), A vertex at (-1, 1, -1, 1), A vertex at (-1, 1, 1, -1), A vertex at (-1, 1, 1, 1))
You can use the
index()
method to enumerate vertices and inequalities:sage: def get_idx(rep): return rep.index() sage: [get_idx(_) for _ in face.ambient_Hrepresentation()] [4] sage: [get_idx(_) for _ in face.ambient_Vrepresentation()] [0, 1, 2, 3, 4, 5, 6, 7] sage: [ ([get_idx(_) for _ in face.ambient_Vrepresentation()], ....: [get_idx(_) for _ in face.ambient_Hrepresentation()]) ....: for face in p.faces(3) ] [([0, 1, 2, 3, 4, 5, 6, 7], [4]), ([0, 1, 2, 3, 8, 9, 10, 11], [5]), ([0, 1, 4, 5, 8, 9, 12, 13], [6]), ([0, 2, 4, 6, 8, 10, 12, 14], [7]), ([2, 3, 6, 7, 10, 11, 14, 15], [2]), ([8, 9, 10, 11, 12, 13, 14, 15], [0]), ([4, 5, 6, 7, 12, 13, 14, 15], [1]), ([1, 3, 5, 7, 9, 11, 13, 15], [3])]
TESTS:
sage: pr = Polyhedron(rays = [[1,0,0],[-1,0,0],[0,1,0]], vertices = [[-1,-1,-1]], lines=[(0,0,1)]) sage: pr.faces(4) () sage: pr.faces(3) (<0,1,2,3>,) sage: pr.faces(2) (<0,1,2>,) sage: pr.faces(1) () sage: pr.faces(0) () sage: pr.faces(-1) ()
-
facet_adjacency_matrix
()¶ Return the adjacency matrix for the facets and hyperplanes.
EXAMPLES:
sage: s4 = polytopes.simplex(4, project=True) sage: s4.facet_adjacency_matrix() [0 1 1 1 1] [1 0 1 1 1] [1 1 0 1 1] [1 1 1 0 1] [1 1 1 1 0]
-
field
()¶ Return the base ring.
OUTPUT:
The ring over which the polyhedron is defined. Must be a sub-ring of the reals to define a polyhedron, in particular comparison must be defined. Popular choices are
ZZ
(the ring of integers, lattice polytope),QQ
(exact arithmetic using gmp),RDF
(double precision floating-point arithmetic), orAA
(real algebraic field).
EXAMPLES:
sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]]) sage: triangle.base_ring() == ZZ True
-
gale_transform
()¶ Return the Gale transform of a polytope as described in the reference below.
OUTPUT:
A list of vectors, the Gale transform. The dimension is the dimension of the affine dependencies of the vertices of the polytope.
EXAMPLES:
This is from the reference, for a triangular prism:
sage: p = Polyhedron(vertices = [[0,0],[0,1],[1,0]]) sage: p2 = p.prism() sage: p2.gale_transform() [(1, 0), (0, 1), (-1, -1), (-1, 0), (0, -1), (1, 1)]
REFERENCES:
Lectures in Geometric Combinatorics, R.R.Thomas, 2006, AMS Press.
-
graph
()¶ Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.
EXAMPLES:
sage: g3 = polytopes.hypercube(3).vertex_graph(); g3 Graph on 8 vertices sage: g3.automorphism_group().cardinality() 48 sage: s4 = polytopes.simplex(4).vertex_graph(); s4 Graph on 5 vertices sage: s4.is_eulerian() True
-
hyperplane_arrangement
()¶ Return the hyperplane arrangement defined by the equations and inequalities.
OUTPUT:
A
hyperplane arrangement
consisting of the hyperplanes defined by theHrepresentation()
. If the polytope is full-dimensional, this is the hyperplane arrangement spanned by the facets of the polyhedron.EXAMPLES:
sage: p = polytopes.hypercube(2) sage: p.hyperplane_arrangement() Arrangement <-t0 + 1 | -t1 + 1 | t1 + 1 | t0 + 1>
-
incidence_matrix
()¶ Return the incidence matrix.
Note
The columns correspond to inequalities/equations in the order
Hrepresentation()
, the rows correspond to vertices/rays/lines in the orderVrepresentation()
EXAMPLES:
sage: p = polytopes.cuboctahedron() sage: p.incidence_matrix() [0 0 1 1 0 1 0 0 0 0 1 0 0 0] [0 0 0 1 0 0 1 0 1 0 1 0 0 0] [0 0 1 1 1 0 0 1 0 0 0 0 0 0] [1 0 0 1 1 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 1 1 1 0 0 0] [0 0 1 0 0 1 0 1 0 0 0 1 0 0] [1 0 0 0 0 0 1 0 1 0 0 0 1 0] [1 0 0 0 1 0 0 1 0 0 0 0 0 1] [0 1 0 0 0 1 0 0 0 1 0 1 0 0] [0 1 0 0 0 0 0 0 1 1 0 0 1 0] [0 1 0 0 0 0 0 1 0 0 0 1 0 1] [1 1 0 0 0 0 0 0 0 0 0 0 1 1] sage: v = p.Vrepresentation(0) sage: v A vertex at (-1, -1, 0) sage: h = p.Hrepresentation(2) sage: h An inequality (1, 1, -1) x + 2 >= 0 sage: h.eval(v) # evaluation (1, 1, -1) * (-1/2, -1/2, 0) + 1 0 sage: h*v # same as h.eval(v) 0 sage: p.incidence_matrix() [0,2] # this entry is (v,h) 1 sage: h.contains(v) True sage: p.incidence_matrix() [2,0] # note: not symmetric 0
-
inequalities
()¶ Return all inequalities.
OUTPUT:
A tuple of inequalities.
EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0,0],[0,0,1],[0,1,0],[1,0,0],[2,2,2]]) sage: p.inequalities()[0:3] (An inequality (1, 0, 0) x + 0 >= 0, An inequality (0, 1, 0) x + 0 >= 0, An inequality (0, 0, 1) x + 0 >= 0) sage: p3 = Polyhedron(vertices = Permutations([1,2,3,4])) sage: ieqs = p3.inequalities() sage: ieqs[0] An inequality (0, 1, 1, 1) x - 6 >= 0 sage: list(_) [-6, 0, 1, 1, 1]
-
inequalities_list
()¶ Return a list of inequalities as coefficient lists.
Note
It is recommended to use
inequalities()
orinequality_generator()
instead to iterate over the list ofInequality
objects.EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0,0],[0,0,1],[0,1,0],[1,0,0],[2,2,2]]) sage: p.inequalities_list()[0:3] [[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]] sage: p3 = Polyhedron(vertices = Permutations([1,2,3,4])) sage: ieqs = p3.inequalities_list() sage: ieqs[0] [-6, 0, 1, 1, 1] sage: ieqs[-1] [-3, 0, 1, 0, 1] sage: ieqs == [list(x) for x in p3.inequality_generator()] True
-
inequality_generator
()¶ Return a generator for the defining inequalities of the polyhedron.
OUTPUT:
A generator of the inequality Hrepresentation objects.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]]) sage: for v in triangle.inequality_generator(): print(v) An inequality (1, 1) x - 1 >= 0 An inequality (0, -1) x + 1 >= 0 An inequality (-1, 0) x + 1 >= 0 sage: [ v for v in triangle.inequality_generator() ] [An inequality (1, 1) x - 1 >= 0, An inequality (0, -1) x + 1 >= 0, An inequality (-1, 0) x + 1 >= 0] sage: [ [v.A(), v.b()] for v in triangle.inequality_generator() ] [[(1, 1), -1], [(0, -1), 1], [(-1, 0), 1]]
-
integral_points
(threshold=100000)¶ Return the integral points in the polyhedron.
Uses either the naive algorithm (iterate over a rectangular bounding box) or triangulation + Smith form.
INPUT:
threshold
– integer (default: 100000). Use the naive algorithm as long as the bounding box is smaller than this.
OUTPUT:
The list of integral points in the polyhedron. If the polyhedron is not compact, a
ValueError
is raised.EXAMPLES:
sage: Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)]).integral_points() ((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1)) sage: simplex = Polyhedron([(1,2,3), (2,3,7), (-2,-3,-11)]) sage: simplex.integral_points() ((-2, -3, -11), (0, 0, -2), (1, 2, 3), (2, 3, 7))
The polyhedron need not be full-dimensional:
sage: simplex = Polyhedron([(1,2,3,5), (2,3,7,5), (-2,-3,-11,5)]) sage: simplex.integral_points() ((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5)) sage: point = Polyhedron([(2,3,7)]) sage: point.integral_points() ((2, 3, 7),) sage: empty = Polyhedron() sage: empty.integral_points() ()
Here is a simplex where the naive algorithm of running over all points in a rectangular bounding box no longer works fast enough:
sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)] sage: simplex = Polyhedron(v); simplex A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices sage: len(simplex.integral_points()) 49
Finally, the 3-d reflexive polytope number 4078:
sage: v = [(1,0,0), (0,1,0), (0,0,1), (0,0,-1), (0,-2,1), ... (-1,2,-1), (-1,2,-2), (-1,1,-2), (-1,-1,2), (-1,-3,2)] sage: P = Polyhedron(v) sage: pts1 = P.integral_points() # Sage's own code sage: all(P.contains(p) for p in pts1) True sage: pts2 = LatticePolytope(v).points() # PALP sage: for p in pts1: p.set_immutable() sage: set(pts1) == set(pts2) True sage: timeit('Polyhedron(v).integral_points()') # not tested - random 625 loops, best of 3: 1.41 ms per loop sage: timeit('LatticePolytope(v).points()') # not tested - random 25 loops, best of 3: 17.2 ms per loop
TESTS:
Test some trivial cases (see trac ticket #17937):
sage: P = Polyhedron(ambient_dim=1) # empty polyhedron in 1 dimension sage: P.integral_points() () sage: P = Polyhedron(ambient_dim=0) # empty polyhedron in 0 dimensions sage: P.integral_points() () sage: P = Polyhedron([[3]]) # single point in 1 dimension sage: P.integral_points() ((3),) sage: P = Polyhedron([[1/2]]) # single non-integral point in 1 dimension sage: P.integral_points() () sage: P = Polyhedron([[]]) # single point in 0 dimensions sage: P.integral_points() ((),)
-
integral_points_count
(verbose=False)¶ Return the number of integral points in the polyhedron.
This method uses the optional package
latte_int
.INPUT:
verbose
(boolean;False
by default) – whether to display verbose output.
EXAMPLES:
sage: P = polytopes.cube() sage: P.integral_points_count() # optional - latte_int 27 sage: P.integral_points_count(verbose=True) # optional - latte_int This is LattE integrale... ... Total time:... 27
We shrink the polyhedron a little bit:
sage: Q = P*(8/9) sage: Q.integral_points_count() # optional - latte_int 1
This no longer works if the coordinates are not rationals:
sage: Q = P*RDF(8/9) sage: Q.integral_points_count() # optional - latte_int Traceback (most recent call last): ... RuntimeError: LattE integrale failed (exit code 1) to execute... ...Parse error in CDD-style input file /dev/stdin sage: Q.integral_points_count(verbose=True) # optional - latte_int Traceback (most recent call last): ... RuntimeError: LattE integrale failed (exit code 1) to execute count --cdd /dev/stdin, see error message above
-
interior_contains
(point)¶ Test whether the interior of the polyhedron contains the given
point
.See also
contains()
andrelative_interior_contains()
.INPUT:
point
– coordinates of a point.
OUTPUT:
True
orFalse
.EXAMPLES:
sage: P = Polyhedron(vertices=[[0,0],[1,1],[1,-1]]) sage: P.contains( [1,0] ) True sage: P.interior_contains( [1,0] ) False
If the polyhedron is of strictly smaller dimension than the ambient space, its interior is empty:
sage: P = Polyhedron(vertices=[[0,1],[0,-1]]) sage: P.contains( [0,0] ) True sage: P.interior_contains( [0,0] ) False
The empty polyhedron needs extra care, see trac ticket #10238:
sage: empty = Polyhedron(); empty The empty polyhedron in ZZ^0 sage: empty.interior_contains([]) False
-
intersection
(other)¶ Return the intersection of one polyhedron with another.
INPUT:
other
– aPolyhedron
.
OUTPUT:
The intersection.
Note that the intersection of two \(\ZZ\)-polyhedra might not be a \(\ZZ\)-polyhedron. In this case, a \(\QQ\)-polyhedron is returned.
EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: oct = polytopes.cross_polytope(3) sage: cube.intersection(oct*2) A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices
As a shorthand, one may use:
sage: cube & oct*2 A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices
The intersection of two \(\ZZ\)-polyhedra is not necessarily a \(\ZZ\)-polyhedron:
sage: P = Polyhedron([(0,0),(1,1)], base_ring=ZZ) sage: P.intersection(P) A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices sage: Q = Polyhedron([(0,1),(1,0)], base_ring=ZZ) sage: P.intersection(Q) A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex sage: _.Vrepresentation() (A vertex at (1/2, 1/2),) TESTS: Check that :trac:`19012` is fixed:: sage: K.<a> = QuadraticField(5) sage: P = Polyhedron([[0,0],[0,a],[1,1]]) sage: Q = Polyhedron(ieqs=[[-1,a,1]]) sage: P.intersection(Q) A 2-dimensional polyhedron in (Number Field in a with defining polynomial x^2 - 5)^2 defined as the convex hull of 4 vertices
-
is_Minkowski_summand
(Y)¶ Test whether
Y
is a Minkowski summand.See
Minkowski_sum()
.OUTPUT:
Boolean. Whether there exists another polyhedron \(Z\) such that
self
can be written as \(Y\oplus Z\).EXAMPLES:
sage: A = polytopes.hypercube(2) sage: B = Polyhedron(vertices=[(0,1), (1/2,1)]) sage: C = Polyhedron(vertices=[(1,1)]) sage: A.is_Minkowski_summand(B) True sage: A.is_Minkowski_summand(C) True sage: B.is_Minkowski_summand(C) True sage: B.is_Minkowski_summand(A) False sage: C.is_Minkowski_summand(A) False sage: C.is_Minkowski_summand(B) False
-
is_compact
()¶ Test for boundedness of the polytope.
EXAMPLES:
sage: p = polytopes.icosahedron() sage: p.is_compact() True sage: p = Polyhedron(ieqs = [[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,-1,0,0]]) sage: p.is_compact() False
-
is_empty
()¶ Test whether the polyhedron is the empty polyhedron
OUTPUT:
Boolean.
EXAMPLES:
sage: P = Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]]); P A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices sage: P.is_empty(), P.is_universe() (False, False) sage: Q = Polyhedron(vertices=()); Q The empty polyhedron in ZZ^0 sage: Q.is_empty(), Q.is_universe() (True, False) sage: R = Polyhedron(lines=[(1,0),(0,1)]); R A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines sage: R.is_empty(), R.is_universe() (False, True)
-
is_full_dimensional
()¶ Return whether the polyhedron is full dimensional.
OUTPUT:
Boolean. Whether the polyhedron is not contained in any strict affine subspace.
EXAMPLES:
sage: polytopes.hypercube(3).is_full_dimensional() True sage: Polyhedron(vertices=[(1,2,3)], rays=[(1,0,0)]).is_full_dimensional() False
-
is_lattice_polytope
()¶ Return whether the polyhedron is a lattice polytope.
OUTPUT:
True
if the polyhedron is compact and has only integral vertices,False
otherwise.EXAMPLES:
sage: polytopes.cross_polytope(3).is_lattice_polytope() True sage: polytopes.regular_polygon(5).is_lattice_polytope() False
-
is_simple
()¶ Test for simplicity of a polytope.
See Wikipedia article Simple_polytope
EXAMPLES:
sage: p = Polyhedron([[0,0,0],[1,0,0],[0,1,0],[0,0,1]]) sage: p.is_simple() True sage: p = Polyhedron([[0,0,0],[4,4,0],[4,0,0],[0,4,0],[2,2,2]]) sage: p.is_simple() False
-
is_simplex
()¶ Return whether the polyhedron is a simplex.
EXAMPLES:
sage: Polyhedron([(0,0,0), (1,0,0), (0,1,0)]).is_simplex() True sage: polytopes.simplex(3).is_simplex() True sage: polytopes.hypercube(3).is_simplex() False
-
is_simplicial
()¶ Tests if the polytope is simplicial
A polytope is simplicial if every facet is a simplex.
See Wikipedia article Simplicial_polytope
EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p.is_simplicial() False sage: q = polytopes.simplex(5, project=True) sage: q.is_simplicial() True sage: p = Polyhedron([[0,0,0],[1,0,0],[0,1,0],[0,0,1]]) sage: p.is_simplicial() True sage: q = Polyhedron([[1,1,1],[-1,1,1],[1,-1,1],[-1,-1,1],[1,1,-1]]) sage: q.is_simplicial() False
The method is not implemented for unbounded polyhedra:
sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)]) sage: p.is_simplicial() Traceback (most recent call last): ... NotImplementedError: This function is implemented for polytopes only.
-
is_universe
()¶ Test whether the polyhedron is the whole ambient space
OUTPUT:
Boolean.
EXAMPLES:
sage: P = Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]]); P A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices sage: P.is_empty(), P.is_universe() (False, False) sage: Q = Polyhedron(vertices=()); Q The empty polyhedron in ZZ^0 sage: Q.is_empty(), Q.is_universe() (True, False) sage: R = Polyhedron(lines=[(1,0),(0,1)]); R A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines sage: R.is_empty(), R.is_universe() (False, True)
-
lattice_polytope
(envelope=False)¶ Return an encompassing lattice polytope.
INPUT:
envelope
– boolean (default:False
). If the polyhedron has non-integral vertices, this option decides whether to return a strictly larger lattice polytope or raise aValueError
. This option has no effect if the polyhedron has already integral vertices.
OUTPUT:
A
LatticePolytope
. If the polyhedron is compact and has integral vertices, the lattice polytope equals the polyhedron. If the polyhedron is compact but has at least one non-integral vertex, a strictly larger lattice polytope is returned.If the polyhedron is not compact, a
NotImplementedError
is raised.If the polyhedron is not integral and
envelope=False
, aValueError
is raised.ALGORITHM:
For each non-integral vertex, a bounding box of integral points is added and the convex hull of these integral points is returned.
EXAMPLES:
First, a polyhedron with integral vertices:
sage: P = Polyhedron( vertices = [(1, 0), (0, 1), (-1, 0), (0, -1)]) sage: lp = P.lattice_polytope(); lp 2-d reflexive polytope #3 in 2-d lattice M sage: lp.vertices() M(-1, 0), M( 0, -1), M( 0, 1), M( 1, 0) in 2-d lattice M
Here is a polyhedron with non-integral vertices:
sage: P = Polyhedron( vertices = [(1/2, 1/2), (0, 1), (-1, 0), (0, -1)]) sage: lp = P.lattice_polytope() Traceback (most recent call last): ... ValueError: Some vertices are not integral. You probably want to add the argument "envelope=True" to compute an enveloping lattice polytope. sage: lp = P.lattice_polytope(True); lp 2-d reflexive polytope #5 in 2-d lattice M sage: lp.vertices() M(-1, 0), M( 0, -1), M( 0, 1), M( 1, 0), M( 1, 1) in 2-d lattice M
-
line_generator
()¶ Return a generator for the lines of the polyhedron.
EXAMPLES:
sage: pr = Polyhedron(rays = [[1,0],[-1,0],[0,1]], vertices = [[-1,-1]]) sage: next(pr.line_generator()).vector() (1, 0)
-
lines
()¶ Return all lines of the polyhedron.
OUTPUT:
A tuple of lines.
EXAMPLES:
sage: p = Polyhedron(rays = [[1,0],[-1,0],[0,1],[1,1]], vertices = [[-2,-2],[2,3]]) sage: p.lines() (A line in the direction (1, 0),)
-
lines_list
()¶ Return a list of lines of the polyhedron. The line data is given as a list of coordinates rather than as a Hrepresentation object.
Note
It is recommended to use
line_generator()
instead to iterate over the list ofLine
objects.EXAMPLES:
sage: p = Polyhedron(rays = [[1,0],[-1,0],[0,1],[1,1]], vertices = [[-2,-2],[2,3]]) sage: p.lines_list() [[1, 0]] sage: p.lines_list() == [list(x) for x in p.line_generator()] True
-
n_Hrepresentation
()¶ Return the number of objects that make up the H-representation of the polyhedron.
OUTPUT:
Integer.
EXAMPLES:
sage: p = polytopes.cross_polytope(4) sage: p.n_Hrepresentation() 16 sage: p.n_Hrepresentation() == p.n_inequalities() + p.n_equations() True
-
n_Vrepresentation
()¶ Return the number of objects that make up the V-representation of the polyhedron.
OUTPUT:
Integer.
EXAMPLES:
sage: p = polytopes.simplex(4) sage: p.n_Vrepresentation() 5 sage: p.n_Vrepresentation() == p.n_vertices() + p.n_rays() + p.n_lines() True
-
n_equations
()¶ Return the number of equations. The representation will always be minimal, so the number of equations is the codimension of the polyhedron in the ambient space.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]]) sage: p.n_equations() 1
-
n_facets
()¶ Return the number of inequalities. The representation will always be minimal, so the number of inequalities is the number of facets of the polyhedron in the ambient space.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]]) sage: p.n_inequalities() 3 sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in range(6)]) sage: p.n_facets() 8
-
n_inequalities
()¶ Return the number of inequalities. The representation will always be minimal, so the number of inequalities is the number of facets of the polyhedron in the ambient space.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]]) sage: p.n_inequalities() 3 sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in range(6)]) sage: p.n_facets() 8
-
n_lines
()¶ Return the number of lines. The representation will always be minimal.
EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0]], rays=[[0,1],[0,-1]]) sage: p.n_lines() 1
-
n_rays
()¶ Return the number of rays. The representation will always be minimal.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0],[0,1]], rays=[[1,1]]) sage: p.n_rays() 1
-
n_vertices
()¶ Return the number of vertices. The representation will always be minimal.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0],[0,1],[1,1]], rays=[[1,1]]) sage: p.n_vertices() 2
-
plot
(point=None, line=None, polygon=None, wireframe='blue', fill='green', projection_direction=None, **kwds)¶ Return a graphical representation.
INPUT:
point
,line
,polygon
– Parameters to pass to point (0d), line (1d), and polygon (2d) plot commands. Allowed values are:- A Python dictionary to be passed as keywords to the plot commands.
- A string or triple of numbers: The color. This is
equivalent to passing the dictionary
{'color':...}
. False
: Switches off the drawing of the corresponding graphics object
wireframe
,fill
– Similar topoint
,line
, andpolygon
, butfill
is used for the graphics objects in the dimension of the polytope (or of dimension 2 for higher dimensional polytopes) andwireframe
is used for all lower-dimensional graphics objects (default: ‘green’ forfill
and ‘blue’ forwireframe
)projection_direction
– coordinate list/tuple/iterable orNone
(default). The direction to use for theschlegel_projection`()
of the polytope. If not specified, no projection is used in dimensions \(< 4\) and parallel projection is used in dimension \(4\).**kwds
– optional keyword parameters that are passed to all graphics objects.
OUTPUT:
A (multipart) graphics object.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: point = Polyhedron([[1,1]]) sage: line = Polyhedron([[1,1],[2,1]]) sage: cube = polytopes.hypercube(3) sage: hypercube = polytopes.hypercube(4)
By default, the wireframe is rendered in blue and the fill in green:
sage: square.plot() Graphics object consisting of 6 graphics primitives sage: point.plot() Graphics object consisting of 1 graphics primitive sage: line.plot() Graphics object consisting of 2 graphics primitives sage: cube.plot() Graphics3d Object sage: hypercube.plot() Graphics3d Object
Draw the lines in red and nothing else:
sage: square.plot(point=False, line='red', polygon=False) Graphics object consisting of 4 graphics primitives sage: point.plot(point=False, line='red', polygon=False) Graphics object consisting of 0 graphics primitives sage: line.plot(point=False, line='red', polygon=False) Graphics object consisting of 1 graphics primitive sage: cube.plot(point=False, line='red', polygon=False) Graphics3d Object sage: hypercube.plot(point=False, line='red', polygon=False) Graphics3d Object
Draw points in red, no lines, and a blue polygon:
sage: square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics object consisting of 2 graphics primitives sage: point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics object consisting of 1 graphics primitive sage: line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics object consisting of 1 graphics primitive sage: cube.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics3d Object sage: hypercube.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics3d Object
If we instead use the
fill
andwireframe
options, the coloring depends on the dimension of the object:sage: square.plot(fill='green', wireframe='red') Graphics object consisting of 6 graphics primitives sage: point.plot(fill='green', wireframe='red') Graphics object consisting of 1 graphics primitive sage: line.plot(fill='green', wireframe='red') Graphics object consisting of 2 graphics primitives sage: cube.plot(fill='green', wireframe='red') Graphics3d Object sage: hypercube.plot(fill='green', wireframe='red') Graphics3d Object
TESTS:
sage: for p in square.plot(): ....: print("{} {}".format(p.options()['rgbcolor'], p)) blue Point set defined by 4 point(s) blue Line defined by 2 points blue Line defined by 2 points blue Line defined by 2 points blue Line defined by 2 points green Polygon defined by 4 points sage: for p in line.plot(): ....: print("{} {}".format(p.options()['rgbcolor'], p)) blue Point set defined by 2 point(s) green Line defined by 2 points sage: for p in point.plot(): ....: print("{} {}".format(p.options()['rgbcolor'], p)) green Point set defined by 1 point(s)
Draw the lines in red and nothing else:
sage: for p in square.plot(point=False, line='red', polygon=False): ....: print("{} {}".format(p.options()['rgbcolor'], p)) red Line defined by 2 points red Line defined by 2 points red Line defined by 2 points red Line defined by 2 points
Draw vertices in red, no lines, and a blue polygon:
sage: for p in square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)): ....: print("{} {}".format(p.options()['rgbcolor'], p)) red Point set defined by 4 point(s) (0, 0, 1) Polygon defined by 4 points sage: for p in line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)): ....: print("{} {}".format(p.options()['rgbcolor'], p)) red Point set defined by 2 point(s) sage: for p in point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)): ....: print("{} {}".format(p.options()['rgbcolor'], p)) red Point set defined by 1 point(s)
Draw in red without wireframe:
sage: for p in square.plot(wireframe=False, fill="red"): ....: print("{} {}".format(p.options()['rgbcolor'], p)) red Polygon defined by 4 points sage: for p in line.plot(wireframe=False, fill="red"): ....: print("{} {}".format(p.options()['rgbcolor'], p)) red Line defined by 2 points sage: for p in point.plot(wireframe=False, fill="red"): ....: print("{} {}".format(p.options()['rgbcolor'], p)) red Point set defined by 1 point(s)
The
projection_direction
option:sage: line3d = Polyhedron([(-1,-1,-1), (1,1,1)]) sage: print(line3d.plot(projection_direction=[2,3,4]).description()) Line defined by 2 points: [(-0.00..., 0.126...), (0.131..., -1.93...)] Point set defined by 2 point(s): [(-0.00..., 0.126...), (0.131..., -1.93...)]
We try to draw the polytope in 2 or 3 dimensions:
sage: type(Polyhedron(ieqs=[(1,)]).plot()) <class 'sage.plot.graphics.Graphics'> sage: type(polytopes.hypercube(1).plot()) <class 'sage.plot.graphics.Graphics'> sage: type(polytopes.hypercube(2).plot()) <class 'sage.plot.graphics.Graphics'> sage: type(polytopes.hypercube(3).plot()) <class 'sage.plot.plot3d.base.Graphics3dGroup'>
In 4d a projection to 3d is used:
sage: type(polytopes.hypercube(4).plot()) <class 'sage.plot.plot3d.base.Graphics3dGroup'> sage: type(polytopes.hypercube(5).plot()) Traceback (most recent call last): ... NotImplementedError: plotting of 5-dimensional polyhedra not implemented
If the polyhedron is not full-dimensional, the
affine_hull()
is used if necessary:sage: type(Polyhedron([(0,), (1,)]).plot()) <class 'sage.plot.graphics.Graphics'> sage: type(Polyhedron([(0,0), (1,1)]).plot()) <class 'sage.plot.graphics.Graphics'> sage: type(Polyhedron([(0,0,0), (1,1,1)]).plot()) <class 'sage.plot.plot3d.base.Graphics3dGroup'> sage: type(Polyhedron([(0,0,0,0), (1,1,1,1)]).plot()) <class 'sage.plot.plot3d.base.Graphics3dGroup'> sage: type(Polyhedron([(0,0,0,0,0), (1,1,1,1,1)]).plot()) <class 'sage.plot.graphics.Graphics'>
-
polar
()¶ Return the polar (dual) polytope.
The original vertices are translated so that their barycenter is at the origin, and then the vertices are used as the coefficients in the polar inequalities.
EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0,1],[0,1,0],[1,0,0],[0,0,0],[1,1,1]], base_ring=QQ) sage: p A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices sage: p.polar() A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices sage: cube = polytopes.hypercube(3) sage: octahedron = polytopes.cross_polytope(3) sage: cube_dual = cube.polar() sage: octahedron == cube_dual True
-
prism
()¶ Return a prism of the original polyhedron.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: cube = square.prism() sage: cube A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: hypercube = cube.prism() sage: hypercube.n_vertices() 16
-
product
(other)¶ Return the Cartesian product.
INPUT:
other
– aPolyhedron_base
.
OUTPUT:
The Cartesian product of
self
andother
with a suitable base ring to encompass the two.EXAMPLES:
sage: P1 = Polyhedron([[0],[1]], base_ring=ZZ) sage: P2 = Polyhedron([[0],[1]], base_ring=QQ) sage: P1.product(P2) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
The Cartesian product is the product in the semiring of polyhedra:
sage: P1 * P1 A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices sage: P1 * P2 A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: P2 * P2 A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: 2 * P1 A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices sage: P1 * 2.0 A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices
-
projection
()¶ Return a projection object.
See also
schlegel_projection()
for a more interesting projection.OUTPUT:
The identity projection. This is useful for plotting polyhedra.
EXAMPLES:
sage: p = polytopes.hypercube(3) sage: proj = p.projection() sage: proj The projection of a polyhedron into 3 dimensions
-
pyramid
()¶ Returns a polyhedron that is a pyramid over the original.
EXAMPLES:
sage: square = polytopes.hypercube(2); square A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices sage: egyptian_pyramid = square.pyramid(); egyptian_pyramid A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 5 vertices sage: egyptian_pyramid.n_vertices() 5 sage: for v in egyptian_pyramid.vertex_generator(): print(v) A vertex at (0, -1, -1) A vertex at (0, -1, 1) A vertex at (0, 1, -1) A vertex at (0, 1, 1) A vertex at (1, 0, 0)
-
radius
()¶ Return the maximal distance from the center to a vertex. All rays and lines are ignored.
OUTPUT:
The radius for a rational polyhedron is, in general, not rational. use
radius_square()
if you need a rational distance measure.EXAMPLES:
sage: p = polytopes.hypercube(4) sage: p.radius() 2
-
radius_square
()¶ Return the square of the maximal distance from the
center()
to a vertex. All rays and lines are ignored.OUTPUT:
The square of the radius, which is in
field()
.EXAMPLES:
sage: p = polytopes.permutahedron(4, project = False) sage: p.radius_square() 5
-
ray_generator
()¶ Return a generator for the rays of the polyhedron.
EXAMPLES:
sage: pi = Polyhedron(ieqs = [[1,1,0],[1,0,1]]) sage: pir = pi.ray_generator() sage: [x.vector() for x in pir] [(1, 0), (0, 1)]
-
rays
()¶ Return a list of rays of the polyhedron.
OUTPUT:
A tuple of rays.
EXAMPLES:
sage: p = Polyhedron(ieqs = [[0,0,0,1],[0,0,1,0],[1,1,0,0]]) sage: p.rays() (A ray in the direction (1, 0, 0), A ray in the direction (0, 1, 0), A ray in the direction (0, 0, 1))
-
rays_list
()¶ Return a list of rays as coefficient lists.
Note
It is recommended to use
rays()
orray_generator()
instead to iterate over the list ofRay
objects.OUTPUT:
A list of rays as lists of coordinates.
EXAMPLES:
sage: p = Polyhedron(ieqs = [[0,0,0,1],[0,0,1,0],[1,1,0,0]]) sage: p.rays_list() [[1, 0, 0], [0, 1, 0], [0, 0, 1]] sage: p.rays_list() == [list(r) for r in p.ray_generator()] True
-
relative_interior_contains
(point)¶ Test whether the relative interior of the polyhedron contains the given
point
.See also
contains()
andinterior_contains()
.INPUT:
point
– coordinates of a point.
OUTPUT:
True
orFalse
.EXAMPLES:
sage: P = Polyhedron(vertices=[(1,0), (-1,0)]) sage: P.contains( (0,0) ) True sage: P.interior_contains( (0,0) ) False sage: P.relative_interior_contains( (0,0) ) True sage: P.relative_interior_contains( (1,0) ) False
The empty polyhedron needs extra care, see trac ticket #10238:
sage: empty = Polyhedron(); empty The empty polyhedron in ZZ^0 sage: empty.relative_interior_contains([]) False
-
render_solid
(**kwds)¶ Return a solid rendering of a 2- or 3-d polytope.
EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p_solid = p.render_solid(opacity = .7) sage: type(p_solid) <class 'sage.plot.plot3d.base.Graphics3dGroup'>
-
render_wireframe
(**kwds)¶ For polytopes in 2 or 3 dimensions, return the edges as a list of lines.
EXAMPLES:
sage: p = Polyhedron([[1,2,],[1,1],[0,0]]) sage: p_wireframe = p.render_wireframe() sage: p_wireframe._objects [Line defined by 2 points, Line defined by 2 points, Line defined by 2 points]
-
representative_point
()¶ Return a “generic” point.
See also
center()
.OUTPUT:
A point as a coordinate vector. The point is chosen to be interior as far as possible. If the polyhedron is not full-dimensional, the point is in the relative interior. If the polyhedron is zero-dimensional, its single point is returned.
EXAMPLES:
sage: p = Polyhedron(vertices=[(3,2)], rays=[(1,-1)]) sage: p.representative_point() (4, 1) sage: p.center() (3, 2) sage: Polyhedron(vertices=[(3,2)]).representative_point() (3, 2)
-
restricted_automorphism_group
(output='abstract')¶ Return the restricted automorphism group.
First, let the linear automorphism group be the subgroup of the affine group \(AGL(d,\RR) = GL(d,\RR) \ltimes \RR^d\) preserving the \(d\)-dimensional polyhedron. The affine group acts in the usual way \(\vec{x}\mapsto A\vec{x}+b\) on the ambient space.
The restricted automorphism group is the subgroup of the linear automorphism group generated by permutations of the generators of the same type. That is, vertices can only be permuted with vertices, ray generators with ray generators, and line generators with line generators.
For example, take the first quadrant
\[Q = \Big\{ (x,y) \Big| x\geq 0,\; y\geq0 \Big\} \subset \QQ^2\]Then the linear automorphism group is
\[\begin{split}\mathrm{Aut}(Q) = \left\{ \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} ,~ \begin{pmatrix} 0 & c \\ d & 0 \end{pmatrix} :~ a, b, c, d \in \QQ_{>0} \right\} \subset GL(2,\QQ) \subset E(d)\end{split}\]Note that there are no translations that map the quadrant \(Q\) to itself, so the linear automorphism group is contained in the general linear group (the subgroup of transformations preserving the origin). The restricted automorphism group is
\[\begin{split}\mathrm{Aut}(Q) = \left\{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} ,~ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \right\} \simeq \ZZ_2\end{split}\]INPUT:
output
– how the group should be represented:"abstract"
(default) – return an abstract permutation group without further meaning."permutation"
– return a permutation group on the indices of the polyhedron generators. For example, the permutation(0,1)
would correspond to swappingself.Vrepresentation(0)
andself.Vrepresentation(1)
."matrix"
– return a matrix group representing affine transformations. When acting on affine vectors, you should append a \(1\) to every vector. If the polyhedron is not full dimensional, the returned matrices act as the identity on the orthogonal complement of the affine space spanned by the polyhedron."matrixlist"
– likematrix
, but return the list of elements of the matrix group. Useful for fields without a good implementation of matrix groups or to avoid the overhead of creating the group.
OUTPUT:
- For
output="abstract"
andoutput="permutation"
: aPermutationGroup
. - For
output="matrix"
: aMatrixGroup
. - For
output="matrixlist"
: a list of matrices.
REFERENCES:
[BSS] David Bremner, Mathieu Dutour Sikiric, Achill Schuermann: Polyhedral representation conversion up to symmetries. http://arxiv.org/abs/math/0702239 EXAMPLES:
sage: P = polytopes.cross_polytope(3) sage: P.restricted_automorphism_group() Permutation Group with generators [(3,4), (2,3)(4,5), (2,5), (1,2)(5,6), (1,6)] sage: P.restricted_automorphism_group(output="permutation") Permutation Group with generators [(2,3), (1,2)(3,4), (1,4), (0,1)(4,5), (0,5)] sage: P.restricted_automorphism_group(output="matrix") Matrix group over Rational Field with 5 generators ( [ 1 0 0 0] [1 0 0 0] [ 1 0 0 0] [0 1 0 0] [-1 0 0 0] [ 0 1 0 0] [0 0 1 0] [ 0 -1 0 0] [1 0 0 0] [ 0 1 0 0] [ 0 0 -1 0] [0 1 0 0] [ 0 0 1 0] [0 0 1 0] [ 0 0 1 0] [ 0 0 0 1], [0 0 0 1], [ 0 0 0 1], [0 0 0 1], [ 0 0 0 1] )
sage: P24 = polytopes.twenty_four_cell() sage: AutP24 = P24.restricted_automorphism_group() sage: PermutationGroup([ ....: '(1,20,2,24,5,23)(3,18,10,19,4,14)(6,21,11,22,7,15)(8,12,16,17,13,9)', ....: '(1,21,8,24,4,17)(2,11,6,15,9,13)(3,20)(5,22)(10,16,12,23,14,19)' ....: ]) == AutP24 True sage: len(AutP24) 1152
Here is the quadrant example mentioned in the beginning:
sage: P = Polyhedron(rays=[(1,0),(0,1)]) sage: P.Vrepresentation() (A vertex at (0, 0), A ray in the direction (0, 1), A ray in the direction (1, 0)) sage: P.restricted_automorphism_group(output="permutation") Permutation Group with generators [(1,2)]
Also, the polyhedron need not be full-dimensional:
sage: P = Polyhedron(vertices=[(1,2,3,4,5),(7,8,9,10,11)]) sage: P.restricted_automorphism_group() Permutation Group with generators [(1,2)] sage: G = P.restricted_automorphism_group(output="matrixlist") sage: G [ [1 0 0 0 0 0] [ -87/55 -82/55 -2/5 38/55 98/55 12/11] [0 1 0 0 0 0] [-142/55 -27/55 -2/5 38/55 98/55 12/11] [0 0 1 0 0 0] [-142/55 -82/55 3/5 38/55 98/55 12/11] [0 0 0 1 0 0] [-142/55 -82/55 -2/5 93/55 98/55 12/11] [0 0 0 0 1 0] [-142/55 -82/55 -2/5 38/55 153/55 12/11] [0 0 0 0 0 1], [ 0 0 0 0 0 1] ] sage: g = AffineGroup(5, QQ)(G[1]) sage: g [ -87/55 -82/55 -2/5 38/55 98/55] [12/11] [-142/55 -27/55 -2/5 38/55 98/55] [12/11] x |-> [-142/55 -82/55 3/5 38/55 98/55] x + [12/11] [-142/55 -82/55 -2/5 93/55 98/55] [12/11] [-142/55 -82/55 -2/5 38/55 153/55] [12/11] sage: g^2 [1 0 0 0 0] [0] [0 1 0 0 0] [0] x |-> [0 0 1 0 0] x + [0] [0 0 0 1 0] [0] [0 0 0 0 1] [0] sage: g(list(P.vertices()[0])) (7, 8, 9, 10, 11) sage: g(list(P.vertices()[1])) (1, 2, 3, 4, 5)
Affine transformations do not change the restricted automorphism group. For example, any non-degenerate triangle has the dihedral group with 6 elements, \(D_6\), as its automorphism group:
sage: initial_points = [vector([1,0]), vector([0,1]), vector([-2,-1])] sage: points = initial_points sage: Polyhedron(vertices=points).restricted_automorphism_group() Permutation Group with generators [(2,3), (1,2)] sage: points = [pt - initial_points[0] for pt in initial_points] sage: Polyhedron(vertices=points).restricted_automorphism_group() Permutation Group with generators [(2,3), (1,2)] sage: points = [pt - initial_points[1] for pt in initial_points] sage: Polyhedron(vertices=points).restricted_automorphism_group() Permutation Group with generators [(2,3), (1,2)] sage: points = [pt - 2*initial_points[1] for pt in initial_points] sage: Polyhedron(vertices=points).restricted_automorphism_group() Permutation Group with generators [(2,3), (1,2)]
The
output="matrixlist"
can be used over fields without a complete implementation of matrix groups:sage: P = polytopes.dodecahedron(); P A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5)^3 defined as the convex hull of 20 vertices sage: G = P.restricted_automorphism_group(output="matrixlist") sage: len(G) 120
Floating-point computations are supported with a simple fuzzy zero implementation:
sage: P = Polyhedron(vertices=[(1/3,0,0,1),(0,1/4,0,1),(0,0,1/5,1)], base_ring=RDF) sage: P.restricted_automorphism_group() Permutation Group with generators [(2,3), (1,2)] sage: len(P.restricted_automorphism_group(output="matrixlist")) 6
TESTS:
sage: P = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)]) sage: P.restricted_automorphism_group(output="permutation") Permutation Group with generators [(1,2)] sage: P.restricted_automorphism_group(output="matrix") Matrix group over Rational Field with 1 generators ( [ 1 0 0] [ 0 -1 1] [ 0 0 1] ) sage: P.restricted_automorphism_group(output="foobar") Traceback (most recent call last): ... ValueError: unknown output 'foobar', valid values are ('abstract', 'permutation', 'matrix', 'matrixlist')
-
schlegel_projection
(projection_dir=None, height=1.1)¶ Return the Schlegel projection.
- The polyhedron is translated such that its
center()
is at the origin. - The vertices are then normalized to the unit sphere
- The normalized points are stereographically projected from a point slightly outside of the sphere.
INPUT:
projection_direction
– coordinate list/tuple/iterable orNone
(default). The direction of the Schlegel projection. For a full-dimensional polyhedron, the default is the first facet normal; Otherwise, the vector consisting of the first n primes is chosen.height
– float (default: \(1.1\)). How far outside of the unit sphere the focal point is.
OUTPUT:
A
Projection
object.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: sch_proj = p.schlegel_projection() sage: schlegel_edge_indices = sch_proj.lines sage: schlegel_edges = [sch_proj.coordinates_of(x) for x in schlegel_edge_indices] sage: len([x for x in schlegel_edges if x[0][0] > 0]) 4
- The polyhedron is translated such that its
-
show
(**kwds)¶ Display graphics immediately
This method attempts to display the graphics immediately, without waiting for the currently running code (if any) to return to the command line. Be careful, calling it from within a loop will potentially launch a large number of external viewer programs.
INPUT:
kwds
– optional keyword arguments. Seeplot()
for the description of available options.
OUTPUT:
This method does not return anything. Use
plot()
if you want to generate a graphics object that can be saved or further transformed.EXAMPLES:
sage: square = polytopes.hypercube(2) sage: square.show(point='red')
-
to_linear_program
(solver=None, return_variable=False, base_ring=None)¶ Return a linear optimization problem over the polyhedron in the form of a
MixedIntegerLinearProgram
.INPUT:
solver
– select a solver (MIP backend). See the documentation of forMixedIntegerLinearProgram
. Set toNone
by default.return_variable
– (default:False
) IfTrue
, return a tuple(p, x)
, wherep
is theMixedIntegerLinearProgram
object andx
is the vector-valued MIP variable in this problem, indexed from 0. IfFalse
, only returnp
.base_ring
– select a field over which the linear program should be set up. UseRDF
to request a fast inexact (floating point) solver even ifself
is exact.
Note that the
MixedIntegerLinearProgram
object will have the null function as an objective to be maximized.See also
polyhedron()
– return the polyhedron associated with aMixedIntegerLinearProgram
object.EXAMPLES:
Exact rational linear program:
sage: p = polytopes.cube() sage: p.to_linear_program() Mixed Integer Program ( maximization, 3 variables, 6 constraints ) sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(2*x[0] + 1*x[1] + 39*x[2]) sage: lp.solve() 42 sage: lp.get_values(x[0], x[1], x[2]) [1, 1, 1]
Floating-point linear program:
sage: lp, x = p.to_linear_program(return_variable=True, base_ring=RDF) sage: lp.set_objective(2*x[0] + 1*x[1] + 39*x[2]) sage: lp.solve() 42.0
Irrational algebraic linear program over an embedded number field:
sage: p=polytopes.icosahedron() sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() 1/4*sqrt5 + 3/4
Same example with floating point:
sage: lp, x = p.to_linear_program(return_variable=True, base_ring=RDF) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # tol 1e-5 1.3090169943749475
Same example with a specific floating point solver:
sage: lp, x = p.to_linear_program(return_variable=True, solver='GLPK') sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # tol 1e-8 1.3090169943749475
Irrational algebraic linear program over \(AA\):
sage: p=polytopes.icosahedron(base_ring=AA) sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() 1.309016994374948?
TESTS:
sage: p=polytopes.flow_polytope(digraphs.DeBruijn(3,2)); p A 19-dimensional polyhedron in QQ^27 defined as the convex hull of 1 vertex and 148 rays sage: p.to_linear_program().polyhedron() == p True sage: p=polytopes.icosahedron() sage: p.to_linear_program(solver='PPL') Traceback (most recent call last): ... TypeError: The PPL backend only supports rational data.
-
translation
(displacement)¶ Return the translated polyhedron.
INPUT:
displacement
– a displacement vector or a list/tuple of coordinates that determines a displacement vector.
OUTPUT:
The translated polyhedron.
EXAMPLES:
sage: P = Polyhedron([[0,0],[1,0],[0,1]], base_ring=ZZ) sage: P.translation([2,1]) A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: P.translation( vector(QQ,[2,1]) ) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices
-
triangulate
(engine='auto', connected=True, fine=False, regular=None, star=None)¶ Returns a triangulation of the polytope.
INPUT:
engine
– either ‘auto’ (default), ‘internal’, or ‘TOPCOM’. The latter two instruct this package to always use its own triangulation algorithms or TOPCOM’s algorithms, respectively. By default (‘auto’), TOPCOM is used if it is available and internal routines otherwise.
The remaining keyword parameters are passed through to the
PointConfiguration
constructor:connected
– boolean (default:True
). Whether the triangulations should be connected to the regular triangulations via bistellar flips. These are much easier to compute than all triangulations.fine
– boolean (default:False
). Whether the triangulations must be fine, that is, make use of all points of the configuration.regular
– boolean orNone
(default:None
). Whether the triangulations must be regular. A regular triangulation is one that is induced by a piecewise-linear convex support function. In other words, the shadows of the faces of a polyhedron in one higher dimension.True
: Only regular triangulations.False
: Only non-regular triangulations.None
(default): Both kinds of triangulation.
star
– eitherNone
(default) or a point. Whether the triangulations must be star. A triangulation is star if all maximal simplices contain a common point. The central point can be specified by its index (an integer) in the given points or by its coordinates (anything iterable.)
OUTPUT:
A triangulation of the convex hull of the vertices as a
Triangulation
. The indices in the triangulation correspond to theVrepresentation()
objects.EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: triangulation = cube.triangulate( ... engine='internal') # to make doctest independent of TOPCOM sage: triangulation (<0,1,2,7>, <0,1,4,7>, <0,2,4,7>, <1,2,3,7>, <1,4,5,7>, <2,4,6,7>) sage: simplex_indices = triangulation[0]; simplex_indices (0, 1, 2, 7) sage: simplex_vertices = [ cube.Vrepresentation(i) for i in simplex_indices ] sage: simplex_vertices [A vertex at (-1, -1, -1), A vertex at (-1, -1, 1), A vertex at (-1, 1, -1), A vertex at (1, 1, 1)] sage: Polyhedron(simplex_vertices) A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
-
vertex_adjacency_matrix
()¶ Return the binary matrix of vertex adjacencies.
EXAMPLES:
sage: polytopes.simplex(4).vertex_adjacency_matrix() [0 1 1 1 1] [1 0 1 1 1] [1 1 0 1 1] [1 1 1 0 1] [1 1 1 1 0]
The rows and columns of the vertex adjacency matrix correspond to the
Vrepresentation()
objects: vertices, rays, and lines. The \((i,j)\) matrix entry equals \(1\) if the \(i\)-th and \(j\)-th V-representation object are adjacent.Two vertices are adjacent if they are the endpoints of an edge, that is, a one-dimensional face. For unbounded polyhedra this clearly needs to be generalized and we define two V-representation objects (see
sage.geometry.polyhedron.constructor
) to be adjacent if they together generate a one-face. There are three possible combinations:- Two vertices can bound a finite-length edge.
- A vertex and a ray can generate a half-infinite edge starting at the vertex and with the direction given by the ray.
- A vertex and a line can generate an infinite edge. The position of the vertex on the line is arbitrary in this case, only its transverse position matters. The direction of the edge is given by the line generator.
For example, take the half-plane:
sage: half_plane = Polyhedron(ieqs=[(0,1,0)]) sage: half_plane.Hrepresentation() (An inequality (1, 0) x + 0 >= 0,)
Its (non-unique) V-representation consists of a vertex, a ray, and a line. The only edge is spanned by the vertex and the line generator, so they are adjacent:
sage: half_plane.Vrepresentation() (A line in the direction (0, 1), A ray in the direction (1, 0), A vertex at (0, 0)) sage: half_plane.vertex_adjacency_matrix() [0 0 1] [0 0 0] [1 0 0]
In one dimension higher, that is for a half-space in 3 dimensions, there is no one-dimensional face. Hence nothing is adjacent:
sage: Polyhedron(ieqs=[(0,1,0,0)]).vertex_adjacency_matrix() [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
EXAMPLES:
In a bounded polygon, every vertex has precisely two adjacent ones:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(P.adjacency_matrix().row(v.index()), v)) (0, 1, 0, 1) A vertex at (0, 1) (1, 0, 1, 0) A vertex at (1, 0) (0, 1, 0, 1) A vertex at (3, 0) (1, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)], ....: rays=[(0,1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(P.adjacency_matrix().row(v.index()), v)) (0, 1, 0, 0, 1) A ray in the direction (0, 1) (1, 0, 1, 0, 0) A vertex at (0, 1) (0, 1, 0, 1, 0) A vertex at (1, 0) (0, 0, 1, 0, 1) A vertex at (3, 0) (1, 0, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two V-representation objects (which can now be vertices or rays). The two rays are not adjacent to each other:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)], ....: rays=[(0,1), (1,1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(P.adjacency_matrix().row(v.index()), v)) (0, 1, 0, 0, 0) A ray in the direction (0, 1) (1, 0, 1, 0, 0) A vertex at (0, 1) (0, 1, 0, 0, 1) A vertex at (1, 0) (0, 0, 0, 0, 1) A ray in the direction (1, 1) (0, 0, 1, 1, 0) A vertex at (3, 0)
-
vertex_digraph
(f, increasing=True)¶ Return the directed graph of the polyhedron according to a linear form.
The underlying undirected graph is the graph of vertices and edges.
INPUT:
f
– a linear form. The linear form can be provided as:- a vector space morphism with one-dimensional codomain, (see
sage.modules.vector_space_morphism.linear_transformation()
andsage.modules.vector_space_morphism.VectorSpaceMorphism
) - a vector ; in this case the linear form is obtained by duality
using the dot product:
f(v) = v.dot_product(f)
.
- a vector space morphism with one-dimensional codomain, (see
increasing
– boolean (defaultTrue
) whether to orient edges in the increasing or decreasing direction.
By default, an edge is oriented from \(v\) to \(w\) if \(f(v) \leq f(w)\).
If \(f(v)=f(w)\), then two opposite edges are created.
EXAMPLES:
sage: penta = Polyhedron([[0,0],[1,0],[0,1],[1,2],[3,2]]) sage: G = penta.vertex_digraph(vector([1,1])); G Digraph on 5 vertices sage: G.sinks() [A vertex at (3, 2)] sage: A = matrix(ZZ, [[1], [-1]]) sage: f = linear_transformation(A) sage: G = penta.vertex_digraph(f) ; G Digraph on 5 vertices sage: G.is_directed_acyclic() False
See also
-
vertex_generator
()¶ Return a generator for the vertices of the polyhedron.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]]) sage: for v in triangle.vertex_generator(): print(v) A vertex at (0, 1) A vertex at (1, 0) A vertex at (1, 1) sage: v_gen = triangle.vertex_generator() sage: next(v_gen) # the first vertex A vertex at (0, 1) sage: next(v_gen) # the second vertex A vertex at (1, 0) sage: next(v_gen) # the third vertex A vertex at (1, 1) sage: try: next(v_gen) # there are only three vertices ....: except StopIteration: print("STOP") STOP sage: type(v_gen) <type 'generator'> sage: [ v for v in triangle.vertex_generator() ] [A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1)]
-
vertex_graph
()¶ Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.
EXAMPLES:
sage: g3 = polytopes.hypercube(3).vertex_graph(); g3 Graph on 8 vertices sage: g3.automorphism_group().cardinality() 48 sage: s4 = polytopes.simplex(4).vertex_graph(); s4 Graph on 5 vertices sage: s4.is_eulerian() True
-
vertices
()¶ Return all vertices of the polyhedron.
OUTPUT:
A tuple of vertices.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]]) sage: triangle.vertices() (A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1)) sage: a_simplex = Polyhedron(ieqs = [ ... [0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1] ... ], eqns = [[1,-1,-1,-1,-1]]) sage: a_simplex.vertices() (A vertex at (1, 0, 0, 0), A vertex at (0, 1, 0, 0), A vertex at (0, 0, 1, 0), A vertex at (0, 0, 0, 1))
-
vertices_list
()¶ Return a list of vertices of the polyhedron.
Note
It is recommended to use
vertex_generator()
instead to iterate over the list ofVertex
objects.EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]]) sage: triangle.vertices_list() [[0, 1], [1, 0], [1, 1]] sage: a_simplex = Polyhedron(ieqs = [ ... [0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1] ... ], eqns = [[1,-1,-1,-1,-1]]) sage: a_simplex.vertices_list() [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]] sage: a_simplex.vertices_list() == [list(v) for v in a_simplex.vertex_generator()] True
-
vertices_matrix
(base_ring=None)¶ Return the coordinates of the vertices as the columns of a matrix.
INPUT:
base_ring
– A ring orNone
(default). The base ring of the returned matrix. If not specified, the base ring of the polyhedron is used.
OUTPUT:
A matrix over
base_ring
whose columns are the coordinates of the vertices. ATypeError
is raised if the coordinates cannot be converted tobase_ring
.EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]]) sage: triangle.vertices_matrix() [0 1 1] [1 0 1] sage: (triangle/2).vertices_matrix() [ 0 1/2 1/2] [1/2 0 1/2] sage: (triangle/2).vertices_matrix(ZZ) Traceback (most recent call last): ... TypeError: no conversion of this rational to integer
-
volume
(engine='auto', **kwds)¶ Return the volume of the polytope.
INPUT:
engine
– string. The backend to use. Allowed values are:'auto'
(default): seetriangulate()
.'internal'
: seetriangulate()
.'TOPCOM'
: seetriangulate()
.'lrs'
: use David Avis’s lrs program (optional).
**kwds
– keyword arguments that are passed to the triangulation engine.
OUTPUT:
The volume of the polytope.
EXAMPLES:
sage: polytopes.hypercube(3).volume() 8 sage: (polytopes.hypercube(3)*2).volume() 64 sage: polytopes.twenty_four_cell().volume() 2
Volume of the same polytopes, using the optional package lrslib (which requires a rational polytope). For mysterious historical reasons, Sage casts lrs’s exact answer to a float:
sage: I3 = polytopes.hypercube(3) sage: I3.volume(engine='lrs') #optional - lrslib 8.0 sage: C24 = polytopes.twenty_four_cell() sage: C24.volume(engine='lrs') #optional - lrslib 2.0
If the base ring is exact, the answer is exact:
sage: P5 = polytopes.regular_polygon(5) sage: P5.volume() 2.377641290737884? sage: polytopes.icosahedron().volume() 5/12*sqrt5 + 5/4 sage: numerical_approx(_) 2.18169499062491
Different engines may have different ideas on the definition of volume of a lower-dimensional object:
sage: I = Polyhedron([(0,0), (1,1)]) sage: I.volume() 0 sage: I.volume(engine='lrs') #optional - lrslib 1.0
-
write_cdd_Hrepresentation
(filename)¶ Export the polyhedron as a H-representation to a file.
INPUT:
filename
– the output file.
See also
cdd_Hrepresentation()
– return the H-representation of the polyhedron as a string.EXAMPLE:
sage: from sage.misc.temporary_file import tmp_filename sage: filename = tmp_filename(ext='.ext') sage: polytopes.cube().write_cdd_Hrepresentation(filename)
-
write_cdd_Vrepresentation
(filename)¶ Export the polyhedron as a V-representation to a file.
INPUT:
filename
– the output file.
See also
cdd_Vrepresentation()
– return the V-representation of the polyhedron as a string.EXAMPLE:
sage: from sage.misc.temporary_file import tmp_filename sage: filename = tmp_filename(ext='.ext') sage: polytopes.cube().write_cdd_Vrepresentation(filename)
-
sage.geometry.polyhedron.base.
is_Polyhedron
(X)¶ Test whether
X
is a Polyhedron.INPUT:
X
– anything.
OUTPUT:
Boolean.
EXAMPLES:
sage: p = polytopes.hypercube(2) sage: from sage.geometry.polyhedron.base import is_Polyhedron sage: is_Polyhedron(p) True sage: is_Polyhedron(123456) False