# Polytope in vertex representation (VPolytope)

`LazySets.VPolytopeModule.VPolytope`

— Type`VPolytope{N, VN<:AbstractVector{N}, VT<:AbstractVector{VN}} <: AbstractPolytope{N}`

Type that represents a convex polytope in vertex representation.

**Fields**

`vertices`

– list of vertices

**Examples**

A polytope in vertex representation can be constructed by passing the list of vertices. For example, we can build the tetrahedron:

```
julia> P = VPolytope([[0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1]]);
julia> P.vertices
4-element Vector{Vector{Int64}}:
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
```

Alternatively, a `VPolytope`

can be constructed passing a matrix of vertices, where each *column* represents a vertex:

```
julia> M = [0 0 0; 1 0 0; 0 1 0; 0 0 1]'
3×4 adjoint(::Matrix{Int64}) with eltype Int64:
0 1 0 0
0 0 1 0
0 0 0 1
julia> P = VPolytope(M);
julia> P.vertices
4-element Vector{Vector{Int64}}:
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
```

## Conversion

`Base.convert`

— Method`convert(::Type{VPolytope}, X::LazySet; [prune]::Bool=true)`

Convert a polytopic set to a polytope in vertex representation.

**Input**

`VPolytope`

– target type`X`

– polytopic set`prune`

– (optional, default:`true`

) option to remove redundant vertices

**Output**

The given set represented as a polytope in vertex representation.

**Algorithm**

This method uses `vertices_list`

. Use the option `prune`

to select whether to remove redundant vertices before constructing the polytope.

## Operations

`LazySets.API.constraints_list`

— Method`constraints_list(P::VPolytope)`

Return a list of constraints defining a polytope in vertex representation.

**Input**

`P`

– polytope in vertex representation

**Output**

A list of constraints of the polytope.

**Algorithm**

We use `tohrep`

to compute the constraint representation of `P`

.

`LazySets.API.dim`

— Method`dim(P::VPolytope)`

Return the dimension of a polytope in vertex representation.

**Input**

`P`

– polytope in vertex representation

**Output**

The ambient dimension of the polytope in vertex representation. If `P`

is empty, the result is $-1$.

**Examples**

```
julia> P = VPolytope();
julia> isempty(P.vertices)
true
julia> dim(P)
-1
julia> P = VPolytope([ones(3)]);
julia> P.vertices
1-element Vector{Vector{Float64}}:
[1.0, 1.0, 1.0]
julia> dim(P) == 3
true
```

`Polyhedra.polyhedron`

— Method```
polyhedron(P::VPolytope;
[backend]=default_polyhedra_backend(P),
[relative_dimension]=nothing)
```

Return a `VRep`

polyhedron from `Polyhedra.jl`

given a polytope in vertex representation.

**Input**

`P`

– polytope in vertex representation`backend`

– (optional, default:`default_polyhedra_backend(P)`

) the backend for polyhedral computations; see Polyhedra's documentation for further information`relative_dimension`

– (default, optional:`nothing`

) an integer representing the (relative) dimension of the polytope; this argument is mandatory if the polytope is empty

**Output**

A `VRep`

polyhedron.

**Notes**

The *relative dimension* (or just *dimension*) refers to the dimension of the set relative to itself, independently of the ambient dimension. For example, a point has (relative) dimension zero, and a line segment has (relative) dimension one.

In this library, `LazySets.dim`

always returns the ambient dimension of the set, such that a line segment in two dimensions has dimension two. However, `Polyhedra.dim`

will assign a dimension equal to one to a line segment because it uses a different convention.

`Base.rand`

— Method```
rand(::Type{VPolytope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
[rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing,
[num_vertices]::Int=-1)
```

Create a random polytope in vertex representation.

**Input**

`VPolytope`

– type for dispatch`N`

– (optional, default:`Float64`

) numeric type`dim`

– (optional, default: 2) dimension`rng`

– (optional, default:`GLOBAL_RNG`

) random number generator`seed`

– (optional, default:`nothing`

) seed for reseeding`num_vertices`

– (optional, default:`-1`

) upper bound on the number of vertices of the polytope (see comment below)

**Output**

A random polytope in vertex representation.

**Algorithm**

All numbers are normally distributed with mean 0 and standard deviation 1.

The number of vertices can be controlled with the argument `num_vertices`

. For a negative value we choose a random number in the range `dim:5*dim`

(except if `dim == 1`

, in which case we choose in the range `1:2`

). Note that we do not guarantee that the vertices are not redundant.

`LazySets.remove_redundant_vertices`

— Method```
remove_redundant_vertices(P::VPolytope{N};
[backend]=nothing,
[solver]=nothing) where {N}
```

Return the polytope obtained by removing the redundant vertices of the given polytope in vertex representation.

**Input**

`P`

– polytope in vertex representation`backend`

– (optional, default:`nothing`

) the backend for polyhedral computations; see`default_polyhedra_backend(P)`

or Polyhedra's documentation for further information`solver`

– (optional, default:`nothing`

) the linear programming solver used in the backend, if needed; see`default_lp_solver_polyhedra(N)`

**Output**

A new polytope such that its vertices are the convex hull of the given polytope.

**Notes**

The optimization problem associated to removing redundant vertices is handled by `Polyhedra`

. If the polyhedral computations backend requires an LP solver, but it has not been specified, we use `default_lp_solver_polyhedra(N)`

to define such solver. Otherwise, the redundancy-removal function of the polyhedral backend is used.

`LazySets.API.reflect`

— Method`reflect(P::VPolytope)`

Concrete reflection of a polytope in vertex representation `P`

, resulting in the reflected set `-P`

.

**Input**

`P`

– polytope in vertex representation

**Output**

The `VPolytope`

representing `-P`

.

`LazySets.tohrep`

— Method```
tohrep(P::VPolytope{N};
[backend]=default_polyhedra_backend(P)) where {N}
```

Transform a polytope in vertex representation to a polytope in constraint representation.

**Input**

`P`

– polytope in vertex representation`backend`

– (optional, default:`default_polyhedra_backend(P)`

) the backend for polyhedral computations; see Polyhedra's documentation for further information

**Output**

A `HPolytope`

as the constraint representation of `P`

.

**Notes**

The conversion may not preserve the numeric type (e.g., with `N == Float32`

) depending on the backend.

`LazySets.tovrep`

— Method`tovrep(P::VPolytope)`

Return a vertex representation of the given polytope in vertex representation (no-op).

**Input**

`P`

– polytope in vertex representation

**Output**

The same polytope instance.

`LazySets.API.vertices_list`

— Method`vertices_list(P::VPolytope)`

Return the list of vertices of a polytope in vertex representation.

**Input**

`P`

– polytope in vertex representation

**Output**

The list of vertices.

`LazySets.API.linear_map`

— Method`linear_map(M::AbstractMatrix, P::VPolytope; [apply_convex_hull]::Bool=false)`

Concrete linear map of a polytope in vertex representation.

**Input**

`M`

– matrix`P`

– polytope in vertex representation`apply_convex_hull`

– (optional, default:`false`

) flag for applying a convex hull to eliminate redundant vertices

**Output**

A polytope in vertex representation.

**Algorithm**

The linear map $M$ is applied to each vertex of the given set $P$, obtaining a polytope in vertex representation. The output type is again a `VPolytope`

.

`Base.:∈`

— Method```
∈(x::AbstractVector{N}, P::VPolytope{N};
solver=default_lp_solver(N)) where {N}
```

Check whether a given point is contained in a polytope in vertex representation.

**Input**

`x`

– point/vector`P`

– polytope in vertex representation`solver`

– (optional, default:`default_lp_solver(N)`

) the backend used to solve the linear program

**Output**

`true`

iff $x ∈ P$.

**Algorithm**

We check, using linear programming, the definition of a convex polytope that a point is in the set if and only if it is a convex combination of the vertices.

Let $\{v_j\}$ be the $m$ vertices of `P`

. Then we solve the following $m$-dimensional linear program.

\[\max 0 \text{ s.t. } ⋀_{i=1}^n ∑_{j=1}^m λ_j v_j[i] = x[i] ∧ ∑_{j=1}^m λ_j = 1 ∧ ⋀_{j=1}^m λ_j ≥ 0\]

`LazySets.API.ρ`

— Method`ρ(d::AbstractVector, P::VPolytope)`

Evaluate the support function of a polytope in vertex representation in a given direction.

**Input**

`d`

– direction`P`

– polytope in vertex representation

**Output**

Evaluation of the support function in the given direction.

`LazySets.API.σ`

— Method`σ(d::AbstractVector, P::VPolytope)`

Return a support vector of a polytope in vertex representation in a given direction.

**Input**

`d`

– direction`P`

– polytope in vertex representation

**Output**

A support vector in the given direction.

**Algorithm**

A support vector maximizes the support function. For a polytope, the support function is always maximized in some vertex. Hence it is sufficient to check all vertices.

`LazySets.API.translate`

— Method`translate(P::VPolytope, v::AbstractVector)`

Translate (i.e., shift) a polytope in vertex representation by a given vector.

**Input**

`P`

– polytope in vertex representation`v`

– translation vector

**Output**

A translated polytope in vertex representation.

**Notes**

See `translate!(::VPolytope, ::AbstractVector)`

for the in-place version.

`LazySets.API.translate!`

— Method`translate!(P::VPolytope, v::AbstractVector)`

Translate (i.e., shift) a polytope in vertex representation by a given vector, in-place.

**Input**

`P`

– polytope in vertex representation`v`

– translation vector

**Output**

The polytope `P`

translated by `v`

.

**Notes**

See `translate(::VPolytope, ::AbstractVector)`

for the out-of-place version.

**Algorithm**

We add the vector to each vertex of the polytope.

`LazySets.API.cartesian_product`

— Method`cartesian_product(P1::VPolytope, P2::VPolytope; [backend]=nothing)`

Compute the Cartesian product of two polytopes in vertex representation.

**Input**

`P1`

– polytope in vertex representation`P2`

– polytope in vertex representation`backend`

– (optional, default:`nothing`

) backend for polyhedral computation

**Output**

The `VPolytope`

obtained by the concrete Cartesian product of `P1`

and `P2`

.

**Notes**

For further information on the supported backends see Polyhedra's documentation.

`LazySets.API.convex_hull`

— Method`convex_hull(P1::VPolytope, P2::VPolytope; [backend]=nothing)`

Compute the convex hull of two polytopes in vertex representation.

**Input**

`P1`

– polytope in vertex representation`P2`

– polytope in vertex representation`backend`

– (optional, default:`nothing`

) the polyhedral computation backend

**Output**

The `VPolytope`

obtained by the concrete convex hull of `P1`

and `P2`

.

**Notes**

This function takes the union of the vertices of each polytope and then relies on a concrete convex-hull algorithm. For low dimensions, a specialized implementation for polygons is used. For higher dimensions, `convex_hull`

relies on the polyhedral backend that can be specified using the `backend`

keyword argument.

For performance reasons, it is suggested to use the `CDDLib.Library()`

backend.

`LazySets.API.minkowski_sum`

— Method```
minkowski_sum(P1::VPolytope, P2::VPolytope;
[apply_convex_hull]=true,
[backend]=nothing,
[solver]=nothing)
```

Compute the Minkowski sum of two polytopes in vertex representation.

**Input**

`P1`

– polytope`P2`

– polytope`apply_convex_hull`

– (optional, default:`true`

) if`true`

, post-process the pairwise sums using a convex-hull algorithm`backend`

– (optional, default:`nothing`

) the backend for polyhedral computations used to post-process with a convex hull; see`default_polyhedra_backend(P1)`

`solver`

– (optional, default:`nothing`

) the backend used to solve the linear program; see`default_lp_solver_polyhedra(N)`

**Output**

A new polytope in vertex representation whose vertices are the convex hull of the sum of all possible sums of vertices of `P1`

and `P2`

.

Inherited from `LazySet`

:

Inherited from `AbstractPolyhedron`

:

Inherited from `AbstractPolytope`

: