Finite polyhedral complexes

This module implements the basic structure of finite polyhedral complexes. For more information, see PolyhedralComplex.

AUTHORS:

• Yuan Zhou (2021-05): initial implementation

List of PolyhedralComplex methods

Maximal cells and cells

maximal_cells()	Return the dictionary of the maximal cells in this polyhedral complex.
maximal_cell_iterator()	Return an iterator over maximal cells in this polyhedral complex.
maximal_cells_sorted()	Return the sorted list of all maximal cells in this polyhedral complex.
n_maximal_cells()	List the maximal cells of dimension \(n\) in this polyhedral complex.
_n_maximal_cells_sorted()	Return the sorted list of maximal cells of dim \(n\) in this complex.
is_maximal_cell()	Return True if the given cell is a maximal cell in this complex.
cells()	Return the dictionary of the cells in this polyhedral complex.
cell_iterator()	Return an iterator over cells in this polyhedral complex.
cells_sorted()	Return the sorted list of all cells in this polyhedral complex.
n_cells()	List the cells of dimension \(n\) in this polyhedral complex.
_n_cells_sorted()	Return the sorted list of \(n\)-cells in this polyhedral complex.
is_cell()	Return True if the given cell is in this polyhedral complex.
face_poset()	Return the poset of nonempty cells in the polyhedral complex.
relative_boundary_cells()	List the maximal cells on the boundary of the polyhedral complex.

Properties of the polyhedral complex

dimension()	Return the dimension of the polyhedral complex.
ambient_dimension()	Return the ambient dimension of the polyhedral complex.
is_pure()	Return True if the polyhedral complex is pure.
is_full_dimensional()	Return True if the polyhedral complex is full dimensional.
is_compact()	Return True if the polyhedral complex is bounded.
is_connected()	Return True if the polyhedral complex is connected.
is_subcomplex()	Return True if this complex is a subcomplex of the other.
is_convex()	Return True if the polyhedral complex is convex.
is_mutable()	Return True if the polyhedral complex is mutable.
is_immutable()	Return True if the polyhedral complex is not mutable.
is_simplicial_complex()	Return True if the polyhedral complex is a simplicial complex.
is_polyhedral_fan()	Return True if the polyhedral complex is a fan.
is_simplicial_fan()	Return True if the polyhedral complex is a simplicial fan.

New polyhedral complexes from old ones

connected_component()	Return the connected component containing a cell as a subcomplex.
connected_components()	Return the connected components of this polyhedral complex.
n_skeleton()	Return the \(n\)-skeleton of this polyhedral complex.
stratify()	Return the (pure) subcomplex formed by the maximal cells of dim \(n\) in this complex.
boundary_subcomplex()	Return the boundary subcomplex of this polyhedral complex.
product()	Return the (Cartesian) product of this polyhedral complex with another one.
disjoint_union()	Return the disjoint union of this polyhedral complex with another one.
union()	Return the union of this polyhedral complex with another one.
join()	Return the join of this polyhedral complex with another one.
subdivide()	Return a new polyhedral complex (with option make_simplicial) subdividing this one.

Update polyhedral complex

set_immutable()	Make this polyhedral complex immutable.
add_cell()	Add a cell to this polyhedral complex.
remove_cell()	Remove a cell from this polyhedral complex.

Miscellaneous

plot()	Return a Graphic object showing the plot of polyhedral complex.
graph()	Return a directed graph corresponding to the 1-skeleton of this polyhedral complex, given that it is bounded.
union_as_polyhedron()	Return a Polyhedron which is the union of cells in this polyhedral complex, given that it is convex.

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 the Generic 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 class Polyhedron of the same ambient dimension. To set up a :class:PolyhedralComplex, it is sufficient to provide the maximal faces. Use keyword argument partial=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); if True, then the constructor checks that each given maximal cell is indeed maximal, and ignores those that are not

• face_to_face_check – boolean (default: False); if True, then the constructor checks whether the cells are face-to-face, and it raises a ValueError if they are not

• is_mutable and is_immutable – boolean (default: True and False respectively); set is_mutable=False or is_immutable=True to make this polyhedral complex immutable

• backend – 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 2-dimensional 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 sub-polyhedral 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 – (default True) if True, return cells in increasing order of dimension, thus starting with the zero-dimensional 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 non-increasing 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 of self

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 right-hand 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 1-skeleton of this polyhedral complex, as a graph.

The vertices of the graph are of type vector. Raises a NotImplementedError if the polyhedral complex is unbounded.

Warning

This may give the wrong answer if the polyhedral complex was constructed with maximality_check set to False.

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 of self.

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

union_as_polyhedron()

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 non-full-dimensional 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 full-dimensional: 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 of self.

Warning

This may give the wrong answer if the polyhedral complex was constructed with maximality_check set to False.

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 to False.

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 of other.

INPUT:

• other – a polyhedral complex

Each maximal cell of self must be a cell of other for this to be True.

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 right-hand 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, default False) if True, 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 to False.

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 to False.

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 non-increasing 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 – non-negative 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 to False.

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 – non-negative integer; the dimension

See also

stratify()

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 right-hand 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 relative-boundary sub-complex.

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 to False.

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 from self and all the cells that contain cell as a subface.

INPUT:

• cell – a cell of the polyhedral complex

• check – boolean (default: False); if True, raise an error if cell 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 sub-polyhedral complex which is constructed from the \(n\)-dimensional maximal cells of this polyhedral complex.

See also

n_skeleton()

Warning

This may give the wrong answer if the polyhedral complex was constructed with maximality_check set to False.

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); if True, the returned polyhedral complex is simplicial

• new_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 right-hand 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 face-to-face

union_as_polyhedron()

Return self as a Polyhedron if self 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 (one-point union) of self with right.

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 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex,
  A 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex},
 1: {A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices},
 2: {A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices}}