Edit on GitHub

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_hull — Method
positive_hull([::Type{T} = fmpq,] R::AbstractCollection[RayVector])

A polyhedral cone, not necessarily pointed, defined by the positive hull of the rows of the matrix R. This means the cone consists of all positive linear combinations of the rows of R. This is an interior description, analogous to the $V$-representation of a polytope.

Redundant rays are allowed.

Examples

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

julia> PO = positive_hull(R)
A polyhedral cone in ambient dimension 2
source
secondary_cone — Method
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)
A subdivision of points in ambient dimension 3

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

julia> dim(C)
4
source

Saving and loading

Objects of type Cone can be saved to a file and loaded from a file in the following way:

julia> C = positive_hull([1 0; 0 1])A polyhedral cone in ambient dimension 2
julia> save("C.cone", C)429
julia> CC = load("C.cone")A polyhedral cone in ambient dimension 2
julia> collect(rays(CC))2-element Vector{RayVector{fmpq}}:
 [1, 0]
 [0, 1]

The file is in JSON format and contains all previously gathered data belonging to the underlying polymake object. In particular, this file can now be read by both polymake and Oscar.

Auxiliary functions

ambient_dim — Method
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
contains — Method
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_vector — Method
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])
A polyhedral cone in ambient dimension 3

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

julia> square = cube(2)
A polyhedron in ambient dimension 2

julia> f_vector(square)
2-element Vector{fmpz}:
 4
 4
source
hilbert_basis — Method
hilbert_basis(C::Cone{fmpq})

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
codim — Method
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
dim — Method
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
polarize — Method
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])
A polyhedral cone in ambient dimension 2

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

julia> rays(Cv)
2-element SubObjectIterator{RayVector{fmpq}}:
 [1, 1//2]
 [0, 1]
source
intersect — Method
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])
A polyhedral cone in ambient dimension 2

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

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

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

julia> dim(C01)
0
source
is_pointed — Method
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_fulldimensional — Method
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_dim — Method
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])
A 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])
A polyhedral cone in ambient dimension 2

julia> is_pointed(C1)
false

julia> lineality_dim(C1)
1
source
lineality_space — Method
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{fmpq}}:
 [1, 0]
source
nfacets — Method
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])
A polyhedral cone in ambient dimension 3

julia> nfacets(C)
4
source
nrays — Method
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
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

Visualization