# Cones

## 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 set $C \subseteq \mathbb{F}^n$ is called a (polyhedral) cone if it can be written as the set of nonnegative linear combinations of finitely many vectors in $\mathbb{F}^n$. Equivalently, cones can be written as the intersection of finitely many homogeneous linear inequalities.

Any cone is a special case of a polyhedron. Conversely, intersecting a cone with a suitable affine hyperplane yields a polyhedron whose faces are in bijection with the faces of the cone. Going back and forth between polyhedra and their homogenizations, the cones, is a frequent operation. This is one reason for keeping cones as a distinct type.

## Construction

positive_hullMethod
positive_hull([::Type{T} = QQFieldElem,] R::AbstractCollection[RayVector] [, L::AbstractCollection[RayVector]]; non_redundant::Bool = false) where T<:scalar_types

A polyhedral cone, not necessarily pointed, defined by the positive hull of the rays R, with lineality given by L.

R is given row-wise as representative vectors, with lineality generated by the rows of L, i.e. the cone consists of all positive linear combinations of the rows of R plus all linear combinations of the rows of L.

This is an interior description, analogous to the $V$-representation of a polytope.

Redundant rays are allowed.

Examples

To construct the positive orthant as a Cone, you can write:

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

julia> PO = positive_hull(R)
Polyhedral cone in ambient dimension 2

To obtain the upper half-space of the plane:

julia> R = [0 1];

julia> L = [1 0];

julia> HS = positive_hull(R, L)
Polyhedral cone in ambient dimension 2
source
secondary_coneMethod
secondary_cone(SOP::SubdivisionOfPoints)

Return the secondary cone of a subdivision of points, the closure of all the weight vectors inducing the given subdivision of points.

Examples

For a non-regular subdivision, the secondary cone can still contain non-trivial weights, but it will not be full-dimensional.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> moaeimnonreg0 = IncidenceMatrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);

julia> MOAE = SubdivisionOfPoints(moaepts, moaeimnonreg0)
Subdivision of points in ambient dimension 3

julia> C = secondary_cone(MOAE)
Polyhedral cone in ambient dimension 6

julia> dim(C)
4
source

## Auxiliary functions

ambient_dimMethod
ambient_dim(C::Cone)

Return the ambient dimension of C.

Examples

The cone C in this example is 2-dimensional within a 3-dimensional ambient space.

julia> C = Cone([1 0 0; 1 1 0; 0 1 0]);

julia> ambient_dim(C)
3
source
containsMethod
contains(C::Cone, v::AbstractVector)

Check whether C contains v.

Examples

The positive orthant only contains vectors with non-negative entries:

julia> C = positive_hull([1 0; 0 1]);

julia> contains(C, [1, 2])
true

julia> contains(C, [1, -2])
false
source
f_vectorMethod
f_vector(C::Cone)

Compute the vector $(f₁,f₂,...,f_{(dim(C)-1))$ where $f_i$ is the number of faces of $C$ of dimension $i$.

Examples

Take the cone over a square, then the f-vector of the cone is the same as of the square.

julia> C = positive_hull([1 0 0; 1 1 0; 1 1 1; 1 0 1])
Polyhedral cone in ambient dimension 3

julia> f_vector(C)
2-element Vector{ZZRingElem}:
4
4

julia> square = cube(2)
Polyhedron in ambient dimension 2

julia> f_vector(square)
2-element Vector{ZZRingElem}:
4
4
source
hilbert_basisMethod
hilbert_basis(C::Cone{QQFieldElem})

Return the Hilbert basis of a pointed cone C as the rows of a matrix.

Examples

This (non-smooth) cone in the plane has a hilbert basis with three elements.

julia> C = Cone([1 0; 1 2])
A polyhedral cone in ambient dimension 2

julia> matrix(ZZ, hilbert_basis(C))
[1   0]
[1   2]
[1   1]

source
codimMethod
codim(C::Cone)

Return the codimension of C.

Examples

The cone C in this example is 2-dimensional within a 3-dimensional ambient space.

julia> C = Cone([1 0 0; 1 1 0; 0 1 0]);

julia> codim(C)
1
source
dimMethod
dim(C::Cone)

Return the dimension of C.

Examples

The cone C in this example is 2-dimensional within a 3-dimensional ambient space.

julia> C = Cone([1 0 0; 1 1 0; 0 1 0]);

julia> dim(C)
2
source
polarizeMethod
polarize(C::Cone)

Return the polar dual of C, the cone consisting of all those linear functions that evaluate positively on all of C.

Examples

julia> C = positive_hull([1 0; -1 2])
Polyhedral cone in ambient dimension 2

julia> Cv = polarize(C)
Polyhedral cone in ambient dimension 2

julia> rays(Cv)
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 1//2]
[0, 1]
source
intersectMethod
intersect(C0::Cone{T}, C1::Cone{T}) where T<:scalar_types

Return the intersection $C0 \cap C1$ of C0 and C1.

Examples

julia> C0 = positive_hull([1 0])
Polyhedral cone in ambient dimension 2

julia> C1 = positive_hull([0 1])
Polyhedral cone in ambient dimension 2

julia> C01 = intersect(C0, C1)
Polyhedral cone in ambient dimension 2

julia> rays(C01)
0-element SubObjectIterator{RayVector{QQFieldElem}}

julia> dim(C01)
0
source
is_pointedMethod
is_pointed(C::Cone)

Determine whether C is pointed, i.e. whether the origin is a face of C.

Examples

A cone with lineality is not pointed, but a cone only consisting of a single ray is.

julia> C = Cone([1 0], [0 1]);

julia> is_pointed(C)
false

julia> C = Cone([1 0]);

julia> is_pointed(C)
true
source
is_fulldimensionalMethod
is_fulldimensional(C::Cone)

Determine whether C is full-dimensional.

Examples

The cone C in this example is 2-dimensional within a 3-dimensional ambient space.

julia> C = Cone([1 0 0; 1 1 0; 0 1 0]);

julia> is_fulldimensional(C)
false
source
lineality_dimMethod
lineality_dim(C::Cone)

Compute the dimension of the lineality space of $C$, i.e. the largest linear subspace contained in $C$.

Examples

A cone is pointed if and only if the dimension of its lineality space is zero.

julia> C = positive_hull([1 0 0; 1 1 0; 1 1 1; 1 0 1])
Polyhedral cone in ambient dimension 3

julia> is_pointed(C)
true

julia> lineality_dim(C)
0

julia> C1 = Cone([1 0],[0 1; 0 -1])
Polyhedral cone in ambient dimension 2

julia> is_pointed(C1)
false

julia> lineality_dim(C1)
1
source
lineality_spaceMethod
lineality_space(C::Cone)

Return a basis of the lineality space of C.

Examples

Three rays are used here to construct the upper half-plane. Actually, two of these rays point in opposite directions. This gives us a 1-dimensional lineality.

julia> UH = Cone([1 0; 0 1; -1 0]);

julia> lineality_space(UH)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
source
nfacetsMethod
nfacets(C::Cone)

Return the number of facets of a cone C.

Examples

The cone over a square at height one has four facets.

julia> C = positive_hull([1 0 0; 1 1 0; 1 1 1; 1 0 1])
Polyhedral cone in ambient dimension 3

julia> nfacets(C)
4
source
nraysMethod
nrays(C::Cone)

Return the number of rays of C.

Examples

Here a cone is constructed from three rays. Calling nrays reveals that one of these was redundant:

julia> R = [1 0; 0 1; 0 2];

julia> PO = positive_hull(R);

julia> nrays(PO)
2
source
raysMethod
rays(C::Cone)

Return the rays of C.

Examples

Here a cone is constructed from three rays. Calling rays reveals that one of these was redundant:

julia> R = [1 0; 0 1; 0 2];

julia> PO = positive_hull(R);

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

The rays can also be converted to a matrix using the matrix(ring, ...) function. If ring=ZZ the primitive generators of the rays are returned.

julia> R = [1 0; 2 3];

julia> P = positive_hull(R);

julia> rays(P)
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
[1, 3//2]

julia> matrix(QQ, rays(P))
[1      0]
[1   3//2]

julia> matrix(ZZ, rays(P))
[1   0]
[2   3]
source
rays_modulo_linealityMethod
rays_modulo_lineality(as, C::Cone)

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

Examples

For a pointed cone, with two generators, we get the usual rays:

julia> C = positive_hull([1 0; 0 1])
Polyhedral cone in ambient dimension 2

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

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

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

julia> RML.lineality_basis
0-element SubObjectIterator{RayVector{QQFieldElem}}

If the cone has lineality, the second iterator iterates over a basis for the space of lineality. The following example has one generator for the positive hull plus one generator for the lineality space:

julia> C = positive_hull([1 0],[0 1])
Polyhedral cone in ambient dimension 2

julia> lineality_dim(C)
1

julia> rays(C)
0-element SubObjectIterator{RayVector{QQFieldElem}}

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

julia> RML.lineality_basis
1-element SubObjectIterator{RayVector{QQFieldElem}}:
[0, 1]`
source