Auxiliary functions
Geometric data
facets
— Methodfacets(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
— Methodvertices([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
— Methodrays([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
— Methodrays_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
— Methodminimal_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
— Methodaffine_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
— Methodambient_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
— Methoddim(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
— Methodcodim(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
— Methodis_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
— Methodis_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
— Methodis_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
— Methodis_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
— Methodlineality_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
— Methodlineality_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
— Methodrecession_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
— Methodrelative_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]
Combinatorial data
n_facets
— Methodn_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
— Methodn_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
— Methodf_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
— Methodfacet_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
— Methodg_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
— Methodh_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
— Methodvertex_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
Groups
linear_symmetries
— Methodlinear_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
— Methodcombinatorial_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
— Methodautomorphism_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
— Methodautomorphism_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
— Methodautomorphism_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
— Methodautomorphism_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)
Other
all_triangulations
— Functionall_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
— Methodboundary_lattice_points(P::Polyhedron{QQFieldElem})
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
— Methodin(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
— Methodissubset(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
— Methodehrhart_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
— Methodehrhart_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
— Methodh_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
— Methodh_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
— Methodinterior_lattice_points(P::Polyhedron{QQFieldElem})
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
— Methodis_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
— Methodis_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
— Methodis_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
— Methodis_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
— Methodis_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
.
This will only recognize algebraically precise solids, i.e. no solids with approximate coordinates.
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
— Methodis_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
.
This will only recognize algebraically precise solids, i.e. no solids with approximate coordinates.
Examples
julia> J = johnson_solid(37)
Polytope in ambient dimension 3 with EmbeddedAbsSimpleNumFieldElem type coefficients
julia> is_johnson_solid(J)
true
is_platonic_solid
— Methodis_platonic_solid(P::Polyhedron)
Check whether P
is a Platonic solid.
See also platonic_solid
.
This will only recognize algebraically precise solids, i.e. no solids with approximate coordinates.
Examples
julia> is_platonic_solid(cube(3))
true
lattice_points
— Methodlattice_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
— Methodlattice_volume(P::Polyhedron{QQFieldElem})
Return the lattice volume of P
.
Examples
julia> C = cube(2);
julia> lattice_volume(C)
8
normalized_volume
— Methodnormalized_volume(P::Polyhedron)
Return the (normalized) volume of P
.
Examples
julia> C = cube(2);
julia> normalized_volume(C)
8
polarize
— Methodpolarize(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
— Methodproject_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
— Methodprint_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
: TargetIO
where the constraints are printed to.trivial::Bool
: Iftrue
, include trivial inequalities.numbered::Bool
: Iftrue
, the each constraint is printed with the index corresponding to the inputAnyVecOrMat
.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
— Methodprint_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
: TargetIO
where the constraints are printed to.trivial::Bool
: Iftrue
, include trivial inequalities.numbered::Bool
: Iftrue
, the each constraint is printed with the index corresponding to the inputAnyVecOrMat
.
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
— Functionregular_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
— Functionregular_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
— Functionsecondary_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
— Methodsolve_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
— Methodsolve_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
— Methodsolve_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
— Methodsolve_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
— Methodsupport_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
— Methodvolume(P::Polyhedron)
Return the (Euclidean) volume of P
.
Examples
julia> C = cube(2);
julia> volume(C)
4