Euclidean-norm ball (Ball2)

Ball2{N<:AbstractFloat, VN<:AbstractVector{N}} <: AbstractBallp{N}

Type that represents a ball in the 2-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 2-norm is defined as the set

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

where $c ∈ ℝ^n$ is its center and $r ∈ ℝ_+$ its radius. Here $‖ ⋅ ‖_2$ denotes the Euclidean norm (also known as 2-norm), defined as $‖ x ‖_2 = \left( ∑\limits_{i=1}^n |x_i|^2 \right)^{1/2}$ for any $x ∈ ℝ^n$.

Examples

Create a five-dimensional ball B in the 2-norm centered at the origin with radius 0.5:

julia> B = Ball2(zeros(5), 0.5)
Ball2{Float64, Vector{Float64}}([0.0, 0.0, 0.0, 0.0, 0.0], 0.5)

julia> dim(B)
5

Evaluate B's support vector in the direction $[1,2,3,4,5]$:

julia> σ([1.0, 2, 3, 4, 5], B)
5-element Vector{Float64}:
 0.06741998624632421
 0.13483997249264842
 0.20225995873897262
 0.26967994498529685
 0.3370999312316211

chebyshev_center_radius(B::Ball2; [kwargs]...)

Compute a Chebyshev center and the corresponding radius of a ball in the 2-norm.

Input

• B – ball in the 2-norm
• kwargs – further keyword arguments (ignored)

Output

The pair (c, r) where c is the Chebyshev center of B and r is the radius of the largest Euclidean ball with center c enclosed by B.

Notes

The Chebyshev center of a ball in the 2-norm is just the center of the ball.

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{Ball2}; [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::Ball2)

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::Ball2)

Algorithm

This method implements the well-known formula for the volume of an n-dimensional ball using factorials. For details, see the Wikipedia article Volume of an n-ball.

∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

∈(x::AbstractVector, B::Ball2)

Notes

This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.

Algorithm

Let $B$ be an $n$-dimensional ball in the 2-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $\left( ∑_{i=1}^n |c_i - x_i|^2 \right)^{1/2} ≤ r$.

Examples

julia> B = Ball2([1., 1.], sqrt(0.5))
Ball2{Float64, Vector{Float64}}([1.0, 1.0], 0.7071067811865476)

julia> [.5, 1.6] ∈ B
false

julia> [.5, 1.5] ∈ B
true

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.

Extended help

sample(B::Ball2, [nsamples]::Int;
       [rng]::AbstractRNG=GLOBAL_RNG,
       [seed]::Union{Int, Nothing}=nothing)

Algorithm

Random sampling with uniform distribution in B is computed using Muller's method of normalized Gaussians. This method requires the package Distributions. See _sample_unit_nball_muller! for implementation details.

ρ(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::Ball2)

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

Extended help

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

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.

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::Ball2, v::AbstractVector)

Translate (i.e., shift) a ball in the 2-norm by the given vector, in-place.

Algorithm

We add the vector to the center of the ball.

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.

Extended help

isdisjoint(B1::Ball2, B2::Ball2, [witness]::Bool=false)

Algorithm

$B1 ∩ B2 = ∅$ iff $‖ c_2 - c_1 ‖_2 > r_1 + r_2$.

A witness is computed depending on the smaller/bigger ball (to break ties, choose B1 for the smaller ball) as follows.

• If the smaller ball's center is contained in the bigger ball, we return it.
• Otherwise start in the smaller ball's center and move toward the other center until hitting the smaller ball's border. In other words, the witness is the point in the smaller ball that is closest to the center of the bigger ball.

⊆(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.

Extended help

⊆(B1::Ball2, B2::Ball2, [witness]::Bool=false)

Algorithm

$B1 ⊆ B2$ iff $‖ c_1 - c_2 ‖_2 + r_1 ≤ r_2$

_sample_unit_nball_muller!(D::Vector{<:Vector}, n::Int, p::Int;
                           [rng]::AbstractRNG=GLOBAL_RNG,
                           [seed]::Union{Int, Nothing}=nothing)

Draw samples from a uniform distribution on an $n$-dimensional unit ball using Muller's method.

Input

• D – output, vector of points
• n – dimension of the ball
• p – number of random samples
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

The modified vector D.

Algorithm

This function implements Muller's method of normalized Gaussians [1] to uniformly sample from the interior of the unit ball.

Given $n$ Gaussian random variables $Z₁, Z₂, …, Z_n$ and a uniformly distributed random variable $r$ with support in $[0, 1]$, the distribution of the vectors

\[\dfrac{r^{1/n}}{α} \left(z₁, z₂, …, z_n\right)^T,\]

where $α := \sqrt{z₁² + z₂² + … + z_n²}$, is uniform over the $n$-dimensional unit ball.

[1] Muller, Mervin E. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM 2.4 (1959): 19-20.