Auxiliary functions

Geometric data

facetsMethod
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
source
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
source
verticesMethod
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]
source
raysMethod
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]

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

julia> matrix(ZZ, rays(PO))
[1   0]
[0   1]
source
affine_hullMethod
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
source
ambient_dimMethod
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
source
dimMethod
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
source
codimMethod
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
source
is_boundedMethod
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
source
is_feasibleMethod
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
source
is_fulldimensionalMethod
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
source
lineality_dimMethod
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
source
lineality_spaceMethod
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]
source
recession_coneMethod
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]
source
relative_interior_pointMethod
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]

julia> matrix(QQ, vertices(square))
[-1   -1]
[ 1   -1]
[-1    1]
[ 1    1]
source

Combinatorial data

nfacetsMethod
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
source
nverticesMethod
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
source
f_vectorMethod
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
source
g_vectorMethod
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
source
h_vectorMethod
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
source

Groups

linear_symmetriesMethod
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)
A 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])
A polyhedron in ambient dimension 2

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

julia> order(G)
2
source
combinatorial_symmetriesMethod
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])
A 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
source
automorphism_group_generatorsMethod
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)
A 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])
A 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)]
source
automorphism_group_generatorsMethod
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)
A 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)
source

Other

all_triangulationsFunction
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]]
source
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]]
source
boundary_lattice_pointsMethod
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]

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]
source
containsMethod
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
source
ehrhart_polynomialMethod
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

source
ehrhart_polynomialMethod
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
source
h_star_polynomialMethod
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

source
h_star_polynomialMethod
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
source
interior_lattice_pointsMethod
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]

julia> matrix(ZZ, interior_lattice_points(c))
[0   0   0]
source
is_normalMethod
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
source
is_simpleMethod
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
source
is_smoothMethod
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
source
is_very_ampleMethod
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
source
lattice_pointsMethod
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]

julia> matrix(ZZ, lattice_points(S))
[0   0]
[0   1]
[0   2]
[1   0]
[1   1]
[2   0]
source
lattice_volumeMethod
lattice_volume(P::Polyhedron{fmpq})

Return the lattice volume of P.

Examples

julia> C = cube(2);

julia> lattice_volume(C)
8
source
normalized_volumeMethod
normalized_volume(P::Polyhedron)

Return the (normalized) volume of P.

Examples

julia> C = cube(2);

julia> normalized_volume(C)
8
source
polarizeMethod
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]
source
project_fullMethod
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
source
print_constraintsMethod
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
source
print_constraintsMethod
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
source
regular_triangulationsFunction
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]]
source
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]]
source
regular_triangulationFunction
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]]
source
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]]
source
secondary_polytopeFunction
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
source
solve_ineqMethod
solve_ineq(as::Type{T}, A::fmpz_mat, b::fmpz_mat) where {T}

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

The output type may be specified in the variable as:

  • fmpz_mat (default) a matrix with integers is returned.
  • SubObjectIterator{PointVector{fmpz}} 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 = 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

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

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

julia> typeof(solve_ineq(SubObjectIterator{PointVector{fmpz}}, A,b))
SubObjectIterator{PointVector{fmpz}}
source
solve_mixedMethod
solve_mixed(as::Type{T}, A::fmpz_mat, b::fmpz_mat, C::fmpz_mat, d::fmpz_mat) where {T}

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

The output type may be specified in the variable as:

  • fmpz_mat (default) a matrix with integers is returned.
  • SubObjectIterator{PointVector{fmpz}} 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 = 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

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

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

julia> typeof(solve_mixed(SubObjectIterator{PointVector{fmpz}}, A, b, C, d))
SubObjectIterator{PointVector{fmpz}}
source
solve_mixedMethod
solve_mixed(as::Type{T}, A::fmpz_mat, b::fmpz_mat, C::fmpz_mat) where {T}

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

The output type may be specified in the variable as:

  • fmpz_mat (default) a matrix with integers is returned.
  • SubObjectIterator{PointVector{fmpz}} 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 = 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

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

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

julia> typeof(solve_mixed(SubObjectIterator{PointVector{fmpz}}, A, b, C))
SubObjectIterator{PointVector{fmpz}}
source
solve_non_negativeMethod
solve_non_negative(as::Type{T}, A::fmpz_mat, b::fmpz_mat) 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:

  • fmpz_mat (default) a matrix with integers is returned.
  • SubObjectIterator{PointVector{fmpz}} 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 = 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

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

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

julia> typeof(solve_non_negative(SubObjectIterator{PointVector{fmpz}}, A,b))
SubObjectIterator{PointVector{fmpz}}
source
support_functionMethod
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
source
volumeMethod
volume(P::Polyhedron)

Return the (Euclidean) volume of P.

Examples

julia> C = cube(2);

julia> volume(C)
4
source