GitHub

Polyhedral Complexes

Introduction

Let $\mathbb{F}$ be an ordered field; the default is that $\mathbb{F}=\mathbb{Q}$ is the field of rational numbers and other fields are not yet supported everywhere in the implementation.

A nonempty finite collection $\mathcal{P}$ of polyhedra in $\mathbb{F}^n$, for $n$ fixed, is a polyhedral complex if

  • the set $\mathcal{F}$ is closed with respect to taking faces and
  • if $C,D\in\mathcal{F}$ then $C\cap D$ is a face of both $C$ and $D$.

Construction

To construct a polyhedral complex, you must pass points of each polyhedron in the polyhedral complex, such that the polyhedron is the convex hull thereof, along with an IncidenceMatrix encoding which points generate which polyhedron.

polyhedral_complex — Function
polyhedral_complex(::T, polyhedra, vr, far_vertices, L) where T<:scalar_types

Arguments

  • T: Type or parent Field of scalar to use, defaults to QQFieldElem.
  • polyhedra::IncidenceMatrix: An incidence matrix; there is a 1 at position (i,j) if the ith polytope contains point j and 0 otherwise.
  • vr::AbstractCollection[PointVector]: The points whose convex hulls make up the polyhedral complex. This matrix also contains the far vertices.
  • far_vertices::Vector{Int}: Vector containing the indices of the rows corresponding to the far vertices in vr.
  • L::AbstractCollection[RayVector]: Generators of the lineality space of the polyhedral complex.

A polyhedral complex formed from points, rays, and lineality combined into polyhedra indicated by an incidence matrix, where the columns represent the points and the rows represent the polyhedra.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]])
2×4 IncidenceMatrix
[1, 2, 3]
[1, 3, 4]


julia> vr = [0 0; 1 0; 1 1; 0 1]
4×2 Matrix{Int64}:
 0  0
 1  0
 1  1
 0  1

julia> PC = polyhedral_complex(IM, vr)
Polyhedral complex in ambient dimension 2

Polyhedral complex with rays and lineality:

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> lineality_dim(PC)
1
source
polyhedral_complex(polytopes::AbstractVector{Polyhedron{T}}) where T<:scalar_types

Assemble a polyhedral complex from a non-empty list of polyhedra.

source
polyhedral_complex(F::PolyhedralFan)

Turn a polyhedral fan into a polyhedral complex.

source
polyhedral_complex(TropV::TropicalVariety)

Return the polyhedral complex of a tropical variety.

source

Auxiliary functions

ambient_dim — Method
ambient_dim(PC::PolyhedralComplex)

Return the ambient dimension of PC.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]])
2×4 IncidenceMatrix
[1, 2, 3]
[1, 3, 4]


julia> V = [0 0; 1 0; 1 1; 0 1]
4×2 Matrix{Int64}:
 0  0
 1  0
 1  1
 0  1

julia> PC = polyhedral_complex(IM, V)
Polyhedral complex in ambient dimension 2

julia> ambient_dim(PC)
2
source
codim — Method
codim(PC::PolyhedralComplex)

Compute the codimension of a polyhedral complex.

Examples

julia> VR = [0 0; 1 0; -1 0; 0 1];

julia> IM = incidence_matrix([[1,2],[1,3],[1,4]]);

julia> far_vertices = [2,3,4];

julia> PC = polyhedral_complex(IM, VR, far_vertices)
A polyhedral complex in ambient dimension 2

julia> codim(PC)
1
source
dim — Method
dim(PC::PolyhedralComplex)

Compute the dimension of the polyhedral complex.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0; 1 0; 1 1; 0 1];

julia> PC = polyhedral_complex(IM, VR)
Polyhedral complex in ambient dimension 2

julia> dim(PC)
2
source
f_vector — Method
f_vector(PC::PolyhedralComplex)

Compute the vector $(f₀,f₁,f₂,...,f_{dim(PC)})$ where $f_i$ is the number of faces of $PC$ of dimension $i$.

Examples

julia> VR = [0 0; 1 0; -1 0; 0 1];

julia> IM = incidence_matrix([[1,2,4],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> PC = polyhedral_complex(IM, VR, far_vertices);

julia> f_vector(PC)
3-element Vector{Int64}:
 1
 3
 2
source
is_embedded — Method
is_embedded(PC::PolyhedralComplex)

Return true if PC is embedded, i.e. if its vertices can be computed as a subset of some $\mathbb{R}^n$.

Examples

julia> VR = [0 0; 1 0; -1 0; 0 1];

julia> IM = incidence_matrix([[1,2],[1,3],[1,4]]);

julia> PC = polyhedral_complex(IM, VR)
Polyhedral complex in ambient dimension 2

julia> is_embedded(PC)
true
source
is_pure — Method
is_pure(PC::PolyhedralComplex)

Determine whether the polyhedral complex is pure.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0; 1 0; 1 1; 0 1];

julia> PC = polyhedral_complex(IM, VR)
Polyhedral complex in ambient dimension 2

julia> is_pure(PC)
true
source
is_simplicial — Method
is_simplicial(PC::PolyhedralComplex)

Determine whether the polyhedral complex is simplicial.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0; 1 0; 1 1; 0 1];

julia> PC = polyhedral_complex(IM, VR)
Polyhedral complex in ambient dimension 2

julia> is_simplicial(PC)
true
source
lineality_dim — Method
lineality_dim(PC::PolyhedralComplex)

Return the lineality dimension of PC.

Examples

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> lineality_dim(PC)
1
source
lineality_space — Method
lineality_space(PC::PolyhedralComplex)

Return the lineality space of PC.

Examples

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> lineality_space(PC)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [0, 0, 1]
source
maximal_polyhedra — Method
maximal_polyhedra(PC::PolyhedralComplex)

Return the maximal polyhedra of PC

Optionally IncidenceMatrix can be passed as a first argument to return the incidence matrix specifying the maximal polyhedra of PC. The indices returned refer to the output of vertices_and_rays.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]])
2×4 IncidenceMatrix
[1, 2, 3]
[1, 3, 4]


julia> VR = [0 0; 1 0; 1 1; 0 1]
4×2 Matrix{Int64}:
 0  0
 1  0
 1  1
 0  1

julia> PC = polyhedral_complex(IM, VR, [2])
Polyhedral complex in ambient dimension 2

julia> maximal_polyhedra(PC)
2-element SubObjectIterator{Polyhedron{QQFieldElem}}:
 Polyhedron in ambient dimension 2
 Polytope in ambient dimension 2

julia> maximal_polyhedra(IncidenceMatrix, PC)
2×4 IncidenceMatrix
[1, 2, 3]
[1, 3, 4]
source
minimal_faces — Method
minimal_faces(as, PC::PolyhedralComplex)

Return the minimal faces of a polyhedral complex as a NamedTuple with two iterators. For a polyhedral complex without lineality, the base_points are the vertices. If PC has lineality L, then every minimal face is an affine translation p+L, where p is only unique modulo L. The return type is a dict, the key :base_points gives an iterator over such p, and the key :lineality_basis lets one access a basis for the lineality space L of PC.

See also vertices and lineality_space.

Examples

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> MFPC = minimal_faces(PC)
(base_points = PointVector{QQFieldElem}[[0, 0, 0]], lineality_basis = RayVector{QQFieldElem}[[0, 0, 1]])

julia> MFPC.base_points
1-element SubObjectIterator{PointVector{QQFieldElem}}:
 [0, 0, 0]

julia> MFPC.lineality_basis
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [0, 0, 1]
source
n_maximal_polyhedra — Method
n_maximal_polyhedra(PC::PolyhedralComplex)

Return the number of maximal polyhedra of PC

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]])
2×4 IncidenceMatrix
[1, 2, 3]
[1, 3, 4]


julia> VR = [0 0; 1 0; 1 1; 0 1]
4×2 Matrix{Int64}:
 0  0
 1  0
 1  1
 0  1

julia> PC = polyhedral_complex(IM, VR, [2])
Polyhedral complex in ambient dimension 2

julia> n_maximal_polyhedra(PC)
2
source
n_polyhedra — Method
n_polyhedra(PC::PolyhedralComplex)

Return the total number of polyhedra in the polyhedral complex PC.

Examples

julia> VR = [0 0; 1 0; -1 0; 0 1];

julia> IM = incidence_matrix([[1,2,4],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> PC = polyhedral_complex(IM, VR, far_vertices);

julia> n_polyhedra(PC)
6
source
n_rays — Method
n_rays(PC::PolyhedralComplex)

Return the number of rays of PC.

Examples

julia> VR = [0 0; 1 0; -1 0; 0 1];

julia> IM = incidence_matrix([[1,2,4],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> PC = polyhedral_complex(IM, VR, far_vertices);

julia> n_rays(PC)
3
source
n_vertices — Method
n_vertices(PC::PolyhedralComplex)

Return the number of vertices of PC.

Examples

julia> VR = [0 0; 1 0; -1 0; 0 1];

julia> IM = incidence_matrix([[1,2,4],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> PC = polyhedral_complex(IM, VR, far_vertices);

julia> n_vertices(PC)
1
source
polyhedra_of_dim — Function
polyhedra_of_dim(PC::PolyhedralComplex, polyhedron_dim::Int)

Return the polyhedra of a given dimension in the polyhedral complex PC.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0; 1 0; 1 1; 0 1];

julia> PC = polyhedral_complex(IM, VR);

julia> P1s = polyhedra_of_dim(PC,1)
5-element SubObjectIterator{Polyhedron{QQFieldElem}}:
 Polytope in ambient dimension 2
 Polytope in ambient dimension 2
 Polytope in ambient dimension 2
 Polytope in ambient dimension 2
 Polytope in ambient dimension 2

julia> for p in P1s
       println(dim(p))
       end
1
1
1
1
1
source
rays — Method
rays([as::Type{T} = RayVector,] PC::PolyhedralComplex)

Return the rays of PC. The rays are defined to be the far vertices, i.e. the one-dimensional faces of the recession cones of its polyhedra, so if PC has lineality, there are no rays.

See also rays_modulo_lineality and vertices.

Optional arguments for as include

  • RayVector.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0; 1 0; 1 1; 0 1];

julia> PC = polyhedral_complex(IM, VR, [2])
Polyhedral complex in ambient dimension 2

julia> rays(PC)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0]

julia> matrix(QQ, rays(RayVector, PC))
[1   0]

The following complex has no vertices:

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> rays(PC)
0-element SubObjectIterator{RayVector{QQFieldElem}}
source
rays_modulo_lineality — Method
rays_modulo_lineality(as, PC::PolyhedralComplex)

Return the rays of the recession fan of PC up to lineality as a NamedTuple with two iterators. If PC has lineality L, then the iterator rays_modulo_lineality iterates over representatives of the rays of PC/L. The iterator lineality_basis gives a basis of the lineality space L.

See also rays and lineality_space.

Examples

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> RML = rays_modulo_lineality(PC)
(rays_modulo_lineality = RayVector{QQFieldElem}[[1, 0, 0], [0, 1, 0], [-1, 0, 0]], lineality_basis = RayVector{QQFieldElem}[[0, 0, 1]])

julia> RML.rays_modulo_lineality
3-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0, 0]
 [0, 1, 0]
 [-1, 0, 0]

julia> RML.lineality_basis
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [0, 0, 1]
source
vertices — Method
vertices([as::Type{T} = PointVector,] PC::PolyhedralComplex)

Return an iterator over the vertices of PC in the format defined by as. The vertices are defined to be the zero-dimensional faces, so if P has lineality, there are no vertices, only minimal faces.

See also minimal_faces and rays.

Optional arguments for as include

  • PointVector.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> V = [0 0; 1 0; 1 1; 0 1];

julia> PC = polyhedral_complex(IM, V)
Polyhedral complex in ambient dimension 2

julia> vertices(PC)
4-element SubObjectIterator{PointVector{QQFieldElem}}:
 [0, 0]
 [1, 0]
 [1, 1]
 [0, 1]

julia> matrix(QQ, vertices(PointVector, PC))
[0   0]
[1   0]
[1   1]
[0   1]

The following complex has no vertices:

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> vertices(PC)
0-element SubObjectIterator{PointVector{QQFieldElem}}
source
vertices_and_rays — Method
vertices_and_rays(PC::PolyhedralComplex)

Return the vertices and rays of PC as a combined set, up to lineality. This function is mainly a helper function for maximal_polyhedra.

Examples

julia> IM = incidence_matrix([[1,2,3],[1,3,4]]);

julia> VR = [0 0 0; 1 0 0; 0 1 0; -1 0 0];

julia> far_vertices = [2,3,4];

julia> L = [0 0 1];

julia> PC = polyhedral_complex(IM, VR, far_vertices, L)
Polyhedral complex in ambient dimension 3

julia> for vr in vertices_and_rays(PC)
       println("$vr : $(typeof(vr))")
       end
QQFieldElem[0, 0, 0] : PointVector{QQFieldElem}
QQFieldElem[1, 0, 0] : RayVector{QQFieldElem}
QQFieldElem[0, 1, 0] : RayVector{QQFieldElem}
QQFieldElem[-1, 0, 0] : RayVector{QQFieldElem}
source