Infinity-norm ball (BallInf)

BallInf{N, VN<:AbstractVector{N}} <: AbstractHyperrectangle{N}

Type that represents a ball in the infinity norm.

Fields

• center – center of the ball as a real vector
• radius – radius of the ball as a real scalar ($≥ 0$)

Notes

Mathematically, a ball in the infinity norm is defined as the set

\[\mathcal{B}_∞^n(c, r) = \{ x ∈ ℝ^n : ‖ x - c ‖_∞ ≤ r \},\]

where $c ∈ ℝ^n$ is its center and $r ∈ ℝ_+$ its radius. Here $‖ ⋅ ‖_∞$ denotes the infinity norm, defined as $‖ x ‖_∞ = \max\limits_{i=1,…,n} \vert x_i \vert$ for any $x ∈ ℝ^n$.

Examples

Construct the two-dimensional unit ball and compute its support function along the positive $x=y$ direction:

julia> B = BallInf(zeros(2), 1.0)
BallInf{Float64, Vector{Float64}}([0.0, 0.0], 1.0)

julia> dim(B)
2

julia> ρ([1.0, 1.0], B)
2.0

isflat(B::BallInf)

Determine whether a ball in the infinity norm is flat, i.e., whether its radius is zero.

Input

• B – ball in the infinity norm

Output

true iff the ball is flat.

Notes

For robustness with respect to floating-point inputs, this function relies on the result of isapproxzero applied to the radius of the ball. Hence, this function depends on the absolute zero tolerance ABSZTOL.

ngens(B::BallInf)

Return the number of generators of a ball in the infinity norm.

Input

• B – ball in the infinity norm

Output

The number of generators.

Algorithm

A ball in the infinity norm has either one generator for each dimension, or zero generators if it is a degenerated ball of radius zero.

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.

Extended help

radius(B::BallInf, [p]::Real=Inf)

Notes

The result is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center.

radius_hyperrectangle(B::BallInf)

Return the box radius of a ball in the infinity norm.

Input

• B – ball in the infinity norm

Output

The box radius of the ball in the infinity norm, which is the same in every dimension.

radius_hyperrectangle(B::BallInf, i::Int)

Return the box radius of a ball in the infinity norm in a given dimension.

Input

• B – ball in the infinity norm
• i – dimension of interest

Output

The box radius of the ball in the infinity norm in the given dimension.

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.

Extended help

rand(::Type{BallInf}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1. Additionally, the radius is nonnegative.

reflect(X::LazySet)

Compute the reflection of a set in the origin.

Input

• X – set

Output

A set representing the reflection $-X$.

Extended help

reflect(B::BallInf)

Algorithm

If $B$ has center $c$ and radius $r$, then $-B$ has center $-c$ and radius $r$.

volume(X::LazySet)

Compute the volume of a set.

Input

• X – set

Output

A real number representing the volume of X.

Extended help

volume(B::BallInf)

Algorithm

We compute the volume by iterative multiplication of the radius.

For floating-point inputs we use this implementation for balls of dimension less than $50$. For balls of higher dimension we instead compute $exp(n * log(2r))$, where $r$ is the radius of the ball.

ρ(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)\]

Extended help

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

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.

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

Extended help

translate!(B::BallInf, v::AbstractVector)

Algorithm

We add the vector to the center of the ball.