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.
PolyhedralComplex
— TypePolyhedralComplex{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 invr
.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
Auxiliary functions
ambient_dim
— Methodambient_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
codim
— Methodcodim(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
dim
— Methoddim(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
f_vector
— Methodf_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
is_embedded
— Methodis_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
maximal_polyhedra
— Methodmaximal_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
n_maximal_polyhedra
— Methodn_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
npolyhedra
— Methodnpolyhedra(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
nrays
— Methodnrays(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
nvertices
— Methodnvertices(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
polyhedra_of_dim
— Functionpolyhedra_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
rays
— Methodrays(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]
vertices
— Methodvertices(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]
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]