Manhattan-norm ball (Ball1)

LazySets.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 ∈ \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, Vector{Float64}}([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 Vector{Float64}:
 0.0
 1.0
source
LazySets.σMethod
σ(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.

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

julia> [.5, -.5] ∈ B
false
julia> [.5, 1.5] ∈ B
true
source
LazySets.vertices_listMethod
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.

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

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

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

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

source

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.

source
vertices_list(em::ExponentialMap{N};
              [backend]=get_exponential_backend()) where {N}

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

Input

  • em – exponential map
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

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.

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

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

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

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

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

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

source

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.

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

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

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

source
LazySets.translateMethod
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.

Notes

See also translate!(::Ball1, ::AbstractVector) for the in-place version.

source
LazySets.translate!Method
translate!(B::Ball1, v::AbstractVector)

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

Input

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

Output

The ball B translated by v.

Notes

See also translate(::Ball1, ::AbstractVector) for the out-of-place version.

source

Inherited from ConvexSet:

Inherited from AbstractPolytope:

Inherited from AbstractCentrallySymmetricPolytope: