Minkowski sum

Binary Minkowski sum (MinkowskiSum)

LazySets.MinkowskiSumType
MinkowskiSum{N, S1<:ConvexSet{N}, S2<:ConvexSet{N}} <: ConvexSet{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 – first set
  • Y – second 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.

source
LazySets.:⊕Method
⊕(X::ConvexSet, Y::ConvexSet)

Unicode alias constructor ⊕ (oplus) for the lazy Minkowski sum operator.

Notes

Write \oplus[TAB] to enter this symbol.

source
Base.:+Method
X + Y

Convenience constructor for Minkowski sum.

Input

  • X – a set
  • Y – another set

Output

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

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

source
LazySets.dimMethod
dim(ms::MinkowskiSum)

Return the dimension of a Minkowski sum.

Input

  • ms – Minkowski sum

Output

The ambient dimension of the Minkowski sum.

source
LazySets.ρMethod
ρ(d::AbstractVector, ms::MinkowskiSum)

Return the support function of a Minkowski sum.

Input

  • d – direction
  • ms – Minkowski sum

Output

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

source
LazySets.σMethod
σ(d::AbstractVector, ms::MinkowskiSum)

Return the support vector of a Minkowski sum.

Input

  • d – direction
  • ms – Minkowski sum

Output

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

Algorithm

The 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$.

source
LazySets.isboundedMethod
isbounded(ms::MinkowskiSum)

Determine whether a Minkowski sum is bounded.

Input

  • ms – Minkowski sum

Output

true iff both wrapped sets are bounded.

source
Base.isemptyMethod
isempty(ms::MinkowskiSum)

Return if a Minkowski sum is empty or not.

Input

  • ms – Minkowski sum

Output

true iff any of the wrapped sets are empty.

source
LazySets.centerMethod
center(ms::MinkowskiSum)

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

Input

  • ms – Minkowski sum of centrally-symmetric sets

Output

The center of the Minkowski sum.

source
LazySets.constraints_listMethod
constraints_list(ms::MinkowskiSum)

Return the list of constraints of a lazy 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.

source
Base.:∈Method
∈(x::AbstractVector, ms::MinkowskiSum{N, S1, S2}) where {N, S1<:AbstractSingleton, S2<:ConvexSet}

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

Input

  • x – point
  • ms – lazy Minkowski sum of a singleton and a set

Output

true iff $x ∈ ms$.

Algorithm

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

source
LazySets.vertices_listMethod
vertices_list(ms::MinkowskiSum)

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

Input

  • ms – Minkowski sum of two sets

Output

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

source

Inherited from ConvexSet:

$n$-ary Minkowski sum (MinkowskiSumArray)

LazySets.MinkowskiSumArrayType

MinkowskiSumArray{N, S<:ConvexSet{N}} <: ConvexSet{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{<:ConvexSet}) – default constructor

  • MinkowskiSumArray([n]::Int=0, [N]::Type=Float64)

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

source
LazySets.dimMethod

dim(msa::MinkowskiSumArray)

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

Input

  • msa – Minkowski sum array

Output

The ambient dimension of the Minkowski sum of a finite number of sets.

source
LazySets.ρMethod

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

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

Input

  • d – direction
  • msa – Minkowski sum array

Output

The support function in the given direction.

Algorithm

The support function of the Minkowski sum of sets is the sum of the support functions of each set.

source
LazySets.σMethod

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

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

Input

  • d – direction
  • msa – Minkowski sum array

Output

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

source
LazySets.isboundedMethod
isbounded(msa::MinkowskiSumArray)

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

source
Base.isemptyMethod

isempty(msa::MinkowskiSumArray)

Return if a Minkowski sum array is empty or not.

Input

  • msa – Minkowski sum array

Output

true iff any of the wrapped sets are empty.

source
LazySets.arrayMethod

array(msa::MinkowskiSumArray)

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

Input

  • msa – Minkowski sum array

Output

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

source
LazySets.centerMethod
center(msa::MinkowskiSumArray)

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

Input

  • msa – Minkowski sum array of centrally-symmetric sets

Output

The center of the Minkowski sum array.

source

Inherited from ConvexSet:

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

LazySets.CachedMinkowskiSumArrayType
CachedMinkowskiSumArray{N, S<:ConvexSet{N}} <: ConvexSet{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 of support vector query results

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

The cache (field cache) is implemented as dictionary whose keys are directions 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 the set arguments are convex, then their Minkowski sum is convex as well.

Constructors:

  • CachedMinkowskiSumArray(array::Vector{<:ConvexSet}) – default constructor

  • CachedMinkowskiSumArray([n]::Int=0, [N]::Type=Float64) – constructor for an empty sum with optional size hint and numeric type

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

source
LazySets.σMethod
σ(d::AbstractVector, cms::CachedMinkowskiSumArray)

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

Input

  • d – direction
  • cms – cached Minkowski sum

Output

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

source
LazySets.isboundedMethod
isbounded(cms::CachedMinkowskiSumArray)

Determine whether a cached Minkowski sum is bounded.

Input

  • cms – cached Minkowski sum

Output

true iff all wrapped sets are bounded.

source
Base.isemptyMethod
isempty(cms::CachedMinkowskiSumArray)

Return if a cached Minkowski sum array is empty or not.

Input

  • cms – cached Minkowski sum

Output

true iff any of the wrapped sets are empty.

Notes

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

source
LazySets.arrayMethod
array(cms::CachedMinkowskiSumArray)

Return the array of a cached Minkowski sum.

Input

  • cms – cached Minkowski sum

Output

The array of a cached Minkowski sum.

source
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 such that for each cached direction the support vector has been computed before.

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
source

Inherited from ConvexSet: