# Representation

Polyhedra can be described in 2 different ways.

- H-representation: As the intersection of finitely many halfspaces given by its facets.
- V-representation: As the convex hull of its vertices + the conic hull of its rays where '+' is the Minkowski sum.

`Polyhedra.HRepresentation`

— Type`HRepresentation{T<:Real}`

Supertype for H-representations with coefficient type `T`

.

`Polyhedra.VRepresentation`

— Type`VRepresentation{T<:Real}`

Supertype for V-representations coefficient type `T`

.

`Polyhedra.Representation`

— Type`Representation{T<:Real}`

Supertype for H-(or V-)representations with coefficient type `T`

.

In `Polyhedra.jl`

, those representations are given the respective abstract types `HRepresentation`

and `VRepresentation`

which are themself subtypes of `Representation`

.

These functions can be called on both H-representation and V-representation

`Polyhedra.fulldim`

— Function`fulldim(rep::Rep)::Int`

Returns the dimension of the space in which polyhedron, representation, element or vector is defined. That is, a straight line in a 3D space has `fulldim`

3 even if its dimension is 1.

`Polyhedra.FullDim`

— Type`FullDim(p)::FullDim`

Similar to `fulldim`

but used for type stability with the vector type. If the vector type is `StaticArrays.SVector`

then it returns a `StaticArrays.Size`

.

`Polyhedra.coefficient_type`

— Function`coefficient_type(rep::Rep)`

Returns the type of the coefficients used in the representation of `rep`

.

## H-representation

The fundamental element of an H-representation is the halfspace

`Polyhedra.HalfSpace`

— Type```
struct HalfSpace{T, AT} <: HRepElement{T, AT}
a::AT
β::T
end
```

An halfspace defined by the set of points $x$ such that $\langle a, x \rangle \le \beta$.

An H-representation can be created as the intersection of several halfspaces. For instance, the polytope

\[\begin{align*} x_1 + x_2 &\leq 1 \\ x_1 - x_2 &\leq 0 \\ x_1 & \geq 0. \end{align*}\]

can be created as follows:

`HalfSpace([1, 1], 1) ∩ HalfSpace([1, -1], 0) ∩ HalfSpace([-1, 0], 0)`

Even if `HalfSpace`

s are enough to describe any polyhedron, it is sometimes important to represent the fact that the polyhedron is contained in an affine subspace. For instance, the simplex

\[\begin{align*} x_1 + x_2 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{align*}\]

is 1-dimensional even if it is defined in a 2-dimensional space.

The fundamental element of an affine subspace is the hyperplane

`Polyhedra.HyperPlane`

— Type```
struct HyperPlane{T, AT} <: HRepElement{T, AT}
a::AT
β::T
end
```

An hyperplane defined by the set of points $x$ such that $\langle a, x \rangle = \beta$.

An affine subspace can be created as the intersection of several hyperplanes. For instance

`HyperPlane([1, 1], 1) ∩ HyperPlane([1, 0], 0)`

represents the 0-dimensional affine subspace only containing the point $(0, 1)$.

To represent a polyhedron that is not full-dimensional, hyperplanes and halfspaces can be mixed in any order. For instance, the simplex defined above can be obtained as follows:

`HalfSpace([-1, 0], 0) ∩ HyperPlane([1, 1], 1) ∩ HalfSpace([0, -1], 0)`

In addition to being created incrementally with intersections, an H-representation can also be created using the `hrep`

function

`Polyhedra.hrep`

— Function`hrep(p::Polyhedron)`

Returns an H-representation for the polyhedron `p`

.

`hrep(hyperplanes::HyperPlaneIt; d::FullDim)`

Creates an affine space of full dimension `d`

from the list of hyperplanes `hyperplanes`

.

**Examples**

`hrep([HyperPlane([0, 1, 0], 1), HyperPlane([0, 0, 1], 0)])`

creates the 1-dimensional affine subspace containing all the points $(x_1, 0, 0)$, i.e. the $x_1$-axis.

`hrep([HyperPlane([1, 1], 1), HyperPlane([1, 0], 0)])`

creates the 0-dimensional affine subspace only containing the point $(0, 1)$.

`hrep(hyperplanes::HyperPlaneIt, halfspaces::HalfSpaceIt; d::FullDim)`

Creates an H-representation for the polyhedron of full dimension `d`

equal to the intersection of the hyperplanes `hyperplanes`

and halfspaces `halfspaces`

.

**Examples**

For instance, the simplex

\[\begin{align*} x_1 + x_2 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{align*}\]

can be created as follows:

```
julia> hrep([HyperPlane([1, 1], 1)], [HalfSpace([0, -1], 0), HalfSpace([-1, 0], 0)])
H-representation Polyhedra.Intersection{Int64, Vector{Int64}, Int64}:
1-element iterator of HyperPlane{Int64, Vector{Int64}}:
HyperPlane([1, 1], 1),
2-element iterator of HalfSpace{Int64, Vector{Int64}}:
HalfSpace([0, -1], 0)
HalfSpace([-1, 0], 0)
```

`hrep(halfspaces::HalfSpaceIt; d::FullDim)`

Creates an H-representation for the polyhedron of full dimension `d`

equal to the intersection of the halfspaces `halfspaces`

.

**Examples**

For instance, the polytope

\[\begin{align*} x_1 + x_2 &\leq 1 \\ x_1 - x_2 &\leq 0 \\ x_1 & \geq 0. \end{align*}\]

can be created as follows:

`hrep([HalfSpace([1, 1], 1), HalfSpace([1, -1], 0), HalfSpace([-1, 0], 0)])`

`hrep(model::JuMP.Model)`

Builds an H-representation from the feasibility set of the JuMP model `model`

. Note that if non-linear constraint are present in the model, they are ignored.

`hrep(A::AbstractMatrix, b::AbstractVector, linset::BitSet=BitSet())`

Creates an H-representation for the polyhedron defined by the inequalities $\langle A_i, x \rangle = b_i$ if `i in linset`

and $\langle A_i, x \rangle \le b_i$ otherwise where $A_i$ is the $i$th row of `A`

, i.e. `A[i,:]`

and $b_i$ is `b[i]`

.

### Interface

An H-representation is represented as an intersection halfspaces and hyperplanes. The halfspaces can be obtained with `halfspaces`

and the hyperplanes with `hyperplanes`

. As an hyperplane $\langle a, x \rangle = \beta$ is the intersection of the two halfspaces $\langle a, x \rangle \le \beta$ and $\langle a, x \rangle \ge \beta$, even if the H-representation contains hyperplanes, a list of halfspaces whose intersection is the polyhedron can be obtained with `allhalfspaces`

, which has `nhalfspaces(p) + 2nhyperplanes(p)`

elements for an H-representation `p`

since each hyperplane is split in two halfspaces.

`Polyhedra.halfspaces`

— Function`halfspaces(hrep::HRep)`

Returns an iterator over the halfspaces of the H-representation `hrep`

.

`Polyhedra.nhalfspaces`

— Function`nhalfspaces(hrep::HRep)`

Returns the number of halfspaces of the H-representation `hrep`

.

`Polyhedra.hashalfspaces`

— Function`hashalfspaces(hrep::HRep)`

Returns whether the H-representation `hrep`

has any halfspace.

`Polyhedra.hyperplanes`

— Function`hyperplanes(hrep::HRep)`

Returns an iterator over the hyperplanes of the H-representation `hrep`

.

`Polyhedra.nhyperplanes`

— Function`nhyperplanes(hrep::HRep)`

Returns the number of hyperplanes of the H-representation `hrep`

.

`Polyhedra.hashyperplanes`

— Function`hashyperplanes(hrep::HRep)`

Returns whether the H-representation `hrep`

has any hyperplane.

`Polyhedra.allhalfspaces`

— Function`allhalfspaces(hrep::HRep)`

Returns an iterator over the halfspaces and hyperplanes in the H-representation `hrep`

splitting hyperplanes in two halfspaces.

**Examples**

```
hrep = HyperPlane([1, 0], 1) ∩ HalfSpace([0, 1], 1)
collect(allhalfspaces(hrep)) # Returns [HalfSpace([1, 0]), HalfSpace([-1, 0]), HalfSpace([0, 1])]
```

`Polyhedra.nallhalfspaces`

— Function`nallhalfspaces(hrep::HRep)`

Returns the number of halfspaces plus twice the number of hyperplanes in the H-representation `hrep`

, i.e. `length(allhalfspaces(hrep))`

`Polyhedra.hasallhalfspaces`

— Function`hasallhalfspaces(hrep::HRep)`

Returns whether the H-representation `hrep`

contains any halfspace or hyperplane.

## V-representation

The fundamental elements of an V-representation are the points (represented by `AbstractVector`

s and and rays

`Polyhedra.Ray`

— Type```
struct Ray{T, AT <: AbstractVector{T}}
a::AT
end
```

The conic hull of `a`

, i.e. the set of points `λa`

where `λ`

is any nonnegative real number.

A V-representation can be created as the minkowski sum between a convex hull of points and a conic hull of rays. For instance, the positive orthant without the simplex defined in the H-representation section can be created as follows:

`convexhull([1, 0], [0, 1]) + conichull([1, 0], [0, 1])`

The V-representation represents the polyhedron as a minkowski sum of a polytope and a polyhedral cone. The polytope is represented using a *P-representation* : a convex hull of points. The polyhedral cone is represented using an *R-representation* : a conic hull of rays.

Even if rays are enough to describe any polyhedral cone, it is sometimes important to represent the fact that the polyhedron contains an affine subspace. For instance, the polyhedron created with

`convexhull([1, 0], [0, 1]) + conichull([1, 1], [-1, -1])`

contains the line `[1, 1]`

.

The fundamental element of an affine subspace is the line

`Polyhedra.Line`

— Type```
struct Line{T, AT <: AbstractVector{T}}
a::AT
end
```

The conic hull of `a`

and `-a`

, i.e. the set of points `λa`

where `λ`

is any real number.

An affine subspace can be created as the conic hull/minkownski sum of several lines. For instance

`conichull(Line([1, 0]), Line([0, 1]))`

represents the full space.

In addition to being created incrementally with convex hull and minkowsky addition, a V-representation can also be created using the `vrep`

function

`Polyhedra.vrep`

— Function`vrep(p::Polyhedron)`

Returns a V-representation for the polyhedron `p`

.

`vrep(lines::LineIt; d::FullDim)`

Creates an affine space of full dimension `d`

from the list of lines `lines`

.

**Examples**

`vrep([Line([1, 0, 0]), Line([0, 1, 0])])`

creates the 2-dimensional affine subspace containing all the points $(x_1, x_2, 0)$, i.e. the $x_1$$x_2$-plane.

`vrep(points::PointIt; d::FullDim)`

Creates a V-representation for the polytope of full dimension `d`

equal to the convex hull of the points `points`

.

**Examples**

The convex hull of $(0, 0)$, $(0, 1)$ and $(1/2, 1/2)$ can be created as follows using exact arithmetic

`vrep([[0, 0], [0, 1], [1//2, 1//2]])`

or as follows using floating point arithmetic

`vrep([[0, 0], [0, 1], [1/2, 1/2]])`

`vrep(lines::LineIt, rays::RayIt; d::FullDim)`

Creates a V-representation for the polyhedral cone of full dimension `d`

equal to the conic hull of the lines `lines`

and rays `rays`

.

**Examples**

`vrep([Line([0, 1])], [Ray([1, 0])])`

creates a V-representation for the halfspace $x_1 \ge 0$.

`vrep(rays::RayIt)`

Creates a V-representation for the polyhedral cone of full dimension `d`

equal to the conic hull of the rays `rays`

.

**Examples**

`vrep([Ray([1, 0]), Ray([0, 1])])`

creates a V-representation for positive orthant.

```
vrep(points::PointIt, lines::LineIt, rays::RayIt;
d = Polyhedra.FullDim_rec(points, lines, rays))
```

Creates a V-representation for the polyhedron of full dimension `d`

equal to the minkowski sum of the convex hull of `points`

with the conic hull of `lines`

and `rays`

.

`vrep(V::AbstractMatrix, R::AbstractMatrix, Rlinset::BitSet=BitSet())`

Creates a V-representation for the polyhedron defined by the points $V_i$, lines $R_i$ if `i in Rlinset`

and rays $R_i$ otherwise where $V_i$ (resp. $R_i$) is the $i$th row of `V`

(resp. `R`

), i.e. `V[i,:]`

(resp. `R[i,:]`

).

### Interface

A P-representation is represented as a convex hull points. The points can be obtained with `points`

.

`Polyhedra.points`

— Function`points(vrep::VRep)`

Returns an iterator over the points of the V-representation `vrep`

.

`Polyhedra.npoints`

— Function`npoints(vrep::VRep)`

Returns the number of points of the V-representation `vrep`

.

`Polyhedra.haspoints`

— Function`haspoints(vrep::VRep)`

Returns whether the V-representation `vrep`

has any point.

An R-representation is represented as a conic hull of lines and rays. The rays can be obtained with `rays`

and the lines with `lines`

. As a line $r$ is the conic hull of of the two rays $r$ and $-r$, even if the R-representation contains lines, a list of rays whose conic hull is the polyhedral cone can be obtained with `allrays`

, which has `nrays(R) + 2nlines(R)`

elements for an R-representation `R`

since each line is split in two rays.

`Polyhedra.rays`

— Function`rays(vrep::VRep)`

Returns an iterator over the rays of the V-representation `vrep`

.

`Polyhedra.nrays`

— Function`nrays(vrep::VRep)`

Returns the number of rays of the V-representation `vrep`

.

`Polyhedra.hasrays`

— Function`hasrays(vrep::VRep)`

Returns whether the V-representation `vrep`

has any ray.

`Polyhedra.lines`

— Function`lines(vrep::VRep)`

Returns an iterator over the lines of the V-representation `vrep`

.

`Polyhedra.nlines`

— Function`nlines(vrep::VRep)`

Returns the number of lines of the V-representation `vrep`

.

`Polyhedra.haslines`

— Function`haslines(vrep::VRep)`

Returns whether the V-representation `vrep`

has any line.

`Polyhedra.allrays`

— Function`allrays(vrep::VRep)`

Returns an iterator over the rays and lines in the V-representation `vrep`

splitting lines in two rays.

**Examples**

```
vrep = Line([1, 0]) + Ray([0, 1])
collect(allrays(vrep)) # Returns [Ray([1, 0]), Ray([-1, 0]), Ray([0, 1])]
```

`Polyhedra.nallrays`

— Function`nallrays(vrep::VRep)`

Returns the number of rays plus twice the number of lines in the V-representation `vrep`

, i.e. `length(allrays(vrep))`

`Polyhedra.hasallrays`

— Function`hasallrays(vrep::VRep)`

Returns whether the V-representation `vrep`

contains any ray or line.