`LazySets.API`

— Module`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.

# Set interface

`LazySets.API.LazySet`

— Type`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`

.

# Unary set functions

`LazySets.API.an_element`

— Method`an_element(X::LazySet)`

Return some element of a nonempty set.

**Input**

`X`

– set

**Output**

An element of `X`

unless `X`

is empty.

`LazySets.API.area`

— Method`area(X::LazySet)`

Compute the area of a two-dimensional set.

**Input**

`X`

– two-dimensional set

**Output**

A number representing the area of `X`

.

`LazySets.API.center`

— Method`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.

`LazySets.API.center`

— Method`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`

.

`LazySets.API.complement`

— Method`complement(X::LazySet)`

Compute the complement of a set.

**Input**

`X`

– set

**Output**

A set representing the complement of `X`

.

`LazySets.API.concretize`

— Method`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.

`LazySets.API.constraints_list`

— Method`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`

.

`LazySets.API.constraints`

— Method`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`

.

`LazySets.API.convex_hull`

— Method`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]\}.\]

`LazySets.API.diameter`

— Function`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 with the same center.

`LazySets.API.dim`

— Method`dim(X::LazySet)`

Compute the ambient dimension of a set.

**Input**

`X`

– set

**Output**

The ambient dimension of the set.

`Base.eltype`

— Method`eltype(T::Type{<:LazySet})`

Determine the numeric type of a set type.

**Input**

`T`

– set type

**Output**

The numeric type of `T`

.

`Base.eltype`

— Method`eltype(X::LazySet)`

Determine the numeric type of a set.

**Input**

`X`

– set

**Output**

The numeric type of `X`

.

`Base.extrema`

— Method`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.

`Base.extrema`

— Method`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`

.

`LazySets.API.high`

— Method`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.

`LazySets.API.high`

— Method`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`

.

`LazySets.API.is_polyhedral`

— Method`is_polyhedral(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.

`LazySets.API.isbounded`

— Method`isbounded(X::LazySet)`

Check whether a set is bounded.

**Input**

`X`

– set

**Output**

`true`

iff the set is bounded.

**Notes**

See also `isboundedtype(::Type{<:LazySet})`

.

`LazySets.API.isboundedtype`

— Method`isboundedtype(T::Type{<:LazySet})`

Check whether a set type only represents bounded sets.

**Input**

`T`

– set type

**Output**

`true`

iff the set type only represents bounded sets.

**Notes**

See also `isbounded(::LazySet)`

.

`LazySets.API.isconvextype`

— Method`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.

`Base.isempty`

— Function`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$

`LazySets.API.isoperation`

— Method`isoperation(X::LazySet)`

Check whether a set is an instance of a (lazy) set operation.

**Input**

`X`

– set

**Output**

`true`

iff `X`

is an instance of a set-based operation.

**Notes**

See also `isoperationtype(::Type{<:LazySet})`

.

`LazySets.API.isoperationtype`

— Method`isoperationtype(T::Type{<:LazySet})`

Check whether a set type is a (lazy) set operation.

**Input**

`T`

– set type

**Output**

`true`

iff the set type represents a set operation.

**Notes**

See also `isoperation(::LazySet)`

.

`LazySets.API.isuniversal`

— Function`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$

`LazySets.API.low`

— Method`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.

`LazySets.API.low`

— Method`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`

.

`LinearAlgebra.norm`

— Function`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.

`LazySets.API.radius`

— Function`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 with the same center.

`Base.rand`

— Method```
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.

`ReachabilityBase.Arrays.rectify`

— Method`rectify(X::LazySet)`

Compute the rectification of a set.

**Input**

`X`

– set

**Output**

A set representing the rectification of `X`

.

`LazySets.API.reflect`

— Method`reflect(X::LazySet)`

Compute the reflection of a set in the origin.

**Input**

`X`

– set

**Output**

A set representing the reflection $-X$.

`LazySets.API.surface`

— Method`surface(X::LazySet)`

Compute the surface area of a set.

**Input**

`X`

– set

**Output**

A real number representing the surface area of `X`

.

`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`

.

`LazySets.API.vertices`

— Method`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`

.

`LazySets.API.volume`

— Method`volume(X::LazySet)`

Compute the volume of a set.

**Input**

`X`

– set

**Output**

A real number representing the volume of `X`

.

# Mixed set functions

`LazySets.API.affine_map`

— Method`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$.

`LazySets.API.exponential_map`

— Method`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$.

`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$.

`LazySets.API.is_interior_point`

— Method`is_interior_point(v::AbstractVector{N}, X::LazySet; [p]=N(Inf), [ε]=_rtol(N)) where {N}`

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

**Input**

`v`

– point/vector`X`

– set`p`

– (optional; default:`N(Inf)`

) norm of the ball used to apply the error tolerance`ε`

– (optional; default:`_rtol(N)`

) error tolerance of the check

**Output**

`true`

iff the point `v`

is strictly contained in `X`

with tolerance `ε`

.

`LazySets.API.linear_map`

— Method`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$.

`SparseArrays.permute`

— Method`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`

.

`LazySets.API.project`

— Method`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`

.

`LazySets.API.sample`

— Method```
sample(X::LazySet, m::Int;
[rng]::AbstractRNG=GLOBAL_RNG,
[seed]::Union{Int,Nothing}=nothing)
```

Compute samples from a set.

**Input**

`X`

– set`m`

– 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`

.

`LazySets.API.scale`

— Method`scale(α::Real, X::LazySet)`

Compute the scaling of a set.

**Input**

`α`

– scalar`X`

– set

**Output**

A set representing $α ⋅ X$.

`LazySets.API.scale!`

— Method`scale!(α::Real, X::LazySet)`

Scale a set by modifying it.

**Input**

`α`

– scalar`X`

– set

**Output**

The scaled set representing $α ⋅ X$.

`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**

A convenience alias `support_function`

is also available.

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

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

`LazySets.API.support_function`

— Function**Algorithm**

The default implementation computes a support vector via `σ`

.

`ρ(d::AbstractVector, hs::HalfSpace)`

Evaluate the support function of a half-space in a given direction.

**Input**

`d`

– direction`hs`

– half-space

**Output**

The support function of the half-space. Unless the direction is (a multiple of) the normal direction of the half-space, the result is `Inf`

.

`ρ(d::AbstractVector, Z::AbstractZonotope)`

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

**Input**

`d`

– direction`Z`

– zonotopic set

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

The support value is $cᵀ d + ‖Gᵀ d‖₁$, where $c$ is the center and $G$ is the generator matrix of `Z`

.

`ρ(d::AbstractVector, H::AbstractHyperrectangle)`

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

**Input**

`d`

– direction`H`

– hyperrectangular set

**Output**

The evaluation of the support function in the given direction.

`ρ(d::AbstractVector, S::AbstractSingleton)`

Evaluate the support function of a set with a single value in a given direction.

**Input**

`d`

– direction`S`

– set with a single value

**Output**

The support value in the given direction.

`ρ(d::AbstractVector, am::AbstractAffineMap)`

Evaluate the support function of an affine map.

**Input**

`d`

– direction`am`

– affine map

**Output**

The evaluation of the support function in the given direction.

`ρ(d::AbstractVector, B::AbstractBallp)`

Evaluate the support function of a ball in the p-norm in the given direction.

**Input**

`d`

– direction`B`

– ball in the p-norm

**Output**

Evaluation of the support function in the given direction.

**Algorithm**

Let $c$ and $r$ be the center and radius of the ball $B$ in the p-norm, respectively, and let $q = \frac{p}{p-1}$. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_q.\]

`ρ(d::AbstractVector, B::Ball1)`

Evaluate the support function of a ball in the 1-norm in the given direction.

**Input**

`d`

– direction`B`

– ball in the 1-norm

**Output**

Evaluation of the support function in the given direction.

**Algorithm**

Let $c$ and $r$ be the center and radius of the ball $B$ in the 1-norm, respectively. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_∞.\]

`ρ(d::AbstractVector, B::Ball2)`

Return the support function of a 2-norm ball in the given direction.

**Input**

`d`

– direction`B`

– ball in the 2-norm

**Output**

The support function in the given direction.

**Algorithm**

Let $c$ and $r$ be the center and radius of the ball $B$ in the 2-norm, respectively. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_2.\]

`ρ(d::AbstractVector, B::BallInf)`

Evaluate the support function of a ball in the infinity norm in the given direction.

**Input**

`d`

– direction`B`

– ball in the infinity norm

**Output**

Evaluation of the support function in the given direction.

**Algorithm**

Let $B$ be a ball in the infinity norm with center $c$ and radius $r$ and let $d$ be the direction of interest. For balls with dimensions less than 30 we use the implementation for `AbstractHyperrectangle`

, tailored to a `BallInf`

, which computes

\[ ∑_{i=1}^n d_i (c_i + \textrm{sgn}(d_i) · r)\]

where $\textrm{sgn}(α) = 1$ if $α ≥ 0$ and $\textrm{sgn}(α) = -1$ if $α < 0$.

For balls of higher dimension we instead exploit that for a support vector $v = σ(d, B) = c + \textrm{sgn}(d) · (r, …, r)ᵀ$ we have

\[ ρ(d, B) = ⟨d, v⟩ = ⟨d, c⟩ + ⟨d, \textrm{sgn}(d) · (r, …, r)ᵀ⟩ = ⟨d, c⟩ + r · ∑_{i=1}^n |d_i|\]

where $⟨·, ·⟩$ denotes the dot product.

`ρ(d::AbstractVector, E::Ellipsoid)`

Return the support function of an ellipsoid in a given direction.

**Input**

`d`

– direction`E`

– ellipsoid

**Output**

The support function of the ellipsoid in the given direction.

**Algorithm**

The support value is $cᵀ d + ‖Bᵀ d‖₂$, where $c$ is the center and $Q = B Bᵀ$ is the shape matrix of `E`

.

`ρ(d::AbstractVector, ∅::EmptySet)`

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

**Input**

`d`

– direction`∅`

– empty set

**Output**

An error.

```
ρ(d::AbstractVector{M}, P::HPoly{N};
solver=default_lp_solver(M, N)) where {M, N}
```

Evaluate the support function of a polyhedron in constraint representation in a given direction.

**Input**

`d`

– direction`P`

– polyhedron in constraint representation`solver`

– (optional, default:`default_lp_solver(M, N)`

) the backend used to solve the linear program

**Output**

The evaluation of the support function for the polyhedron. If a polytope is unbounded in the given direction, we throw an error. If a polyhedron is unbounded in the given direction, the result is `Inf`

.

`ρ(d::AbstractVector, H::Hyperplane)`

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

**Input**

`d`

– direction`H`

– hyperplane

**Output**

The support function of the hyperplane. If the set is unbounded in the given direction, the result is `Inf`

.

`ρ(d::AbstractVector, x::Interval)`

Evaluate the support function of an interval in a given direction.

**Input**

`d`

– direction`x`

– interval

**Output**

Evaluation of the support function in the given direction.

`ρ(d::AbstractVector, L::Line)`

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

**Input**

`d`

– direction`L`

– line

**Output**

Evaluation of the support function in the given direction.

`ρ(d::AbstractVector, L::LineSegment)`

Evaluate the support function of a 2D line segment in a given direction.

**Input**

`d`

– direction`L`

– 2D line segment

**Output**

Evaluation of the support function in the given direction.

`ρ(d::AbstractVector, R::RotatedHyperrectangle)`

Evaluate the support function of a rotated hyperrectangle in a given direction.

**Input**

`d`

– direction`R`

– rotated hyperrectangle

**Output**

Evaluation of the support function in the given direction.

`ρ(d::AbstractVector, P::SparsePolynomialZonotope; [enclosure_method]=nothing)`

Bound the support function of $P$ in the direction $d$.

**Input**

`d`

– direction`P`

– sparse polynomial zonotope`enclosure_method`

– (optional; default:`nothing`

) method to use for enclosure; an`AbstractEnclosureAlgorithm`

from the`Rangeenclosures.jl`

package

**Output**

An overapproximation of the support function in the given direction.

**Algorithm**

This method implements Proposition 3.1.16 in [1].

[1] Kochdumper, Niklas. *Extensions of polynomial zonotopes and their application to verification of cyber-physical systems.* PhD diss., Technische Universität München, 2022.

`ρ(d::AbstractVector, U::Universe)`

Return the support function of a universe.

**Input**

`d`

– direction`U`

– universe

**Output**

The support function in the given direction.

**Algorithm**

If the direction is all zero, the result is zero. Otherwise, the result is `Inf`

.

`ρ(d::AbstractVector, P::VPolytope)`

Evaluate the support function of a polytope in vertex representation in a given direction.

**Input**

`d`

– direction`P`

– polytope in vertex representation

**Output**

Evaluation of the support function in the given direction.

`ρ(d::AbstractVector, Z::ZeroSet)`

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

**Input**

`d`

– direction`Z`

– zero set

**Output**

`0`

.

`ρ(d::AbstractVector, B::Bloating)`

Return the support function of a bloated set in a given direction.

**Input**

`d`

– direction`B`

– bloated set

**Output**

The support function of the bloated set in the given direction.

`ρ(d::AbstractVector, cp::CartesianProduct)`

Evaluate the support function of a Cartesian product.

**Input**

`d`

– direction`cp`

– Cartesian product

**Output**

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

`ρ(d::AbstractVector, cpa::CartesianProductArray)`

Evaluate the support function of a Cartesian product of a finite number of sets.

**Input**

`d`

– direction`cpa`

– Cartesian product of a finite number of sets

**Output**

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

`ρ(d::AbstractVector, ch::ConvexHull)`

Evaluate the support function of the convex hull of two sets in a given direction.

**Input**

`d`

– direction`ch`

– convex hull of two sets

**Output**

The evaluation of the support function of the convex hull in the given direction.

`ρ(d::AbstractVector, cha::ConvexHullArray)`

Evaluate the support function of a convex hull of a finite number of sets in a given direction.

**Input**

`d`

– direction`cha`

– convex hull of a finite number of sets

**Output**

The evaluation of the support function of the convex hull of a finite number of sets in the given direction.

**Algorithm**

This algorithm calculates the maximum over all $ρ(d, X_i)$, where the $X_1, …, X_k$ are the sets in the array of `cha`

.

```
ρ(d::AbstractVector, em::ExponentialMap;
[backend]=get_exponential_backend())
```

Evaluate the support function of the exponential map.

**Input**

`d`

– direction`em`

– exponential map`backend`

– (optional; default:`get_exponential_backend()`

) exponentiation backend

**Output**

The evaluation of the support function in the given direction.

**Notes**

If $E = \exp(M)⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $ρ(d, E) = ρ(\exp(M)^T d, X)$ for any direction $d$.

```
ρ(d::AbstractVector, eprojmap::ExponentialProjectionMap;
[backend]=get_exponential_backend())
```

Evaluate the support function of a projection of an exponential map.

**Input**

`d`

– direction`eprojmap`

– projection of an exponential map`backend`

– (optional; default:`get_exponential_backend()`

) exponentiation backend

**Output**

Evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

**Notes**

If $S = (L⋅M⋅R)⋅X$, where $L$ and $R$ are matrices, $M$ is a matrix exponential, and $X$ is a set, it follows that $ρ(d, S) = ρ(R^T⋅M^T⋅L^T⋅d, X)$ for any direction $d$.

`ρ(d::AbstractVector, cap::Intersection)`

Return an upper bound on the support function of the intersection of two sets in a given direction.

**Input**

`d`

– direction`cap`

– intersection of two sets

**Output**

An upper bound on the support function in the given direction.

**Algorithm**

The support function of an intersection of $X$ and $Y$ is upper-bounded by the minimum of the support-function evaluations for $X$ and $Y$.

```
ρ(d::AbstractVector, cap::Intersection{N, S1, S2};
algorithm::String="line_search", kwargs...
) where {N, S1<:LazySet{N},
S2<:Union{HalfSpace{N}, Hyperplane{N}, Line2D{N}}}
```

Evaluate the support function of the intersection of a compact set and a half-space/hyperplane/line in a given direction.

**Input**

`d`

– direction`cap`

– lazy intersection of a compact set and a half-space/hyperplane/ line`algorithm`

– (optional, default:`"line_search"`

): the algorithm to calculate the support function; valid options are:`"line_search"`

– solve the associated univariate optimization problem using a line-search method (either Brent or the Golden Section method)`"projection"`

– only valid for intersection with a hyperplane/line; evaluate the support function by reducing the problem to the 2D intersection of a rank-2 linear transformation of the given compact set in the plane generated by the given direction`d`

and the hyperplane's normal vector`n`

`"simple"`

– take the $\min$ of the support-function evaluation of each operand

**Output**

The scalar value of the support function of the set `cap`

in the given direction.

**Notes**

It is assumed that the first set of the intersection (`cap.X`

) is compact.

Any additional number of arguments to the algorithm backend can be passed as keyword arguments.

**Algorithm**

The algorithms are based on solving the associated optimization problem

\[\min_{λ ∈ D_h} ρ(ℓ - λa, X) + λb.\]

where $D_h = \{ λ : λ ≥ 0 \}$ if $H$ is a half-space or $D_h = \{ λ : λ ∈ ℝ \}$ if $H$ is a hyperplane.

For additional information we refer to:

[1] G. Frehse, R. Ray. *Flowpipe-Guard Intersection for Reachability Computations with Support Functions.* [2] C. Le Guernic. *Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics*, PhD thesis [3] T. Rockafellar, R. Wets. *Variational Analysis*.

```
ρ(d::AbstractVector, cap::Intersection{N, S1, S2};
kwargs...) where {N, S1<:LazySet{N}, S2<:AbstractPolyhedron{N}}
```

Return an upper bound on the support function of the intersection between a compact set and a polyhedron along a given direction.

**Input**

`d`

– direction`cap`

– intersection of a compact set and a polyhedron`kwargs`

– additional arguments that are passed to the support-function algorithm

**Output**

An upper bound of the support function of the given intersection.

**Algorithm**

The idea is to solve the univariate optimization problem `ρ(di, X ∩ Hi)`

for each half-space in the polyhedron and then take the minimum. This gives an overapproximation of the exact support value.

This algorithm is inspired from [1].

[1] G. Frehse, R. Ray. *Flowpipe-Guard Intersection for Reachability Computations with Support Functions*.

**Notes**

This method relies on the `constraints_list`

of the polyhedron.

```
ρ(d::AbstractVector, cap::Intersection{N, S1, S2}; kwargs...
) where {N, S1<:AbstractPolyhedron{N}, S2<:AbstractPolyhedron{N}}
```

Evaluate the support function of the intersection between two polyhedral sets.

**Input**

`d`

– direction`cap`

– intersection of two polyhedral sets`kwargs`

– additional arguments that are passed to the support-function algorithm

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

We combine the constraints of the two polyhedra to a new `HPolyhedron`

, for which we then evaluate the support function.

`ρ(d::AbstractVector, lm::LinearMap; kwargs...)`

Evaluate the support function of the linear map.

**Input**

`d`

– direction`lm`

– linear map`kwargs`

– additional arguments that are passed to the support function algorithm

**Output**

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

**Notes**

If $L = M⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $ρ(d, L) = ρ(M^T d, S)$ for any direction $d$.

`ρ(d::AbstractVector, ilm::InverseLinearMap)`

Evaluate the support function of the inverse linear map.

**Input**

`d`

– direction`ilm`

– inverse linear map

**Output**

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

**Notes**

If $L = M^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $ρ(d, L) = ρ((M^T)^{-1} d, X)$ for any direction $d$.

`ρ(d::AbstractVector, ms::MinkowskiSum)`

Evaluate the support function of a Minkowski sum of two sets.

**Input**

`d`

– direction`ms`

– Minkowski sum of two sets

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

The support function in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support functions of $X$ and $Y$ in direction $d$.

ρ(d::AbstractVector, msa::MinkowskiSumArray)

Evaluate the support function of a Minkowski sum of a finite number of sets in a given direction.

**Input**

`d`

– direction`msa`

– Minkowski sum of a finite number of sets

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

The support function of the Minkowski sum of multiple sets evaluations to the sum of the support-function evaluations of each set.

`ρ(d::AbstractVector, rm::ResetMap)`

Evaluate the support function of a reset map.

**Input**

`d`

– direction`rm`

– reset map

**Output**

The evaluation of the support function in the given direction.

**Notes**

We use the usual dot-product definition, but for unbounded sets we redefine the product between $0$ and $±∞$ as $0$; Julia returns `NaN`

here.

```
julia> Inf * 0.0
NaN
```

See the discussion here.

`ρ(d::AbstractVector, tr::Translation)`

Evaluate the support function of a translation.

**Input**

`d`

– direction`tr`

– translation of a set

**Output**

The evaluation of the support function in the given direction.

`ρ(d::AbstractVector, cup::UnionSet)`

Evaluate the support function of the union of two sets in a given direction.

**Input**

`d`

– direction`cup`

– union of two sets

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

The support function of the union of two sets $X$ and $Y$ evaluates to the maximum of the support-function evaluations of $X$ and $Y$.

ρ(d::AbstractVector, cup::UnionSetArray)

Evaluate the support function of the union of a finite number of sets in a given direction.

**Input**

`d`

– direction`cup`

– union of a finite number of sets

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

The support function of the union of a finite number of sets $X₁, X₂, ...$ can be obtained as the maximum of $ρ(d, X₂), ρ(d, X₂), ...$.

`ρ(d::AbstractVector, R::Rectification)`

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

**Input**

`d`

– direction`R`

– rectification

**Output**

The support value of the rectification in the given direction.

**Algorithm**

We use different procedures for different types of input sets. If the wrapped set has a suitable structure for which we can efficiently compute the support vector, we fall back to the evaluation of the support function by means of the support vector. Otherwise we compute the union of projections to obtain a precise result (see `to_union_of_projections`

), and then compute the support function for this union. (The union is cached internally, so subsequent queries are more efficient.)

`ρ(d::AbstractVector, X::Star)`

Evaluate the support function of a star.

**Input**

`d`

– direction`X`

– star

**Output**

The support function in the given direction.

`ρ(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**

A convenience alias `support_function`

is also available.

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

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

`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**

A convenience alias `support_vector`

is also available.

`LazySets.API.support_vector`

— Function`σ(d::AbstractVector, hs::HalfSpace)`

Return the support vector of a half-space in a given direction.

**Input**

`d`

– direction`hs`

– half-space

**Output**

The support vector in the given direction, which is only defined in the following two cases:

- The direction has norm zero.
- The direction is (a multiple of) the normal direction of the half-space.

In both cases the result is any point on the boundary (the defining hyperplane). Otherwise this function throws an error.

`σ(d::AbstractVector, Z::AbstractZonotope)`

Return a support vector of a zonotopic set in a given direction.

**Input**

`d`

– direction`Z`

– zonotopic set

**Output**

A support vector in the given direction. If the direction has norm zero, the vertex with $ξ_i = 1 \ \ ∀ i = 1,…, p$ is returned.

`σ(d::AbstractVector, H::AbstractHyperrectangle)`

Return a support vector of a hyperrectangular set in a given direction.

**Input**

`d`

– direction`H`

– hyperrectangular set

**Output**

A support vector in the given direction.

If the direction vector is zero in dimension $i$, the result will have the center's coordinate in that dimension. For instance, for the two-dimensional infinity-norm ball, if the direction points to the right, the result is the vector `[1, 0]`

in the middle of the right-hand facet.

If the direction has norm zero, the result can be any point in `H`

. The default implementation returns the center of `H`

.

`σ(d::AbstractVector, S::AbstractSingleton)`

Return the support vector of a set with a single value.

**Input**

`d`

– direction`S`

– set with a single value

**Output**

The support vector, which is the set's vector itself, irrespective of the given direction.

`σ(d::AbstractVector, am::AbstractAffineMap)`

Return a support vector of an affine map.

**Input**

`d`

– direction`am`

– affine map

**Output**

A support vector in the given direction.

`σ(d::AbstractVector, B::AbstractBallp)`

Return the support vector of a ball in the p-norm in a given direction.

**Input**

`d`

– direction`B`

– ball in the p-norm

**Output**

The support vector in the given direction. If the direction has norm zero, the center of the ball is returned.

**Algorithm**

The support vector of the unit ball in the $p$-norm along direction $d$ is:

\[σ(d, \mathcal{B}_p^n(0, 1)) = \dfrac{\tilde{v}}{‖\tilde{v}‖_q},\]

where $\tilde{v}_i = \frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $\tilde{v}_i = 0$ otherwise, for all $i=1,…,n$, and $q$ is the conjugate number of $p$. By the affine transformation $x = r\tilde{x} + c$, one obtains that the support vector of $\mathcal{B}_p^n(c, r)$ is

\[σ(d, \mathcal{B}_p^n(c, r)) = \dfrac{v}{‖v‖_q},\]

where $v_i = c_i + r\frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $v_i = 0$ otherwise, for all $i = 1, …, n$.

`σ(d::AbstractVector, B::Ball1)`

Return the support vector of a ball in the 1-norm in the given direction.

**Input**

`d`

– direction`B`

– ball in the 1-norm

**Output**

The support vector in the given direction.

`σ(d::AbstractVector, B::Ball2)`

Return the support vector of a 2-norm ball in the given direction.

**Input**

`d`

– direction`B`

– ball in the 2-norm

**Output**

The support vector in the given direction. If the direction has norm zero, the center is returned.

**Notes**

Let $c$ and $r$ be the center and radius of a ball $B$ in the 2-norm, respectively. For nonzero direction $d$ we have

\[σ(d, B) = c + r \frac{d}{‖d‖_2}.\]

This function requires computing the 2-norm of the input direction, which is performed in the given precision of the numeric datatype of both the direction and the set. Exact inputs are not supported.

`σ(d::AbstractVector, B::BallInf)`

Return the support vector of a ball in the infinity norm in the given direction.

**Input**

`d`

– direction`B`

– ball in the infinity norm

**Output**

The support vector in the given direction. If the direction has norm zero, the center of the ball is returned.

`σ(d::AbstractVector, E::Ellipsoid)`

Return the support vector of an ellipsoid in a given direction.

**Input**

`d`

– direction`E`

– ellipsoid

**Output**

The support vector in the given direction.

**Algorithm**

Let $E$ be an ellipsoid of center $c$ and shape matrix $Q = BB^\mathrm{T}$. Its support vector along direction $d$ can be deduced from that of the unit Euclidean ball $\mathcal{B}_2$ using the algebraic relations for the support vector,

\[σ_{B\mathcal{B}_2 ⊕ c}(d) = c + Bσ_{\mathcal{B}_2} (B^\mathrm{T} d) = c + \dfrac{Qd}{\sqrt{d^\mathrm{T}Q d}}.\]

`σ(d::AbstractVector, ∅::EmptySet)`

Return the support vector of an empty set.

**Input**

`d`

– direction`∅`

– empty set

**Output**

An error.

```
σ(d::AbstractVector, P::HPolygon;
[linear_search]::Bool=(length(P.constraints) < 10))
```

Return a support vector of a polygon in a given direction.

**Input**

`d`

– direction`P`

– polygon in constraint representation`linear_search`

– (optional, default: see below) flag for controlling whether to perform a linear search or a binary search

**Output**

The support vector in the given direction. The result is always one of the vertices; in particular, if the direction has norm zero, any vertex is returned.

**Algorithm**

Comparison of directions is performed using polar angles; see the definition of `⪯`

for two-dimensional vectors.

For polygons with 10 or more constraints we use a binary search by default.

```
σ(d::AbstractVector, P::HPolygonOpt;
[linear_search]::Bool=(length(P.constraints) < 10))
```

Return a support vector of an optimized polygon in a given direction.

**Input**

`d`

– direction`P`

– optimized polygon in constraint representation`linear_search`

– (optional, default: see below) flag for controlling whether to perform a linear search or a binary search

**Output**

The support vector in the given direction. The result is always one of the vertices; in particular, if the direction has norm zero, any vertex is returned.

**Algorithm**

Comparison of directions is performed using polar angles; see the definition of `⪯`

for two-dimensional vectors.

For polygons with 10 or more constraints we use a binary search by default.

```
σ(d::AbstractVector{M}, P::HPoly{N};
solver=default_lp_solver(M, N) where {M, N}
```

Return a support vector of a polyhedron in constraint representation in a given direction.

**Input**

`d`

– direction`P`

– polyhedron in constraint representation`solver`

– (optional, default:`default_lp_solver(M, N)`

) the backend used to solve the linear program

**Output**

The support vector in the given direction. If a polytope is unbounded in the given direction, we throw an error. If a polyhedron is unbounded in the given direction, the result contains `±Inf`

entries.

`σ(d::AbstractVector, H::Hyperplane)`

Return a support vector of a hyperplane.

**Input**

`d`

– direction`H`

– hyperplane

**Output**

A support vector in the given direction, which is only defined in the following two cases:

- The direction has norm zero.
- The direction is the hyperplane's normal direction or its opposite direction.

In all cases, any point on the hyperplane is a solution. Otherwise this function throws an error.

`σ(d::AbstractVector, x::Interval)`

Return the support vector of an interval in a given direction.

**Input**

`d`

– direction`x`

– interval

**Output**

The support vector in the given direction.

`σ(d::AbstractVector, L::Line2D)`

Return the support vector of a 2D line in a given direction.

**Input**

`d`

– direction`L`

– 2D line

**Output**

The support vector in the given direction, which is defined the same way as for the more general `Hyperplane`

.

`σ(d::AbstractVector, L::Line)`

Return a support vector of a line in a given direction.

**Input**

`d`

– direction`L`

– line

**Output**

A support vector in the given direction.

`σ(d::AbstractVector, L::LineSegment)`

Return the support vector of a 2D line segment in a given direction.

**Input**

`d`

– direction`L`

– 2D line segment

**Output**

The support vector in the given direction.

**Algorithm**

If the angle between the vector $q - p$ and $d$ is bigger than 90° and less than 270° (measured in counter-clockwise order), the result is $p$, otherwise it is $q$. If the angle is exactly 90° or 270°, or if the direction has norm zero, this implementation returns $q$.

`σ(d::AbstractVector, R::RotatedHyperrectangle)`

Return a support vector of a rotated hyperrectangle in a given direction.

**Input**

`d`

– direction`R`

– rotated hyperrectangle

**Output**

A support vector in the given direction.

`σ(d::AbstractVector, U::Universe)`

Return the support vector of a universe.

**Input**

`d`

– direction`U`

– universe

**Output**

A vector with infinity values, except in dimensions where the direction is zero.

`σ(d::AbstractVector, P::VPolygon)`

Return a support vector of a polygon in a given direction.

**Input**

`d`

– direction`P`

– polygon in vertex representation

**Output**

A support vector in the given direction. If the direction has norm zero, the first vertex is returned.

**Algorithm**

This implementation uses a binary search algorithm when the polygon has more than 10 vertices and a brute-force search when it has 10 or fewer vertices. The brute-force search compares the projection of each vector along the given direction and runs in $O(n)$ where $n$ is the number of vertices. The binary search runs in $O(log n)$ and we follow this implementation based on an algorithm described in [1].

[1] Joseph O'Rourke, *Computational Geometry in C (2nd Edition)*.

`σ(d::AbstractVector, P::VPolytope)`

Return a support vector of a polytope in vertex representation in a given direction.

**Input**

`d`

– direction`P`

– polytope in vertex representation

**Output**

A support vector in the given direction.

**Algorithm**

A support vector maximizes the support function. For a polytope, the support function is always maximized in some vertex. Hence it is sufficient to check all vertices.

`σ(d::AbstractVector, P::VPolytope)`

Return a support vector of a tetrahedron in a given direction.

**Input**

`d`

– direction`P`

– tetrahedron

**Output**

A support vector in the given direction.

**Algorithm**

Currently falls back to the `VPolytope`

implementation.

`σ(d::AbstractVector, B::Bloating)`

Return the support vector of a bloated set in a given direction.

**Input**

`d`

– direction`B`

– bloated set

**Output**

The support vector of the bloated set in the given direction.

`σ(d::AbstractVector, cp::CartesianProduct)`

Return a support vector of a Cartesian product.

**Input**

`d`

– direction`cp`

– Cartesian product

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

`σ(d::AbstractVector, cpa::CartesianProductArray)`

Compute a support vector of a Cartesian product of a finite number of sets.

**Input**

`d`

– direction`cpa`

– Cartesian product of a finite number of sets

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the product sets.

`σ(d::AbstractVector, ch::ConvexHull)`

Return a support vector of the convex hull of two sets in a given direction.

**Input**

`d`

– direction`ch`

– convex hull of two sets

**Output**

A support vector of the convex hull in the given direction.

`σ(d::AbstractVector, cha::ConvexHullArray)`

Return a support vector of a convex hull of a finite number of sets in a given direction.

**Input**

`d`

– direction`cha`

– convex hull of a finite number of sets

**Output**

A support vector in the given direction.

```
σ(d::AbstractVector, em::ExponentialMap;
[backend]=get_exponential_backend())
```

Return a support vector of an exponential map.

**Input**

`d`

– direction`em`

– exponential map`backend`

– (optional; default:`get_exponential_backend()`

) exponentiation backend

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

**Notes**

If $E = \exp(M)⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $σ(d, E) = \exp(M)⋅σ(\exp(M)^T d, X)$ for any direction $d$.

```
σ(d::AbstractVector, eprojmap::ExponentialProjectionMap;
[backend]=get_exponential_backend())
```

Return a support vector of a projection of an exponential map.

**Input**

`d`

– direction`eprojmap`

– projection of an exponential map`backend`

– (optional; default:`get_exponential_backend()`

) exponentiation backend

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

**Notes**

If $S = (L⋅M⋅R)⋅X$, where $L$ and $R$ are matrices, $M$ is a matrix exponential, and $X$ is a set, it follows that $σ(d, S) = L⋅M⋅R⋅σ(R^T⋅M^T⋅L^T⋅d, X)$ for any direction $d$.

`σ(d::AbstractVector, cap::Intersection)`

Return a support vector of an intersection of two sets in a given direction.

**Input**

`d`

– direction`cap`

– intersection of two sets

**Output**

A support vector in the given direction.

**Algorithm**

We compute the concrete intersection, which may be expensive.

`σ(d::AbstractVector, ia::IntersectionArray)`

Return a support vector of an intersection of a finite number of sets in a given direction.

**Input**

`d`

– direction`ia`

– intersection of a finite number of sets

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the individual sets.

**Algorithm**

This implementation computes the concrete intersection, which can be expensive.

`σ(d::AbstractVector, lm::LinearMap)`

Return a support vector of the linear map.

**Input**

`d`

– direction`lm`

– linear map

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

**Notes**

If $L = M⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $σ(d, L) = M⋅σ(M^T d, S)$ for any direction $d$.

`σ(d::AbstractVector, ilm::InverseLinearMap)`

Return a support vector of a inverse linear map.

**Input**

`d`

– direction`ilm`

– inverse linear map

**Output**

**Notes**

If $L = M^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, since (M^T)^{-1}=(M^{-1})^T, it follows that $σ(d, L) = M^{-1}⋅σ((M^T)^{-1} d, X)$ for any direction $d$.

`σ(d::AbstractVector, ms::MinkowskiSum)`

Return a support vector of a Minkowski sum of two sets.

**Input**

`d`

– direction`ms`

– Minkowski sum of two sets

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

**Algorithm**

A valid support vector in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support vectors of $X$ and $Y$ in direction $d$.

σ(d::AbstractVector, msa::MinkowskiSumArray)

Return a support vector of a Minkowski sum of a finite number of sets in a given direction.

**Input**

`d`

– direction`msa`

– Minkowski sum of a finite number of sets

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

`σ(d::AbstractVector, cms::CachedMinkowskiSumArray)`

Return a support vector of a cached Minkowski sum in a given direction.

**Input**

`d`

– direction`cms`

– cached Minkowski sum

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

**Notes**

The result is cached, i.e., any further query with the same direction runs in constant time. When sets are added to the cached Minkowski sum, the query is only performed for the new sets.

`σ(d::AbstractVector, rm::ResetMap)`

Return a support vector of a reset map.

**Input**

`d`

– direction`rm`

– reset map

**Output**

`σ(d::AbstractVector, sih::SymmetricIntervalHull)`

Return a support vector of the symmetric interval hull of a set in a given direction.

**Input**

`d`

– direction`sih`

– symmetric interval hull of a set

**Output**

A support vector of the symmetric interval hull of a set in the given direction. If the direction has norm zero, the origin is returned.

**Algorithm**

For each non-zero entry in `d`

we need to either look up the bound (if it has been computed before) or compute it, in which case we store it for future queries.

`σ(d::AbstractVector, tr::Translation)`

Return a support vector of a translation.

**Input**

`d`

– direction`tr`

– translation of a set

**Output**

`σ(d::AbstractVector, cup::UnionSet; [algorithm]="support_vector")`

Return a support vector of the union of two sets in a given direction.

**Input**

`d`

– direction`cup`

– union of two sets`algorithm`

– (optional, default: "support*vector"): the algorithm to compute the support vector; if "support*vector", use the support vector of each argument; if "support_function" use the support function of each argument and evaluate the support vector of only one of them

**Output**

A support vector in the given direction.

**Algorithm**

The support vector of the union of two sets $X$ and $Y$ can be obtained as the vector that maximizes the support function of either $X$ or $Y$, i.e., it is sufficient to find the $\argmax(ρ(d, X), ρ(d, Y)])$ and evaluate its support vector.

The default implementation, with option `algorithm="support_vector"`

, computes the support vector of $X$ and $Y$ and then compares the support function using a dot product.

If the support function can be computed more efficiently, the alternative implementation `algorithm="support_function"`

can be used, which evaluates the support function of each set directly and then calls only the support vector of either $X$ *or* $Y$.

σ(d::AbstractVector, cup::UnionSetArray; [algorithm]="support_vector")

Return a support vector of the union of a finite number of sets in a given direction.

**Input**

`d`

– direction`cup`

– union of a finite number of sets`algorithm`

– (optional, default: "support*vector"): the algorithm to compute the support vector; if "support*vector", use the support vector of each argument; if "support_function", use the support function of each argument and evaluate the support vector of only one of them

**Output**

A support vector in the given direction.

**Algorithm**

The support vector of the union of a finite number of sets $X₁, X₂, ...$ can be obtained as the vector that maximizes the support function, i.e., it is sufficient to find the $\argmax([ρ(d, X₂), ρ(d, X₂), ...])$ and evaluate its support vector.

The default implementation, with option `algorithm="support_vector"`

, computes the support vector of all $X₁, X₂, ...$ and then compares the support function using the dot product.

If the support function can be computed more efficiently, the alternative implementation `algorithm="support_function"`

can be used, which evaluates the support function of each set directly and then calls only the support vector of one of the $Xᵢ$.

`σ(d::AbstractVector, R::Rectification)`

Return a support vector of a rectification.

**Input**

`d`

– direction`R`

– rectification

**Output**

```
σ(d::AbstractVector,
R::Rectification{N, <:AbstractHyperrectangle{N}}) where {N}
```

Return a support vector of the rectification of a hyperrectangular set.

**Input**

`d`

– direction`R`

– rectification of a hyperrectangular set

**Output**

A support vector in the given direction.

**Algorithm**

Let $R(·)$ be the rectification of a vector respectively a set, and let $H$ be a hyperrectangle. Then $σ_{R(H)}(d) = R(σ_{H}(d))$.

`σ(d::AbstractVector, R::Rectification{N, <:CartesianProduct{N}}) where {N}`

Return a support vector of the rectification of a Cartesian product of two sets.

**Input**

`d`

– direction`R`

– rectification of a Cartesian product of two sets

**Output**

A support vector in the given direction.

**Notes**

Note that this implementation creates new `Rectification`

objects that do not get preserved. Hence a second support-vector query does not benefit from the computations in the first query. For this use case another implementation should be added.

**Algorithm**

Rectification distributes with the Cartesian product. Let $R(·)$ be the rectification of a set. We can just query a support vector for $R(X)$ and $R(Y)$ recursively: $σ_{R(X × Y)}(d) = σ_{R(X)}(d_X) × σ_{R(Y)}(d_Y)$, where $x × y$ concatenates vectors $x$ and $y$.

```
σ(d::AbstractVector,
R::Rectification{N, <:CartesianProductArray{N}}) where {N}
```

Return a support vector of the rectification of a Cartesian product of a finite number of sets.

**Input**

`d`

– direction`R`

– rectification of a Cartesian product of a finite number of sets

**Output**

A support vector in the given direction.

**Notes**

Note that this implementation creates new `Rectification`

objects that do not get preserved. Hence a second support-vector query does not benefit from the computations in the first query. For this use case another implementation should be added.

**Algorithm**

Rectification distributes with the Cartesian product. Let $R(·)$ be the rectification of a set. We can just query a support vector for each subspace recursively: $σ_{R(X_1 × ⋯ × X_m)}(d) = σ_{R(X_1)}(d_{X_1}) × ⋯ × σ_{R(X_m)}(d_{X_m})$, where $x × y$ concatenates vectors $x$ and $y$.

`σ(d::AbstractVector, X::Star)`

Return a support vector of a star.

**Input**

`d`

– direction`X`

– star

**Output**

A support vector in the given direction.

`σ(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**

A convenience alias `support_vector`

is also available.

`LazySets.API.translate`

— Method`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\}$.

`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\}$.

# Binary set functions

`LazySets.API.cartesian_product`

— Method`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\}.\]

`LazySets.API.difference`

— Method`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 \}\]

`ReachabilityBase.Arrays.distance`

— Method`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 otherwise the $p$-norm of the shortest line segment between any pair of points. Formally,

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

`LazySets.API.exact_sum`

— Method`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 $X ⊞ Y$.

**Notes**

The convenience alias `⊞`

is also available, which can be typed by `\boxplus<tab>`

.

`LazySets.API.:⊞`

— Function`⊞(X::LazySet, Y::LazySet)`

Convenience alias for the (concrete) `exact_sum`

function.

**Notes**

"`⊞`

" can be typed by `\boxplus<tab>`

.

`LazySets.API.intersection`

— Method`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\}.\]

`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.

The convenience alias `isapprox`

is also available.

"`≈`

" can be typed by `\approx<tab>`

.

`Base.isdisjoint`

— Method`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.

`LazySets.API.is_intersection_empty`

— Function`is_intersection_empty(X::LazySet, Y::LazySet, [witness]::Bool=false)`

Convenience alias for the `isdisjoint`

function.

`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.

`LazySets.API.isequivalent`

— Method`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).

`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`

:

`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.

`LazySets.API.linear_combination`

— Method`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\}.\]

`LazySets.API.minkowski_difference`

— Method`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 = \{x \mid x + y ∈ X ~∀~y ∈ Y\}\]

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.

`LazySets.API.pontryagin_difference`

— Function`pontryagin_difference(X::LazySet, Y::LazySet)`

Convenience alias for the `minkowski_difference`

function.

`LazySets.API.minkowski_sum`

— Method`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\}.\]