Finite polyhedral complexes¶
This module implements the basic structure of finite polyhedral complexes.
For more information, see PolyhedralComplex
.
AUTHORS:
Yuan Zhou (202105): initial implementation
List of PolyhedralComplex methods¶
Maximal cells and cells
Return the dictionary of the maximal cells in this polyhedral complex. 

Return an iterator over maximal cells in this polyhedral complex. 

Return the sorted list of all maximal cells in this polyhedral complex. 

List the maximal cells of dimension \(n\) in this polyhedral complex. 


Return the sorted list of maximal cells of dim \(n\) in this complex. 
Return 

Return the dictionary of the cells in this polyhedral complex. 

Return an iterator over cells in this polyhedral complex. 

Return the sorted list of all cells in this polyhedral complex. 

List the cells of dimension \(n\) in this polyhedral complex. 


Return the sorted list of \(n\)cells in this polyhedral complex. 
Return 

Return the poset of nonempty cells in the polyhedral complex. 

List the maximal cells on the boundary of the polyhedral complex. 
Properties of the polyhedral complex
Return the dimension of the polyhedral complex. 

Return the ambient dimension of the polyhedral complex. 

Return 

Return 

Return 

Return 

Return 

Return 

Return 

Return 

Return 

Return 

Return 
New polyhedral complexes from old ones
Return the connected component containing a cell as a subcomplex. 

Return the connected components of this polyhedral complex. 

Return the \(n\)skeleton of this polyhedral complex. 

Return the (pure) subcomplex formed by the maximal cells of dim \(n\) in this complex. 

Return the boundary subcomplex of this polyhedral complex. 

Return the (Cartesian) product of this polyhedral complex with another one. 

Return the disjoint union of this polyhedral complex with another one. 

Return the union of this polyhedral complex with another one. 

Return the join of this polyhedral complex with another one. 

Return a new polyhedral complex (with option 
Update polyhedral complex
Make this polyhedral complex immutable. 

Add a cell to this polyhedral complex. 

Remove a cell from this polyhedral complex. 
Miscellaneous
Return a Graphic object showing the plot of polyhedral complex. 

Return a directed graph corresponding to the 1skeleton of this polyhedral complex, given that it is bounded. 

Return a 
Classes and functions¶
 class sage.geometry.polyhedral_complex.PolyhedralComplex(maximal_cells=None, backend=None, maximality_check=True, face_to_face_check=False, is_mutable=True, is_immutable=False, ambient_dim=None)¶
Bases:
sage.topology.cell_complex.GenericCellComplex
A polyhedral complex.
A polyhedral complex \(PC\) is a collection of polyhedra in a certain ambient space \(\RR^n\) such that the following hold.
If a polyhedron \(P\) is in \(PC\), then all the faces of \(P\) are in \(PC\).
If polyhedra \(P\) and \(Q\) are in \(PC\), then \(P \cap Q\) is either empty or a face of both \(P\) and \(Q\).
In this context, a “polyhedron” means the geometric realization of a polyhedron. This is in contrast to
simplicial complex
, whose cells are abstract simplices. The concept of a polyhedral complex generalizes that of a geometric simplicial complex.Note
This class derives from
GenericCellComplex
, and so inherits its methods. Some of those methods are not listed here; see theGeneric Cell Complex
page instead.INPUT:
maximal_cells
– a list, a tuple, or a dictionary (indexed by dimension) of cells of the Complex. Each cell is of classPolyhedron
of the same ambient dimension. To set up a :class:PolyhedralComplex, it is sufficient to provide the maximal faces. Use keyword argumentpartial=True
to set up a partial polyhedral complex, which is a subset of the faces (viewed as relatively open) of a polyhedral complex that is not necessarily closed under taking intersection.maximality_check
– boolean (default:True
); ifTrue
, then the constructor checks that each given maximal cell is indeed maximal, and ignores those that are notface_to_face_check
– boolean (default:False
); ifTrue
, then the constructor checks whether the cells are facetoface, and it raises aValueError
if they are notis_mutable
andis_immutable
– boolean (default:True
andFalse
respectively); setis_mutable=False
oris_immutable=True
to make this polyhedral complex immutablebackend
– string (optional); the name of the backend used for computations on Sage polyhedra; if it is not given, then each cell has its own backend; otherwise it must be one of the following:'ppl'
 the Parma Polyhedra Library'cdd'
 CDD'normaliz'
 normaliz'polymake'
 polymake'field'
 a generic Sage implementation
ambient_dim
– integer (optional); used to set up an empty complex in the intended ambient space
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1/3, 1/3), (0, 0), (1/7, 2/7)]), ....: Polyhedron(vertices=[(1/7, 2/7), (0, 0), (0, 1/4)])]) sage: [p.Vrepresentation() for p in pc.cells_sorted()] [(A vertex at (0, 0), A vertex at (0, 1/4), A vertex at (1/7, 2/7)), (A vertex at (0, 0), A vertex at (1/3, 1/3), A vertex at (1/7, 2/7)), (A vertex at (0, 0), A vertex at (0, 1/4)), (A vertex at (0, 0), A vertex at (1/7, 2/7)), (A vertex at (0, 0), A vertex at (1/3, 1/3)), (A vertex at (0, 1/4), A vertex at (1/7, 2/7)), (A vertex at (1/3, 1/3), A vertex at (1/7, 2/7)), (A vertex at (0, 0),), (A vertex at (0, 1/4),), (A vertex at (1/7, 2/7),), (A vertex at (1/3, 1/3),)] sage: pc.plot() Graphics object consisting of 10 graphics primitives sage: pc.is_pure() True sage: pc.is_full_dimensional() True sage: pc.is_compact() True sage: pc.boundary_subcomplex() Polyhedral complex with 4 maximal cells sage: pc.is_convex() True sage: pc.union_as_polyhedron().Hrepresentation() (An inequality (1, 4) x + 1 >= 0, An inequality (1, 1) x + 0 >= 0, An inequality (1, 0) x + 0 >= 0) sage: pc.face_poset() Finite poset containing 11 elements sage: pc.is_connected() True sage: pc.connected_component() == pc True
 add_cell(cell)¶
Add a cell to this polyhedral complex.
INPUT:
cell
– a polyhedron
This changes the polyhedral complex, by adding a new cell and all of its subfaces.
EXAMPLES:
Set up an empty complex in the intended ambient space, then add a cell:
sage: pc = PolyhedralComplex(ambient_dim=2) sage: pc.add_cell(Polyhedron(vertices=[(1, 2), (0, 2)])) sage: pc Polyhedral complex with 1 maximal cell
If you add a cell which is already present, there is no effect:
sage: pc.add_cell(Polyhedron(vertices=[(1, 2)])) sage: pc Polyhedral complex with 1 maximal cell sage: pc.dimension() 1
Add a cell and check that dimension is correctly updated:
sage: pc.add_cell(Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])) sage: pc.dimension() 2 sage: pc.maximal_cells() {2: {A 2dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices}} sage: pc.is_convex() True
Add another cell and check that the properties are correctly updated:
sage: pc.add_cell(Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)])) sage: pc Polyhedral complex with 2 maximal cells sage: len(pc._cells[1]) 5 sage: pc._face_poset Finite poset containing 11 elements sage: pc._is_convex True sage: pc._polyhedron.vertices_list() [[0, 0], [0, 2], [1, 1], [1, 2]]
Add a ray which makes the complex non convex:
sage: pc.add_cell(Polyhedron(rays=[(1, 0)])) sage: pc Polyhedral complex with 3 maximal cells sage: len(pc._cells[1]) 6 sage: (pc._is_convex is False) and (pc._polyhedron is None) True
 alexander_whitney(cell, dim_left)¶
The decomposition of
cell
in this complex into left and right factors, suitable for computing cup products.Todo
Implement
alexander_whitney()
of a polyhedral complex.EXAMPLES:
sage: pc = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc.alexander_whitney(None, 1) Traceback (most recent call last): ... NotImplementedError: alexander_whitney is not implemented for polyhedral complex
 ambient_dimension()¶
The ambient dimension of this cell complex: the ambient dimension of each of its cells.
EXAMPLES:
sage: pc = PolyhedralComplex([Polyhedron(vertices=[(1, 2, 3)])]) sage: pc.ambient_dimension() 3 sage: empty_pc = PolyhedralComplex([]) sage: empty_pc.ambient_dimension() 1 sage: pc0 = PolyhedralComplex(ambient_dim=2) sage: pc0.ambient_dimension() 2
 boundary_subcomplex()¶
Return the subpolyhedral complex that is the boundary of
self
.A point \(P\) is on the boundary of a set \(S\) if \(P\) is in the closure of \(S\) but not in the interior of \(S\).
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: bd = PolyhedralComplex([p1, p2]).boundary_subcomplex() sage: len(bd.n_maximal_cells(2)) 0 sage: len(bd.n_maximal_cells(1)) 4 sage: pt = PolyhedralComplex([p3]) sage: pt.boundary_subcomplex() == pt True
Test on polyhedral complex which is not pure:
sage: pc_non_pure = PolyhedralComplex([p1, p3]) sage: pc_non_pure.boundary_subcomplex() == pc_non_pure.n_skeleton(1) True
Test with
maximality_check == False
:sage: pc_invalid = PolyhedralComplex([p2, p3], ....: maximality_check=False) sage: pc_invalid.boundary_subcomplex() == pc_invalid.n_skeleton(1) True
Test unbounded cases:
sage: pc1 = PolyhedralComplex([ ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]])]) sage: pc1.boundary_subcomplex() == pc1.n_skeleton(1) True sage: pc1b = PolyhedralComplex([Polyhedron( ....: vertices=[[1,0,0], [0,1,0]], rays=[[1,0,0],[0,1,0]])]) sage: pc1b.boundary_subcomplex() == pc1b True sage: pc2 = PolyhedralComplex([ ....: Polyhedron(vertices=[[1,0], [1,0]], lines=[[0,1]])]) sage: pc2.boundary_subcomplex() == pc2.n_skeleton(1) True sage: pc3 = PolyhedralComplex([ ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]]), ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]])]) sage: pc3.boundary_subcomplex() == pc3.n_skeleton(1) False
 cell_iterator(increasing=True)¶
An iterator for the cells in this polyhedral complex.
INPUT:
increasing
– (defaultTrue
) ifTrue
, return cells in increasing order of dimension, thus starting with the zerodimensional cells; otherwise it returns cells in decreasing order of dimension
Note
Among the cells of a fixed dimension, there is no sorting.
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])]) sage: len(list(pc.cell_iterator())) 11
 cells(subcomplex=None)¶
The cells of this polyhedral complex, in the form of a dictionary: the keys are integers, representing dimension, and the value associated to an integer \(d\) is the set of \(d\)cells.
INPUT:
subcomplex
– (optional) if a subcomplex is given then return the cells which are not in this subcomplex
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])]) sage: list(pc.cells().keys()) [2, 1, 0]
 cells_sorted(subcomplex=None)¶
The sorted list of the cells of this polyhedral complex in nonincreasing dimensions.
INPUT:
subcomplex
– (optional) if a subcomplex is given then return the cells which are not in this subcomplex
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])]) sage: len(pc.cells_sorted()) 11 sage: pc.cells_sorted()[0].Vrepresentation() (A vertex at (0, 0), A vertex at (0, 2), A vertex at (1, 2))
 chain_complex(subcomplex=None, augmented=False, verbose=False, check=True, dimensions=None, base_ring=Integer Ring, cochain=False)¶
The chain complex associated to this polyhedral complex.
Todo
Implement chain complexes of a polyhedral complex.
EXAMPLES:
sage: pc = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc.chain_complex() Traceback (most recent call last): ... NotImplementedError: chain_complex is not implemented for polyhedral complex
 connected_component(cell=None)¶
Return the connected component of this polyhedral complex containing a given cell.
INPUT:
cell
– (default:self.an_element()
) a cell ofself
OUTPUT:
The connected component containing
cell
. If the polyhedral complex is empty or if it does not contain the given cell, raise an error.EXAMPLES:
sage: t1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: t2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: v1 = Polyhedron(vertices=[(1, 1)]) sage: v2 = Polyhedron(vertices=[(0, 2)]) sage: v3 = Polyhedron(vertices=[(1, 0)]) sage: o = Polyhedron(vertices=[(0, 0)]) sage: r = Polyhedron(rays=[(1, 0)]) sage: l = Polyhedron(vertices=[(1, 0)], lines=[(1, 1)]) sage: pc1 = PolyhedralComplex([t1, t2]) sage: pc1.connected_component() == pc1 True sage: pc1.connected_component(v1) == pc1 True sage: pc2 = PolyhedralComplex([t1, v2]) sage: pc2.connected_component(t1) == PolyhedralComplex([t1]) True sage: pc2.connected_component(o) == PolyhedralComplex([t1]) True sage: pc2.connected_component(v3) Traceback (most recent call last): ... ValueError: the polyhedral complex does not contain the given cell sage: pc2.connected_component(r) Traceback (most recent call last): ... ValueError: the polyhedral complex does not contain the given cell sage: pc3 = PolyhedralComplex([t1, t2, r]) sage: pc3.connected_component(v2) == pc3 True sage: pc4 = PolyhedralComplex([t1, t2, r, l]) sage: pc4.connected_component(o) == pc3 True sage: pc4.connected_component(v3) Traceback (most recent call last): ... ValueError: the polyhedral complex does not contain the given cell sage: pc5 = PolyhedralComplex([t1, t2, r, l, v3]) sage: pc5.connected_component(v3) == PolyhedralComplex([v3]) True sage: PolyhedralComplex([]).connected_component() Traceback (most recent call last): ... ValueError: the empty polyhedral complex has no connected components
 connected_components()¶
Return the connected components of this polyhedral complex, as list of (sub)PolyhedralComplexes.
EXAMPLES:
sage: t1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: t2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: v1 = Polyhedron(vertices=[(1, 1)]) sage: v2 = Polyhedron(vertices=[(0, 2)]) sage: v3 = Polyhedron(vertices=[(1, 0)]) sage: o = Polyhedron(vertices=[(0, 0)]) sage: r = Polyhedron(rays=[(1, 0)]) sage: l = Polyhedron(vertices=[(1, 0)], lines=[(1, 1)]) sage: pc1 = PolyhedralComplex([t1, t2]) sage: len(pc1.connected_components()) 1 sage: pc2 = PolyhedralComplex([t1, v2]) sage: len(pc2.connected_components()) 2 sage: pc3 = PolyhedralComplex([t1, t2, r]) sage: len(pc3.connected_components()) 1 sage: pc4 = PolyhedralComplex([t1, t2, r, l]) sage: len(pc4.connected_components()) 2 sage: pc5 = PolyhedralComplex([t1, t2, r, l, v3]) sage: len(pc5.connected_components()) 3 sage: PolyhedralComplex([]).connected_components() Traceback (most recent call last): ... ValueError: the empty polyhedral complex has no connected components
 dimension()¶
The dimension of this cell complex: the maximum dimension of its cells.
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 2)]) ]) sage: pc.dimension() 2 sage: empty_pc = PolyhedralComplex([]) sage: empty_pc.dimension() 1
 disjoint_union(right)¶
The disjoint union of this polyhedral complex with another one.
INPUT:
right
– the other polyhedral complex (the righthand factor)
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 0), (0, 0), (0, 1)]) sage: p2 = Polyhedron(vertices=[(0, 1), (0, 0), (1, 0)]) sage: p3 = Polyhedron(vertices=[(0, 1), (1, 1), (1, 0)]) sage: pc = PolyhedralComplex([p1]).disjoint_union(PolyhedralComplex([p3])) sage: set(pc.maximal_cell_iterator()) == set([p1, p3]) True sage: pc.disjoint_union(PolyhedralComplex([p2])) Traceback (most recent call last): ... ValueError: the two complexes are not disjoint
 face_poset()¶
The face poset of this polyhedral complex, the poset of nonempty cells, ordered by inclusion.
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1/3, 1/3), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 1/2)])]) sage: poset = pc.face_poset() sage: poset Finite poset containing 11 elements sage: d = {i: i.vertices_matrix() for i in poset} sage: poset.plot(element_labels=d) Graphics object consisting of 28 graphics primitives
For a nonbounded polyhedral complex:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1/3, 1/3), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 1/2)]), ....: Polyhedron(vertices=[(1/2, 1/2)], lines=[(1, 1)]), ....: Polyhedron(rays=[(1, 0)])]) sage: poset = pc.face_poset() sage: poset Finite poset containing 13 elements sage: d = {i:''.join([str(v)+'\n' ....: for v in i.Vrepresentation()]) for i in poset} sage: poset.show(element_labels=d, figsize=15) # not tested sage: pc = PolyhedralComplex([ ....: Polyhedron(rays=[(1,0),(0,1)]), ....: Polyhedron(rays=[(1,0),(0,1)]), ....: Polyhedron(rays=[(1,0),(0,1)]), ....: Polyhedron(rays=[(1,0),(0,1)])]) sage: pc.face_poset() Finite poset containing 9 elements
 graph()¶
The 1skeleton of this polyhedral complex, as a graph.
The vertices of the graph are of type
vector
. Raises aNotImplementedError
if the polyhedral complex is unbounded.Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])]) sage: g = pc.graph(); g Graph on 4 vertices sage: g.vertices() [(0, 0), (0, 2), (1, 1), (1, 2)] sage: g.edges(labels=False) [((0, 0), (0, 2)), ((0, 0), (1, 1)), ((0, 0), (1, 2)), ((0, 2), (1, 2)), ((1, 1), (1, 2))] sage: PolyhedralComplex([Polyhedron(rays=[(1,1)])]).graph() Traceback (most recent call last): ... NotImplementedError: the polyhedral complex is unbounded
Wrong answer due to
maximality_check=False
:sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: PolyhedralComplex([p1, p2]).is_pure() True sage: PolyhedralComplex([p2, p3], maximality_check=True).is_pure() True sage: PolyhedralComplex([p2, p3], maximality_check=False).is_pure() False
 is_cell(c)¶
Return whether the given cell
c
is a cell ofself
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2]) sage: pc.is_cell(p3) True sage: pc.is_cell(Polyhedron(vertices=[(0, 0)])) True
 is_compact()¶
Test for boundedness of the polyhedral complex
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 1/2)]) sage: p2 = Polyhedron(rays=[(1, 0)]) sage: PolyhedralComplex([p1]).is_compact() True sage: PolyhedralComplex([p1, p2]).is_compact() False
 is_connected()¶
Return whether
self
is connected.EXAMPLES:
sage: pc1 = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])]) sage: pc1.is_connected() True sage: pc2 = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(0, 2)])]) sage: pc2.is_connected() False sage: pc3 = PolyhedralComplex([ ....: Polyhedron(vertices=[(1/3, 1/3), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 1/2)]), ....: Polyhedron(vertices=[(1/2, 1/2)], lines=[(1, 1)]), ....: Polyhedron(rays=[(1, 0)])]) sage: pc3.is_connected() False sage: pc4 = PolyhedralComplex([ ....: Polyhedron(vertices=[(1/3, 1/3), (0, 0), (1, 2)]), ....: Polyhedron(rays=[(1, 0)])]) sage: pc4.is_connected() True
 is_convex()¶
Return whether the set of points in
self
is a convex set.When
self
is convex, the union of its cells is a Polyhedron.See also
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(0, 0), (1, 1), (2, 0)]) sage: p4 = Polyhedron(vertices=[(2, 2)]) sage: PolyhedralComplex([p1, p2]).is_convex() True sage: PolyhedralComplex([p1, p3]).is_convex() False sage: PolyhedralComplex([p1, p4]).is_convex() False
Test unbounded cases:
sage: pc1 = PolyhedralComplex([ ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]])]) sage: pc1.is_convex() True sage: pc2 = PolyhedralComplex([ ....: Polyhedron(vertices=[[1,0], [1,0]], lines=[[0,1]])]) sage: pc2.is_convex() True sage: pc3 = PolyhedralComplex([ ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]]), ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]])]) sage: pc3.is_convex() False sage: pc4 = PolyhedralComplex([Polyhedron(rays=[[1,0], [1,1]]), ....: Polyhedron(rays=[[1,0], [1,1]])]) sage: pc4.is_convex() False
The whole 3d space minus the first orthant is not convex:
sage: pc5 = PolyhedralComplex([ ....: Polyhedron(rays=[[1,0,0], [0,1,0], [0,0,1]]), ....: Polyhedron(rays=[[1,0,0], [0,1,0], [0,0,1]]), ....: Polyhedron(rays=[[1,0,0], [0,1,0], [0,0,1]]), ....: Polyhedron(rays=[[1,0,0], [0,1,0], [0,0,1]]), ....: Polyhedron(rays=[[1,0,0], [0,1,0], [0,0,1]]), ....: Polyhedron(rays=[[1,0,0], [0,1,0], [0,0,1]]), ....: Polyhedron(rays=[[1,0,0], [0,1,0], [0,0,1]])]) sage: pc5.is_convex() False
Test some nonfulldimensional examples:
sage: l = PolyhedralComplex([Polyhedron(vertices=[(1, 2), (0, 2)])]) sage: l.is_convex() True sage: pc1b = PolyhedralComplex([Polyhedron( ....: vertices=[[1,0,0], [0,1,0]], rays=[[1,0,0],[0,1,0]])]) sage: pc1b.is_convex() True sage: pc4b = PolyhedralComplex([ ....: Polyhedron(rays=[[1,0,0], [1,1,0]]), ....: Polyhedron(rays=[[1,0,0], [1,1,0]])]) sage: pc4b.is_convex() False
 is_full_dimensional()¶
Return whether this polyhedral complex is fulldimensional: its dimension is equal to its ambient dimension.
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2, p3]) sage: pc.is_full_dimensional() True sage: PolyhedralComplex([p3]).is_full_dimensional() False
 is_immutable()¶
Return whether
self
is immutable.EXAMPLES:
sage: pc1 = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc1.is_immutable() False sage: pc2 = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])], ....: is_mutable=False) sage: pc2.is_immutable() True sage: pc3 = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])], ....: is_immutable=True) sage: pc3.is_immutable() True
 is_maximal_cell(c)¶
Return whether the given cell
c
is a maximal cell ofself
.Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2, p3]) sage: pc.is_maximal_cell(p1) True sage: pc.is_maximal_cell(p3) False
Wrong answer due to
maximality_check=False
:sage: pc_invalid = PolyhedralComplex([p1, p2, p3], ....: maximality_check=False) sage: pc_invalid.is_maximal_cell(p3) True
 is_mutable()¶
Return whether
self
is mutable.EXAMPLES:
sage: pc1 = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc1.is_mutable() True sage: pc2 = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])], ....: is_mutable=False) sage: pc2.is_mutable() False sage: pc1 == pc2 True sage: pc3 = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])], ....: is_immutable=True) sage: pc3.is_mutable() False sage: pc2 == pc3 True
 is_polyhedral_fan()¶
Test if this polyhedral complex is a polyhedral fan.
A polyhedral complex is a fan if all of its (maximal) cells are cones.
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(0, 0), (1, 1), (1, 2)]) sage: p2 = Polyhedron(rays=[(1, 0)]) sage: PolyhedralComplex([p1]).is_polyhedral_fan() False sage: PolyhedralComplex([p2]).is_polyhedral_fan() True sage: halfplane = Polyhedron(rays=[(1, 0), (1, 0), (0, 1)]) sage: PolyhedralComplex([halfplane]).is_polyhedral_fan() True
 is_pure()¶
Test if this polyhedral complex is pure.
A polyhedral complex is pure if and only if all of its maximal cells have the same dimension.
Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2, p3]) sage: pc.is_pure() True
Wrong answer due to
maximality_check=False
:sage: pc_invalid = PolyhedralComplex([p1, p2, p3], ....: maximality_check=False) sage: pc_invalid.is_pure() False
 is_simplicial_complex()¶
Test if this polyhedral complex is a simplicial complex.
A polyhedral complex is simplicial if all of its (maximal) cells are simplices, i.e., every cell is a bounded polytope with \(d+1\) vertices, where \(d\) is the dimension of the polytope.
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(0, 0), (1, 1), (1, 2)]) sage: p2 = Polyhedron(rays=[(1, 0)]) sage: PolyhedralComplex([p1]).is_simplicial_complex() True sage: PolyhedralComplex([p2]).is_simplicial_complex() False
 is_simplicial_fan()¶
Test if this polyhedral complex is a simplicial fan.
A polyhedral complex is a simplicial fan if all of its (maximal) cells are simplical cones, i.e., every cell is a pointed cone (with vertex being the origin) generated by \(d\) linearly independent rays, where \(d\) is the dimension of the cone.
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(0, 0), (1, 1), (1, 2)]) sage: p2 = Polyhedron(rays=[(1, 0)]) sage: PolyhedralComplex([p1]).is_simplicial_fan() False sage: PolyhedralComplex([p2]).is_simplicial_fan() True sage: halfplane = Polyhedron(rays=[(1, 0), (1, 0), (0, 1)]) sage: PolyhedralComplex([halfplane]).is_simplicial_fan() False
 is_subcomplex(other)¶
Return whether
self
is a subcomplex ofother
.INPUT:
other
– a polyhedral complex
Each maximal cell of
self
must be a cell ofother
for this to beTrue
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1/3, 1/3), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 1/2)]) sage: p3 = Polyhedron(vertices=[(0, 0), (1, 0)]) sage: pc = PolyhedralComplex([p1, Polyhedron(vertices=[(1, 0)])]) sage: pc.is_subcomplex(PolyhedralComplex([p1, p2, p3])) True sage: pc.is_subcomplex(PolyhedralComplex([p1, p2])) False
 join(right)¶
The join of this polyhedral complex with another one.
INPUT:
right
– the other polyhedral complex (the righthand factor)
EXAMPLES:
sage: pc = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc_join = pc.join(pc) sage: pc_join Polyhedral complex with 1 maximal cell sage: next(pc_join.maximal_cell_iterator()).vertices() (A vertex at (0, 0, 0), A vertex at (0, 0, 1), A vertex at (0, 1, 1), A vertex at (1, 0, 0))
 maximal_cell_iterator(increasing=False)¶
An iterator for the maximal cells in this polyhedral complex.
INPUT:
increasing
– (optional, defaultFalse
) ifTrue
, return maximal cells in increasing order of dimension. Otherwise it returns cells in decreasing order of dimension.
Note
Among the cells of a fixed dimension, there is no sorting.
Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2, p3]) sage: len(list(pc.maximal_cell_iterator())) 2
Wrong answer due to
maximality_check=False
:sage: pc_invalid = PolyhedralComplex([p1, p2, p3], ....: maximality_check=False) sage: len(list(pc_invalid.maximal_cell_iterator())) 3
 maximal_cells()¶
The maximal cells of this polyhedral complex, in the form of a dictionary: the keys are integers, representing dimension, and the value associated to an integer \(d\) is the set of \(d\)maximal cells.
Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2, p3]) sage: len(pc.maximal_cells()[2]) 2 sage: 1 in pc.maximal_cells() False
Wrong answer due to
maximality_check=False
:sage: pc_invalid = PolyhedralComplex([p1, p2, p3], ....: maximality_check=False) sage: len(pc_invalid.maximal_cells()[1]) 1
 maximal_cells_sorted()¶
Return the sorted list of the maximal cells of this polyhedral complex by nonincreasing dimensions.
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])]) sage: [p.vertices_list() for p in pc.maximal_cells_sorted()] [[[0, 0], [0, 2], [1, 2]], [[0, 0], [1, 1], [1, 2]]]
 n_maximal_cells(n)¶
List of maximal cells of dimension
n
of this polyhedral complex.INPUT:
n
– nonnegative integer; the dimension
Note
The resulting list need not be sorted. If you want a sorted list of \(n\)cells, use
_n_maximal_cells_sorted()
.Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2, p3]) sage: len(pc.n_maximal_cells(2)) 2 sage: len(pc.n_maximal_cells(1)) 0
Wrong answer due to
maximality_check=False
:sage: pc_invalid = PolyhedralComplex([p1, p2, p3], ....: maximality_check=False) sage: len(pc_invalid.n_maximal_cells(1)) 1
 n_skeleton(n)¶
The \(n\)skeleton of this polyhedral complex.
The \(n\)skeleton of a polyhedral complex is obtained by discarding all of the cells in dimensions larger than \(n\).
INPUT:
n
– nonnegative integer; the dimension
See also
EXAMPLES:
sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]), ....: Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)])]) sage: pc.n_skeleton(2) Polyhedral complex with 2 maximal cells sage: pc.n_skeleton(1) Polyhedral complex with 5 maximal cells sage: pc.n_skeleton(0) Polyhedral complex with 4 maximal cells
 plot(**kwds)¶
Return a plot of the polyhedral complex, if it is of dim at most 3.
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2]) sage: pc.plot() Graphics object consisting of 10 graphics primitives
 product(right)¶
The (Cartesian) product of this polyhedral complex with another one.
INPUT:
right
– the other polyhedral complex (the righthand factor)
OUTPUT:
the product
self x right
EXAMPLES:
sage: pc = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc_square = pc.product(pc) sage: pc_square Polyhedral complex with 1 maximal cell sage: next(pc_square.maximal_cell_iterator()).vertices() (A vertex at (0, 0), A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1))
 relative_boundary_cells()¶
Return the maximal cells of the relativeboundary subcomplex.
A point \(P\) is in the relative boundary of a set \(S\) if \(P\) is in the closure of \(S\) but not in the relative interior of \(S\).
Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: p4 = Polyhedron(vertices=[(2, 2)]) sage: pc = PolyhedralComplex([p1, p2]) sage: rbd_cells = pc.relative_boundary_cells() sage: len(rbd_cells) 4 sage: all(p.dimension() == 1 for p in rbd_cells) True sage: pc_lower_dim = PolyhedralComplex([p3]) sage: sorted([p.vertices() for p in pc_lower_dim.relative_boundary_cells()]) [(A vertex at (0, 2),), (A vertex at (1, 2),)]
Test on polyhedral complex which is not pure:
sage: pc_non_pure = PolyhedralComplex([p1, p3, p4]) sage: (set(pc_non_pure.relative_boundary_cells()) ....: == set([f.as_polyhedron() for f in p1.faces(1)] + [p3, p4])) True
Test with
maximality_check == False
:sage: pc_invalid = PolyhedralComplex([p2, p3], ....: maximality_check=False) sage: (set(pc_invalid.relative_boundary_cells()) ....: == set([f.as_polyhedron() for f in p2.faces(1)])) True
Test unbounded case:
sage: pc3 = PolyhedralComplex([ ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]]), ....: Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,0], [0,1]])]) sage: len(pc3.relative_boundary_cells()) 4
 remove_cell(cell, check=False)¶
Remove
cell
fromself
and all the cells that containcell
as a subface.INPUT:
cell
– a cell of the polyhedral complexcheck
– boolean (default:False
); ifTrue
, raise an error ifcell
is not a cell of this complex
This does not return anything; instead, it changes the polyhedral complex.
EXAMPLES:
If you add a cell which is already present, there is no effect:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: r = Polyhedron(rays=[(1, 0)]) sage: pc = PolyhedralComplex([p1, p2, r]) sage: pc.dimension() 2 sage: pc.remove_cell(Polyhedron(vertices=[(0, 0), (1, 2)])) sage: pc.dimension() 1 sage: pc Polyhedral complex with 5 maximal cells sage: pc.remove_cell(Polyhedron(vertices=[(1, 2)])) sage: pc.dimension() 1 sage: pc Polyhedral complex with 3 maximal cells sage: pc.remove_cell(Polyhedron(vertices=[(0, 0)])) sage: pc.dimension() 0
 set_immutable()¶
Make this polyhedral complex immutable.
EXAMPLES:
sage: pc = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc.is_mutable() True sage: pc.set_immutable() sage: pc.is_mutable() False
 stratify(n)¶
Return the pure subpolyhedral complex which is constructed from the \(n\)dimensional maximal cells of this polyhedral complex.
See also
Warning
This may give the wrong answer if the polyhedral complex was constructed with
maximality_check
set toFalse
.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(1, 2), (0, 2)]) sage: pc = PolyhedralComplex([p1, p2, p3]) sage: pc.stratify(2) == pc True sage: pc.stratify(1) Polyhedral complex with 0 maximal cells
Wrong answer due to
maximality_check=False
:sage: pc_invalid = PolyhedralComplex([p1, p2, p3], ....: maximality_check=False) sage: pc_invalid.stratify(1) Polyhedral complex with 1 maximal cell
 subdivide(make_simplicial=False, new_vertices=None, new_rays=None)¶
Construct a new polyhedral complex by iterative stellar subdivision of
self
for each new vertex/ray given.Currently, subdivision is only supported for bounded polyhedral complex or polyhedral fan.
INPUT:
make_simplicial
– boolean (default:False
); ifTrue
, the returned polyhedral complex is simplicialnew_vertices
,new_rays
– list (optional); new generators to be added during subdivision
EXAMPLES:
sage: square_vertices = [(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)] sage: pc = PolyhedralComplex([ ....: Polyhedron(vertices=[(0, 0, 0)] + square_vertices), ....: Polyhedron(vertices=[(0, 0, 2)] + square_vertices)]) sage: pc.is_compact() and not pc.is_simplicial_complex() True sage: subdivided_pc = pc.subdivide(new_vertices=[(0, 0, 1)]) sage: subdivided_pc Polyhedral complex with 8 maximal cells sage: subdivided_pc.is_simplicial_complex() True sage: simplicial_pc = pc.subdivide(make_simplicial=True) sage: simplicial_pc Polyhedral complex with 4 maximal cells sage: simplicial_pc.is_simplicial_complex() True sage: fan = PolyhedralComplex([Polyhedron(rays=square_vertices)]) sage: fan.is_polyhedral_fan() and not fan.is_simplicial_fan() True sage: fan.subdivide(new_vertices=[(0, 0, 1)]) Traceback (most recent call last): ... ValueError: new vertices cannot be used for subdivision sage: subdivided_fan = fan.subdivide(new_rays=[(0, 0, 1)]) sage: subdivided_fan Polyhedral complex with 4 maximal cells sage: subdivided_fan.is_simplicial_fan() True sage: simplicial_fan = fan.subdivide(make_simplicial=True) sage: simplicial_fan Polyhedral complex with 2 maximal cells sage: simplicial_fan.is_simplicial_fan() True sage: halfspace = PolyhedralComplex([Polyhedron(rays=[(0, 0, 1)], ....: lines=[(1, 0, 0), (0, 1, 0)])]) sage: halfspace.is_simplicial_fan() False sage: subdiv_halfspace = halfspace.subdivide(make_simplicial=True) sage: subdiv_halfspace Polyhedral complex with 4 maximal cells sage: subdiv_halfspace.is_simplicial_fan() True
 union(right)¶
The union of this polyhedral complex with another one.
INPUT:
right
– the other polyhedral complex (the righthand factor)
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 0), (0, 0), (0, 1)]) sage: p2 = Polyhedron(vertices=[(0, 1), (0, 0), (1, 0)]) sage: p3 = Polyhedron(vertices=[(0, 1), (1, 1), (1, 0)]) sage: pc = PolyhedralComplex([p1]).union(PolyhedralComplex([p3])) sage: set(pc.maximal_cell_iterator()) == set([p1, p3]) True sage: pc.union(PolyhedralComplex([p2])) Polyhedral complex with 3 maximal cells sage: p4 = Polyhedron(vertices=[(0, 1), (0, 0), (1, 0), (1, 1)]) sage: pc.union(PolyhedralComplex([p4])) Traceback (most recent call last): ... ValueError: the given cells are not facetoface
 union_as_polyhedron()¶
Return
self
as aPolyhedron
ifself
is convex.EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 2), (0, 0), (0, 2)]) sage: p3 = Polyhedron(vertices=[(0, 0), (1, 1), (2, 0)]) sage: P = PolyhedralComplex([p1, p2]).union_as_polyhedron() sage: P.vertices_list() [[0, 0], [0, 2], [1, 1], [1, 2]] sage: PolyhedralComplex([p1, p3]).union_as_polyhedron() Traceback (most recent call last): ... ValueError: the polyhedral complex is not convex
 wedge(right)¶
The wedge (onepoint union) of
self
withright
.Todo
Implement the wedge product of two polyhedral complexes.
EXAMPLES:
sage: pc = PolyhedralComplex([Polyhedron(vertices=[[0], [1]])]) sage: pc.wedge(pc) Traceback (most recent call last): ... NotImplementedError: wedge is not implemented for polyhedral complex
 sage.geometry.polyhedral_complex.cells_list_to_cells_dict(cells_list)¶
Helper function that returns the dictionary whose keys are the dimensions, and the value associated to an integer \(d\) is the set of \(d\)dimensional polyhedra in the given list.
EXAMPLES:
sage: p1 = Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)]) sage: p2 = Polyhedron(vertices=[(1, 1), (0, 0)]) sage: p3 = Polyhedron(vertices=[(0, 0)]) sage: p4 = Polyhedron(vertices=[(1, 1)]) sage: sage.geometry.polyhedral_complex.cells_list_to_cells_dict([p1, p2, p3, p4]) {0: {A 0dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex, A 0dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex}, 1: {A 1dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices}, 2: {A 2dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices}}