Manhattan-norm ball (Ball1)

Ball1{N<:Real} <: 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

where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius.

Fields

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

Examples

Unit ball in the 1-norm in the plane:

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

We evaluate the support vector in the East direction:

julia> σ([0.,1], B)
2-element Array{Float64,1}:
 0.0
 1.0

σ(d::AbstractVector{N}, B::Ball1{N}) where {N<:Real}

Return the support vector of a ball in the 1-norm in a given direction.

Input

• d – direction
• B – ball in the 1-norm

Output

Support vector in the given direction.

∈(x::AbstractVector{N}, B::Ball1{N})::Bool where {N<:Real}

Check whether a given point is contained in a ball in the 1-norm.

Input

• x – point/vector
• B – ball in the 1-norm

Output

true iff $x ∈ B$.

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 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., 1.], 1.);

julia> [.5, -.5] ∈ B
false
julia> [.5, 1.5] ∈ B
true

vertices_list(B::Ball1{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

A list containing the vertices of the ball in the 1-norm.

center(B::Ball1{N})::Vector{N} where {N<:Real}

Return the center of a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

The center of the ball in the 1-norm.

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

Create a random ball in the 1-norm.

Input

• Ball1 – type for dispatch
• 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 ball in the 1-norm.

Algorithm

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

constraints_list(P::Ball1{N}) where {N<:Real}

Return the list of constraints defining a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

The list of constraints of the ball.

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.

translate(B::Ball1{N}, v::AbstractVector{N}) where {N<:Real}

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

Input

• B – ball in the 1-norm
• v – translation vector

Output

A translated ball in the 1-norm.

Algorithm

We add the vector to the center of the ball.