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:

• Michael Joswig, Thorsten Theobald (2013)
• Günter M. Ziegler (1995)

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

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

AbstractCollection[PointVector] can be given as:

AbstractCollection[RayVector] can be given as:

Halfspaces and Hyperplanes

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:

AbstractCollection[LinearHyperplane] can be given as:

AbstractCollection[AffineHalfspace] can be given as:

AbstractCollection[AffineHyperplane] can be given as:

IncidenceMatrix

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

 IncidenceMatrix

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]

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.

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

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

 column(i::IncidenceMatrix, n::Int)

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

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.

visualize(P::Union{Polyhedron, Cone, PolyhedralFan, PolyhedralComplex})

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 Ewgenij Gawrilow, Simon Hampe, Michael Joswig (2016). 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:

• Taylor Brysiewicz,
• Michael Joswig,
• Lars Kastner,
• Benjamin Lorenz.

You can ask questions in the OSCAR Slack.

Alternatively, you can raise an issue on github.