Introduction

The polyhedral geometry part of OSCAR provides functionality for handling

  • convex polytopes, unbounded polyhedra and cones
  • polyhedral fans
  • linear programs

General textbooks offering details on theory and algorithms include:

Scalar types

The objects from polyhedral geometry operate on a given type, which (usually) resembles a field. This is indicated by the template parameter, e.g. the properties of a Polyhedron{QQFieldElem} are rational numbers of type QQFieldElem, if applicable. Supported scalar types are FieldElem and Float64, but some functionality might not work properly if the parent Field does not satisfy certain mathematic conditions, like being ordered. When constructing a polyhedral object from scratch, for the "simpler" types QQFieldElem and Float64 it suffices to pass the Type, but more complex FieldElems require a parent Field object. This can be set by either passing the desired Field instead of the type, or by inserting the type and have a matching FieldElem in your input data. If no type or field is given, the scalar type defaults to QQFieldElem.

The parent Field of the coefficients of an object O with coefficients of type T can be retrieved with the coefficient_field function, and it holds elem_type(coefficient_field(O)) == T.

coefficient_fieldMethod
coefficient_field(P::Union{Polyhedron{T}, Cone{T}, PolyhedralFan{T}, PolyhedralComplex{T}) where T<:scalar_types

Return the parent Field of the coefficients of P.

Examples

julia> c = cross_polytope(2)
Polytope in ambient dimension 2

julia> coefficient_field(c)
Rational field
source
Warning

Support for fields other than the rational numbers is currently in an experimental stage.

These three lines result in the same polytope over rational numbers. Besides the general support mentioned above, naming a Field explicitly is encouraged because it allows user control and increases efficiency.

julia> P = convex_hull(QQ, [1 0 0; 0 0 1]) # passing a `Field` always works
Polyhedron in ambient dimension 3

julia> P == convex_hull(QQFieldElem, [1 0 0; 0 0 1]) # passing the type works for `QQFieldElem` and `Float64` only
true

julia> P == convex_hull([1 0 0; 0 0 1]) # `Field` defaults to `QQ`
true

Type compatibility

When working in polyhedral geometry it can prove advantageous to have various input formats for the same kind of re-occurring quantitative input information. This example shows three different ways to write the points whose convex hull is to be computed, all resulting in identical Polyhedron objects:

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

julia> P == convex_hull([[1, 0, 0], [0, 0, 1]])
true

julia> P == convex_hull(vertices(P))
true

convex_hull is only one of many functions and constructors supporting this behavior, and there are also more types that can be described this way besides PointVector. Whenever the docs state an argument is required to be of type AbstractCollection[ElType] (where ElType is the Oscar type of single instances described in this collection), the user can choose the input to follow any of the corresponding notions below.

Vectors

There are two specialized Vector-like types, PointVector and RayVector, which commonly are returned by functions from Polyhedral Geometry. These can also be manually constructed:

point_vectorFunction
point_vector(p = QQ, v::AbstractVector)

Return a PointVector resembling a point whose coordinates equal the entries of v. p specifies the Field or Type of its coefficients.

source
ray_vectorFunction
ray_vector(p = QQ, v::AbstractVector)

Return a RayVector resembling a ray from the origin through the point whose coordinates equal the entries of v. p specifies the Field or Type of its coefficients.

source

While RayVectors can not be used do describe PointVectors (and vice versa), matrices are generally allowed.

AbstractCollection[PointVector] can be given as:

TypeA PointVector corresponds to...
AbstractVector{<:PointVector}an element of the vector.
AbstractVector{<:AbstractVector}an element of the vector.
AbstractMatrix/MatElema row of the matrix.
AbstractVector/PointVectorthe vector itself (only one PointVector is described).
SubObjectIterator{<:PointVector}an element of the iterator.

AbstractCollection[RayVector] can be given as:

TypeA RayVector corresponds to...
AbstractVector{<:RayVector}an element of the vector.
AbstractVector{<:AbstractVector}an element of the vector.
AbstractMatrix/MatElema row of the matrix.
AbstractVector/RayVectorthe vector itself (only one RayVector is described).
SubObjectIterator{<:RayVector}an element of the iterator.

Halfspaces and Hyperplanes

Similar to points and rays, there are types AffineHalfspace, LinearHalfspace, AffineHyperplane and LinearHyperplane:

affine_halfspaceFunction
affine_halfspace(p = QQ, a, b)

Return the AffineHalfspace H(a,b), which is given by a vector a and a value b such that $H(a,b) = \{ x | ax ≤ b \}.$ p specifies the Field or Type of its coefficients.

source
linear_halfspaceFunction
linear_halfspace(p = QQ, a, b)

Return the LinearHalfspace H(a), which is given by a vector a such that $H(a,b) = \{ x | ax ≤ 0 \}.$ p specifies the Field or Type of its coefficients.

source
affine_hyperplaneFunction
affine_hyperplane(p = QQ, a, b)

Return the AffineHyperplane H(a,b), which is given by a vector a and a value b such that $H(a,b) = \{ x | ax = b \}.$ p specifies the Field or Type of its coefficients.

source
linear_hyperplaneFunction
linear_hyperplane(p = QQ, a, b)

Return the LinearHyperplane H(a), which is given by a vector a such that $H(a,b) = \{ x | ax = 0 \}.$ p specifies the Field or Type of its coefficients.

source

These collections allow to mix up affine halfspaces/hyperplanes and their linear counterparts, but note that an error will be produced when trying to convert an affine description with bias not equal to zero to a linear description.

AbstractCollection[LinearHalfspace] can be given as:

TypeA LinearHalfspace corresponds to...
AbstractVector{<:Halfspace}an element of the vector.
AbstractMatrix/MatElem Athe halfspace with normal vector A[i, :].
AbstractVector{<:AbstractVector} Athe halfspace with normal vector A[i].
SubObjectIterator{<:Halfspace}an element of the iterator.

AbstractCollection[LinearHyperplane] can be given as:

TypeA LinearHyperplane corresponds to...
AbstractVector{<:Hyperplane}an element of the vector.
AbstractMatrix/MatElem Athe hyperplane with normal vector A[i, :].
AbstractVector{<:AbstractVector} Athe hyperplane with normal vector A[i].
SubObjectIterator{<:Hyperplane}an element of the iterator.

AbstractCollection[AffineHalfspace] can be given as:

TypeAn AffineHalfspace corresponds to...
AbstractVector{<:Halfspace}an element of the vector.
Tuple over matrix A and vector bthe affine halfspace with normal vector A[i, :] and bias b[i].
SubObjectIterator{<:Halfspace}an element of the iterator.

AbstractCollection[AffineHyperplane] can be given as:

TypeAn AffineHyperplane corresponds to...
AbstractVector{<:Hyperplane}an element of the vector.
Tuple over matrix A and vector bthe affine hyperplane with normal vector A[i, :] and bias b[i].
SubObjectIterator{<:Hyperplane}an element of the iterator.

IncidenceMatrix

Some methods will require input or return output in form of an IncidenceMatrix.

IncidenceMatrixType
 IncidenceMatrix

A matrix with boolean entries. Each row corresponds to a fixed element of a collection of mathematical objects and the same holds for the columns and a second (possibly equal) collection. A 1 at entry (i, j) is interpreted as an incidence between object i of the first collection and object j of the second one.

Examples

Note that the input and print of an IncidenceMatrix lists the non-zero indices for each row.

julia> IM = IncidenceMatrix([[1,2,3],[4,5,6]])
2×6 IncidenceMatrix
[1, 2, 3]
[4, 5, 6]


julia> IM[1, 2]
true

julia> IM[2, 3]
false

julia> IM[:, 4]
2-element SparseVectorBool
[2]
source

From the example it can be seen that this type supports julia's matrix functionality. There are also functions to retrieve specific rows or columns as a Set over the non-zero indices.

rowMethod
 row(i::IncidenceMatrix, n::Int)

Return the indices where the n-th row of i is true, as a Set{Int}.

Examples

julia> IM = IncidenceMatrix([[1,2,3],[4,5,6]])
2×6 IncidenceMatrix
[1, 2, 3]
[4, 5, 6]


julia> row(IM, 2)
Set{Int64} with 3 elements:
  5
  4
  6
source
columnMethod
 column(i::IncidenceMatrix, n::Int)

Return the indices where the n-th column of i is true, as a Set{Int}.

Examples

julia> IM = IncidenceMatrix([[1,2,3],[4,5,6]])
2×6 IncidenceMatrix
[1, 2, 3]
[4, 5, 6]


julia> column(IM, 5)
Set{Int64} with 1 element:
  2
source

A typical application is the assignment of rays to the cones of a polyhedral fan for its construction, see polyhedral_fan.

Visualization

Lower dimensional polyhedral objects can be visualized through polymake's backend.

visualizeMethod
visualize(P::Union{Polyhedron{T}, Cone{T}, PolyhedralFan{T}, PolyhedralComplex{T}, SubdivisionOfPoints{T}}) where T<:Union{FieldElem, Float64}

Visualize a polyhedral object of dimension at most four (in 3-space). In dimensions up to 3 a usual embedding is shown. Four-dimensional polytopes are visualized as a Schlegel diagram, which is a projection onto one of the facets; e.g., see Chapter 5 of [Zie95].

In higher dimensions there is no standard method; use projections to lower dimensions or try ideas from [GJRW10].

source

Serialization

Most objects from the polyhedral geometry section can be saved through the polymake interface in the background. These functions are documented in the subsections on the different objects. The format of the files is JSON and you can find details of the specification here.

More details on the serialization, albeit concerning the older XML format, can be found in [GHJ16]. Even though the underlying format changed to JSON, the abstract mathematical structure of the data files is still the same.

Contact

Please direct questions about this part of OSCAR to the following people:

You can ask questions in the OSCAR Slack.

Alternatively, you can raise an issue on github.