LazySets.APIModule
API

This module contains an API (application programming interface) for set libraries. The module only defines and documents the general functions and does not provide implementations.

source

Set interface

LazySets.API.LazySetType
LazySet

Abstract type for a set of points.

This type is not exported and is only used to define interface methods without type piracy.

The LazySets library defines its own set interface, which is also called LazySet.

source

Unary set functions

LazySets.API.an_elementMethod
an_element(X::LazySet)

Return some element of a nonempty set.

Input

  • X – set

Output

An element of X unless X is empty.

source
LazySets.API.areaMethod
area(X::LazySet)

Compute the area of a two-dimensional set, respectively the surface area of a three-dimensional set.

Input

  • X – two- or three-dimensional set

Output

A number representing the (surface) area of X.

source
LazySets.API.centerMethod
center(X::LazySet, i::Int)

Compute the center of a centrally symmetric set in a given dimension.

Input

  • X – centrally symmetric set
  • i – dimension

Output

A real number representing the center of the set in the given dimension.

source
LazySets.API.centerMethod
center(X::LazySet)

Compute the center of a centrally symmetric set.

Input

  • X – centrally symmetric set

Output

A vector with the center, or midpoint, of X.

source
LazySets.API.complementMethod
complement(X::LazySet)

Compute the complement of a set.

Input

  • X – set

Output

A set representing the complement of X.

source
LazySets.API.concretizeMethod
concretize(X::LazySet)

Construct a concrete representation of a (possibly lazy) set.

Input

  • X – set

Output

A concrete representation of X (as far as possible).

Notes

Since not every lazy set has a concrete set representation in this library, the result may still be partially lazy.

source
LazySets.API.constraints_listMethod
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.

source
LazySets.API.constraintsMethod
constraints(X::LazySet)

Construct an iterator over the constraints of a polyhedral set.

Input

  • X – polyhedral set

Output

An iterator over the constraints of X.

source
LazySets.API.convex_hullMethod
convex_hull(X::LazySet)

Compute the convex hull of a set.

Input

  • X – set

Output

A set representing the convex hull of X.

Notes

The convex hull of a set $X$ is defined as

\[ \{λx + (1-λ)y \mid x, y ∈ X, λ ∈ [0, 1]\}.\]

source
LazySets.API.diameterFunction
diameter(X::LazySet, [p]::Real=Inf)

Return the diameter of a set.

Input

  • X – set
  • p – (optional, default: Inf) norm

Output

A real number representing the diameter.

Notes

The diameter of a set is the maximum distance between any two elements of the set, or, equivalently, the diameter of the enclosing ball (of the given $p$-norm) of minimal volume.

source
LazySets.API.dimMethod
dim(X::LazySet)

Compute the ambient dimension of a set.

Input

  • X – set

Output

The ambient dimension of the set.

source
Base.eltypeMethod
eltype(T::Type{<:LazySet})

Determine the numeric type of a set type.

Input

  • T – set type

Output

The numeric type of T.

source
Base.eltypeMethod
eltype(X::LazySet)

Determine the numeric type of a set.

Input

  • X – set

Output

The numeric type of X.

source
Base.extremaMethod
extrema(X::LazySet, i::Int)

Compute the lowest and highest coordinate of a set in a given dimension.

Input

  • X – set
  • i – dimension

Output

Two real numbers representing the lowest and highest coordinate of the set in the given dimension.

Notes

The result is equivalent to (low(X, i), high(X, i)), but sometimes it can be computed more efficiently.

The resulting values are the lower and upper ends of the projection.

source
Base.extremaMethod
extrema(X::LazySet)

Compute the lowest and highest coordinate of a set in each dimension.

Input

  • X – set

Output

Two vectors with the lowest and highest coordinates of X in each dimension.

Notes

See also extrema(X::LazySet, i::Int).

The result is equivalent to (low(X), high(X)), but sometimes it can be computed more efficiently.

The resulting points are the lowest and highest corners of the box approximation, so they are not necessarily contained in X.

Algorithm

The default implementation computes the extrema via low and high.

source
LazySets.API.highMethod
high(X::LazySet, i::Int)

Compute the highest coordinate of a set in a given dimension.

Input

  • X – set
  • i – dimension

Output

A real number representing the highest coordinate of the set in the given dimension.

Notes

The resulting value is the upper end of the projection.

source
LazySets.API.highMethod
high(X::LazySet)

Compute the highest coordinate of a set in each dimension.

Input

  • X – set

Output

A vector with the highest coordinate of the set in each dimension.

Notes

See also high(X::LazySet, i::Int).

The result is the uppermost corner of the box approximation, so it is not necessarily contained in X.

source
LazySets.API.isconvextypeMethod
isconvextype(T::Type{<:LazySet})

Check whether T is convex just by using type information.

Input

  • T – subtype of LazySet

Output

true iff the set type only represents convex sets.

Notes

Since this operation only acts on types (not on values), it can return false negatives, i.e., there may be instances where the set is convex, even though the answer of this function is false. The examples below illustrate this point.

source
Base.isemptyFunction
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$
source
LazySets.API.ispolyhedralMethod
ispolyhedral(X::LazySet)

Check whether a set is polyhedral.

Input

  • X – set

Output

true only if the set is polyhedral.

Notes

The answer is conservative, i.e., may sometimes be false even if the set is polyhedral.

source
LazySets.API.isuniversalFunction
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$
source
LazySets.API.lowMethod
low(X::LazySet, i::Int)

Compute the lowest coordinate of a set in a given dimension.

Input

  • X – set
  • i – dimension

Output

A real number representing the lowest coordinate of the set in the given dimension.

Notes

The resulting value is the lower end of the projection.

source
LazySets.API.lowMethod
low(X::LazySet)

Compute the lowest coordinates of a set in each dimension.

Input

  • X – set

Output

A vector with the lowest coordinate of the set in each dimension.

Notes

See also low(X::LazySet, i::Int).

The result is the lowermost corner of the box approximation, so it is not necessarily contained in X.

source
LinearAlgebra.normFunction
norm(X::LazySet, [p]::Real=Inf)

Return the norm of a set.

Input

  • X – set
  • p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

The norm of a set is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.

source
LazySets.API.radiusFunction
radius(X::LazySet, [p]::Real=Inf)

Return the radius of a set.

Input

  • X – set
  • p – (optional, default: Inf) norm

Output

A real number representing the radius.

Notes

The radius of a set is the radius of the enclosing ball (of the given $p$-norm) of minimal volume.

source
Base.randMethod
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.

source
LazySets.API.reflectMethod
reflect(X::LazySet)

Compute the reflection of a set in the origin.

Input

  • X – set

Output

A set representing the reflection $-X$.

source
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
LazySets.API.verticesMethod
vertices(X::LazySet)

Construct an iterator over the vertices of a polytopic set.

Input

  • X – polytopic set

Output

An iterator over the vertices of X.

source
LazySets.API.volumeMethod
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.

source

Mixed set functions

LazySets.API.affine_mapMethod
affine_map(M::AbstractMatrix, X::LazySet, v::AbstractVector)

Compute the affine map $M · X + v$.

Input

  • M – matrix
  • X – set
  • v – translation vector

Output

A set representing the affine map $M · X + v$.

source
ReachabilityBase.Arrays.distanceMethod
distance(x::AbstractVector, X::LazySet; [p]::Real=2)
distance(X::LazySet, x::AbstractVector; [p]::Real=2)

Compute the standard distance (induced by the $p$-norm) between a point and a set.

Input

  • x – point/vector
  • X – set
  • p – (optional; default: 2) value of the $p$-norm

Output

A real number representing the distance between x and X.

Notes

The standard distance is zero if the point lies inside the set, and infinite if the set is empty. Otherwise, it is the $p$-norm of the shortest line segment between the point and any other point in the set. Formally,

\[ \inf_{y ∈ X} \{ d(x, y) \}.\]

source
LazySets.API.exponential_mapMethod
exponential_map(M::AbstractMatrix, X::LazySet)

Compute the exponential map of M and X, i.e., $eᴹ ⋅ X$.

Input

  • M – matrix
  • X – set

Output

A set representing the exponential map $eᴹ ⋅ X$.

source
Base.:∈Method
∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

  • x – point/vector
  • X – set

Output

true iff $x ∈ X$.

source
LazySets.API.is_interior_pointMethod
is_interior_point(v::AbstractVector, X::LazySet; [p]::Real=Inf, [ε]::Real=_rtol(eltype(X)))

Check whether a point is contained in the interior of a set.

Input

  • v – point/vector
  • X – set
  • p – (optional; default: Inf) norm of the ball used to apply the error tolerance
  • ε – (optional; default: _rtol(eltype(X))) error tolerance of the check

Output

true iff the point v is strictly contained in X with tolerance ε.

source
LazySets.API.linear_mapMethod
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$.

source
SparseArrays.permuteMethod
permute(X::LazySet, p::AbstractVector{Int})

Permute the dimensions of a set according to a given permutation vector.

Input

  • X – set
  • p – permutation vector

Output

A new set corresponding to X where the dimensions have been permuted according to p.

source
LazySets.API.projectMethod
project(X::LazySet, block::AbstractVector{Int})

Project a set to a given block by using a concrete linear map.

Input

  • X – set
  • block – block structure - a vector with the dimensions of interest

Output

A set representing the projection of X to block block.

source
LazySets.API.sampleFunction
sample(X::LazySet, [m]::Int=1;
       [rng]::AbstractRNG=GLOBAL_RNG,
       [seed]::Union{Int,Nothing}=nothing)

Compute random samples from a set.

Input

  • X – set
  • m – (optional; default: 1) number of random samples
  • rng – (optional, default: GLOBAL_RNG) random number generator
  • seed – (optional, default: nothing) seed for reseeding

Output

A vector of m elements in X if X is nonempty, and an error otherwise.

source
LazySets.API.scaleMethod
scale(α::Real, X::LazySet)

Compute the scaling of a set.

Input

  • α – scalar
  • X – set

Output

A set representing $α ⋅ X$.

source
LazySets.API.scale!Method
scale!(α::Real, X::LazySet)

Scale a set by modifying it.

Input

  • α – scalar
  • X – set

Output

The scaled set representing $α ⋅ X$.

source
LazySets.API.ρMethod
ρ(d::AbstractVector, X::LazySet)

Evaluate the support function of a set in a given direction.

Input

  • d – direction
  • X – set

Output

The evaluation of the support function of X in direction d.

Notes

The convenience alias support_function is also available.

We have the following identity based on the support vector $σ$:

\[ ρ(d, X) = d ⋅ σ(d, X)\]

source
LazySets.API.σMethod
σ(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

The convenience alias support_vector is also available.

source
LazySets.API.translateMethod
translate(X::LazySet, v::AbstractVector)

Compute the translation of a set with a vector.

Input

  • X – set
  • v – vector

Output

A set representing $X + \{v\}$.

source
LazySets.API.translate!Method
translate!(X::LazySet, v::AbstractVector)

Translate a set with a vector by modifying it.

Input

  • X – set
  • v – vector

Output

The translated set representing $X + \{v\}$.

source

Binary set functions

LazySets.API.cartesian_productMethod
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\}.\]

source
LazySets.API.convex_hullMethod
convex_hull(X::LazySet, Y::LazySet)

Compute the convex hull of (the union of) two sets.

Input

  • X – set
  • Y – set

Output

A set representing the convex hull of $X ∪ Y$.

Notes

See convex_hull(::LazySet) for the convex hull of a single set.

source
LazySets.API.differenceMethod
difference(X::LazySet, Y::LazySet)

Compute the set difference of two sets.

Input

  • X – set
  • Y – set

Output

A set representing the difference $X ∖ Y$.

Notes

The set difference is defined as:

\[ X ∖ Y = \{x \mid x ∈ X \text{ and } x ∉ Y \}\]

source
ReachabilityBase.Arrays.distanceMethod
distance(X::LazySet, Y::LazySet; [p]::Real=2)

Compute the standard distance (induced by the $p$-norm) between two sets.

Input

  • X – set
  • Y – set
  • p – (optional; default: 2) value of the $p$-norm

Output

A real number representing the distance between X and Y.

Notes

The standard distance is zero if the sets intersect, and infinite if one of the sets is empty. Otherwise, it is the $p$-norm of the shortest line segment between any pair of points. Formally,

\[ \inf_{x ∈ X, y ∈ Y} \{ d(x, y) \}.\]

source
LazySets.API.exact_sumMethod
exact_sum(X::LazySet, Y::LazySet)

Compute the exact sum of two parametric sets.

Input

  • X – parametric set
  • Y – parametric set

Output

A set representing the exact sum, sometimes written $X ⊞ Y$.

Notes

For parametric sets, the exact sum behaves like the Minkowski sum, except that the parameters are shared. Thus, for nonparametric sets, it coincides with the Minkowski sum.

source
LazySets.API.intersectionMethod
intersection(X::LazySet, Y::LazySet)

Compute the intersection of two sets.

Input

  • X – set
  • Y – set

Output

A set representing the intersection $X ∩ Y$.

Notes

The intersection of two sets $X$ and $Y$ is defined as

\[ X ∩ Y = \{x \mid x ∈ X \text{ and } x ∈ Y\}.\]

source
Base.:≈Method
≈(X::LazySet, Y::LazySet)

Check whether two sets of the same type are approximately equal.

Input

  • X – set
  • Y – set of the same base type as X

Output

true iff X is approximately equal to Y.

Notes

The check is purely syntactic and the sets need to have the same base type, i.e., X::T1 ≈ Y::T2 always returns false even if X and Y represent the same set. But X::T{Int64} ≈ Y::T{Float64} is a valid comparison. Note that, unlike most other binary operations, a query with X and Y of different dimension is allowed (and results in the answer false).

"" can be typed by \approx<tab>. The convenience alias isapprox is also available.

source
Base.isdisjointMethod
isdisjoint(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether two sets are disjoint (i.e., do not intersect), 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 is_intersection_empty is also available.

source
Base.:==Method
==(X::LazySet, Y::LazySet)

Check whether two sets use exactly the same set representation.

Input

  • X – set
  • Y – set

Output

true iff X is equal to Y.

Notes

The check is purely syntactic and the sets need to have the same base type, i.e., X::T1 == Y::T2 always returns false even if X and Y represent the same set. But X::T{Int64} == Y::T{Float64} is a valid comparison. Note that, unlike most other binary operations, a query with X and Y of different dimension is allowed (and results in the answer false).

source
LazySets.API.isequivalentMethod
isequivalent(X::LazySet, Y::LazySet)

Check whether two sets are equivalent, i.e., represent the same set of points.

Input

  • X – set
  • Y – set

Output

true iff X is equivalent to Y (up to numerical precision).

source
LazySets.API.:⊂Method
⊂(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether a set is a strict 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, v) iff $X ⊂ Y$ for some $v ∈ Y ∖ X$
    • (false, []) iff $X ⊂ Y$ does not hold

Notes

Strict inclusion is sometimes written as . The following identity holds:

\[ X ⊂ Y ⇔ X ⊆ Y ∧ Y ⊈ X\]

Algorithm

The default implementation first checks inclusion of X in Y and then checks noninclusion of Y in X:

source
Base.:⊆Method
⊆(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.

source
LazySets.API.linear_combinationMethod
linear_combination(X::LazySet, Y::LazySet)

Compute the linear combination of two sets.

Input

  • X – set
  • Y – set

Output

A set representing the linear combination of X and Y.

Notes

The linear combination of two sets $X$ and $Y$ is defined as

\[ \left\{\frac{1}{2}(1+λ)x + \frac{1}{2}(1-λ)y \mid x ∈ X, y ∈ Y, λ ∈ [-1, 1]\right\}.\]

If $X$ and $Y$ are convex, their linear combination is identical with the convex hull of their union $X ∪ Y$.

source
LazySets.API.minkowski_differenceMethod
minkowski_difference(X::LazySet, Y::LazySet)

Compute the Minkowski difference of two sets.

Input

  • X – set
  • Y – set

Output

A set representing the Minkowski difference $X ⊖ Y$.

Notes

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

\[ X ⊖ Y = \{z \mid \{z\} ⊕ Y ⊆ X\}\]

The convenience alias pontryagin_difference is also available.

There is some inconsistency in the literature regarding the naming conventions. In this library, both Minkowski difference and Pontryagin difference refer to the geometric difference of two sets.

source
LazySets.API.minkowski_sumMethod
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\}.\]

source