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{QQFieldElem}}:
 Polyhedron in ambient dimension 3
 Polyhedron in ambient dimension 3
 Polyhedron in ambient dimension 3
 Polyhedron in ambient dimension 3
 Polyhedron in ambient dimension 3
 Polyhedron in ambient dimension 3

julia> facets(Halfspace, C)
6-element SubObjectIterator{AffineHalfspace{QQFieldElem}} 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{QQFieldElem}} 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{QQFieldElem}}:
 [-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{QQFieldElem}}:
 [1, 0]
 [0, 1]

julia> matrix(QQ, rays(PO))
[1   0]
[0   1]

julia> matrix(ZZ, rays(PO))
[1   0]
[0   1]

rays_modulo_lineality(as, P::Polyhedron)

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

Examples

julia> P = convex_hull([0 0 1], [0 1 0], [1 0 0])
Polyhedron in ambient dimension 3

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

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

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

minimal_faces(as, P::Polyhedron)

Return the minimal faces of a polyhedron as a NamedTuple with two iterators. For a polyhedron without lineality, the base_points are the vertices. If P has lineality L, then every minimal face is an affine translation p+L, where p is only unique modulo L. The return type is a dict, the key :base_points gives an iterator over such p, and the key :lineality_basis lets one access a basis for the lineality space L of P.

Examples

The polyhedron P is just a line through the origin:

julia> P = convex_hull([0 0], nothing, [1 0])
Polyhedron in ambient dimension 2

julia> lineality_dim(P)
1

julia> vertices(P)
0-element SubObjectIterator{PointVector{QQFieldElem}}

julia> minimal_faces(P)
(base_points = PointVector{QQFieldElem}[[0, 0]], lineality_basis = RayVector{QQFieldElem}[[1, 0]])

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{QQFieldElem}} 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

is_lattice_polytope(P::Polyhedron{QQFieldElem})

Check whether P is a lattice polytope, i.e. it is bounded and has integral vertices.

Examples

julia> c = cube(3)
Polyhedron in ambient dimension 3

julia> is_lattice_polytope(c)
true

julia> c = cube(3, 0, 4//3)
Polyhedron in ambient dimension 3

julia> is_lattice_polytope(c)
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])
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{QQFieldElem}}:
 [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{QQFieldElem}}:
 [0, -1]
 [-1, 0]
 [-1, -1]

julia> recession_cone(P)
Polyhedral cone in ambient dimension 2

julia> rays(recession_cone(P))
2-element SubObjectIterator{RayVector{QQFieldElem}}:
 [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)
Polyhedron in ambient dimension 2

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

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

julia> matrix(QQ, vertices(square))
[-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_polytope(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{ZZRingElem}:
 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_polytope(3))
2-element Vector{ZZRingElem}:
 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_polytope(3))
4-element Vector{ZZRingElem}:
 1
 3
 3
 1

linear_symmetries(P::Polyhedron)

Get the group of linear symmetries on the vertices of a polyhedron. These are morphisms of the form $x\mapsto Ax+b$,with $A$ a matrix and $b$ a vector, that preserve the polyhedron $P$. The result is given as permutations of the vertices (or rather vertex indices) of $P$.

Examples

The 3-dimensional cube has 48 linear symmetries.

julia> c = cube(3)
Polyhedron in ambient dimension 3

julia> G = linear_symmetries(c)
Group([ (3,5)(4,6), (2,3)(6,7), (1,2)(3,4)(5,6)(7,8) ])

julia> order(G)
48

The quadrangle one obtains from moving one vertex of the square out along the diagonal has two linear symmetries.

julia> quad = convex_hull([0 0; 1 0; 2 2; 0 1])
Polyhedron in ambient dimension 2

julia> G = linear_symmetries(quad)
Group([ (2,4) ])

julia> order(G)
2

combinatorial_symmetries(P::Polyhedron)

Compute the combinatorial symmetries (i.e., automorphisms of the face lattice) of a given polytope $P$. The result is given as permutations of the vertices (or rather vertex indices) of $P$. This group contains the linear_symmetries as a subgroup.

Examples

The quadrangle one obtains from moving one vertex of the square out along the diagonal has eight combinatorial symmetries, but only two linear symmetries.

julia> quad = convex_hull([0 0; 1 0; 2 2; 0 1])
Polyhedron in ambient dimension 2

julia> G = combinatorial_symmetries(quad)
Group([ (2,4), (1,2)(3,4) ])

julia> order(G)
8

julia> G = linear_symmetries(quad)
Group([ (2,4) ])

julia> order(G)
2

automorphism_group(P::Polyhedron; type = :combinatorial, action = :all)

Compute the group of automorphisms of a polyhedron. The parameters and return values are the same as for automorphism_group_generators(P::Polyhedron; type = :combinatorial, action = :all) except that groups are returned instead of generators of groups.

automorphism_group_generators(P::Polyhedron; type = :combinatorial, action = :all)

Compute generators of the group of automorphisms of a polyhedron.

The optional parameter type takes two values:

• :combinatorial (default) – Return the combinatorial symmetries, the automorphisms of the face lattice.
• :linear – Return the linear automorphisms.

The optional parameter action takes three values:

• :all (default) – Return the generators of the permutation action on both vertices and facets as a Dict{Symbol, Vector{PermGroupElem}}.
• :on_vertices – Only return generators of the permutation action on the vertices.
• :on_facets – Only return generators of the permutation action on the facets.

The return value is a Dict{Symbol, Vector{PermGroupElem}} with two entries, one for the key :on_vertices containing the generators for the action permuting the vertices, and :on_facets for the facets.

Examples

Compute the automorphisms of the 3dim cube:

julia> c = cube(3)
Polyhedron in ambient dimension 3

julia> automorphism_group_generators(c)
Dict{Symbol, Vector{PermGroupElem}} with 2 entries:
  :on_vertices => [(3,5)(4,6), (2,3)(6,7), (1,2)(3,4)(5,6)(7,8)]
  :on_facets   => [(3,5)(4,6), (1,3)(2,4), (1,2)]

julia> automorphism_group_generators(c; action = :on_vertices)
3-element Vector{PermGroupElem}:
 (3,5)(4,6)
 (2,3)(6,7)
 (1,2)(3,4)(5,6)(7,8)

julia> automorphism_group_generators(c; action = :on_facets)
3-element Vector{PermGroupElem}:
 (3,5)(4,6)
 (1,3)(2,4)
 (1,2)

Compute the automorphisms of a non-quadratic quadrangle. Since it has less symmetry than the square, it has less linear symmetries.

julia> quad = convex_hull([0 0; 1 0; 2 2; 0 1])
Polyhedron in ambient dimension 2

julia> automorphism_group_generators(quad)
Dict{Symbol, Vector{PermGroupElem}} with 2 entries:
  :on_vertices => [(2,4), (1,2)(3,4)]
  :on_facets   => [(1,2)(3,4), (1,3)]

julia> automorphism_group_generators(quad; type = :combinatorial)
Dict{Symbol, Vector{PermGroupElem}} with 2 entries:
  :on_vertices => [(2,4), (1,2)(3,4)]
  :on_facets   => [(1,2)(3,4), (1,3)]

julia> automorphism_group_generators(quad; type = :linear)
Dict{Symbol, Vector{PermGroupElem}} with 2 entries:
  :on_vertices => [(2,4)]
  :on_facets   => [(1,2)(3,4)]

automorphism_group(IM::IncidenceMatrix; action = :all)

Compute the group of automorphisms of an IncidenceMatrix. The parameters and return values are the same as for automorphism_group_generators(IM::IncidenceMatrix; action = :all) except that groups are returned instead of generators of groups.

automorphism_group_generators(IM::IncidenceMatrix; action = :all)

Compute the generators of the group of automorphisms of an IncidenceMatrix.

The optional parameter action takes three values:

• :all (default) – Return the generators of the permutation action on both columns and rows as a Dict{Symbol, Vector{PermGroupElem}}.
• :on_cols – Only return generators of the permutation action on the columns.
• :on_rows – Only return generators of the permutation action on the rows.

Examples

Compute the automorphisms of the incidence matrix of the 3dim cube:

julia> c = cube(3)
Polyhedron in ambient dimension 3

julia> IM = vertex_indices(facets(c))
6×8 IncidenceMatrix
[1, 3, 5, 7]
[2, 4, 6, 8]
[1, 2, 5, 6]
[3, 4, 7, 8]
[1, 2, 3, 4]
[5, 6, 7, 8]


julia> automorphism_group_generators(IM)
Dict{Symbol, Vector{PermGroupElem}} with 2 entries:
  :on_cols => [(3,5)(4,6), (2,3)(6,7), (1,2)(3,4)(5,6)(7,8)]
  :on_rows => [(3,5)(4,6), (1,3)(2,4), (1,2)]

julia> automorphism_group_generators(IM; action = :on_rows)
3-element Vector{PermGroupElem}:
 (3,5)(4,6)
 (1,3)(2,4)
 (1,2)

julia> automorphism_group_generators(IM; action = :on_cols)
3-element Vector{PermGroupElem}:
 (3,5)(4,6)
 (2,3)(6,7)
 (1,2)(3,4)(5,6)(7,8)

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)
Polyhedron in ambient dimension 2

julia> V = vertices(c)
4-element SubObjectIterator{PointVector{QQFieldElem}}:
 [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)
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{QQFieldElem})

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

Examples

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

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

julia> matrix(ZZ, boundary_lattice_points(c))
[-1    0    0]
[ 0   -1    0]
[ 0    0   -1]
[ 0    0    1]
[ 0    1    0]
[ 1    0    0]

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

Check whether the vector v is contained in the polyhedron P.

Examples

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

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

julia> [1, 2] in PO
true

julia> [1, -2] in PO
false

issubset(P::Polyhedron, Q::Polyhedron)

Check whether P is a subset of the polyhedron Q.

Examples

julia> P = cube(3,0,1)
Polyhedron in ambient dimension 3

julia> Q = cube(3,-1,2)
Polyhedron in ambient dimension 3

julia> issubset(P, Q)
true

julia> issubset(Q, P)
false

ehrhart_polynomial(P::Polyhedron{QQFieldElem})

Compute the Ehrhart polynomial of P.

Examples

julia> c = cube(3)
Polyhedron in ambient dimension 3

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

ehrhart_polynomial(R::QQMPolyRing, P::Polyhedron{QQFieldElem})

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

Examples

julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over QQ, x)

julia> c = cube(3)
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

julia> c = cube(3)
Polyhedron in ambient dimension 3

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

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

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

Examples

julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over QQ, x)

julia> c = cube(3)
Polyhedron in ambient dimension 3

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

interior_lattice_points(P::Polyhedron{QQFieldElem})

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

Examples

julia> c = cube(3)
Polyhedron in ambient dimension 3

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

julia> matrix(ZZ, interior_lattice_points(c))
[0   0   0]

is_normal(P::Polyhedron{QQFieldElem})

Check whether P is normal.

Examples

The 3-cube is normal.

julia> C = cube(3)
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)
Polyhedron in ambient dimension 2

julia> is_simple(c)
true

is_smooth(P::Polyhedron{QQFieldElem})

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{QQFieldElem})

Check whether P is very ample.

Examples

julia> c = cube(3)
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])
Polyhedron in ambient dimension 3

julia> is_very_ample(P)
false

lattice_points(P::Polyhedron{QQFieldElem})

Return the integer points contained in the bounded polyhedron P.

Examples

julia> S = 2 * simplex(2);

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

julia> matrix(ZZ, lattice_points(S))
[0   0]
[0   1]
[0   2]
[1   0]
[1   1]
[2   0]

lattice_volume(P::Polyhedron{QQFieldElem})

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)
Polyhedron in ambient dimension 2

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

julia> vertices(P)
4-element SubObjectIterator{PointVector{QQFieldElem}}:
 [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.

Examples

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

julia> is_fulldimensional(P)
false

julia> p = project_full(P)
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)
Polyhedron in ambient dimension 2

julia> V = vertices(c)
4-element SubObjectIterator{PointVector{QQFieldElem}}:
 [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)
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)
Polyhedron in ambient dimension 2

julia> V = vertices(c)
4-element SubObjectIterator{PointVector{QQFieldElem}}:
 [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)
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)
Polyhedron in ambient dimension 3

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

solve_ineq(as::Type{T}, A::ZZMatrix, b::ZZMatrix) where {T}

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

The output type may be specified in the variable as:

• ZZMatrix (default) a matrix with integers is returned.
• SubObjectIterator{PointVector{ZZRingElem}} an iterator over integer points is returned.

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 = ZZMatrix([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

julia> typeof(solve_ineq(A,b))
ZZMatrix

julia> typeof(solve_ineq(ZZMatrix, A,b))
ZZMatrix

julia> typeof(solve_ineq(SubObjectIterator{PointVector{ZZRingElem}}, A,b))
SubObjectIterator{PointVector{ZZRingElem}}

solve_mixed(as::Type{T}, A::ZZMatrix, b::ZZMatrix, C::ZZMatrix, d::ZZMatrix) where {T}

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

The output type may be specified in the variable as:

• ZZMatrix (default) a matrix with integers is returned.
• SubObjectIterator{PointVector{ZZRingElem}} an iterator over integer points is returned.

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 = ZZMatrix([1 1]);

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

julia> C = ZZMatrix([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

julia> typeof(solve_mixed(A, b, C, d))
ZZMatrix

julia> typeof(solve_mixed(ZZMatrix, A, b, C, d))
ZZMatrix

julia> typeof(solve_mixed(SubObjectIterator{PointVector{ZZRingElem}}, A, b, C, d))
SubObjectIterator{PointVector{ZZRingElem}}

solve_mixed(as::Type{T}, A::ZZMatrix, b::ZZMatrix, C::ZZMatrix) where {T}

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

The output type may be specified in the variable as:

• ZZMatrix (default) a matrix with integers is returned.
• SubObjectIterator{PointVector{ZZRingElem}} an iterator over integer points is returned.

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 = ZZMatrix([1 1]);

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

julia> C = ZZMatrix([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

julia> typeof(solve_mixed(A, b, C))
ZZMatrix

julia> typeof(solve_mixed(ZZMatrix, A, b, C))
ZZMatrix

julia> typeof(solve_mixed(SubObjectIterator{PointVector{ZZRingElem}}, A, b, C))
SubObjectIterator{PointVector{ZZRingElem}}

solve_non_negative(as::Type{T}, A::ZZMatrix, b::ZZMatrix) where {T}

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

The output type may be specified in the variable as:

• ZZMatrix (default) a matrix with integers is returned.
• SubObjectIterator{PointVector{ZZRingElem}} an iterator over integer points is returned.

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 = ZZMatrix([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

julia> typeof(solve_non_negative(A,b))
ZZMatrix

julia> typeof(solve_non_negative(ZZMatrix, A,b))
ZZMatrix

julia> typeof(solve_non_negative(SubObjectIterator{PointVector{ZZRingElem}}, A,b))
SubObjectIterator{PointVector{ZZRingElem}}

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