# Minkowski sum

## Binary Minkowski sum (MinkowskiSum)

`LazySets.MinkowskiSum`

— Type`MinkowskiSum{N, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}`

Type that represents the Minkowski sum of two sets, i.e., the set

\[X \oplus Y = \{x + y : x \in X, y \in Y\}.\]

**Fields**

`X`

– set`Y`

– set

**Notes**

The `ZeroSet`

is the neutral element and the `EmptySet`

is the absorbing element for `MinkowskiSum`

.

The Minkowski sum preserves convexity: if the set arguments are convex, then their Minkowski sum is convex as well.

`LazySets.:⊕`

— Method`⊕(X::LazySet, Y::LazySet)`

Unicode alias constructor ⊕ (`oplus`

) for the lazy Minkowski sum operator.

**Input**

`X`

– set`Y`

– set

**Output**

The symbolic Minkowski sum of $X$ and $Y$.

**Notes**

Write `\oplus[TAB]`

to enter this symbol.

`Base.:+`

— Method`+(X::LazySet, Y::LazySet)`

Convenience constructor for the Minkowski sum of two sets.

**Input**

`X`

– set`Y`

– set

**Output**

The symbolic Minkowski sum of $X$ and $Y$.

`LazySets.swap`

— Method`swap(ms::MinkowskiSum)`

Return a new `MinkowskiSum`

object with the arguments swapped.

**Input**

`ms`

– Minkowski sum of two sets

**Output**

A new `MinkowskiSum`

object with the arguments swapped.

`LazySets.dim`

— Method`dim(ms::MinkowskiSum)`

Return the dimension of a Minkowski sum of two sets.

**Input**

`ms`

– Minkowski sum of two sets

**Output**

The ambient dimension of the Minkowski sum of two sets.

`LazySets.ρ`

— Method`ρ(d::AbstractVector, ms::MinkowskiSum)`

Evaluate the support function of a Minkowski sum of two sets.

**Input**

`d`

– direction`ms`

– Minkowski sum of two sets

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

The support function in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support functions of $X$ and $Y$ in direction $d$.

`LazySets.σ`

— Method`σ(d::AbstractVector, ms::MinkowskiSum)`

Return a support vector of a Minkowski sum of two sets.

**Input**

`d`

– direction`ms`

– Minkowski sum of two sets

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

**Algorithm**

A valid support vector in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support vectors of $X$ and $Y$ in direction $d$.

`LazySets.isbounded`

— Method`isbounded(ms::MinkowskiSum)`

Check whether a Minkowski sum of two sets is bounded.

**Input**

`ms`

– Minkowski sum of two sets

**Output**

`true`

iff both wrapped sets are bounded.

`Base.isempty`

— Method`isempty(ms::MinkowskiSum)`

Check whether a Minkowski sum of two sets is empty.

**Input**

`ms`

– Minkowski sum of two sets

**Output**

`true`

iff any of the wrapped sets are empty.

`LazySets.center`

— Method`center(ms::MinkowskiSum)`

Return the center of a Minkowski sum of two centrally-symmetric sets.

**Input**

`ms`

– Minkowski sum of two centrally-symmetric sets

**Output**

The center of the Minkowski sum.

`LazySets.constraints_list`

— Method`constraints_list(ms::MinkowskiSum)`

Return a list of constraints of the Minkowski sum of two polyhedral sets.

**Input**

`ms`

– Minkowski sum of two polyhedral sets

**Output**

The list of constraints of the Minkowski sum.

**Algorithm**

We compute a concrete set representation via `minkowski_sum`

and call `constraints_list`

on the result.

`Base.:∈`

— Method```
∈(x::AbstractVector, ms::MinkowskiSum{N, S1, S2})
where {N, S1<:AbstractSingleton}
```

Check whether a given point is contained in the Minkowski sum of a singleton and another set.

**Input**

`x`

– point/vector`ms`

– Minkowski sum of a singleton and another set

**Output**

`true`

iff $x ∈ ms$.

**Algorithm**

Note that $x ∈ (S ⊕ P)$, where $S = \{s\}$ is a singleton set and $P$ is a set, if and only if $(x-s) ∈ P$.

`LazySets.vertices_list`

— Method`vertices_list(ms::MinkowskiSum)`

Return a list of vertices for the Minkowski sum of two sets.

**Input**

`ms`

– Minkowski sum of two sets

**Output**

A list of vertices of the Minkowski sum of two sets.

**Algorithm**

We compute the concrete Minkowski sum (via `minkowski_sum`

) and call `vertices_list`

on the result.

Inherited from `LazySet`

:

`norm`

`radius`

`diameter`

- [
`an_element`

](@ref an_element(::LazySet) `singleton_list`

## $n$-ary Minkowski sum (MinkowskiSumArray)

`LazySets.MinkowskiSumArray`

— TypeMinkowskiSumArray{N, S<:LazySet{N}} <: LazySet{N}

Type that represents the Minkowski sum of a finite number of sets.

**Fields**

`array`

– array of sets

**Notes**

This type assumes that the dimensions of all elements match.

The `ZeroSet`

is the neutral element and the `EmptySet`

is the absorbing element for `MinkowskiSumArray`

.

The Minkowski sum preserves convexity: if the set arguments are convex, then their Minkowski sum is convex as well.

Constructors:

`MinkowskiSumArray(array::Vector{<:LazySet})`

– default constructor`MinkowskiSumArray([n]::Int=0, [N]::Type=Float64)`

– constructor for an empty sum with optional size hint and numeric type

`LazySets.dim`

— Methoddim(msa::MinkowskiSumArray)

Return the dimension of a Minkowski sum of a finite number of sets.

**Input**

`msa`

– Minkowski sum of a finite number of sets

**Output**

The ambient dimension of the Minkowski sum of a finite number of sets, or `0`

if there is no set in the array.

`LazySets.ρ`

— Methodρ(d::AbstractVector, msa::MinkowskiSumArray)

Evaluate the support function of a Minkowski sum of a finite number of sets in a given direction.

**Input**

`d`

– direction`msa`

– Minkowski sum of a finite number of sets

**Output**

The evaluation of the support function in the given direction.

**Algorithm**

The support function of the Minkowski sum of multiple sets evaluations to the sum of the support-function evaluations of each set.

`LazySets.σ`

— Methodσ(d::AbstractVector, msa::MinkowskiSumArray)

Return a support vector of a Minkowski sum of a finite number of sets in a given direction.

**Input**

`d`

– direction`msa`

– Minkowski sum of a finite number of sets

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

`LazySets.isbounded`

— Method`isbounded(msa::MinkowskiSumArray)`

Check whether a Minkowski sum of a finite number of sets is bounded.

**Input**

`msa`

– Minkowski sum of a finite number of sets

**Output**

`true`

iff all wrapped sets are bounded.

`Base.isempty`

— Methodisempty(msa::MinkowskiSumArray)

Check whether a Minkowski sum of a finite number of sets is empty.

**Input**

`msa`

– Minkowski sum of a finite number of sets

**Output**

`true`

iff any of the wrapped sets is empty.

`LazySets.array`

— Methodarray(msa::MinkowskiSumArray)

Return the array of a Minkowski sum of a finite number of sets.

**Input**

`msa`

– Minkowski sum of a finite number of sets

**Output**

The array of a Minkowski sum of a finite number of sets.

`LazySets.center`

— Method`center(msa::MinkowskiSumArray)`

Return the center of a Minkowski sum of a finite number of centrally-symmetric sets.

**Input**

`msa`

– Minkowski sum of a finite number of centrally-symmetric sets

**Output**

The center of the set.

Inherited from `LazySet`

:

`norm`

`radius`

`diameter`

- [
`an_element`

](@ref an_element(::LazySet) `singleton_list`

## $n$-ary Minkowski sum with cache (CachedMinkowskiSumArray)

`LazySets.CachedMinkowskiSumArray`

— Type`CachedMinkowskiSumArray{N, S<:LazySet{N}} <: LazySet{N}`

Type that represents the Minkowski sum of a finite number of sets. Support vector queries are cached.

**Fields**

`array`

– array of sets`cache`

– cache for results of support-vector queries

**Notes**

This type assumes that the dimensions of all sets in the array match.

The `ZeroSet`

is the neutral element and the `EmptySet`

is the absorbing element for `CachedMinkowskiSumArray`

.

The cache (field `cache`

) is implemented as a dictionary whose keys are direction vectors and whose values are pairs `(k, s)`

where `k`

is the number of elements in the array `array`

when the support vector was evaluated last time, and `s`

is the support vector that was obtained. Thus this type assumes that `array`

is not modified except by adding new sets at the end.

The Minkowski sum preserves convexity: if all sets are convex, then their Minkowski sum is convex as well.

Constructors:

`CachedMinkowskiSumArray(array::Vector{<:LazySet})`

– default constructor`CachedMinkowskiSumArray([n]::Int=0, [N]::Type=Float64)`

– constructor for an empty sum with optional size hint and numeric type

`LazySets.dim`

— Method`dim(cms::CachedMinkowskiSumArray)`

Return the dimension of a cached Minkowski sum.

**Input**

`cms`

– cached Minkowski sum

**Output**

The ambient dimension of the cached Minkowski sum, or `0`

if there is no set in the array.

`LazySets.σ`

— Method`σ(d::AbstractVector, cms::CachedMinkowskiSumArray)`

Return a support vector of a cached Minkowski sum in a given direction.

**Input**

`d`

– direction`cms`

– cached Minkowski sum

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

**Notes**

The result is cached, i.e., any further query with the same direction runs in constant time. When sets are added to the cached Minkowski sum, the query is only performed for the new sets.

`LazySets.isbounded`

— Method`isbounded(cms::CachedMinkowskiSumArray)`

Check whether a cached Minkowski sum is bounded.

**Input**

`cms`

– cached Minkowski sum

**Output**

`true`

iff all wrapped sets are bounded.

`Base.isempty`

— Method`isempty(cms::CachedMinkowskiSumArray)`

Check whether a cached Minkowski sum array is empty.

**Input**

`cms`

– cached Minkowski sum

**Output**

`true`

iff any of the wrapped sets are empty.

**Notes**

Forgotten sets cannot be checked anymore. Normally they should not have been empty because otherwise the support-vector query would have crashed before. In that case, the cached Minkowski sum should not be used further.

`LazySets.array`

— Method`array(cms::CachedMinkowskiSumArray)`

Return the array of a cached Minkowski sum.

**Input**

`cms`

– cached Minkowski sum

**Output**

The array of a cached Minkowski sum.

`LazySets.forget_sets!`

— Method`forget_sets!(cms::CachedMinkowskiSumArray)`

Tell a cached Minkowski sum to forget the stored sets (but not the support vectors). Only those sets are forgotten for which a support vector has been computed in each of the cached directions.

**Input**

`cms`

– cached Minkowski sum

**Output**

The number of sets that have been forgotten.

**Notes**

This function should only be used under the assertion that no new directions are queried in the future; otherwise such support-vector results will be incorrect.

This implementation is optimistic and first tries to remove all sets. However, it also checks that for all cached directions the support vector has been computed before. If it finds that this is not the case, the implementation identifies the biggest index $k$ such that the above holds for the $k$ oldest sets, and then it only removes these. See the example below.

**Examples**

```
julia> x1 = BallInf(ones(3), 3.); x2 = Ball1(ones(3), 5.);
julia> cms1 = CachedMinkowskiSumArray(2); cms2 = CachedMinkowskiSumArray(2);
julia> d = ones(3);
julia> a1 = array(cms1); a2 = array(cms2);
julia> push!(a1, x1); push!(a2, x1);
julia> σ(d, cms1); σ(d, cms2);
julia> push!(a1, x2); push!(a2, x2);
julia> σ(d, cms1);
julia> idx1 = forget_sets!(cms1) # support vector was computed for both sets
2
julia> idx1 = forget_sets!(cms2) # support vector was only computed for first set
1
```

Inherited from `LazySet`

: