Polytopes (AbstractPolytope)

A polytope is a bounded set with finitely many vertices (V-representation) resp. facets (H-representation). Note that there is a special interface combination Centrally symmetric polytope.

LazySets.AbstractPolytopeType
AbstractPolytope{N} <: AbstractPolyhedron{N}

Abstract type for compact convex polytopic sets.

Notes

Every concrete AbstractPolytope must define the following method:

  • vertices_list(::AbstractPolytope) – return a list of all vertices
julia> subtypes(AbstractPolytope)
5-element Vector{Any}:
 AbstractCentrallySymmetricPolytope
 AbstractPolygon
 HPolytope
 Tetrahedron
 VPolytope

A polytope is a bounded polyhedron (see AbstractPolyhedron). Polytopes are compact convex sets with either of the following equivalent properties:

  1. They are the intersection of a finite number of closed half-spaces.
  2. They are the convex hull of finitely many vertices.
source

This interface requires to implement the following function:

LazySets.API.vertices_listMethod
vertices_list(X::LazySet)

Compute a list of vertices of a polytopic set.

Input

  • X – polytopic set

Output

A list of the vertices of X.

source

This interface defines the following functions:

LazySets.API.isboundedMethod
isbounded(P::AbstractPolytope)

Check whether a polytopic set is bounded.

Input

  • P – polytopic set

Output

true (since a polytopic set must be bounded).

source
Base.isemptyMethod
isempty(P::AbstractPolytope)

Check whether a polytopic set is empty.

Input

  • P – polytopic set

Output

true if the given polytopic set contains no vertices, and false otherwise.

Algorithm

This algorithm checks whether the vertices_list of P is empty.

source
LazySets.API.isuniversalMethod
isuniversal(P::AbstractPolytope{N}, [witness]::Bool=false) where {N}

Check whether a polytopic set is universal.

Input

  • P – polytopic set
  • witness – (optional, default: false) compute a witness if activated

Output

  • If witness option is deactivated: false
  • If witness option is activated: (false, v) where $v ∉ P$ unless the list of constraints is empty (which should not happen for a normal polytope)

Algorithm

A witness is produced using isuniversal(H) where H is the first linear constraint of P.

source
LazySets.API.volumeMethod
volume(P::AbstractPolytope; backend=default_polyhedra_backend(P))

Compute the volume of a polytopic set.

Input

  • P – polytopic set
  • backend – (optional, default: default_polyhedra_backend(P)) the backend for polyhedral computations; see Polyhedra's documentation for further information

Output

The volume of P.

Algorithm

The volume is computed by the Polyhedra library.

source

Implementations