Balls in the p-norm (AbstractBallp)
A ball is a centrally-symmetric set with a characteristic p-norm.
LazySets.AbstractBallp
— TypeAbstractBallp{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:
center(::AbstractBallp)
– return the centerradius_ball(::AbstractBallp)
– return the ball radiusball_norm(::AbstractBallp)
– return the characteristic norm
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
.
This interface defines the following functions:
LazySets.σ
— Methodσ(d::AbstractVector, B::AbstractBallp)
Return the support vector of a ball in the p-norm in a given direction.
Input
d
– directionB
– 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$.
LazySets.ρ
— Methodρ(d::AbstractVector, B::AbstractBallp)
Evaluate the support function of a ball in the p-norm in the given direction.
Input
d
– directionB
– 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.\]
Base.:∈
— Method∈(x::AbstractVector, B::AbstractBallp)
Check whether a given point is contained in a ball in the p-norm.
Input
x
– point/vectorB
– 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