Polytope in vertex representation (VPolytope)

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]

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

∈(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\]

ρ(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.

σ(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.

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.

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.

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.

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.

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.