GitHub

Balls in the p-norm (AbstractBallp)

A ball is a centrally-symmetric set with a characteristic p-norm.

LazySets.AbstractBallp — Type
AbstractBallp{N} <: AbstractCentrallySymmetric{N}

Abstract type for p-norm balls.

Notes

See Ballp for a standard implementation of this interface.

Every concrete AbstractBallp must define the following methods:

  • ball_norm(::AbstractBallp) – return the characteristic norm
  • radius_ball(::AbstractBallp) – return the ball radius

The subtypes of AbstractBallp:

julia> subtypes(AbstractBallp)
2-element Vector{Any}:
 Ball2
 Ballp

There are two further set types implementing the AbstractBallp interface, but they also implement other interfaces and hence cannot be subtypes: Ball1 and BallInf.

source

This interface requires to implement the following functions:

LazySets.ball_norm — Method
ball_norm(B::AbstractBallp)

Determine the norm (p) of a p-norm ball.

Input

  • B – p-norm ball

Output

A number representing the norm.

source
LazySets.radius_ball — Method
radius_ball(B::AbstractBallp)

Compute the radius of a p-norm ball.

Input

  • B – p-norm ball

Output

A number representing the radius.

source

This interface defines the following functions:

Base.:∈ — Method
∈(x::AbstractVector, B::AbstractBallp)

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

Input

  • x – point/vector
  • B – ball in the p-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 p-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 $\left( ∑_{i=1}^n |c_i - x_i|^p \right)^{1/p} ≤ r$.

Examples

julia> B = Ballp(1.5, [1.0, 1.0], 1.)
Ballp{Float64, Vector{Float64}}(1.5, [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::AbstractBallp)

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

Input

  • d – direction
  • B – ball in the p-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 p-norm, respectively, and let $q = \frac{p}{p-1}$. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_q.\]

source
LazySets.API.σ — Method
σ(d::AbstractVector, B::AbstractBallp)

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

Input

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

Output

The support vector in the given direction. If the direction has norm zero, the center of the ball is returned.

Algorithm

The support vector of the unit ball in the $p$-norm along direction $d$ is:

\[σ(d, \mathcal{B}_p^n(0, 1)) = \dfrac{\tilde{v}}{‖\tilde{v}‖_q},\]

where $\tilde{v}_i = \frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $\tilde{v}_i = 0$ otherwise, for all $i=1,…,n$, and $q$ is the conjugate number of $p$. By the affine transformation $x = r\tilde{x} + c$, one obtains that the support vector of $\mathcal{B}_p^n(c, r)$ is

\[σ(d, \mathcal{B}_p^n(c, r)) = \dfrac{v}{‖v‖_q},\]

where $v_i = c_i + r\frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $v_i = 0$ otherwise, for all $i = 1, …, n$.

source

Implementations