Polytopes (AbstractPolytope)

AbstractPolytope{N} <: AbstractPolyhedron{N}

Abstract type for compact convex polytopic sets.

Notes

See HPolytope or VPolytope for standard implementations of this interface.

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.

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.

isempty(X::LazySet, witness::Bool=false)

Check whether a set is empty.

Input

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

Output

• If the witness option is deactivated: true iff $X = ∅$
• If the witness option is activated:
  • (true, []) iff $X = ∅$
  • (false, v) iff $X ≠ ∅$ for some $v ∈ X$

Extended help

isempty(P::AbstractPolytope)

Algorithm

This algorithm checks whether the vertices_list of P is empty.

isuniversal(X::LazySet, witness::Bool=false)

Check whether a set is universal.

Input

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

Output

• If the witness option is deactivated: true iff $X = ℝ^n$
• If the witness option is activated:
  • (true, []) iff $X = ℝ^n$
  • (false, v) iff $X ≠ ℝ^n$ for some $v ∉ X$

Extended help

isuniversal(P::AbstractPolytope, [witness]::Bool=false)

Algorithm

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

volume(X::LazySet)

Compute the volume, or Lebesgue measure, of a set.

Input

• X – set

Output

A real number representing the Lebesgue measure of X.

Notes

The Lebesgue measure has the following common special cases:

• In 1D, it coincides with the length.
• In 2D, it coincides with the area (see also area).
• In 3D, it coincides with the volume.

In higher dimensions, it is also known as the hypervolume or simply volume.

Extended help

volume(P::AbstractPolytope; backend=default_polyhedra_backend(P))

Input

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

Algorithm

The volume is computed by the Polyhedra library.

⊆(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether a set is a subset of another set, and optionally compute a witness.

Input

• X – set
• Y – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X ⊆ Y$
• If the witness option is activated:
  • (true, []) iff $X ⊆ Y$
  • (false, v) iff $X ⊈ Y$ for some $v ∈ X ∖ Y$

Notes

The convenience alias issubset is also available.

Extended help

⊆(P::AbstractPolytope, S::LazySet, [witness]::Bool=false;
  [algorithm]="constraints")

Input

• algorithm – (optional, default: "constraints") algorithm for the inclusion check; available options are:

  • "constraints", using the list of constraints of S (requires that S is polyhedral) and support-function evaluations of S

  • "vertices", using the list of vertices of P and membership evaluations of S

Notes

S is assumed to be convex, which is asserted via isconvextype.

Algorithm

• "vertices":

Since $S$ is convex, $P ⊆ S$ iff $v ∈ S$ for all vertices $v$ of $P$.

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.

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.