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.

PolyhedralComplexType
PolyhedralComplex{T}(polyhedra, vr, far_vertices, L) where T<:scalar_types

Arguments

  • 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 = IncidenceMatrix([[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 = PolyhedralComplex(IM, vr)
A polyhedral complex in ambient dimension 2
source

Auxiliary functions

ambient_dimMethod
ambient_dim(PC::PolyhedralComplex)

Return the ambient dimension of PC.

Examples

julia> IM = IncidenceMatrix([[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 = PolyhedralComplex(IM, V)
A polyhedral complex in ambient dimension 2

julia> ambient_dim(PC)
2
source
codimMethod
codim(PC::PolyhedralComplex)

Compute the codimension of a polyhedral complex.

Examples

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

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

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

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

julia> codim(PC)
1
source
dimMethod
dim(PC::PolyhedralComplex)

Compute the dimension of the polyhedral complex.

Examples

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

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

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

julia> dim(PC)
2
source
f_vectorMethod
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 = IncidenceMatrix([[1,2,4],[1,3,4]]);

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

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

julia> f_vector(PC)
3-element Vector{Int64}:
 1
 3
 2
source
is_embeddedMethod
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 = IncidenceMatrix([[1,2],[1,3],[1,4]]);

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

julia> is_embedded(PC)
true
source
maximal_polyhedraMethod
maximal_polyhedra(PC::PolyhedralComplex)

Return the maximal polyhedra of PC

Examples

julia> IM = IncidenceMatrix([[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 = PolyhedralComplex(IM, VR, [2])
A polyhedral complex in ambient dimension 2

julia> maximal_polyhedra(PC)
2-element SubObjectIterator{Polyhedron{fmpq}}:
 A polyhedron in ambient dimension 2
 A polyhedron in ambient dimension 2
source
n_maximal_polyhedraMethod
n_maximal_polyhedra(PC::PolyhedralComplex)

Return the number of maximal polyhedra of PC

Examples

julia> IM = IncidenceMatrix([[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 = PolyhedralComplex(IM, VR, [2])
A polyhedral complex in ambient dimension 2

julia> n_maximal_polyhedra(PC)
2
source
npolyhedraMethod
npolyhedra(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 = IncidenceMatrix([[1,2,4],[1,3,4]]);

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

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

julia> npolyhedra(PC)
6
source
nraysMethod
nrays(PC::PolyhedralComplex)

Return the number of rays of PC.

Examples

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

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

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

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

julia> nrays(PC)
3
source
nverticesMethod
nvertices(PC::PolyhedralComplex)

Return the number of vertices of PC.

Examples

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

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

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

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

julia> nvertices(PC)
1
source
polyhedra_of_dimFunction
polyhedra_of_dim(PC::PolyhedralComplex, polyhedron_dim::Int)

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

Examples

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

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

julia> PC = PolyhedralComplex(IM, VR);

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

julia> for p in P1s
       println(dim(p))
       end
1
1
1
1
1
source
raysMethod
rays(PC::PolyhedralComplex)

Return the rays of PC

Examples

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

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

julia> PC = PolyhedralComplex(IM, VR, [2])
A polyhedral complex in ambient dimension 2

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

julia> matrix(QQ, rays(PC))
[1   0]
source
verticesMethod
vertices(as, P)

Return an iterator over the vertices of P in the format defined by as.

Optional arguments for as include

  • PointVector.

Examples

The following code computes the vertices of the Minkowski sum of a triangle and a square:

julia> P = simplex(2) + cube(2);

julia> vertices(PointVector, P)
5-element SubObjectIterator{PointVector{fmpq}}:
 [-1, -1]
 [2, -1]
 [2, 1]
 [-1, 2]
 [1, 2]
source
vertices(T::TropicalVariety{M, EMB})
vertices(T::TropicalCurve{M, EMB})
vertices(T::TropicalHypersurface{M, EMB})
vertices(T::TropicalLinearSpace{M, EMB})

Return the vertices of T, which are points in euclidean space if T is embedded or elements in an ordered set otherwise.

Examples

The vertices of a plane tropical line, plane tropical honeycomb quadric, and plane tropical honeycomb cubic

julia> RR = TropicalSemiring(min);

julia> S,(x,y) = RR["x","y"];

julia> f1 = x+y+1;

julia> tropicalLine = TropicalHypersurface(f1);

julia> vertices(tropicalLine)
1-element SubObjectIterator{PointVector{fmpq}}:
 [1, 1]

julia> f2 = 1*x^2+x*y+1*y^2+x+y+1;

julia> tropicalQuadric = TropicalHypersurface(f1);

julia> vertices(tropicalQuadric)
1-element SubObjectIterator{PointVector{fmpq}}:
 [1, 1]

julia> f3 = x^3+x*y^2+x^2*y+y^3+x^2+x*y+y^2+x+y+1;

julia> tropicalCubic = TropicalHypersurface(f3);

julia> vertices(tropicalCubic)
2-element SubObjectIterator{PointVector{fmpq}}:
 [0, 0]
 [1, 1]
source