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 ∈ \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

Unit ball in the 1-norm in the plane:

julia> B = Ball1(zeros(2), 1.)
Ball1{Float64,Array{Float64,1}}([0.0, 0.0], 1.0)
julia> dim(B)
2

We evaluate the support vector in the East direction:

julia> σ([0.,1], B)
2-element Array{Float64,1}:
 0.0
 1.0

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

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

Input

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

Output

Support vector in the given direction.

∈(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., 1.], 1.);

julia> [.5, -.5] ∈ B
false
julia> [.5, 1.5] ∈ B
true

vertices_list(P::AbstractHPolygon{N};
              apply_convex_hull::Bool=true,
              check_feasibility::Bool=true) where {N}

Return the list of vertices of a polygon in constraint representation.

Input

• P – polygon in constraint representation
• apply_convex_hull – (optional, default: true) flag to post-process the intersection of constraints with a convex hull
• check_feasibility – (optional, default: true) flag to check whether the polygon was empty (required for correctness in case of empty polygons)

Output

List of vertices.

Algorithm

We compute each vertex as the intersection of consecutive lines defined by the half-spaces. If check_feasibility is active, we then check if the constraints of the polygon were actually feasible (i.e., they pointed in the right direction). For this we compute the average of all vertices and check membership in each constraint.

vertices_list(B::Ball1{N, VN}) where {N, VN<:AbstractVector}

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.

vertices_list(∅::EmptySet{N}) where {N}

Return the list of vertices of an empty set.

Input

• ∅ – empty set

Output

The empty list of vertices, as the empty set does not contain any vertices.

vertices_list(P::HPolytope{N};
              [backend]=nothing, [prune]::Bool=true) where {N}

Return the list of vertices of a polytope in constraint representation.

Input

• P – polytope in constraint representation
• backend – (optional, default: nothing) the polyhedral computations backend
• prune – (optional, default: true) flag to remove redundant vertices

Output

List of vertices.

Algorithm

If the polytope is two-dimensional, the polytope is converted to a polygon in H-representation and then its vertices_list function is used. This ensures that, by default, the optimized two-dimensional methods are used.

It is possible to use the Polyhedra backend in two-dimensions as well by passing, e.g. backend=CDDLib.Library().

If the polytope is not two-dimensional, the concrete polyhedra manipulation library Polyhedra is used. The actual computation is performed by a given backend; for the default backend used in LazySets see default_polyhedra_backend(P). For further information on the supported backends see Polyhedra's documentation.

vertices_list(cp::CartesianProduct{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product.

Input

• cp – Cartesian product

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

vertices_list(cpa::CartesianProductArray{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

vertices_list(em::ExponentialMap{N}) where {N}

Return the list of vertices of a (polytopic) exponential map.

Input

• em – exponential map

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polytopic. Then the result is just the exponential map applied to the vertices of X.

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.

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.

constraints_list(H::AbstractHyperrectangle{N}) where {N}

Return the list of constraints of an axis-aligned hyperrectangular set.

Input

• H – hyperrectangular set

Output

A list of linear constraints.

constraints_list(P::Ball1{N}) where {N}

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

Input

• B – ball in the 1-norm

Output

The list of constraints of the ball.

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.

constraints_list(x::Interval{N}) where {N}

Return the list of constraints of the given interval.

Input

• x – interval

Output

The list of constraints of the interval represented as two one-dimensional half-spaces.

constraints_list(L::Line{N, VN}) where {N, VN}

Return the list of constraints of a line.

Input

• L – line

Output

A list containing 2n-2 half-spaces whose intersection is L, where n is the ambient dimension of L.

constraints_list(U::Universe{N}) where {N}

Return the list of constraints defining a universe.

Input

• U – universe

Output

The empty list of constraints, as the universe is unconstrained.

constraints_list(P::HParallelotope{N, VN}) where {N, VN}

Return the list of constraints of the given parallelotope.

Input

• P – parallelotope in constraint representation

Output

The list of constraints of P.

constraints_list(cpa::CartesianProductArray{N}) where {N}

Return the list of constraints of a (polyhedral) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

A list of constraints.

constraints_list(ia::IntersectionArray{N}) where {N}

Return the list of constraints of an intersection of a finite number of (polyhedral) sets.

Input

• ia – intersection of a finite number of (polyhedral) sets

Output

The list of constraints of the intersection.

Notes

We assume that the underlying sets are polyhedral, i.e., offer a method constraints_list.

Algorithm

We create the polyhedron from the constraints_lists of the sets and remove redundant constraints.

constraints_list(rm::ResetMap{N}) where {N}

Return the list of constraints of a polytopic reset map.

Input

• rm – reset map of a polytope

Output

The list of constraints of the reset map.

Notes

We assume that the underlying set X is a polytope, i.e., is bounded and offers a method constraints_list(X).

Algorithm

We fall back to constraints_list of a LinearMap of the A-matrix in the affine-map view of a reset map. Each reset dimension $i$ is projected to zero, expressed by two constraints for each reset dimension. Then it remains to shift these constraints to the new value.

For instance, if the dimension $5$ was reset to $4$, then there will be constraints $x₅ ≤ 0$ and $-x₅ ≤ 0$. We then modify the right-hand side of these constraints to $x₅ ≤ 4$ and $-x₅ ≤ -4$, respectively.

constraints_list(rm::ResetMap{N, S}) where {N, S<:AbstractHyperrectangle}

Return the list of constraints of a hyperrectangular reset map.

Input

• rm – reset map of a hyperrectangular set

Output

The list of constraints of the reset map.

Algorithm

We iterate through all dimensions. If there is a reset, we construct the corresponding (flat) constraints. Otherwise, we construct the corresponding constraints of the underlying set.

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

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

Input

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

Output

A translated ball in the 1-norm.

Algorithm

We add the vector to the center of the ball.