Manhattan-norm ball (Ball1)

LazySets.Ball1Module.Ball1Type
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
source

Operations

LazySets.API.centerMethod
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.

source
LazySets.API.constraints_listMethod
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.

source
Base.randMethod
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.

source
LazySets.API.reflectMethod
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$.

source
LazySets.API.vertices_listMethod
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).

source
Base.:∈Function
∈(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
source
LazySets.API.ρMethod
ρ(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‖_∞.\]

source
LazySets.API.σMethod
σ(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.

source
LazySets.API.translate!Method
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.

source

Undocumented implementations:

Inherited from LazySet:

Inherited from AbstractPolyhedron:

Inherited from AbstractPolytope:

Inherited from AbstractCentrallySymmetricPolytope: