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}}:
 Polytope in ambient dimension 3
 Polytope in ambient dimension 3
 Polytope in ambient dimension 3
 Polytope in ambient dimension 3
 Polytope in ambient dimension 3
 Polytope in ambient dimension 3

julia> facets(Halfspace, C)
6-element SubObjectIterator{AffineHalfspace{QQFieldElem}} over the halfspaces of R^3 described by:
-x_1 <= 1
x_1 <= 1
-x_2 <= 1
x_2 <= 1
-x_3 <= 1
x_3 <= 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 <= 1
x_1 <= 1
-x_2 <= 1
x_2 <= 1
-x_3 <= 1
x_3 <= 1

vertices([as::Type{T} = PointVector,] P::Polyhedron)

Return an iterator over the vertices of P in the format defined by as. The vertices are defined to be the zero-dimensional faces, so if P has lineality, there are no vertices, only minimal faces.

See also minimal_faces and rays.

Optional arguments for as include

• PointVector.

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

julia> point_matrix(vertices(P))
[-1   -1]
[ 2   -1]
[ 2    1]
[-1    2]
[ 1    2]

A half-space (here in $3$-space) has no vertices:

julia> UH = polyhedron([-1 0 0], [0])
Polyhedron in ambient dimension 3

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

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. The rays are defined to be the one-dimensional faces of the recession cone, so if P has lineality, there are no rays.

See also rays_modulo_lineality, recession_cone and vertices.

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{QQFieldElem}}:
 [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]

A half-space has no rays:

julia> UH = polyhedron([-1 0 0], [0])
Polyhedron in ambient dimension 3

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

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.

See also rays and lineality_space.

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.

See also vertices and lineality_space.

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_3 = 2
x_4 = 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)
Polytope in ambient dimension 3

julia> is_lattice_polytope(c)
true

julia> c = cube(3, 0, 4//3)
Polytope 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)
Polytope 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]

n_facets(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> n_facets(cross_polytope(5))
32

n_vertices(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> n_vertices(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

facet_sizes(P::Polyhedron{T})

Number of vertices in each facet.

Example

julia> p = johnson_solid(4) 
Polytope in ambient dimension 3 with EmbeddedAbsSimpleNumFieldElem type coefficients

julia> facet_sizes(p)
10-element Vector{Int64}:
 8
 4
 3
 4
 4
 3
 4
 3
 3
 4

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

vertex_sizes(P::Polyhedron{T})

Number of incident facets for each vertex.

Example

julia> vertex_sizes(bipyramid(simplex(2)))
5-element Vector{Int64}:
 4
 4
 4
 3
 3

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)
Polytope in ambient dimension 3

julia> G = linear_symmetries(c)
Permutation group of degree 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)
Permutation group of degree 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)
Permutation group of degree 4

julia> order(G)
8

julia> G = linear_symmetries(quad)
Permutation group of degree 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)
Polytope 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)
Polytope 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)
Polytope 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)
Polytope 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)

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

Examples

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

julia> Q = cube(3,-1,2)
Polytope 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)
Polytope 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)
Polytope 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)
Polytope 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)
Polytope in ambient dimension 3

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

interior_lattice_points(P::Polyhedron)

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

Examples

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

is_archimedean_solid(P::Polyhedron)

Check whether P is an Archimedean solid, i.e., a $3$-dimensional vertex transitive polytope with regular facets, but not a prism or antiprism.

See also archimedean_solid.

Examples

julia> TO = archimedean_solid("truncated_octahedron")
Polytope in ambient dimension 3

julia> is_archimedean_solid(TO)
true

julia> T = tetrahedron()
Polytope in ambient dimension 3

julia> is_archimedean_solid(T)
false

is_johnson_solid(P::Polyhedron)

Check whether P is a Johnson solid, i.e., a $3$-dimensional polytope with regular faces that is not vertex transitive.

See also johnson_solid.

Examples

julia> J = johnson_solid(37)
Polytope in ambient dimension 3 with EmbeddedAbsSimpleNumFieldElem type coefficients

julia> is_johnson_solid(J)
true

is_platonic_solid(P::Polyhedron)

Check whether P is a Platonic solid.

See also platonic_solid.

Examples

julia> is_platonic_solid(cube(3))
true

lattice_points(P::Polyhedron)

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

julia> P = polarize(square)
Polytope 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([io = stdout,] A::AnyVecOrMat, b::AbstractVector; trivial = false, numbered = false, cmp = :lte)

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

Optional & Keyword Arguments

• io::IO: Target IO where the constraints are printed to.
• trivial::Bool: If true, include trivial inequalities.
• numbered::Bool: If true, the each constraint is printed with the index corresponding to the input AnyVecOrMat.
• cmp::Symbol: Defines the string used for the comparison sign; supports :lte (less than or equal) and :eq (equal).

Trivial inequalities are always counted for numbering, even when omitted.

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_1 + 4*x_3 + 5*x_4 <= 0
2: 4*x_1 + 4*x_2 + 4*x_3 + 3*x_4 <= 1
3: x_1 <= 2
5: 0 <= -4
6: 9*x_1 + 9*x_2 + 9*x_3 + 9*x_4 <= 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_1 + 4*x_3 + 5*x_4 <= 0
4*x_1 + 4*x_2 + 4*x_3 + 3*x_4 <= 1
x_1 <= 2
0 <= 3
0 <= -4
9*x_1 + 9*x_2 + 9*x_3 + 9*x_4 <= 5

print_constraints([io = stdout,] P::Polyhedron; trivial = false, numbered = false)

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

Optional & Keyword Arguments

• io::IO: Target IO where the constraints are printed to.
• trivial::Bool: If true, include trivial inequalities.
• numbered::Bool: If true, the each constraint is printed with the index corresponding to the input AnyVecOrMat.

Trivial inequalities are always counted for numbering, even when omitted.

Examples

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

julia> print_constraints(cube(3))
-x_1 <= 1
x_1 <= 1
-x_2 <= 1
x_2 <= 1
-x_3 <= 1
x_3 <= 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)
Polytope 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, 2, 4], [1, 3, 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)
Polytope in ambient dimension 2

julia> regular_triangulations(c)
2-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [2, 3, 4]]
 [[1, 2, 4], [1, 3, 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)
Polytope 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)
Polytope 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)
Polytope in ambient dimension 3

julia> sc = secondary_polytope(c)
Polytope 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. The solutions are the (transposed) rows of the output.
• 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$. 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> it = solve_mixed(SubObjectIterator{PointVector{ZZRingElem}}, A, b, C);

julia> typeof(it)
SubObjectIterator{PointVector{ZZRingElem}}

julia> for x in it
       print(A*x," ")
       end
[7] [7] [7] [7] [7] [7] [7] [7] 

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. The solutions are the (transposed) rows of the output.
• 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$. 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> it = solve_mixed(SubObjectIterator{PointVector{ZZRingElem}}, A, b, C);

julia> typeof(it)
SubObjectIterator{PointVector{ZZRingElem}}

julia> for x in it
       print(A*x," ")
       end
[3] [3] [3] [3] 

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