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(X::LazySet)

Compute a list of linear constraints of a polyhedral set.

Input

• X – polyhedral set

Output

A list of the linear constraints of X.

constraints_list(P::VPolytope)

Algorithm

For one- and two-dimensional sets, we respectively convert to an Interval or a VPolytope and call the corresponding constraints_list function. For higher-dimensional sets, we use tohrep to compute the constraint representation and call the corresponding constraints_list function.

dim(X::LazySet)

Compute the ambient dimension of a set.

Input

• X – set

Output

The ambient dimension of the set.

dim(P::VPolytope)

Output

If P is empty, the result is $-1$.

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(T::Type{<:LazySet}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing
    )

Create a random set of the given set type.

Input

• T – set type
• 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

Output

A random set of the given set type.

Extended help

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

Input

• num_vertices – (optional, default: -1) upper bound on the number of vertices of the polytope (see comment below)

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 this implementation does not guarantee that the vertices are not redundant, and hence the result may have fewer vertices than specified in num_vertices.

remove_redundant_vertices(P::VPolytope; [backend]=nothing, [solver]=nothing)

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.

tohrep(P::VPolytope; [backend]=default_polyhedra_backend(P))

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.

linear_map(M::AbstractMatrix, X::LazySet)

Compute the linear map $M · X$.

Input

• M – matrix
• X – set

Output

A set representing the linear map $M · X$.

Extended help

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

Input

• apply_convex_hull – (optional, default: false) flag for applying a convex hull to eliminate redundant vertices

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, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

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

Input

• solver – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

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, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

A convenience alias support_vector is also available.

Extended help

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

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.

cartesian_product(X::LazySet, Y::LazySet)

Compute the Cartesian product of two sets.

Input

• X – set
• Y – set

Output

A set representing the Cartesian product $X × Y$.

Notes

The Cartesian product of two sets $X$ and $Y$ is defined as

\[ X × Y = \{[x, y] \mid x ∈ X, y ∈ Y\}.\]

Extended help

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

Input

• backend – (optional, default: nothing) backend for polyhedral computation

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.

intersection(P1::Union{VPolygon, VPolytope}, P2::Union{VPolygon, VPolytope};
             [backend]=nothing, [prunefunc]=nothing)

Compute the intersection of two polytopes in vertex representation.

Input

• P1 – polytope in vertex representation
• P2 – polytope in vertex representation
• backend – (optional, default: nothing) the backend for polyhedral computations
• prunefunc – (optional, default: nothing) function to prune the vertices of the result

Output

A VPolytope.

Notes

If prunefunc is nothing, this implementation sets it to (X -> removevredundancy!(X; ztol=_ztol(eltype(P1)))).

minkowski_sum(X::LazySet, Y::LazySet)

Compute the Minkowski sum of two sets.

Input

• X – set
• Y – set

Output

A set representing the Minkowski sum $X ⊕ Y$.

Notes

The Minkowski sum of two sets $X$ and $Y$ is defined as

\[ X ⊕ Y = \{x + y \mid x ∈ X, y ∈ Y\}.\]

Extended help

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

Input

• 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)

Algorithm

The resulting polytope in vertex representation consists of the vertices corresponding to the convex hull of the sum of all possible sums of vertices of P1 and P2.