Polytope in vertex representation (VPolytope)

VPolytope{N, VN<:AbstractVector{N}} <: 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]

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

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

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

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.

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.

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.

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.

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.

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.

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.