GitHub

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.AbstractPolytope — Type
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_list — Method
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.isbounded — Method
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.isempty — Method
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.isuniversal — Method
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.volume — Method
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

The following functions can be implemented for sets in vertex representation:

LazySets.remove_redundant_vertices — Method
remove_redundant_vertices(P::AbstractPolytope)

Return an equivalent polytope in vertex representation with redundant vertices removed.

Input

  • P – polytope in vertex representation

Output

A new polytope with the redundant vertices removed.

source
LazySets.remove_redundant_vertices! — Method
remove_redundant_vertices!(P::AbstractPolytope)

Remove the redundant vertices from a polytope in vertex representation in-place.

Input

  • P – polytope in vertex representation

Output

A new polytope with the redundant vertices removed.

source

Implementations