Polytope in constraint representation (HPolytope)

Convex polytopes are bounded polyhedra. The type HPolytope represents polytopes. While identical to HPolyhedron in implementation, HPolytope instances are assumed to be bounded.

LazySets.HPolytopeType
HPolytope{N, VN<:AbstractVector{N}} <: AbstractPolytope{N}

Type that represents a convex polytope in H-representation, that is a finite intersection of half-spaces,

\[P = \bigcap_{i = 1}^m H_i,\]

where each $H_i = \{x \in \mathbb{R}^n : a_i^T x \leq b_i \}$ is a half-space, $a_i \in \mathbb{R}^n$ is the normal vector of the $i$-th half-space and $b_i$ is the displacement. It is assumed that $P$ is bounded (see also HPolyhedron which does not make such assumption).

Fields

  • constraints – vector of linear constraints
  • check_boundedness – (optional, default: false) flag for checking if the constraints make the polytope bounded; (boundedness is a running assumption of this type)

Note

Recall that a polytope is a bounded polyhedron. Boundedness is a running assumption in this type.

source

Some functionality is shared with HPolyhedron. Below follows the additional functionality specific to HPolytope.

Base.randMethod
rand(::Type{HPolytope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random polytope in constraint representation.

Input

  • HPolytope – 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 constraint representation.

Algorithm

We create a random polytope in vertex representation and convert it to constraint representation (hence the argument num_vertices). See rand(::Type{VPolytope}).

source
LazySets.vertices_listMethod
vertices_list(P::AbstractHPolygon{N};
              apply_convex_hull::Bool=true,
              check_feasibility::Bool=true) where {N}

Return the list of vertices of a polygon in constraint representation.

Input

  • P – polygon in constraint representation
  • apply_convex_hull – (optional, default: true) flag to post-process the intersection of constraints with a convex hull
  • check_feasibility – (optional, default: true) flag to check whether the polygon was empty (required for correctness in case of empty polygons)

Output

List of vertices.

Algorithm

We compute each vertex as the intersection of consecutive lines defined by the half-spaces. If check_feasibility is active, we then check if the constraints of the polygon were actually feasible (i.e., they pointed in the right direction). For this we compute the average of all vertices and check membership in each constraint.

source
vertices_list(B::Ball1{N, VN}) where {N, VN<:AbstractVector}

Return the list of vertices of a ball in the 1-norm.

Input

  • B – ball in the 1-norm

Output

A list containing the vertices of the ball in the 1-norm.

source
vertices_list(∅::EmptySet{N}) where {N}

Return the list of vertices of an empty set.

Input

  • – empty set

Output

The empty list of vertices, as the empty set does not contain any vertices.

source
vertices_list(P::HPolytope{N};
              [backend]=nothing, [prune]::Bool=true) where {N}

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

Input

  • P – polytope in constraint representation
  • backend – (optional, default: nothing) the polyhedral computations backend
  • prune – (optional, default: true) flag to remove redundant vertices

Output

List of vertices.

Algorithm

If the polytope is two-dimensional, the polytope is converted to a polygon in H-representation and then its vertices_list function is used. This ensures that, by default, the optimized two-dimensional methods are used.

It is possible to use the Polyhedra backend in two-dimensions as well by passing, e.g. backend=CDDLib.Library().

If the polytope is not two-dimensional, the concrete polyhedra manipulation library Polyhedra is used. The actual computation is performed by a given backend; for the default backend used in LazySets see default_polyhedra_backend(P). For further information on the supported backends see Polyhedra's documentation.

source
vertices_list(cp::CartesianProduct{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product.

Input

  • cp – Cartesian product

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

source

vertices_list(cpa::CartesianProductArray{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product of a finite number of sets.

Input

  • cpa – Cartesian product array

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

source
vertices_list(em::ExponentialMap{N};
              [backend]=get_exponential_backend()) where {N}

Return the list of vertices of a (polytopic) exponential map.

Input

  • em – exponential map
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polytopic. Then the result is just the exponential map applied to the vertices of X.

source
LazySets.isboundedFunction
isbounded(P::HPolytope, [use_type_assumption]::Bool=true)

Determine whether a polytope in constraint representation is bounded.

Input

  • P – polytope in constraint representation
  • use_type_assumption – (optional, default: true) flag for ignoring the type assumption that polytopes are bounded

Output

true if use_type_assumption is activated. Otherwise, true iff P is bounded.

Algorithm

If !use_type_assumption, we convert P to an HPolyhedron P2 and then use isbounded(P2).

source

Inherited from AbstractPolytope: