# Utilities

## Operations

`Base.:+`

— Function`+(p1::VRep, p2::VRep)`

Minkowski sum between `p1`

and `p2`

using the V-representation. If the V-representation is not computed for `p1`

or `p2`

, it is computed.

```
+(p::Rep, el::Union{Line, Ray})
+(el::Union{Line, Ray}, p::Rep)
```

Same as `p + vrep([el])`

.

`Base.:*`

— Function`*(p1::Rep, p2::Rep)`

Cartesian product between the polyhedra `p1`

and `p2`

.

`*(P::Union{AbstractMatrix, UniformScaling}, p::VRep)`

Transform the polyhedron represented by $p$ into $P p$ by transforming each element of the V-representation (points, symmetric points, rays and lines) `x`

into $P x$.

`*(α::Number, p::Rep)`

Transform the polyhedron represented by $p$ into $\alpha p$ by transforming each element of the V-representation (points, symmetric points, rays and lines) `x`

into $\alpha x$.

`Base.:\`

— Function(P::Union{AbstractMatrix, UniformScaling}, p::HRep)

Transform the polyhedron represented by $p$ into $P^{-1} p$ by transforming each halfspace $\langle a, x \rangle \le \beta$ into $\langle P^\top a, x \rangle \le \beta$ and each hyperplane $\langle a, x \rangle = \beta$ into $\langle P^\top a, x \rangle = \beta$.

`Base.:/`

— Function`/(p::HRep, P::Union{AbstractMatrix, UniformScaling})`

Transform the polyhedron represented by $p$ into $P^{-T} p$ by transforming each halfspace $\langle a, x \rangle \le \beta$ into $\langle P a, x \rangle \le \beta$ and each hyperplane $\langle a, x \rangle = \beta$ into $\langle P a, x \rangle = \beta$.

`Base.intersect`

— Function`intersect(P1::HRep, P2::HRep)`

Takes the intersection of `P1`

and `P2`

$\{\, x : x \in P_1, x \in P_2 \,\}$. It is very efficient between two H-representations or between two polyhedron for which the H-representation has already been computed. However, if `P1`

(resp. `P2`

) is a polyhedron for which the H-representation has not been computed yet, it will trigger a representation conversion which is costly. See the Polyhedral Computation FAQ for a discussion on this operation.

The type of the result will be chosen closer to the type of `P1`

. For instance, if `P1`

is a polyhedron (resp. H-representation) and `P2`

is a H-representation (resp. polyhedron), `intersect(P1, P2)`

will be a polyhedron (resp. H-representation). If `P1`

and `P2`

are both polyhedra (resp. H-representation), the resulting polyhedron type (resp. H-representation type) will be computed according to the type of `P1`

. The coefficient type however, will be promoted as required taking both the coefficient type of `P1`

and `P2`

into account.

`intersect(v::VRepresentation{T}, h::HRepElement)`

Compute the intersection of `v`

with an halfspace or hyperplane `h`

. The method used by default is to keep the V-representation element of `v`

that are in `h`

and add new ones generated as the intersection between the hyperplane defining `h`

and the segment between two adjacent V-representation elements of `v`

that are in either sides of the hyperplane. See Lemma 3 of [FP96] for more detail on the method.

[FP96] Fukuda, K. and Prodon, A. **Double description method revisited** *Combinatorics and computer science*, *Springer*, **1996**, 91-111

`Base.intersect!`

— Function`intersect!(p::HRep, h::Union{HRepresentation, HRepElement})`

Same as `intersect`

except that `p`

is modified to be equal to the intersection.

`Polyhedra.convexhull`

— Function`convexhull(P1::VRep, P2::VRep)`

Takes the convex hull of `P1`

and `P2`

$\{\, \lambda x + (1-\lambda) y : x \in P_1, y \in P_2 \,\}$. It is very efficient between two V-representations or between two polyhedron for which the V-representation has already been computed. However, if `P1`

(resp. `P2`

) is a polyhedron for which the V-representation has not been computed yet, it will trigger a representation conversion which is costly.

The type of the result will be chosen closer to the type of `P1`

. For instance, if `P1`

is a polyhedron (resp. V-representation) and `P2`

is a V-representation (resp. polyhedron), `convexhull(P1, P2)`

will be a polyhedron (resp. V-representation). If `P1`

and `P2`

are both polyhedra (resp. V-representation), the resulting polyhedron type (resp. V-representation type) will be computed according to the type of `P1`

. The coefficient type however, will be promoted as required taking both the coefficient type of `P1`

and `P2`

into account.

`convexhull(p1::HRepresentation, p2::HRepresentation)`

Returns the Balas [Theorem 3.3, B85] extended H-representation of the convex hull of `p1`

and `p2`

.

[B85] Balas, E., 1985. *Disjunctive programming and a hierarchy of relaxations for discrete optimization problems*. SIAM Journal on Algebraic Discrete Methods, 6(3), pp.466-486.

`Polyhedra.convexhull!`

— Function`convexhull!(p1::VRep, p2::VRep)`

Same as `convexhull`

except that `p1`

is modified to be equal to the convex hull.

`Polyhedra.translate`

— Function`translate(p::Polyhedra.Rep, v::AbstractVector)`

Computes translation of the polyhedron `p`

with the vector `v`

. That is, computes

\[\{\, x + v \mid x \in p \,\}.\]

By default, if the H-representation, it simply translates every hyperplanes and halfspace, otherwise, it translates every points of the V-representation. That is, this operation can be achieved both in the H-representation and V-representation hence does not trigger any representation conversion.

`Polyhedra.polar`

— Function`polar(rep::Representation)`

Return the polar of the polyhedron `rep`

assumed to contain the origin. The polar of a convex set `S`

is defined as the set of `y`

such that `⟨x, y⟩ ≤ 1`

for all `x in S`

. Note that the polar of a V-representation is a H-representation and vice versa.

## Volume

`Polyhedra.volume`

— Function`volume(p::Polyhedron{T}) where {T}`

Returns the `fulldim(p)`

-dimensional hyper-volume of the polyhedron `p`

. Returns `Inf`

or `-one(T)`

if it is infinite depending on whether the type `T`

has an infinite value.

`Polyhedra.surface`

— Function`surface(p::Polyhedron{T}) where {T}`

Returns the `fulldim(p)-1`

-dimensional hyper-volume of the surface of the polyhedron `p`

. Returns `Inf`

or `-one(T)`

if it is infinite depending on whether the type `T`

has an infinite value.

`Polyhedra.center_of_mass`

— Function`center_of_mass(p::Polyhedron{T}) where {T}`

Returns the center of mass of `p`

, represented as a `Vector{T}`

of length `fulldim(p)`

. Throws an error if `p`

is degenerate.

## Largest inscribed ball with center

`Polyhedra.maximum_radius_with_center`

— Function`maximum_radius_with_center(h::HRep, center)`

Return the maximum radius `r`

such that the Euclidean ball of center `center`

and radius `r`

is included in the polyhedron `h`

.

## Chebyshev center

`Polyhedra.chebyshevcenter`

— Function`chebyshevcenter(p::Rep[, solver])`

If `p`

is a H-representation or is a polyhedron for which the H-representation has already been computed, calls `hchebyshevcenter`

, otherwise, call `vchebyshevcenter`

.

`Polyhedra.hchebyshevcenter`

— Function`hchebyshevcenter(p::HRep[, solver]; linearity_detected=false, proper=true)`

Return a tuple with the center and radius of the largest euclidean ball contained in the polyhedron `p`

. Throws an error if the polyhedron is empty or if the radius is infinite. Linearity is detected first except if `linearity_detected`

.

Note that a polytope may have several Chebyshev center. In general, the set of Chebyshev center of a polytope `p`

is a polytope which has a lower dimension than `p`

if `p`

has a positive dimension. For instance, if `p`

is the rectangle `[-2, 2] x [-1, 1]`

, the Chebyshev radius of `p`

is 1 and the set of Chebyshev centers is `[-1, 1] x {0}`

. The *proper* Chebyshev center is `(0, 0)`

, the Chebyshev center of `[-1, 1] x {0}`

. If `!proper`

then any Chebyshev center is returned (the one returned depends on the solver). Otherwise the proper Chebyshev center is computed. The proper Chebyshev center is defined by induction on the dimension of `p`

. If `p`

has dimension 0 then it is a singleton and its proper Chebyshev center is the only element of `p`

. Otherwise, the dimension of the set `q`

of Chebyshev centers of `p`

is smaller than the dimension of `p`

and the proper Chebyshev center of `p`

is the proper Chebyshev center of `q`

.

`Polyhedra.vchebyshevcenter`

— Function`vchebyshevcenter(p::VRep[, solver])`

Return a tuple with the center and radius of the smallest euclidean ball containing the polyhedron `p`

. Throws an error if the polyhedron is empty or if the radius is infinite (i.e. `p`

is not a polytope, it contains rays).

## Defining new representation

The following macros make it easy to define new representations:

`Polyhedra.@subrepelem`

— MacroThe representation `rep`

contain the elements `elem`

inside a representation in the field `field`

.

`Polyhedra.@norepelem`

— MacroThe representation `rep`

does not contain any `elem`

.

`Polyhedra.@vecrepelem`

— MacroThe representation `rep`

contain the elements `elem`

inside a vector in the field `field`

.