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

center(B::Ball1)

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.

constraints_list(P::Ball1)

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

Input

• B – ball in the 1-norm

Output

The list of constraints of the ball.

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(::Type{Ball1}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing
    )

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.

reflect(B::Ball1)

Concrete reflection of a ball in the 1-norm B, resulting in the reflected set -B.

Input

• B – ball in the 1-norm

Output

The Ball1 representing -B.

Algorithm

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

vertices_list(B::Ball1)

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.

Notes

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

∈(x::AbstractVector, B::Ball1, [failfast]::Bool=false)

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

Input

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

Output

true iff $x ∈ B$.

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

Evaluate the support function of a ball in the 1-norm in the given direction.

Input

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

Output

Evaluation of the support function in the given direction.

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

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

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

Input

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

Output

The support vector in the given direction.

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

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

Input

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

Output

The in-place translated ball in the 1-norm.

Algorithm

We add the vector to the center of the ball.

Notes

See also translate(::Ball1, ::AbstractVector) for the out-of-place version.