# Containment/Redundancy

## Containment

`Base.in`

— Function`in(p::VRepElement, h::HRepElement)`

Returns whether `p`

is in `h`

. If `h`

is an hyperplane, it returns whether $\langle a, x \rangle \approx \beta$. If `h`

is an halfspace, it returns whether $\langle a, x \rangle \le \beta$.

`in(p::VRepElement, h::HRep)`

Returns whether `p`

is in `h`

, e.g. in all the hyperplanes and halfspaces supporting `h`

.

`Base.issubset`

— Function`issubset(p::Rep, h::HRepElement)`

Returns whether `p`

is a subset of `h`

, i.e. whether `h`

supports the polyhedron `p`

.

`Polyhedra.ininterior`

— Function`ininterior(p::VRepElement, h::HRepElement)`

Returns whether `p`

is in the interior of `h`

. If `h`

is an hyperplane, it always returns `false`

. If `h`

is an halfspace $\langle a, x \rangle \leq \beta$, it returns whether `p`

is in the open halfspace $\langle a, x \rangle < \beta$

`ininterior(p::VRepElement, h::HRep)`

Returns whether `p`

is in the interior of `h`

, e.g. in the interior of all the hyperplanes and halfspaces supporting `h`

.

`Polyhedra.inrelativeinterior`

— Function`inrelativeinterior(p::VRepElement, h::HRepElement)`

Returns whether `p`

is in the relative interior of `h`

. If `h`

is an hyperplane, it is equivalent to `p in h`

since the relative interior of an hyperplane is itself. If `h`

is an halfspace, it is equivalent to `ininterior(p, h)`

.

`inrelativeinterior(p::VRepElement, h::HRep)`

Returns whether `p`

is in the relative interior of `h`

, e.g. in the relative interior of all the hyperplanes and halfspaces supporting `h`

.

`Polyhedra.support_function`

— Functionsupport*function(h::AbstractVector, rep::Rep, solver=Polyhedra.linear*objective_solver(p))

Return the value of the support function of `rep`

at `h`

. See [Section 13, R15] for more details.

[R15] Rockafellar, R.T. *Convex analysis*. Princeton university press, **2015**.

## Linearity

`Polyhedra.detecthlinearity!`

— Function`detecthlinearity!(p::HRep; kws...)`

Detects all the hyperplanes contained in the H-representation and remove all redundant hyperplanes.

The remaining keyword arguments `kws`

are passed to `detecthlinearity`

.

**Examples**

The representation

`h = HalfSpace([1, 1], 1]) ∩ HalfSpace([-1, -1], -1)`

contains the hyperplane `HyperPlane([1, 1], 1)`

.

`Polyhedra.detecthlinearity`

— Function`detecthlinearity(hr::HRepresentation, solver; kws...)`

Return a new H-representation with linearity detected using `solver`

.

The remaining keyword arguments `kws`

are passed to `detect_new_linearities`

.

`Polyhedra.detectvlinearity!`

— Function`detectvlinearity!(p::VRep, solver=default_solver(p); kws...)`

Detects all the lines contained in the V-representation and remove all redundant lines.

The remaining keyword arguments `kws`

are passed to `detectvlinearity`

.

**Examples**

The representation

`v = conichull([1, 1], [-1, -1])`

contains the line `Line([1, 1])`

.

`Polyhedra.detectvlinearity`

— Function`detectvlinearity(vr::VRepresentation, solver; kws...)`

Return a new V-representation with linearity detected using `solver`

.

The remaining keyword arguments `kws`

are passed to `detect_new_linearities`

.

`Polyhedra.detect_new_linearities`

— Function`detect_new_linearities(rep::HRepresentation{T}, solver; verbose=0, ztol=Base.rtoldefault(T)) where {T}`

Given a polyhedron with H-representation `rep`

, detect whether a new hyperplane can be generated from the halfspaces in `halfspaces`

using an linear program solved by `solver`

. The method is similar to the method used for lines described as follows. This function is automatically called by `removehredundancy`

if a solver is provided.

`detect_new_linearities(rep::VRepresentation{T}, solver; verbose=0, ztol=Base.rtoldefault(T)) where {T}`

Given a cone defined by the V-representation `rep`

(ignoring the points in the representation if any), detect whether a new line can be generated from the rays in `rays`

using an linear program solved by `solver`

. The method is as follows (suppose `lines`

is empty for simplicity). This function is automatically called by `removevredundancy`

if a solver is provided.

The keyword argument `ztol`

is used as a tolerance to decide whether a number is zero.

If there was a line `l`

in the cone, it would mean that there exist `μ >= 0`

and `ν >= 0`

such that `Σ μ_i r_i = l`

and `Σ ν_i r_i = -l`

. We deduce from this that `Σ λ_i r_i = 0`

where `λ = μ + ν`

.

Conversely, if there are `λ >= 0`

such that `Σ λ_i r_i = 0`

then let `j`

be the index of `λ`

with largest magnitude (to make sure it is nonzero). We have `Σ_{i != j} λ_i/λ_j r_i = -r_j`

. As both `r_j`

and `-r_j`

are in the cone, `r_j`

generates a line in the cone. However, this means that we now have `Σ_{i != j} λ_i/λ_j r_i ≡ 0 (mod r_j)`

so if there is another `λ_i`

with nonzero value, we can transform it to a line as well. In summary, we have a line `r_i`

for each `i`

such that `λ_i != 0`

.

The dual program is:

```
max z
s.t. r_i'x ≥ z
```

When the primal is feasible, the dual program may still be feasible. We know that `z = 0`

by strong duality as the objective value needs to be equal to the objective of the primal which is zero. So the constraints are `r_i'x ≥ 0`

. If we have `r_i'x > 0`

for some `i`

, it means that `-r_i`

does not belong to the cone hence `r_i`

can be dropped for the purpose of searching for lines.

**Note**

In CDDLib, the dual program is solved, if the objective value is zero then linearity are found by, for each `i`

such that `r_i'x = 0`

, solve an LP to find whether `-r_i`

belongs to the cone. CDDLib ignores the primal results provided in `λ`

which directly gives linearity without the need to solve an LP for each ray. The method implemented in Polyhedra is therefore significantly more efficient as its complexity is `O(dimension of linespace)`

which is upper bounded by `O(fulldim)`

while the method of CDDLib is `O(number of rays)`

.

`Polyhedra.dim`

— Function`dim(h::HRep, current=false)`

Returns the dimension of the affine hull of the polyhedron. That is the number of non-redundant hyperplanes that define it. If `current`

is `true`

then it simply returns the dimension according the current number of hyperplanes, assuming that the H-linearity has already been detected. Otherwise, it first calls `detecthlinearity!`

.

## Duplicates

`Polyhedra.removeduplicates`

— Function`removeduplicates(rep::Representation)`

Removes the duplicates in the Representation.

- In an H-representation, it removes the redundant hyperplanes and it remove an halfspace when it is equal to another halfspace in the affine hull. For instance,
`HalfSpace([1, 1], 1)`

is equal to`HalfSpace([1, 0], 0)`

in the affine hull generated by`HyperPlane([0, 1], 1])`

. - In a V-representation, it removes the redundant lines and it remove a point (resp. ray) when it is equal to another point (resp. ray) in the line hull. For instance, in the line hull generated by
`Line([0, 1])`

,`[1, 1]`

is equal to`[1, 0]`

and`Ray([2, 2])`

is equal to`Ray([1, 0])`

.

## Redundancy

`Polyhedra.Redundancy`

— Type`@enum Redundancy UNKNOWN_REDUNDANCY LINEARITY_DETECTED NO_REDUNDANCY`

Redundancy of a H-representation or V-representation.

`UNKNOWN_REDUNDANCY`

: It is unknown whether there are any undetected linearity or redundancy.`LINEARITY_DETECTED`

: There are no undetected linearity.`NO_REDUNDANCY`

: There are no undetected linearity not redundancy.

An *undetected linearity* for a V-representation is a `Line`

that is implicit in a conic hull of `Ray`

s. For instance, `conichull([1, 1], [-1, -1])`

has undetected linearity because it contains the `Line`

`Line([1, 1])`

. Some undetected linearity is less obvious, e.g., `conichull([1, 0, -1], [0, 1, 1], [-1, -1, 0])`

contains the `Line`

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

as the sum of the first two `Ray`

s is `Ray([1, 1, 0])`

.

An *undetected linearity* for a H-representation is a `HyperPlane`

that is implicit in an intersection of `HalfSpace`

s. For instance, `HalfSpace([1, 1], 1) ∩ HalfSpace([-1, -1], 1)`

has undetected linearity because it contains the `HyperPlane`

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

. Some undetected linearity is less obvious, e.g., `HalfSpace([1, 0], -1) ∩ HalfSpace([0, 1], 1) ∩ HalfSpace([-1, -1], 0)`

contains the `HyperPlane`

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

as the sum of the first two `HalfSpace`

s is `HalfSpace([1, 1], 0)`

.

`Polyhedra.hredundancy`

— Function`hredundancy(p::Polyhedron)`

Return the `Redundancy`

of `hrep(p)`

.

`Polyhedra.vredundancy`

— Function`vredundancy(p::Polyhedron)`

Return the `Redundancy`

of `vrep(p)`

.

`Polyhedra.isredundant`

— Function`isredundant(p::Rep, idx::Index; strongly=false)`

Return a `Bool`

indicating whether the element with index `idx`

can be removed without changing the polyhedron represented by `p`

. If `strongly`

is `true`

,

- if
`idx`

is an H-representation element`h`

, it returns`true`

only if no V-representation element of`p`

is in the hyperplane of`h`

. - if
`idx`

is a V-representation element`v`

, it returns`true`

only if`v`

is in the relative interior of`p`

.

`Polyhedra.removehredundancy`

— Function`removehredundancy(hr::HRepresentation, solver)`

Return a H-representation of the polyhedron represented by `hr`

with all the elements of `hr`

except the redundant ones, i.e. the elements that can be expressed as convex combination of other ones.

`Polyhedra.removehredundancy!`

— Function`removehredundancy!(p::HRep; kws...)`

Removes the elements of the H-representation of `p`

that can be removed without changing the polyhedron represented by `p`

. That is, it only keeps the halfspaces corresponding to facets of the polyhedron.

The remaining keyword arguments `kws`

are passed to `detectvlinearity!`

and `detecthlinearity!`

.

`Polyhedra.removevredundancy`

— Function`removevredundancy(vr::VRepresentation, solver)`

Return a V-representation of the polyhedron represented by `vr`

with all the elements of `vr`

except the redundant ones, i.e. the elements that can be expressed as convex combination of other ones.

`Polyhedra.removevredundancy!`

— Function`removevredundancy!(p::VRep; strongly=false, planar=true, kws...)`

Removes the elements of the V-representation of `p`

that can be removed without changing the polyhedron represented by `p`

. That is, it only keeps the extreme points and rays. This operation is often called "convex hull" as the remaining points are the extreme points of the convex hull of the initial set of points. If `strongly=true`

, weakly redundant points, i.e., points that are not extreme but are not in the relative interior either, may be kept. If `fulldim(p)`

is 2, `strongly`

is `false`

and `planar`

is `true`

, a planar convex hull algorithm is used.

The remaining keyword arguments `kws`

are passed to `detectvlinearity!`

and `detecthlinearity!`

.