# 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**

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
```

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

`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
```

`LazySets.vertices_list`

— Method```
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};
[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`

.

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

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

`LazySets.constraints_list`

— Method`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_list`

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

`LazySets.translate`

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

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

Inherited from `ConvexSet`

:

Inherited from `AbstractPolytope`

:

Inherited from `AbstractCentrallySymmetricPolytope`

: