Auxiliary functions

facets(as::Type{T} = AffineHalfspace, P::Polyhedron)

Return the facets of P in the format defined by as.

The allowed values for as are

• Halfspace,
• Polyhedron,
• Pair.

Examples

We can retrieve the six facets of the 3-dimensional cube this way:

julia> C = cube(3);

julia> facets(Polyhedron, C)
6-element SubObjectIterator{Polyhedron{fmpq}}:
 A polyhedron in ambient dimension 3
 A polyhedron in ambient dimension 3
 A polyhedron in ambient dimension 3
 A polyhedron in ambient dimension 3
 A polyhedron in ambient dimension 3
 A polyhedron in ambient dimension 3

julia> facets(Halfspace, C)
6-element SubObjectIterator{AffineHalfspace{fmpq}} over the Halfspaces of R^3 described by:
-x₁ ≦ 1
x₁ ≦ 1
-x₂ ≦ 1
x₂ ≦ 1
-x₃ ≦ 1
x₃ ≦ 1

facets(P::Polyhedron)

Return the facets of P as halfspaces.

Examples

We can retrieve the six facets of the 3-dimensional cube this way:

julia> C = cube(3);

julia> facets(C)
6-element SubObjectIterator{AffineHalfspace{fmpq}} over the Halfspaces of R^3 described by:
-x₁ ≦ 1
x₁ ≦ 1
-x₂ ≦ 1
x₂ ≦ 1
-x₃ ≦ 1
x₃ ≦ 1

vertices(P::Polyhedron)

Return an iterator over the vertices of a polyhedron P as points.

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(P)
5-element SubObjectIterator{PointVector{fmpq}}:
 [-1, -1]
 [2, -1]
 [2, 1]
 [-1, 2]
 [1, 2]

rays(P::Polyhedron)

Return minimal set of generators of the cone of unbounded directions of P (i.e. its rays) as points.

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(PO)
2-element SubObjectIterator{RayVector{fmpq}}:
 [1, 0]
 [0, 1]

affine_hull(P::Polytope)

Return the (affine) hyperplanes generating the affine hull of P.

Examples

This triangle in $\mathbb{R}^4$ is contained in the plane defined by $P = \{ (x_1, x_2, x_3, x_4) | x_3 = 2 ∧ x_4 = 5 \}$.

julia> t = convex_hull([0 0 2 5; 1 0 2 5; 0 1 2 5]);

julia> affine_hull(t)
2-element SubObjectIterator{AffineHyperplane{fmpq}} over the Hyperplanes of R^4 described by:
x₃ = 2
x₄ = 5

ambient_dim(P::Polyhedron)

Return the ambient dimension of P.

Examples

julia> V = [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1];

julia> P = convex_hull(V);

julia> ambient_dim(P)
3

dim(P::Polyhedron)

Return the dimension of P.

Examples

julia> V = [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1];

julia> P = convex_hull(V);

julia> dim(P)
2

codim(P::Polyhedron)

Return the codimension of P.

Examples

julia> V = [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1];

julia> P = convex_hull(V);

julia> codim(P)
1

is_bounded(P::Polyhedron)

Check whether P is bounded.

Examples

julia> P = Polyhedron([1 -3; -1 1; -1 0; 0 -1],[1,1,1,1]);

julia> is_bounded(P)
false

is_feasible(P::Polyhedron)

Check whether P is feasible, i.e. non-empty.

Examples

julia> P = Polyhedron([1 -1; -1 1; -1 0; 0 -1],[-1,-1,1,1]);

julia> is_feasible(P)
false

is_fulldimensional(P::Polyhedron)

Check whether P is full-dimensional.

Examples

julia> V = [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1];

julia> is_fulldimensional(convex_hull(V))
false

lineality_dim(P::Polyhedron)

Return the dimension of the lineality space, i.e. the dimension of the largest affine subspace contained in P.

Examples

Polyhedron with one lineality direction.

julia> C = convex_hull([0 0], [1 0], [1 1])
A polyhedron in ambient dimension 2

julia> lineality_dim(C)
1

lineality_space(P::Polyhedron)

Return a matrix whose row span is the lineality space of P.

Examples

Despite not being reflected in this construction of the upper half-plane, its lineality in $x$-direction is recognized:

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

julia> lineality_space(UH)
1-element SubObjectIterator{RayVector{fmpq}}:
 [1, 0]

recession_cone(P::Polyhedron)

Return the recession cone of P.

Examples

julia> P = Polyhedron([1 -2; -1 1; -1 0; 0 -1],[2,1,1,1]);

julia> vertices(P)
3-element SubObjectIterator{PointVector{fmpq}}:
 [0, -1]
 [-1, 0]
 [-1, -1]

julia> recession_cone(P)
A polyhedral cone in ambient dimension 2

julia> rays(recession_cone(P))
2-element SubObjectIterator{RayVector{fmpq}}:
 [1, 1//2]
 [1, 1]

relative_interior_point(P::Polyhedron)

Compute a point in the relative interior point of P, i.e. a point in P not contained in any facet.

Examples

The square $[-1,1]^3$ has the origin as a relative interior point.

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

julia> relative_interior_point(square)
2-element PointVector{fmpq}:
 0
 0

julia> vertices(square)
4-element SubObjectIterator{PointVector{fmpq}}:
 [-1, -1]
 [1, -1]
 [-1, 1]
 [1, 1]

nfacets(P::Polyhedron)

Return the number of facets of P.

Examples

The number of facets of the 5-dimensional cross polytope can be retrieved via the following line:

julia> nfacets(cross(5))
32

nvertices(P::Polyhedron)

Return the number of vertices of P.

Examples

The 3-cube's number of vertices can be obtained with this input:

julia> C = cube(3);

julia> nvertices(C)
8

f_vector(P::Polyhedron)

Return the vector $(f₀,f₁,f₂,...,f_{(dim(P)-1))$` where $f_i$ is the number of faces of $P$ of dimension $i$.

Examples

Here we compute the f-vector of the 5-cube:

julia> f_vector(cube(5))
5-element Vector{fmpz}:
 32
 80
 80
 40
 10

g_vector(P::Polyhedron)

Return the (toric) $g$-vector of a polytope. Defined by $g_0 = 1 $ and $g_k = h_k - h_{k-1}$, for $1 \leq k \leq \lceil (d+1)/2\rceil$ where $h$ is the $h$-vector and $d=\dim(P)$. Undefined for unbounded polyhedra.

Examples

julia> g_vector(cross(3))
2-element Vector{fmpz}:
 1
 2

h_vector(P::Polyhedron)

Return the (toric) h-vector of a polytope. For simplicial polytopes this is a linear transformation of the f-vector. Undefined for unbounded polyhedra.

Examples

julia> h_vector(cross(3))
4-element Vector{fmpz}:
 1
 3
 3
 1

all_triangulations(pts::AbstractCollection[PointVector]; full=false)

Compute all triangulations on the points given as the rows of pts. Optionally select full=true to output full triangulations only, i.e. those that use all given points.

The return type is a Vector{Vector{Vector{Int}}} where each Vector{Vector{Int}} encodes a triangulation, in which a Vector{Int} encodes a simplex as the set of indices of the vertices of the simplex. I.e. the Vector{Int} [1,2,4] corresponds to the simplex that is the convex hull of the first, second, and fourth input point.

Examples

julia> c = cube(2,0,1)
A polyhedron in ambient dimension 2

julia> V = vertices(c)
4-element SubObjectIterator{PointVector{fmpq}}:
 [0, 0]
 [1, 0]
 [0, 1]
 [1, 1]

julia> all_triangulations(V)
2-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [2, 3, 4]]
 [[1, 2, 4], [1, 3, 4]]

all_triangulations(P::Polyhedron)

Compute all triangulations that can be formed using the vertices of the given bounded and full-dimensional polytope P.

The return type is a Vector{Vector{Vector{Int}}} where each Vector{Vector{Int}} encodes a triangulation, in which a Vector{Int} encodes a simplex as the set of indices of the vertices of the simplex. I.e. the Vector{Int} [1,2,4] corresponds to the simplex that is the convex hull of the first, second, and fourth input point.

Examples

julia> c = cube(2,0,1)
A polyhedron in ambient dimension 2

julia> all_triangulations(c)
2-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [2, 3, 4]]
 [[1, 2, 4], [1, 3, 4]]

boundary_lattice_points(P::Polyhedron{fmpq})

Return the integer points contained in the boundary of the bounded polyhedron P.

Examples

julia> c = polarize(cube(3))
A polyhedron in ambient dimension 3

julia> boundary_lattice_points(c)
6-element SubObjectIterator{PointVector{fmpz}}:
 [-1, 0, 0]
 [0, -1, 0]
 [0, 0, -1]
 [0, 0, 1]
 [0, 1, 0]
 [1, 0, 0]

contains(P::Polyhedron, v::AbstractVector)

Check whether P contains v.

Examples

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

julia> PO = Polyhedron([-1 0; 0 -1], [0, 0]);

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

julia> contains(PO, [1, -2])
false

ehrhart_polynomial(P::Polyhedron{fmpq})

Compute the Ehrhart polynomial of P.

Examples

```jldoctest julia> c = cube(3) A polyhedron in ambient dimension 3

julia> ehrhart_polynomial(c) 8x^3 + 12x^2 + 6*x + 1

ehrhart_polynomial(R::FmpqMPolyRing, P::Polyhedron{fmpq})

Compute the Ehrhart polynomial of P and return it as a polynomial in R.

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rational Field, x)

julia> c = cube(3)
A polyhedron in ambient dimension 3

julia> ehrhart_polynomial(R, c)
8*x^3 + 12*x^2 + 6*x + 1

h_star_polynomial(P::Polyhedron)

Compute the $h^*$ polynomial of P.

Examples

```jldoctest julia> c = cube(3) A polyhedron in ambient dimension 3

julia> hstarpolynomial(c) x^3 + 23x^2 + 23x + 1

h_star_polynomial(R::FmpqMPolyRing, P::Polyhedron)

Compute the $h^*$ polynomial of P and return it as a polynomial in R.

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rational Field, x)

julia> c = cube(3)
A polyhedron in ambient dimension 3

julia> h_star_polynomial(R, c)
x^3 + 23*x^2 + 23*x + 1

interior_lattice_points(P::Polyhedron{fmpq})

Return the integer points contained in the interior of the bounded polyhedron P.

Examples

julia> c = cube(3)
A polyhedron in ambient dimension 3

julia> interior_lattice_points(c)
1-element SubObjectIterator{PointVector{fmpz}}:
 [0, 0, 0]

is_normal(P::Polyhedron{fmpq})

Check whether P is normal.

Examples

The 3-cube is normal.

julia> C = cube(3)
A polyhedron in ambient dimension 3

julia> is_normal(C)
true

But this pyramid is not:

julia> P = convex_hull([0 0 0; 0 1 1; 1 1 0; 1 0 1]);

julia> is_normal(P)
false

is_simple(P::Polyhedron)

Check whether P is simple.

Examples

julia> c = cube(2,0,1)
A polyhedron in ambient dimension 2

julia> is_simple(c)
true

is_smooth(P::Polyhedron{fmpq})

Check whether P is smooth.

Examples

A cube is always smooth.

julia> C = cube(8);

julia> is_smooth(C)
true

is_very_ample(P::Polyhedron{fmpq})

Check whether P is very ample.

Examples

julia> c = cube(3)
A polyhedron in ambient dimension 3

julia> is_very_ample(c)
true

julia> P = convex_hull([0 0 0; 1 1 0; 1 0 1; 0 1 1])
A polyhedron in ambient dimension 3

julia> is_very_ample(P)
false

lattice_points(P::Polyhedron{fmpq})

Return the integer points contained in the bounded polyhedron P.

Examples

julia> S = 2 * simplex(2);

julia> lattice_points(S)
6-element SubObjectIterator{PointVector{fmpz}}:
 [0, 0]
 [0, 1]
 [0, 2]
 [1, 0]
 [1, 1]
 [2, 0]

lattice_volume(P::Polyhedron{fmpq})

Return the lattice volume of P.

Examples

julia> C = cube(2);

julia> lattice_volume(C)
8

normalized_volume(P::Polyhedron)

Return the (normalized) volume of P.

Examples

julia> C = cube(2);

julia> normalized_volume(C)
8

polarize(P::Polyhedron)

Return the polar dual of the polyhedron P, consisting of all linear functions whose evaluation on P does not exceed 1.

Examples

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

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

julia> vertices(P)
4-element SubObjectIterator{PointVector{fmpq}}:
 [1, 0]
 [-1, 0]
 [0, 1]
 [0, -1]

project_full(P::Polyhedron)

Project the polyhedron down such that it becomes full dimensional in the new ambient space.

julia> P = convex_hull([1 0 0; 0 0 0])
A polyhedron in ambient dimension 3

julia> is_fulldimensional(P)
false

julia> p = project_full(P)
A polyhedron in ambient dimension 1

julia> is_fulldimensional(p)
true

print_constraints(A::AnyVecOrMat, b::AbstractVector; trivial::Bool = false, numbered::Bool = false)

Pretty print the constraints given by $P(A,b) = \{ x | Ax ≤ b \}$.

Trivial inequalities are counted but omitted. They are included if trivial is set to true.

Examples

julia> print_constraints([-1 0 4 5; 4 4 4 3; 1 0 0 0; 0 0 0 0; 0 0 0 0; 9 9 9 9], [0, 1, 2, 3, -4, 5]; numbered = true)
1: -x₁ + 4*x₃ + 5*x₄ ≦ 0
2: 4*x₁ + 4*x₂ + 4*x₃ + 3*x₄ ≦ 1
3: x₁ ≦ 2
5: 0 ≦ -4
6: 9*x₁ + 9*x₂ + 9*x₃ + 9*x₄ ≦ 5

julia> print_constraints([-1 0 4 5; 4 4 4 3; 1 0 0 0; 0 0 0 0; 0 0 0 0; 9 9 9 9], [0, 1, 2, 3, -4, 5]; trivial = true)
-x₁ + 4*x₃ + 5*x₄ ≦ 0
4*x₁ + 4*x₂ + 4*x₃ + 3*x₄ ≦ 1
x₁ ≦ 2
0 ≦ 3
0 ≦ -4
9*x₁ + 9*x₂ + 9*x₃ + 9*x₄ ≦ 5

print_constraints(P::Polyhedron; trivial::Bool = false, numbered::Bool = false)

Pretty print the constraints given by $P(A,b) = \{ x | Ax ≤ b \}$.

Trivial inequalities are counted but omitted. They are included if trivial is set to true.

Examples

The 3-cube is given by $-1 ≦ x_i ≦ 1 ∀ i ∈ \{1, 2, 3\}$.

julia> print_constraints(cube(3))
-x₁ ≦ 1
x₁ ≦ 1
-x₂ ≦ 1
x₂ ≦ 1
-x₃ ≦ 1
x₃ ≦ 1

regular_triangulations(pts::AbstractCollection[PointVector]; full=false)

Compute all regular triangulations on the points given as the rows of pts.

A triangulation is regular if it can be induced by weights, i.e. attach a weight to every point, take the convex hull of these new vectors and then take the subdivision corresponding to the facets visible from below (lower envelope). Optionally specify full, i.e. that every triangulation must use all points.

The return type is a Vector{Vector{Vector{Int}}} where each Vector{Vector{Int}} encodes a triangulation, in which a Vector{Int} encodes a simplex as the set of indices of the vertices of the simplex. I.e. the Vector{Int} [1,2,4] corresponds to the simplex that is the convex hull of the first, second, and fourth input point.

Examples

julia> c = cube(2,0,1)
A polyhedron in ambient dimension 2

julia> V = vertices(c)
4-element SubObjectIterator{PointVector{fmpq}}:
 [0, 0]
 [1, 0]
 [0, 1]
 [1, 1]

julia> regular_triangulations(V)
2-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [2, 3, 4]]
 [[1, 3, 4], [1, 2, 4]]

regular_triangulations(P::Polyhedron)

Compute all regular triangulations that can be formed using the vertices of the given bounded and full-dimensional polytope P.

A triangulation is regular if it can be induced by weights, i.e. attach a weight to every point, take the convex hull of these new vectors and then take the subdivision corresponding to the facets visible from below (lower envelope).

The return type is a Vector{Vector{Vector{Int}}} where each Vector{Vector{Int}} encodes a triangulation, in which a Vector{Int} encodes a simplex as the set of indices of the vertices of the simplex. I.e. the Vector{Int} [1,2,4] corresponds to the simplex that is the convex hull of the first, second, and fourth input point.

Examples

julia> c = cube(2,0,1)
A polyhedron in ambient dimension 2

julia> regular_triangulations(c)
2-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [2, 3, 4]]
 [[1, 3, 4], [1, 2, 4]]

regular_triangulation(pts::AbstractCollection[PointVector]; full=false)

Computes ONE regular triangulations on the points given as the rows of pts.

A triangulation is regular if it can be induced by weights, i.e. attach a weight to every point, take the convex hull of these new vectors and then take the subdivision corresponding to the facets visible from below (lower envelope). Optionally specify full, i.e. that every triangulation must use all points.

As for regular_triangulation(pts::AnyVecOrMat; full=false) the return type is Vector{Vector{Vector{Int}}}. Here, only one triangulation is computed, so the outer vector is of length one. Its entry of type Vector{Vector{Int}} encodes the triangulation in question. Recall that a Vector{Int} encodes a simplex as the set of indices of the vertices of the simplex. I.e. the Vector{Int} [1,2,4] corresponds to the simplex that is the convex hull of the first, second, and fourth input point.

Examples

julia> c = cube(2,0,1)
A polyhedron in ambient dimension 2

julia> V = vertices(c)
4-element SubObjectIterator{PointVector{fmpq}}:
 [0, 0]
 [1, 0]
 [0, 1]
 [1, 1]

julia> regular_triangulation(V)
1-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [2, 3, 4]]

regular_triangulation(P::Polyhedron)

Computes ONE regular triangulations that can be formed using the vertices of the given bounded and full-dimensional polytope P.

A triangulation is regular if it can be induced by weights, i.e. attach a weight to every point, take the convex hull of these new vectors and then take the subdivision corresponding to the facets visible from below (lower envelope).

As for regular_triangulations(P::Polyhedron) the return type is Vector{Vector{Vector{Int}}}. Here, only one triangulation is computed, so the outer vector is of length one. Its entry of type Vector{Vector{Int}} encodes the triangulation in question. Recall that a Vector{Int} encodes a simplex as the set of indices of the vertices of the simplex. I.e. the Vector{Int} [1,2,4] corresponds to the simplex that is the convex hull of the first, second, and fourth input point.

Examples

julia> c = cube(2,0,1)
A polyhedron in ambient dimension 2

julia> regular_triangulation(c)
1-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [2, 3, 4]]

secondary_polytope(P::Polyhedron)

Compute the secondary polytope of a polyhedron, i.e. the convex hull of all the gkz vectors of all its (regular) triangulations. A triangulation here means only using the vertices of P.

Examples

Compute the secondary polytope of the cube.

julia> c = cube(3)
A polyhedron in ambient dimension 3

julia> sc = secondary_polytope(c)
A polyhedron in ambient dimension 8

solve_ineq(A::fmpz_mat, b::fmpz_mat)

Solve $Ax<=b$, assumes finite set of solutions.

Examples

The following gives the vertices of the square. The solutions are the rows of the output. Note that the output can be permuted, hence we sort it.

julia> A = fmpz_mat([1 0; 0 1; -1 0; 0 -1]);

julia> b = zero_matrix(FlintZZ, 4,1); b[1,1]=1; b[2,1]=1; b[3,1]=0; b[4,1]=0;

julia> sortslices(Matrix{BigInt}(solve_ineq(A, b)), dims=1)
4×2 Matrix{BigInt}:
 0  0
 0  1
 1  0
 1  1

solve_mixed(A::fmpz_mat, b::fmpz_mat, C::fmpz_mat, d::fmpz_mat)

Solve $Ax = b$ under $Cx >= d$, assumes a finite solution set.

Examples

Find all $(x_1, x_2)\in\mathbb{Z}^2$ such that $x_1+x_2=7$, $x_1\ge 2$, and $x_2\ge 3$. The solutions are the rows of the output. Note that the output can be permuted, hence we sort it.

julia> A = fmpz_mat([1 1]);

julia> b = zero_matrix(FlintZZ, 1,1); b[1,1]=7;

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

julia> d = zero_matrix(FlintZZ,2,1); d[1,1]=2; d[2,1]=3;

julia> sortslices(Matrix{BigInt}(solve_mixed(A, b, C, d)), dims=1)
3×2 Matrix{BigInt}:
 2  5
 3  4
 4  3

solve_mixed(A::fmpz_mat, b::fmpz_mat, C::fmpz_mat)

Solve $Ax = b$ under $Cx >= 0$, assumes a finite solution set.

Examples

Find all $(x_1, x_2)\in\mathbb{Z}^2_{\ge 0}$ such that $x_1+x_2=3$. The solutions are the rows of the output. Note that the output can be permuted, hence we sort it.

julia> A = fmpz_mat([1 1]);

julia> b = zero_matrix(FlintZZ, 1,1); b[1,1]=3;

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

julia> sortslices(Matrix{BigInt}(solve_mixed(A, b, C)), dims=1)
4×2 Matrix{BigInt}:
 0  3
 1  2
 2  1
 3  0

solve_non_negative(A::fmpz_mat, b::fmpz_mat)

Find all solutions to $Ax = b$, $x>=0$. Assumes a finite set of solutions.

Examples

Find all $(x_1, x_2)\in\mathbb{Z}^2_{\ge 0}$ such that $x_1+x_2=3$. The solutions are the rows of the output. Note that the output can be permuted, hence we sort it.

julia> A = fmpz_mat([1 1]);

julia> b = zero_matrix(FlintZZ, 1,1); b[1,1]=3;

julia> sortslices(Matrix{BigInt}(solve_non_negative(A, b)), dims=1)
4×2 Matrix{BigInt}:
 0  3
 1  2
 2  1
 3  0

support_function(P::Polyhedron; convention::Symbol = :max)

Produce a function $h(ω) = max\{dot(x,ω)\ |\ x \in P\}$. $max$ may be changed to $min$ by setting convention = :min.

Examples

julia> P = cube(3) + simplex(3);

julia> φ = support_function(P);

julia> φ([1,2,3])
9

julia> ψ = support_function(P, convention = :min);

julia> ψ([1,2,3])
-6

volume(P::Polyhedron)

Return the (Euclidean) volume of P.

Examples

julia> C = cube(2);

julia> volume(C)
4