Symmetric interval hull (SymmetricIntervalHull)

SymmetricIntervalHull{N, S<:LazySet{N}} <: AbstractHyperrectangle{N}

Type that represents the symmetric interval hull of a compact set.

Fields

• X – compact set
• cache – partial storage of already computed bounds, organized as mapping from dimension to tuples (bound, valid), where valid is a flag indicating if the bound entry has been computed

Notes

The symmetric interval hull can be computed with $2n$ support vector queries of unit vectors, where $n$ is the dimension of the wrapped set (i.e., two queries per dimension). When asking for the support vector for a direction $d$, one needs $2k$ such queries, where $k$ is the number of non-zero entries in $d$.

However, if one asks for many support vectors in a loop, the number of computations may exceed $2n$. To be most efficient in such cases, this type stores the intermediately computed bounds in the cache field.

The set X must be compact.

The result is a hyperrectangle and hence in particular convex.

dim(sih::SymmetricIntervalHull)

Return the dimension of the symmetric interval hull of a set.

Input

• sih – symmetric interval hull of a set

Output

The ambient dimension of the symmetric interval hull of a set.

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

Return the 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

The 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. One such computation just asks for the support vector of the underlying set for both the positive and negative unit vector in the respective dimension.

center(sih::SymmetricIntervalHull{N}, i::Int) where {N}

Return the center along a given dimension of the symmetric interval hull of a set.

Input

• sih – symmetric interval hull of a set
• i – dimension of interest

Output

The center along a given dimension of the symmetric interval hull of a set.

center(sih::SymmetricIntervalHull{N}) where {N}

Return the center of the symmetric interval hull of a set.

Input

• sih – symmetric interval hull of a set

Output

The origin.

radius_hyperrectangle(sih::SymmetricIntervalHull)

Return the box radius of the symmetric interval hull of a set in every dimension.

Input

• sih – symmetric interval hull of a set

Output

The box radius of the symmetric interval hull of a set.

Notes

This function computes the symmetric interval hull explicitly.

radius_hyperrectangle(sih::SymmetricIntervalHull, i::Int)

Return the box radius of the symmetric interval hull of a set in a given dimension.

Input

• sih – symmetric interval hull of a set
• i – dimension of interest

Output

The radius in the given dimension. If it was computed before, this is just a look-up, otherwise it requires two support vector computations.