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)[source]#

Bases: 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

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()                                                                 # needs sage.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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1)/Integer(3), Integer(1)/Integer(3)), (Integer(0), Integer(0)), (Integer(1)/Integer(7), Integer(2)/Integer(7))]),
...         Polyhedron(vertices=[(Integer(1)/Integer(7), Integer(2)/Integer(7)), (Integer(0), Integer(0)), (Integer(0), Integer(1)/Integer(4))])])
>>> [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),)]
>>> pc.plot()                                                                 # needs sage.plot
Graphics object consisting of 10 graphics primitives
>>> pc.is_pure()
True
>>> pc.is_full_dimensional()
True
>>> pc.is_compact()
True
>>> pc.boundary_subcomplex()
Polyhedral complex with 4 maximal cells
>>> pc.is_convex()
True
>>> 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)
>>> pc.face_poset()
Finite poset containing 11 elements
>>> pc.is_connected()
True
>>> pc.connected_component() == pc
True

add_cell(cell)[source]#

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

sage: pc = PolyhedralComplex(ambient_dim=2)
sage: pc.add_cell(Polyhedron(vertices=[(1, 2), (0, 2)]))
sage: pc
Polyhedral complex with 1 maximal cell

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex(ambient_dim=Integer(2))
>>> pc.add_cell(Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))]))
>>> pc
Polyhedral complex with 1 maximal cell

If you add a cell which is already present, there is no effect:

Sage

sage: pc.add_cell(Polyhedron(vertices=[(1, 2)]))
sage: pc
Polyhedral complex with 1 maximal cell
sage: pc.dimension()
1

Python

>>> from sage.all import *
>>> pc.add_cell(Polyhedron(vertices=[(Integer(1), Integer(2))]))
>>> pc
Polyhedral complex with 1 maximal cell
>>> pc.dimension()
1

Add a cell and check that dimension is correctly updated:

Sage

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

Python

>>> from sage.all import *
>>> pc.add_cell(Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))]))
>>> pc.dimension()
2
>>> pc.maximal_cells()
{2: {A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices}}
>>> pc.is_convex()
True

Add another cell and check that the properties are correctly updated:

Sage

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]]

Python

>>> from sage.all import *
>>> pc.add_cell(Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]))
>>> pc
Polyhedral complex with 2 maximal cells
>>> len(pc._cells[Integer(1)])
5
>>> pc._face_poset
Finite poset containing 11 elements
>>> pc._is_convex
True
>>> pc._polyhedron.vertices_list()
[[0, 0], [0, 2], [1, 1], [1, 2]]

Add a ray which makes the complex non convex:

Sage

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

Python

>>> from sage.all import *
>>> pc.add_cell(Polyhedron(rays=[(Integer(1), Integer(0))]))
>>> pc
Polyhedral complex with 3 maximal cells
>>> len(pc._cells[Integer(1)])
6
>>> (pc._is_convex is False) and (pc._polyhedron is None)
True

alexander_whitney(cell, dim_left)[source]#

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

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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])])
>>> pc.alexander_whitney(None, Integer(1))
Traceback (most recent call last):
...
NotImplementedError: alexander_whitney is not implemented for polyhedral complex

ambient_dimension()[source]#

The ambient dimension of this cell complex: the ambient dimension of each of its cells.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([Polyhedron(vertices=[(Integer(1), Integer(2), Integer(3))])])
>>> pc.ambient_dimension()
3
>>> empty_pc = PolyhedralComplex([])
>>> empty_pc.ambient_dimension()
-1
>>> pc0 = PolyhedralComplex(ambient_dim=Integer(2))
>>> pc0.ambient_dimension()
2

boundary_subcomplex()[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> bd = PolyhedralComplex([p1, p2]).boundary_subcomplex()
>>> len(bd.n_maximal_cells(Integer(2)))
0
>>> len(bd.n_maximal_cells(Integer(1)))
4
>>> pt = PolyhedralComplex([p3])
>>> pt.boundary_subcomplex() == pt
True

Test on polyhedral complex which is not pure:

Sage

sage: pc_non_pure = PolyhedralComplex([p1, p3])
sage: pc_non_pure.boundary_subcomplex() == pc_non_pure.n_skeleton(1)
True

Python

>>> from sage.all import *
>>> pc_non_pure = PolyhedralComplex([p1, p3])
>>> pc_non_pure.boundary_subcomplex() == pc_non_pure.n_skeleton(Integer(1))
True

Test with maximality_check == False:

Sage

sage: pc_invalid = PolyhedralComplex([p2, p3],
....:                                maximality_check=False)
sage: pc_invalid.boundary_subcomplex() == pc_invalid.n_skeleton(1)
True

Python

>>> from sage.all import *
>>> pc_invalid = PolyhedralComplex([p2, p3],
...                                maximality_check=False)
>>> pc_invalid.boundary_subcomplex() == pc_invalid.n_skeleton(Integer(1))
True

Test unbounded cases:

Sage

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

Python

>>> from sage.all import *
>>> pc1 = PolyhedralComplex([
...         Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]], rays=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]])])
>>> pc1.boundary_subcomplex() == pc1.n_skeleton(Integer(1))
True
>>> pc1b = PolyhedralComplex([Polyhedron(
...         vertices=[[Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(1),Integer(0)]], rays=[[Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)]])])
>>> pc1b.boundary_subcomplex() == pc1b
True
>>> pc2 = PolyhedralComplex([
...         Polyhedron(vertices=[[-Integer(1),Integer(0)], [Integer(1),Integer(0)]], lines=[[Integer(0),Integer(1)]])])
>>> pc2.boundary_subcomplex() == pc2.n_skeleton(Integer(1))
True
>>> pc3 = PolyhedralComplex([
...         Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]], rays=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]]),
...         Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),-Integer(1)]], rays=[[Integer(1),Integer(0)], [Integer(0),-Integer(1)]])])
>>> pc3.boundary_subcomplex() == pc3.n_skeleton(Integer(1))
False

cell_iterator(increasing=True)[source]#

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

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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])])
>>> len(list(pc.cell_iterator()))
11

cells(subcomplex=None)[source]#

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

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]

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])])
>>> list(pc.cells().keys())
[2, 1, 0]

cells_sorted(subcomplex=None)[source]#

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

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))

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
... Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
... Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])])
>>> len(pc.cells_sorted())
11
>>> pc.cells_sorted()[Integer(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)[source]#

The chain complex associated to this polyhedral complex.

Todo

Implement chain complexes of a polyhedral complex.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])])
>>> pc.chain_complex()
Traceback (most recent call last):
...
NotImplementedError: chain_complex is not implemented for polyhedral complex

connected_component(cell=None)[source]#

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

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

Python

>>> from sage.all import *
>>> t1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> t2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> v1 = Polyhedron(vertices=[(Integer(1), Integer(1))])
>>> v2 = Polyhedron(vertices=[(Integer(0), Integer(2))])
>>> v3 = Polyhedron(vertices=[(-Integer(1), Integer(0))])
>>> o =  Polyhedron(vertices=[(Integer(0), Integer(0))])
>>> r = Polyhedron(rays=[(Integer(1), Integer(0))])
>>> l = Polyhedron(vertices=[(-Integer(1), Integer(0))], lines=[(Integer(1), -Integer(1))])
>>> pc1 = PolyhedralComplex([t1, t2])
>>> pc1.connected_component() == pc1
True
>>> pc1.connected_component(v1) == pc1
True
>>> pc2 = PolyhedralComplex([t1, v2])
>>> pc2.connected_component(t1) == PolyhedralComplex([t1])
True
>>> pc2.connected_component(o) == PolyhedralComplex([t1])
True
>>> pc2.connected_component(v3)
Traceback (most recent call last):
...
ValueError: the polyhedral complex does not contain the given cell
>>> pc2.connected_component(r)
Traceback (most recent call last):
...
ValueError: the polyhedral complex does not contain the given cell
>>> pc3 = PolyhedralComplex([t1, t2, r])
>>> pc3.connected_component(v2) == pc3
True
>>> pc4 = PolyhedralComplex([t1, t2, r, l])
>>> pc4.connected_component(o) == pc3
True
>>> pc4.connected_component(v3)
Traceback (most recent call last):
...
ValueError: the polyhedral complex does not contain the given cell
>>> pc5 = PolyhedralComplex([t1, t2, r, l, v3])
>>> pc5.connected_component(v3) == PolyhedralComplex([v3])
True
>>> PolyhedralComplex([]).connected_component()
Traceback (most recent call last):
...
ValueError: the empty polyhedral complex has no connected components

connected_components()[source]#

Return the connected components of this polyhedral complex, as list of (sub-)PolyhedralComplexes.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> t1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> t2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> v1 = Polyhedron(vertices=[(Integer(1), Integer(1))])
>>> v2 = Polyhedron(vertices=[(Integer(0), Integer(2))])
>>> v3 = Polyhedron(vertices=[(-Integer(1), Integer(0))])
>>> o =  Polyhedron(vertices=[(Integer(0), Integer(0))])
>>> r = Polyhedron(rays=[(Integer(1), Integer(0))])
>>> l = Polyhedron(vertices=[(-Integer(1), Integer(0))], lines=[(Integer(1), -Integer(1))])
>>> pc1 = PolyhedralComplex([t1, t2])
>>> len(pc1.connected_components())
1
>>> pc2 = PolyhedralComplex([t1, v2])
>>> len(pc2.connected_components())
2
>>> pc3 = PolyhedralComplex([t1, t2, r])
>>> len(pc3.connected_components())
1
>>> pc4 = PolyhedralComplex([t1, t2, r, l])
>>> len(pc4.connected_components())
2
>>> pc5 = PolyhedralComplex([t1, t2, r, l, v3])
>>> len(pc5.connected_components())
3
>>> PolyhedralComplex([]).connected_components()
Traceback (most recent call last):
...
ValueError: the empty polyhedral complex has no connected components

dimension()[source]#

The dimension of this cell complex: the maximum dimension of its cells.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))]) ])
>>> pc.dimension()
2
>>> empty_pc = PolyhedralComplex([])
>>> empty_pc.dimension()
-1

disjoint_union(right)[source]#

The disjoint union of this polyhedral complex with another one.

INPUT:

right – the other polyhedral complex (the right-hand factor)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(-Integer(1), Integer(0)), (Integer(0), Integer(0)), (Integer(0), Integer(1))])
>>> p2 = Polyhedron(vertices=[(Integer(0), -Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(0))])
>>> p3 = Polyhedron(vertices=[(Integer(0), -Integer(1)), (Integer(1), -Integer(1)), (Integer(1), Integer(0))])
>>> pc = PolyhedralComplex([p1]).disjoint_union(PolyhedralComplex([p3]))
>>> set(pc.maximal_cell_iterator()) == set([p1, p3])
True
>>> pc.disjoint_union(PolyhedralComplex([p2]))
Traceback (most recent call last):
...
ValueError: the two complexes are not disjoint

face_poset()[source]#

The face poset of this polyhedral complex, the poset of nonempty cells, ordered by inclusion.

EXAMPLES:

Sage

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)                                          # needs sage.plot
Graphics object consisting of 28 graphics primitives

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1)/Integer(3), Integer(1)/Integer(3)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(1)/Integer(2))])])
>>> poset = pc.face_poset()
>>> poset
Finite poset containing 11 elements
>>> d = {i: i.vertices_matrix() for i in poset}
>>> poset.plot(element_labels=d)                                          # needs sage.plot
Graphics object consisting of 28 graphics primitives

For a nonbounded polyhedral complex:

Sage

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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1)/Integer(3), Integer(1)/Integer(3)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(1)/Integer(2))]),
...         Polyhedron(vertices=[(-Integer(1)/Integer(2), -Integer(1)/Integer(2))], lines=[(Integer(1), -Integer(1))]),
...         Polyhedron(rays=[(Integer(1), Integer(0))])])
>>> poset = pc.face_poset()
>>> poset
Finite poset containing 13 elements
>>> d = {i:''.join([str(v)+'\n'
...      for v in i.Vrepresentation()]) for i in poset}
>>> poset.show(element_labels=d, figsize=Integer(15))        # not tested
>>> pc = PolyhedralComplex([
... Polyhedron(rays=[(Integer(1),Integer(0)),(Integer(0),Integer(1))]),
... Polyhedron(rays=[(-Integer(1),Integer(0)),(Integer(0),Integer(1))]),
... Polyhedron(rays=[(-Integer(1),Integer(0)),(Integer(0),-Integer(1))]),
... Polyhedron(rays=[(Integer(1),Integer(0)),(Integer(0),-Integer(1))])])
>>> pc.face_poset()
Finite poset containing 9 elements

graph()[source]#

Return the 1-skeleton of this polyhedral complex, as a graph.

The vertices of the graph are of type vector. This 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

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(sort=True)
[(0, 0), (0, 2), (1, 1), (1, 2)]
sage: g.edges(sort=True, 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

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])])
>>> g = pc.graph(); g
Graph on 4 vertices
>>> g.vertices(sort=True)
[(0, 0), (0, 2), (1, 1), (1, 2)]
>>> g.edges(sort=True, labels=False)
[((0, 0), (0, 2)), ((0, 0), (1, 1)), ((0, 0), (1, 2)), ((0, 2), (1, 2)), ((1, 1), (1, 2))]
>>> PolyhedralComplex([Polyhedron(rays=[(Integer(1),Integer(1))])]).graph()
Traceback (most recent call last):
...
NotImplementedError: the polyhedral complex is unbounded

Wrong answer due to maximality_check=False:

Sage

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> PolyhedralComplex([p1, p2]).is_pure()
True
>>> PolyhedralComplex([p2, p3], maximality_check=True).is_pure()
True
>>> PolyhedralComplex([p2, p3], maximality_check=False).is_pure()
False

is_cell(c)[source]#

Return whether the given cell c is a cell of self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> pc = PolyhedralComplex([p1, p2])
>>> pc.is_cell(p3)
True
>>> pc.is_cell(Polyhedron(vertices=[(Integer(0), Integer(0))]))
True

is_compact()[source]#

Test for boundedness of the polyhedral complex

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(1)/Integer(2))])
>>> p2 = Polyhedron(rays=[(Integer(1), Integer(0))])
>>> PolyhedralComplex([p1]).is_compact()
True
>>> PolyhedralComplex([p1, p2]).is_compact()
False

is_connected()[source]#

Return whether self is connected.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> pc1 = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])])
>>> pc1.is_connected()
True
>>> pc2 = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(0), Integer(2))])])
>>> pc2.is_connected()
False
>>> pc3 = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1)/Integer(3), Integer(1)/Integer(3)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(1)/Integer(2))]),
...         Polyhedron(vertices=[(-Integer(1)/Integer(2), -Integer(1)/Integer(2))], lines=[(Integer(1), -Integer(1))]),
...         Polyhedron(rays=[(Integer(1), Integer(0))])])
>>> pc3.is_connected()
False
>>> pc4 = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1)/Integer(3), Integer(1)/Integer(3)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(rays=[(Integer(1), Integer(0))])])
>>> pc4.is_connected()
True

is_convex()[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(0), Integer(0)), (Integer(1), Integer(1)), (Integer(2), Integer(0))])
>>> p4 = Polyhedron(vertices=[(Integer(2), Integer(2))])
>>> PolyhedralComplex([p1, p2]).is_convex()
True
>>> PolyhedralComplex([p1, p3]).is_convex()
False
>>> PolyhedralComplex([p1, p4]).is_convex()
False

Test unbounded cases:

Sage

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

Python

>>> from sage.all import *
>>> pc1 = PolyhedralComplex([
...         Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]], rays=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]])])
>>> pc1.is_convex()
True
>>> pc2 = PolyhedralComplex([
...         Polyhedron(vertices=[[-Integer(1),Integer(0)], [Integer(1),Integer(0)]], lines=[[Integer(0),Integer(1)]])])
>>> pc2.is_convex()
True
>>> pc3 = PolyhedralComplex([
...         Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]], rays=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]]),
...         Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),-Integer(1)]], rays=[[Integer(1),Integer(0)], [Integer(0),-Integer(1)]])])
>>> pc3.is_convex()
False
>>> pc4 = PolyhedralComplex([Polyhedron(rays=[[Integer(1),Integer(0)], [-Integer(1),Integer(1)]]),
...                          Polyhedron(rays=[[Integer(1),Integer(0)], [-Integer(1),-Integer(1)]])])
>>> pc4.is_convex()
False

The whole 3d space minus the first orthant is not convex:

Sage

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

Python

>>> from sage.all import *
>>> pc5 = PolyhedralComplex([
...         Polyhedron(rays=[[Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(1),Integer(0)], [Integer(0),Integer(0),-Integer(1)]]),
...         Polyhedron(rays=[[Integer(1),Integer(0),Integer(0)], [Integer(0),-Integer(1),Integer(0)], [Integer(0),Integer(0),-Integer(1)]]),
...         Polyhedron(rays=[[Integer(1),Integer(0),Integer(0)], [Integer(0),-Integer(1),Integer(0)], [Integer(0),Integer(0),Integer(1)]]),
...         Polyhedron(rays=[[-Integer(1),Integer(0),Integer(0)], [Integer(0),-Integer(1),Integer(0)], [Integer(0),Integer(0),-Integer(1)]]),
...         Polyhedron(rays=[[-Integer(1),Integer(0),Integer(0)], [Integer(0),-Integer(1),Integer(0)], [Integer(0),Integer(0),Integer(1)]]),
...         Polyhedron(rays=[[-Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(1),Integer(0)], [Integer(0),Integer(0),-Integer(1)]]),
...         Polyhedron(rays=[[-Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(1),Integer(0)], [Integer(0),Integer(0),Integer(1)]])])
>>> pc5.is_convex()
False

Test some non-full-dimensional examples:

Sage

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

Python

>>> from sage.all import *
>>> l = PolyhedralComplex([Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])])
>>> l.is_convex()
True
>>> pc1b = PolyhedralComplex([Polyhedron(
...         vertices=[[Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(1),Integer(0)]], rays=[[Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)]])])
>>> pc1b.is_convex()
True
>>> pc4b = PolyhedralComplex([
...         Polyhedron(rays=[[Integer(1),Integer(0),Integer(0)], [-Integer(1),Integer(1),Integer(0)]]),
...         Polyhedron(rays=[[Integer(1),Integer(0),Integer(0)], [-Integer(1),-Integer(1),Integer(0)]])])
>>> pc4b.is_convex()
False

is_full_dimensional()[source]#

Return whether this polyhedral complex is full-dimensional: its dimension is equal to its ambient dimension.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> pc = PolyhedralComplex([p1, p2, p3])
>>> pc.is_full_dimensional()
True
>>> PolyhedralComplex([p3]).is_full_dimensional()
False

is_immutable()[source]#

Return whether self is immutable.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> pc1 = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])])
>>> pc1.is_immutable()
False
>>> pc2 = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])],
...                        is_mutable=False)
>>> pc2.is_immutable()
True
>>> pc3 = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])],
...                        is_immutable=True)
>>> pc3.is_immutable()
True

is_maximal_cell(c)[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> pc = PolyhedralComplex([p1, p2, p3])
>>> pc.is_maximal_cell(p1)
True
>>> pc.is_maximal_cell(p3)
False

Wrong answer due to maximality_check=False:

Sage

sage: pc_invalid = PolyhedralComplex([p1, p2, p3],
....:              maximality_check=False)
sage: pc_invalid.is_maximal_cell(p3)
True

Python

>>> from sage.all import *
>>> pc_invalid = PolyhedralComplex([p1, p2, p3],
...              maximality_check=False)
>>> pc_invalid.is_maximal_cell(p3)
True

is_mutable()[source]#

Return whether self is mutable.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> pc1 = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])])
>>> pc1.is_mutable()
True
>>> pc2 = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])],
...                        is_mutable=False)
>>> pc2.is_mutable()
False
>>> pc1 == pc2
True
>>> pc3 = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])],
...                        is_immutable=True)
>>> pc3.is_mutable()
False
>>> pc2 == pc3
True

is_polyhedral_fan()[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(0), Integer(0)), (Integer(1), Integer(1)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(rays=[(Integer(1), Integer(0))])
>>> PolyhedralComplex([p1]).is_polyhedral_fan()
False
>>> PolyhedralComplex([p2]).is_polyhedral_fan()
True
>>> halfplane = Polyhedron(rays=[(Integer(1), Integer(0)), (-Integer(1), Integer(0)), (Integer(0), Integer(1))])
>>> PolyhedralComplex([halfplane]).is_polyhedral_fan()
True

is_pure()[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> pc = PolyhedralComplex([p1, p2, p3])
>>> pc.is_pure()
True

Wrong answer due to maximality_check=False:

Sage

sage: pc_invalid = PolyhedralComplex([p1, p2, p3],
....:              maximality_check=False)
sage: pc_invalid.is_pure()
False

Python

>>> from sage.all import *
>>> pc_invalid = PolyhedralComplex([p1, p2, p3],
...              maximality_check=False)
>>> pc_invalid.is_pure()
False

is_simplicial_complex()[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(0), Integer(0)), (Integer(1), Integer(1)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(rays=[(Integer(1), Integer(0))])
>>> PolyhedralComplex([p1]).is_simplicial_complex()
True
>>> PolyhedralComplex([p2]).is_simplicial_complex()
False

is_simplicial_fan()[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(0), Integer(0)), (Integer(1), Integer(1)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(rays=[(Integer(1), Integer(0))])
>>> PolyhedralComplex([p1]).is_simplicial_fan()
False
>>> PolyhedralComplex([p2]).is_simplicial_fan()
True
>>> halfplane = Polyhedron(rays=[(Integer(1), Integer(0)), (-Integer(1), Integer(0)), (Integer(0), Integer(1))])
>>> PolyhedralComplex([halfplane]).is_simplicial_fan()
False

is_subcomplex(other)[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1)/Integer(3), Integer(1)/Integer(3)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(1)/Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(0), Integer(0)), (Integer(1), Integer(0))])
>>> pc = PolyhedralComplex([p1, Polyhedron(vertices=[(Integer(1), Integer(0))])])
>>> pc.is_subcomplex(PolyhedralComplex([p1, p2, p3]))
True
>>> pc.is_subcomplex(PolyhedralComplex([p1, p2]))
False

join(right)[source]#

The join of this polyhedral complex with another one.

INPUT:

right – the other polyhedral complex (the right-hand factor)

EXAMPLES:

Sage

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))

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([Polyhedron(vertices=[[Integer(0)], [Integer(1)]])])
>>> pc_join = pc.join(pc)
>>> pc_join
Polyhedral complex with 1 maximal cell
>>> 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)[source]#

An iterator for the maximal cells in this polyhedral complex.

INPUT:

increasing – (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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> pc = PolyhedralComplex([p1, p2, p3])
>>> len(list(pc.maximal_cell_iterator()))
2

Wrong answer due to maximality_check=False:

Sage

sage: pc_invalid = PolyhedralComplex([p1, p2, p3],
....:              maximality_check=False)
sage: len(list(pc_invalid.maximal_cell_iterator()))
3

Python

>>> from sage.all import *
>>> pc_invalid = PolyhedralComplex([p1, p2, p3],
...              maximality_check=False)
>>> len(list(pc_invalid.maximal_cell_iterator()))
3

maximal_cells()[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> pc = PolyhedralComplex([p1, p2, p3])
>>> len(pc.maximal_cells()[Integer(2)])
2
>>> Integer(1) in pc.maximal_cells()
False

Wrong answer due to maximality_check=False:

Sage

sage: pc_invalid = PolyhedralComplex([p1, p2, p3],
....:              maximality_check=False)
sage: len(pc_invalid.maximal_cells()[1])
1

Python

>>> from sage.all import *
>>> pc_invalid = PolyhedralComplex([p1, p2, p3],
...              maximality_check=False)
>>> len(pc_invalid.maximal_cells()[Integer(1)])
1

maximal_cells_sorted()[source]#

Return the sorted list of the maximal cells of this polyhedral complex by non-increasing dimensions.

EXAMPLES:

Sage

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]]]

Python

>>> from sage.all import *
>>> pc = PolyhedralComplex([
...         Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))]),
...         Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])])
>>> [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)[source]#

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

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

Python

>>> from sage.all import *
>>> p1 = Polyhedron(vertices=[(Integer(1), Integer(1)), (Integer(0), Integer(0)), (Integer(1), Integer(2))])
>>> p2 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(0)), (Integer(0), Integer(2))])
>>> p3 = Polyhedron(vertices=[(Integer(1), Integer(2)), (Integer(0), Integer(2))])
>>> pc = PolyhedralComplex([p1, p2, p3])
>>> len(pc.n_maximal_cells(Integer(2)))
2
>>> len(pc.n_maximal_cells(Integer(1)))
0

Wrong answer due to maximality_check=False:

Sage

sage: pc_invalid = PolyhedralComplex([p1, p2, p3],
....:              maximality_check=False)
sage: len(pc_invalid.n_maximal_cells(1))
1

Python

>>> from sage.all import *
>>> pc_invalid = PolyhedralComplex([p1, p2, p3],
...              maximality_check=False)
>>> len(pc_invalid.n_maximal_cells(Integer(1)))
1

n_skeleton(n)[source]#

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