Manhattan-norm ball (Ball1)

LazySets.Ball1 — Type

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 ∈ \mathbb{R}^n : ∑_{i=1}^n |c_i - x_i| ≤ r \},\]

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

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

LazySets.center — Method

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.σ — 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.ρ — 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

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.vertices_list — Method

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.rand — Method

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.constraints_list — Method

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

LazySets.translate — Method