Edit on GitHub

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 — Method
PolyhedralFan{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
source
normal_fan — Method
normal_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]
source
face_fan — Method
face_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
source

Auxiliary functions

ambient_dim — Method
ambient_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
source
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
source
dim — Method
dim(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
source
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
source
f_vector — Method
f_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
source
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
source
is_complete — Method
is_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
source
is_pointed — Method
is_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
source
is_regular — Method
is_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
source
is_simplicial — Method
is_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
source
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
source
is_smooth — Method
is_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
source
lineality_dim — Method
lineality_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
source
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
source
lineality_space — Method
lineality_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]
source
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]
source
maximal_cones — Method
maximal_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
source
cones — Method
cones(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
source
n_maximal_cones — Method
n_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
source
nrays — Method
nrays(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
source
rays — Method
rays(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]
source
primitive_collections — Method
primitive_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])
source
starsubdivision — Method
starsubdivision(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]
source
* — 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
source

Visualization

visualize — Method
visualize(PF::PolyhedralFan)

Visualize a polyhedral fan.

source