Polytope in vertex representation (VPolytope)

VPolytope{N, VN<:AbstractVector{N}} <: AbstractPolytope{N}

Type that represents a convex polytope in V-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
3-element Array{Array{Int64,1},1}:
 [0, 1, 0, 0]
 [0, 0, 1, 0]
 [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 LinearAlgebra.Adjoint{Int64,Array{Int64,2}}:
 0  1  0  0
 0  0  1  0
 0  0  0  1

julia> P = VPolytope(M);

julia> P.vertices
4-element Array{Array{Int64,1},1}:
 [0, 0, 0]
 [1, 0, 0]
 [0, 1, 0]
 [0, 0, 1]

dim(P::VPolytope)

Return the dimension of a polytope in V-representation.

Input

• P – polytope in V-representation

Output

The ambient dimension of the polytope in V-representation. If it is empty, the result is $-1$.

Examples

julia> v = VPolytope();

julia> isempty(v.vertices)
true

julia> dim(v)
-1

julia> v = VPolytope([ones(3)]);

julia> v.vertices
1-element Array{Array{Float64,1},1}:
 [1.0, 1.0, 1.0]

julia> dim(v) == 3
true

σ(d::AbstractVector, P::VPolytope)

Return the support vector of a polytope in V-representation in a given direction.

Input

• d – direction
• P – polytope in V-representation

Output

The 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.

∈(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. } \bigwedge_{i=1}^n \sum_{j=1}^m λ_j v_j[i] = x[i] ∧ \sum_{j=1}^m λ_j = 1 ∧ \bigwedge_{j=1}^m λ_j ≥ 0\]

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.

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.

Algorithm

We add the vector to each vertex of the polytope.

vertices_list(P::VPolytope)

Return the list of vertices of a polytope in V-representation.

Input

• P – polytope in vertex representation

Output

List of vertices.

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.

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 set, we use default_lp_solver_polyhedra(N) to define such solver. Otherwise, the redundancy removal function of the polyhedral backend is used.

constraints_list(P::VPolytope)

Return the list of constraints defining a polytope in V-representation.

Input

• P – polytope in V-representation

Output

The list of constraints of the polytope.

Algorithm

First the H-representation of $P$ is computed, then its list of constraints is returned.

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

Transform a polytope in V-representation to a polytope in H-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

The HPolytope which is the constraint representation of the given polytope in vertex representation.

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.

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

Return an VRep polyhedron from Polyhedra.jl given a polytope in V-representation.

Input

• P – polytope
• 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.

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 V-representation. The output type is again a VPolytope.