Minkowski sum

MinkowskiSum{N, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}

Type that represents the Minkowski sum of two convex sets.

Fields

• X – first convex set
• Y – second convex set

Notes

The ZeroSet is the neutral element and the EmptySet is the absorbing element for MinkowskiSum.

⊕(X::LazySet, Y::LazySet)

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

X + Y

Convenience constructor for Minkowski sum.

Input

• X – a convex set
• Y – another convex set

Output

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

swap(ms::MinkowskiSum)

Return a new MinkowskiSum object with the arguments swapped.

Input

• ms – Minkowski sum of two convex sets

Output

A new MinkowskiSum object with the arguments swapped.

dim(ms::MinkowskiSum)

Return the dimension of a Minkowski sum.

Input

• ms – Minkowski sum

Output

The ambient dimension of the Minkowski sum.

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

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

isbounded(ms::MinkowskiSum)

Determine whether a Minkowski sum is bounded.

Input

• ms – Minkowski sum

Output

true iff both wrapped sets are bounded.

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.

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.

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

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

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.

vertices_list(ms::MinkowskiSum{N, Z1, Z2}) where {N, Z1<:AbstractZonotope{N}, Z2<:AbstractZonotope{N}}

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

Input

• ms – Minkowski sum of two zonotopic sets

Output

The list of vertices of the Minkowski sum of two zonotopic sets.

MinkowskiSumArray{N, S<:LazySet{N}} <: LazySet{N}

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

Fields

• array – array of convex 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.

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

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.

ρ(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.

σ(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.

isbounded(msa::MinkowskiSumArray)

Determine whether a Minkowski sum of a finite number of convex sets is bounded.

Input

• msa – Minkowski sum of a finite number of convex sets

Output

true iff all wrapped sets are bounded.

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.

array(msa::MinkowskiSumArray)

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

Input

• msa – Minkowski sum array

Output

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

CachedMinkowskiSumArray{N, S<:LazySet{N}} <: LazySet{N}

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

Fields

• array – array of convex 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.

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

dim(cms::CachedMinkowskiSumArray)

Return the dimension of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The ambient dimension of the caching Minkowski sum.

σ(d::AbstractVector, cms::CachedMinkowskiSumArray)

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

Input

• d – direction
• cms – caching 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 caching Minkowski sum, the query is only performed for the new sets.

isbounded(cms::CachedMinkowskiSumArray)

Determine whether a caching Minkowski sum is bounded.

Input

• cms – caching Minkowski sum

Output

true iff all wrapped sets are bounded.

isempty(cms::CachedMinkowskiSumArray)

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

Input

• cms – caching 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 caching Minkowski sum should not be used further.

array(cms::CachedMinkowskiSumArray)

Return the array of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The array of a caching Minkowski sum.

forget_sets!(cms::CachedMinkowskiSumArray)

Tell a caching 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 – caching 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