Polyhedral Fans
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{F}$ of (polyhedral) cones in $\mathbb{F}^n$, for $n$ fixed, is a (polyhedral) fan 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 fan, you must pass the rays of each cone in the fan, along with an IncidenceMatrix
encoding which rays generate which cones.
PolyhedralFan
— MethodPolyhedralFan{T}(Rays, Cones; non_redundant = false) where T<:scalar_types
Arguments
Rays::AbstractCollection[RayVector]
: Rays generating the cones of the fan; encoded row-wise as representative vectors.Cones::IncidenceMatrix
: An incidence matrix; there is a 1 at position (i,j) if cone i has ray j as extremal ray, and 0 otherwise.
A polyhedral fan formed from rays and cones made of these rays. The cones are given as an IncidenceMatrix, where the columns represent the rays and the rows represent the cones.
Examples
To obtain the upper half-space of the plane:
julia> R = [1 0; 1 1; 0 1; -1 0; 0 -1];
julia> IM=IncidenceMatrix([[1,2],[2,3],[3,4],[4,5],[1,5]]);
julia> PF=PolyhedralFan(R,IM)
A polyhedral fan in ambient dimension 2
normal_fan
— Methodnormal_fan(P::Polyhedron)
Return the normal fan of P
. The maximal cones of the normal fan of P
are dual to the edge cones at the vertices of P
.
Examples
The rays of a normal fan of a cube point in every positive and negative unit direction.
julia> C = cube(3);
julia> NF = normal_fan(C)
A polyhedral fan in ambient dimension 3
julia> rays(NF)
6-element SubObjectIterator{RayVector{fmpq}}:
[1, 0, 0]
[-1, 0, 0]
[0, 1, 0]
[0, -1, 0]
[0, 0, 1]
[0, 0, -1]
face_fan
— Methodface_fan(P::Polyhedron)
Return the face fan of P
. The polytope P
has to contain the origin, then the maximal cones of the face fan of P
are the cones over the facets of P
.
Examples
By definition, this bounded polyhedron's number of facets equals the amount of maximal cones of its face fan.
julia> C = cross(3);
julia> FF = face_fan(C)
A polyhedral fan in ambient dimension 3
julia> n_maximal_cones(FF) == nfacets(C)
true
Auxiliary functions
ambient_dim
— Methodambient_dim(PF::PolyhedralFan)
Return the ambient dimension PF
, which is the dimension of the embedding space.
This is equal to the dimension of the fan if and only if the fan is full-dimensional.
Examples
The normal fan of the 4-cube is embedded in the same ambient space.
julia> ambient_dim(normal_fan(cube(4)))
4
ambient_dim(T::TropicalVariety{M, EMB})
ambient_dim(T::TropicalCurve{M, EMB})
ambient_dim(T::TropicalHypersurface{M, EMB})
ambient_dim(T::TropicalLinearSpace{M, EMB})
Return the ambient dimension of T
if it is embedded. Otherwise an error is thrown.
Examples
A tropical hypersurface in $\mathbb{R}^n$ is of ambient dimension n
julia> RR = TropicalSemiring(min);
julia> S,(x,y) = RR["x","y"];
julia> f = x+y+1;
julia> tropicalLine = TropicalHypersurface(f);
julia> ambient_dim(tropicalLine)
2
dim
— Methoddim(PF::PolyhedralFan)
Return the dimension of PF
.
Examples
This fan in the plane contains a 2-dimensional cone and is thus 2-dimensional itself.
julia> PF = PolyhedralFan([1 0; 0 1; -1 -1], IncidenceMatrix([[1, 2], [3]]));
julia> dim(PF)
2
dim(T::TropicalVariety{M, EMB})
dim(T::TropicalCurve{M, EMB})
dim(T::TropicalHypersurface{M, EMB})
dim(T::TropicalLinearSpace{M, EMB})
Return the dimension of T
.
Examples
A tropical hypersurface in $\mathbb{R}^n$ is always of dimension n-1
julia> RR = TropicalSemiring(min);
julia> S,(x,y) = RR["x","y"];
julia> f = x+y+1;
julia> tropicalLine = TropicalHypersurface(f);
julia> dim(tropicalLine)
1
f_vector
— Methodf_vector(PF::PolyhedralFan)
Compute the vector $(f₁,f₂,...,f_{dim(PF)-1})$` where $f_i$ is the number of faces of $PF$ of dimension $i$.
Examples
The f-vector of the normal fan of a polytope is the reverse of the f-vector of the polytope.
julia> c = cube(3)
A polyhedron in ambient dimension 3
julia> f_vector(c)
3-element Vector{fmpz}:
8
12
6
julia> nfc = normal_fan(c)
A polyhedral fan in ambient dimension 3
julia> f_vector(nfc)
3-element Vector{fmpz}:
6
12
8
f_vector(T::TropicalVariety{M, EMB})
f_vector(T::TropicalCurve{M, EMB})
f_vector(T::TropicalHypersurface{M, EMB})
f_vector(T::TropicalLinearSpace{M, EMB})
Return the f-Vector of T
.
Examples
A tropical hypersurface in $\mathbb{R}^n$ is of lineality dimension n
julia> RR = TropicalSemiring(min);
julia> S,(x,y) = RR["x","y"];
julia> f = x+y+1;
julia> tropicalLine = TropicalHypersurface(f);
julia> f_vector(tropicalLine)
2-element Vector{Int64}:
1
3
is_complete
— Methodis_complete(PF::PolyhedralFan)
Determine whether PF
is complete, i.e. its support, the set-theoretic union of its cones, covers the whole space.
Examples
Normal fans of polytopes are complete.
julia> is_complete(normal_fan(cube(3)))
true
is_pointed
— Methodis_pointed(PF::PolyhedralFan)
Determine whether PF
is pointed, i.e. all its cones are pointed.
Examples
The normal fan of a non-fulldimensional polytope is not pointed.
julia> C = convex_hull([0 0; 1 0])
A polyhedron in ambient dimension 2
julia> is_fulldimensional(C)
false
julia> nf = normal_fan(C)
A polyhedral fan in ambient dimension 2
julia> is_pointed(nf)
false
julia> lineality_dim(nf)
1
is_regular
— Methodis_regular(PF::PolyhedralFan)
Determine whether PF
is regular, i.e. the normal fan of a polytope.
Examples
This fan is not complete and thus not regular.
julia> PF = PolyhedralFan([1 0; 0 1; -1 -1], IncidenceMatrix([[1, 2], [3]]));
julia> is_regular(PF)
false
is_simplicial
— Methodis_simplicial(PF::PolyhedralFan)
Determine whether PF
is simplicial, i.e. every cone should be generated by a basis of the ambient space.
Examples
The normal_fan
of the cube is simplicial, while the face_fan
is not.
julia> is_simplicial(normal_fan(cube(3)))
true
julia> is_simplicial(face_fan(cube(3)))
false
is_simplicial(T::TropicalVariety{M, EMB})
is_simplicial(T::TropicalCurve{M, EMB})
is_simplicial(T::TropicalHypersurface{M, EMB})
is_simplicial(T::TropicalLinearSpace{M, EMB})
Return true
if T
is a simplicial polyhedral complex, false
otherwise.
Examples
A tropical hypersurface in $\mathbb{R}^n$ is of lineality dimension n
julia> RR = TropicalSemiring(min);
julia> S,(x,y) = RR["x","y"];
julia> f = x+y+1;
julia> tropicalLine = TropicalHypersurface(f);
julia> is_simplicial(tropicalLine)
true
is_smooth
— Methodis_smooth(PF::PolyhedralFan{fmpq})
Determine whether PF
is smooth.
Examples
Even though the cones of this fan cover the positive orthant together, one of these und thus the whole fan is not smooth.
julia> PF = PolyhedralFan([0 1; 2 1; 1 0], IncidenceMatrix([[1, 2], [2, 3]]));
julia> is_smooth(PF)
false
lineality_dim
— Methodlineality_dim(PF::PolyhedralFan)
Return the dimension of the lineality space of the polyhedral fan PF
, i.e. the dimension of the largest linear subspace.
Examples
The dimension of the lineality space is zero if and only if the fan is pointed.
julia> C = convex_hull([0 0; 1 0])
A polyhedron in ambient dimension 2
julia> is_fulldimensional(C)
false
julia> nf = normal_fan(C)
A polyhedral fan in ambient dimension 2
julia> is_pointed(nf)
false
julia> lineality_dim(nf)
1
lineality_dim(T::TropicalVariety{M, EMB})
lineality_dim(T::TropicalCurve{M, EMB})
lineality_dim(T::TropicalHypersurface{M, EMB})
lineality_dim(T::TropicalLinearSpace{M, EMB})
Return the dimension of the lineality space of T
if it is embedded. Otherwise an error is thrown.
Examples
A tropical hypersurface in $\mathbb{R}^n$ is of lineality dimension n
julia> RR = TropicalSemiring(min);
julia> S,(x,y) = RR["x","y"];
julia> f = x+y;
julia> tropicalAndAffineLine = TropicalHypersurface(f);
julia> lineality_dim(tropicalAndAffineLine)
1
lineality_space
— Methodlineality_space(PF::PolyhedralFan)
Return a non-redundant matrix whose rows are generators of the lineality space of PF
.
Examples
This fan consists of two cones, one containing all the points with $y ≤ 0$ and one containing all the points with $y ≥ 0$. The fan's lineality is the common lineality of these two cones, i.e. in $x$-direction.
julia> PF = PolyhedralFan([1 0; 0 1; -1 0; 0 -1], IncidenceMatrix([[1, 2, 3], [3, 4, 1]]))
A polyhedral fan in ambient dimension 2
julia> lineality_space(PF)
1-element SubObjectIterator{RayVector{fmpq}}:
[1, 0]
lineality_space(T::TropicalVariety{M, EMB})
lineality_space(T::TropicalCurve{M, EMB})
lineality_space(T::TropicalHypersurface{M, EMB})
lineality_space(T::TropicalLinearSpace{M, EMB})
Return the lineality space of T
if it is embedded. Otherwise an error is thrown.
Examples
A tropical hypersurface in $\mathbb{R}^n$ is of lineality spaceension n
julia> RR = TropicalSemiring(min);
julia> S,(x,y) = RR["x","y"];
julia> f = x+y;
julia> tropicalAndAffineLine = TropicalHypersurface(f);
julia> lineality_space(tropicalAndAffineLine)
1-element SubObjectIterator{RayVector{fmpq}}:
[-1, -1]
maximal_cones
— Methodmaximal_cones(PF::PolyhedralFan)
Return the maximal cones of PF
.
Examples
Here we ask for the the number of rays for each maximal cone of the face fan of the 3-cube and use that maximal_cones
returns an iterator.
julia> PF = face_fan(cube(3));
julia> for c in maximal_cones(PF)
println(nrays(c))
end
4
4
4
4
4
4
cones
— Methodcones(PF::PolyhedralFan, cone_dim::Int)
Return an iterator over the cones of PF
of dimension cone_dim
.
Examples
The 12 edges of the 3-cube correspond to the 2-dimensional cones of its face fan:
julia> PF = face_fan(cube(3));
julia> cones(PF, 2)
12-element SubObjectIterator{Cone{fmpq}}:
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
A polyhedral cone in ambient dimension 3
n_maximal_cones
— Methodn_maximal_cones(PF::PolyhedralFan)
Return the number of maximal cones of PF
.
Examples
The cones given in this construction are non-redundant. Thus there are two maximal cones.
julia> PF = PolyhedralFan([1 0; 0 1; -1 -1], IncidenceMatrix([[1, 2], [3]]));
julia> n_maximal_cones(PF)
2
nrays
— Methodnrays(PF::PolyhedralFan)
Return the number of rays of PF
.
Examples
The 3-cube has 8 vertices. Accordingly, its face fan has 8 rays.
julia> nrays(face_fan(cube(3)))
8
rays
— Methodrays(as::Type{T} = RayVector, P::Polyhedron)
Return a minimal set of generators of the cone of unbounded directions of P
(i.e. its rays) in the format defined by as
.
Optional arguments for as
include
RayVector
.
Examples
We can verify that the positive orthant of the plane is generated by the two rays in positive unit direction:
julia> PO = convex_hull([0 0], [1 0; 0 1]);
julia> rays(RayVector, PO)
2-element SubObjectIterator{RayVector{fmpq}}:
[1, 0]
[0, 1]
primitive_collections
— Methodprimitive_collections(PF::PolyhedralFan)
Return the primitive collections of a polyhedral fan.
Examples
julia> primitive_collections(normal_fan(simplex(3)))
1-element Vector{Set{Int64}}:
Set([4, 2, 3, 1])
starsubdivision
— Methodstarsubdivision(PF::PolyhedralFan, n::Int)
Return the star subdivision of a polyhedral fan at its n-th maximal torus orbit.
Examples
julia> star = starsubdivision(normal_fan(simplex(3)), 1)
A polyhedral fan in ambient dimension 3
julia> rays(star)
5-element SubObjectIterator{RayVector{fmpq}}:
[0, 1, 0]
[0, 0, 1]
[-1, -1, -1]
[1, 0, 0]
[1, 1, 1]
julia> ray_indices(maximal_cones(star))
6×5 IncidenceMatrix
[1, 2, 3]
[2, 3, 4]
[1, 3, 4]
[2, 4, 5]
[1, 2, 5]
[1, 4, 5]
*
— Method*(PF1::PolyhedralFan, PF2::PolyhedralFan)
Return the Cartesian/direct product of two polyhedral fans.
Examples
julia> normal_fan(simplex(2))*normal_fan(simplex(3))
A polyhedral fan in ambient dimension 5
Visualization
visualize
— Methodvisualize(PF::PolyhedralFan)
Visualize a polyhedral fan.