Manhattan-norm ball (Ball1)

Ball1{N, VN<:AbstractVector{N}} <: AbstractCentrallySymmetricPolytope{N}

Type that represents a ball in the 1-norm (also known as the Manhattan norm). The ball is also known as a cross-polytope.

It is defined as the set

\[\mathcal{B}_1^n(c, r) = \{ x ∈ ℝ^n : ∑_{i=1}^n |c_i - x_i| ≤ r \},\]

where $c ∈ ℝ^n$ is its center and $r ∈ ℝ_+$ its radius.

Fields

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

Examples

The unit ball in the 1-norm in the plane:

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

We evaluate the support vector in the North direction:

julia> σ([0.0, 1.0], B)
2-element Vector{Float64}:
 0.0
 1.0

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.

Extended help

constraints_list(P::Ball1)

Notes

In $n$ dimensions there are $2^n$ constraints (unless the radius is 0).

Algorithm

The constraints can be defined as $d_i^T (x-c) ≤ r$ for all $d_i$, where $d_i$ is a vector with elements $1$ or $-1$ in $n$ dimensions. To span all possible $d_i$, the function Iterators.product is used.

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

Algorithm

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

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.

Extended help

vertices_list(B::Ball1)

Notes

In $n$ dimensions there are $2n$ vertices (unless the radius is 0).

∈(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::Ball1, [failfast]::Bool=false)

Input

• x – point/vector
• B – ball in the 1-norm
• failfast – (optional, default: false) optimization for negative answer

Notes

The default behavior (failfast == false) is worst-case optimized, i.e., the implementation 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, the option failfast == true terminates faster.

Algorithm

Let $B$ be an $n$-dimensional ball in the 1-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 $∑_{i=1}^n |c_i - x_i| ≤ r$.

Examples

julia> B = Ball1([1.0, 1.0], 1.0);

julia> [0.5, -0.5] ∈ B
false
julia> [0.5, 1.5] ∈ B
true

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

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‖_∞.\]

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

Algorithm

We add the vector to the center of the ball.