Box Approximation

box_approximation(S::LazySet{N}) where {N}

Overapproximate a set by a tight hyperrectangle.

Input

• S – set

Output

A tight hyperrectangle.

Notes

An alias for this function is interval_hull.

Algorithm

The center and radius of the hyperrectangle are obtained by averaging the low and high coordinates of S computed with the extrema function.

box_approximation(S::CartesianProductArray{N, <:AbstractHyperrectangle}) where {N}

Overapproximate the Cartesian product of a finite number of hyperrectangular sets by a tight hyperrectangle.

Input

• S– Cartesian product of a finite number of hyperrectangular sets

Output

A hyperrectangle.

Algorithm

This method falls back to the convert method. Since the sets wrapped by the Cartesian product array are hyperrectangles, this can be done without overapproximation.

box_approximation(S::CartesianProduct{N, <:AbstractHyperrectangle, <:AbstractHyperrectangle}) where {N}

Overapproximate the Cartesian product of two hyperrectangular sets by a tight hyperrectangle.

Input

• S– Cartesian product of two hyperrectangular sets

Output

A hyperrectangle.

Algorithm

This method falls back to the convert method. Since the sets wrapped by the Cartesian product array are hyperrectangles, this can be done without overapproximation.

box_approximation(lm::LinearMap{N, <:AbstractHyperrectangle}) where {N}

Return a tight overapproximation of the linear map of a hyperrectangular set using a hyperrectangle.

Input

• lm– linear map of a hyperrectangular set

Output

A hyperrectangle.

Algorithm

If c and r denote the center and vector radius of a hyperrectangle H, a tight hyperrectangular overapproximation of M * H is obtained by transforming c ↦ M*c and r ↦ abs.(M) * r, where abs.(⋅) denotes the element-wise absolute-value operator.

box_approximation(R::Rectification{N}) where {N}

Overapproximate the rectification of a set by a tight hyperrectangle.

Input

• R– rectification of a set

Output

A hyperrectangle.

Algorithm

Box approximation and rectification distribute. We first check whether the wrapped set is empty. If so, we return the empty set. Otherwise, we compute the box approximation of the wrapped set, rectify the resulting box (which is simple), and finally convert the resulting set to a box.

box_approximation(Z::AbstractZonotope)

Return a tight overapproximation of a zonotope with an axis-aligned box.

Input

• Z – zonotope

Output

A hyperrectangle.

Algorithm

This function implements the method in [Section 5.1.2, 1]. A zonotope $Z = ⟨c, G⟩$ can be tightly overapproximated by an axis-aligned hyperrectangle such that its center is $c$ and the radius along dimension $i$ is the column-sum of the absolute values of the $i$-th row of $G$ for $i = 1,…, p$, where $p$ is the number of generators of $Z$.

[1] Althoff, M., Stursberg, O., & Buss, M. (2010). Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes. Nonlinear analysis: hybrid systems, 4(2), 233-249.

box_approximation(am::AbstractAffineMap{N, <:AbstractHyperrectangle}) where {N}

Overapproximate the affine map of a hyperrectangular set by a tight hyperrectangle.

Input

• am – affine map of a hyperrectangular set

Output

A hyperrectangle.

Algorithm

If c and r denote the center and vector radius of a hyperrectangle H and v is the translation vector, a tight hyperrectangular overapproximation of M * H + v is obtained by transforming c ↦ M*c+v and r ↦ abs.(M) * r, where abs.(⋅) denotes the element-wise absolute-value operator.

box_approximation(ch::ConvexHull; [algorithm]::String="box")

Overapproximate a convex hull with a tight hyperrectangle.

Input

• ch – convex hull
• algorithm – (optional; default: "box") algorithm choice

Output

A hyperrectangle.

Algorithm

Let X and Y be the two sets of ch. We make use of the following property:

\[□(CH(X, Y)) = □\left( X ∪ Y \right) = □\left( □(X) ∪ □(Y) \right)\]

If algorithm == "extrema", we compute the low and high coordinates of X and Y via extrema.

If algorithm == "box", we instead compute the box approximations of X and Y via box_approximation.

In both cases we then take the box approximation of the result.

The "extrema" algorithm is more efficient if extrema is efficient because it does not need to allocate the intermediate hyperrectangles.

box_approximation(ms::MinkowskiSum)

Overapproximate the Minkowski sum of two sets with a tight hyperrectangle.

Input

• ms – Minkowski sum

Output

A hyperrectangle.

Algorithm

The box approximation distributes over the Minkowski sum:

\[□(X ⊕ Y) = □(X) ⊕ □(Y)\]

It suffices to compute the box approximation of each summand and then take the concrete Minkowski sum for hyperrectangles.

interval_hull

Alias for box_approximation.

□(X::LazySet)

Alias for box_approximation(X).

symmetric_interval_hull(S::LazySet{N}) where {N}

Overapproximate a set by a tight hyperrectangle centered in the origin.

Input

• S – set

Output

A tight hyperrectangle that is centrally symmetric wrt. the origin.

Notes

An alias for this function is box_approximation_symmetric.

Algorithm

The center of the box is the origin, and the radius is obtained via the extrema function.

box_approximation_symmetric

Alias for symmetric_interval_hull.

ballinf_approximation(S::LazySet)

Overapproximate a set by a tight ball in the infinity norm.

Input

• S – set

Output

A tight ball in the infinity norm.

Algorithm

The center and radius of the ball are obtained by averaging the low and high coordinates of S computed with the extrema function.