# 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 `FieldElem`

s 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_field`

— Method`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
```

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_vector`

— Function`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.

`ray_vector`

— Function`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.

While `RayVector`

s can not be used do describe `PointVector`

s (and vice versa), matrices are generally allowed.

`AbstractCollection[PointVector]`

can be given as:

Type | A `PointVector` corresponds to... |
---|---|

`AbstractVector{<:PointVector}` | an element of the vector. |

`AbstractVector{<:AbstractVector}` | an element of the vector. |

`AbstractMatrix` /`MatElem` | a row of the matrix. |

`AbstractVector` /`PointVector` | the vector itself (only one `PointVector` is described). |

`SubObjectIterator{<:PointVector}` | an element of the iterator. |

`AbstractCollection[RayVector]`

can be given as:

Type | A `RayVector` corresponds to... |
---|---|

`AbstractVector{<:RayVector}` | an element of the vector. |

`AbstractVector{<:AbstractVector}` | an element of the vector. |

`AbstractMatrix` /`MatElem` | a row of the matrix. |

`AbstractVector` /`RayVector` | the 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_halfspace`

— Function`affine_halfspace(p = QQ, a, b)`

Return the `Oscar.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.

`linear_halfspace`

— Function`linear_halfspace(p = QQ, a, b)`

Return the `Oscar.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.

`affine_hyperplane`

— Function`affine_hyperplane(p = QQ, a, b)`

Return the `Oscar.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.

`linear_hyperplane`

— Function`linear_hyperplane(p = QQ, a, b)`

Return the `Oscar.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.

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:

Type | A `LinearHalfspace` corresponds to... |
---|---|

`AbstractVector{<:Halfspace}` | an element of the vector. |

`AbstractMatrix` /`MatElem` `A` | the halfspace with normal vector `A[i, :]` . |

`AbstractVector{<:AbstractVector}` `A` | the halfspace with normal vector `A[i]` . |

`SubObjectIterator{<:Halfspace}` | an element of the iterator. |

`AbstractCollection[LinearHyperplane]`

can be given as:

Type | A `LinearHyperplane` corresponds to... |
---|---|

`AbstractVector{<:Hyperplane}` | an element of the vector. |

`AbstractMatrix` /`MatElem` `A` | the hyperplane with normal vector `A[i, :]` . |

`AbstractVector{<:AbstractVector}` `A` | the hyperplane with normal vector `A[i]` . |

`SubObjectIterator{<:Hyperplane}` | an element of the iterator. |

`AbstractCollection[AffineHalfspace]`

can be given as:

Type | An `AffineHalfspace` corresponds to... |
---|---|

`AbstractVector{<:Halfspace}` | an element of the vector. |

`Tuple` over matrix `A` and vector `b` | the affine halfspace with normal vector `A[i, :]` and bias `b[i]` . |

`SubObjectIterator{<:Halfspace}` | an element of the iterator. |

`AbstractCollection[AffineHyperplane]`

can be given as:

Type | An `AffineHyperplane` corresponds to... |
---|---|

`AbstractVector{<:Hyperplane}` | an element of the vector. |

`Tuple` over matrix `A` and vector `b` | the 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`

.

`IncidenceMatrix`

— Type`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 of this example and the print of an `IncidenceMatrix`

list the non-zero indices for each row.

```
julia> IM = incidence_matrix([[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]
```

The unique nature of the `IncidenceMatrix`

allows for different ways of construction:

`incidence_matrix`

— Function`incidence_matrix(r::Base.Integer, c::Base.Integer)`

Return an `IncidenceMatrix`

of size r x c whose entries are all `false`

.

**Examples**

```
julia> IM = incidence_matrix(8, 5)
8×5 IncidenceMatrix
[]
[]
[]
[]
[]
[]
[]
[]
```

`incidence_matrix(mat::Union{AbstractMatrix{Bool}, IncidenceMatrix})`

Convert `mat`

to an `IncidenceMatrix`

.

**Examples**

```
julia> IM = incidence_matrix([true false true false true false; false true false true false true])
2×6 IncidenceMatrix
[1, 3, 5]
[2, 4, 6]
```

`incidence_matrix(mat::AbstractMatrix)`

Convert the `0`

/`1`

matrix `mat`

to an `IncidenceMatrix`

. Entries become `true`

if the initial entry is `1`

and `false`

if the initial entry is `0`

.

**Examples**

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

`incidence_matrix(r::Base.Integer, c::Base.Integer, incidenceRows::AbstractVector{<:AbstractVector{<:Base.Integer}})`

Return an `IncidenceMatrix`

of size r x c. The i-th element of `incidenceRows`

lists the indices of the `true`

entries of the i-th row.

**Examples**

```
julia> IM = incidence_matrix(3, 4, [[2, 3], [1]])
3×4 IncidenceMatrix
[2, 3]
[1]
[]
```

`incidence_matrix(incidenceRows::AbstractVector{<:AbstractVector{<:Base.Integer}})`

Return an `IncidenceMatrix`

where the i-th element of `incidenceRows`

lists the indices of the `true`

entries of the i-th row. The dimensions of the result are the smallest possible row and column count that can be deduced from the input.

**Examples**

```
julia> IM = incidence_matrix([[2, 3], [1]])
2×3 IncidenceMatrix
[2, 3]
[1]
```

`incidence_matrix(g::Graph{T}) where {T <: Union{Directed, Undirected}}`

Return an unsigned (boolean) incidence matrix representing a graph `g`

.

**Examples**

```
julia> g = Graph{Directed}(5);
julia> add_edge!(g, 1, 3);
julia> add_edge!(g, 3, 4);
julia> incidence_matrix(g)
5×2 IncidenceMatrix
[1]
[]
[1, 2]
[2]
[]
```

From the examples 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`

— Method`row(i::IncidenceMatrix, n::Int)`

Return the indices where the `n`

-th row of `i`

is `true`

, as a `Set{Int}`

.

**Examples**

```
julia> IM = incidence_matrix([[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`

— Method`column(i::IncidenceMatrix, n::Int)`

Return the indices where the `n`

-th column of `i`

is `true`

, as a `Set{Int}`

.

**Examples**

```
julia> IM = incidence_matrix([[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`

— Method`visualize(P::Union{Polyhedron{T}, Cone{T}, PolyhedralFan{T}, PolyhedralComplex{T}, SubdivisionOfPoints{T}}; kwargs...) 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].

**Extended help**

**Keyword Arguments**

**Colors**

Colors can be given as

- a literal
`String`

, e.g.`"green"`

. - a
`String`

of the format`"r g b"`

where $r, g, b \in {0, \dots, 255}$ are integers corresponding to the R/G/B values of the color. - a
`String`

of the format`"r g b"`

where $r, g, b \in [0, 1]$ are decimal values corresponding to the R/G/B values of the color.

Possible arguments are:

`FacetColor`

: Filling color of the polygons.`EdgeColor`

: Color of the boundary lines.`PointColor`

/`VertexColor`

: Color of the spheres or rectangles representing the points.

**Scaling and other gradient properties**

These arguments can be given as a floating point number:

`FacetTransparency`

: Transparency factor of the polygons between 0 (opaque) and 1 (completely translucent).`EdgeThickness`

: Scaling factor for the thickness of the boundary lines.`PointThickness`

/VertexThickness`: Scaling factor for the size of the spheres or rectangles representing the points.

**Camera**

These arguments can be given as a 3-element vector over floating point numbers:

`ViewPoint`

: Position of the camera.`ViewDirection`

: Direction of the camera.

**Appearance and Texts**

These arguments can be given as a string:

`FacetStyle`

: If set to`"hidden"`

, the inner area of the polygons are not rendered at all.`FacetLabels`

: If set to`"hidden"`

, the facet labels are not displayed (in the most cases this is the default behavior). TODO`EdgeStyle`

: If set to`"hidden"`

, the boundary lines are not rendered.`Name`

: The name of this visual object in the drawing.`PointLabels`

/`VertexLabels`

: If set to`"hidden"`

, no point labels are displayed.`PointStyle`

/`VertexStyle`

: If set to`"hidden"`

, neither point nor its label is rendered.`LabelAlignment`

: Defines the alignment of the vertex labels:`"left"`

,`"right"`

or`"center"`

.

## 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:

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

You can ask questions in the OSCAR Slack.

Alternatively, you can raise an issue on github.