Cartesian product

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

Type that represents the Cartesian product of two sets, that is the set

\[Z = \{ z ∈ \mathbb{R}^{n + m} : z = (x, y),\qquad x ∈ X, y ∈ Y \}.\]

If $X ⊆ \mathbb{R}^n$ and $Y ⊆ \mathbb{R}^m$, then $Z$ is $n+m$-dimensional.

Fields

• X – first set
• Y – second set

Notes

The Cartesian product of three elements is obtained recursively. See also CartesianProductArray for an implementation of a Cartesian product of many sets without recursion, instead using an array, making the operations more efficient.

The EmptySet is the absorbing element for CartesianProduct.

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

In some docstrings the word "block" is used to denote each wrapped set, with the natural order, i.e. we say that the first block of a Cartesian product cp is cp.X and the second block is cp.Y.

Examples

The Cartesian product between two sets X and Y can be constructed either using CartesianProduct(X, Y) or the short-cut notation X × Y (to enter the times symbol, write imes[TAB]).

julia> I1 = Interval(0, 1);

julia> I2 = Interval(2, 4);

julia> I12 = I1 × I2;

julia> typeof(I12)
CartesianProduct{Float64,Interval{Float64,IntervalArithmetic.Interval{Float64}},Interval{Float64,IntervalArithmetic.Interval{Float64}}}

A hyperrectangle is the cartesian product of intervals, so we can convert I12 exactly to a Hyperrectangle type:

julia> convert(Hyperrectangle, I12)
Hyperrectangle{Float64,Array{Float64,1},Array{Float64,1}}([0.5, 3.0], [0.5, 1.0])

×

Unicode alias constructor × (times) for the binary Cartesian product operator.

Notes

Write \times[TAB] to enter this symbol.

    *(X::LazySet, Y::LazySet)

Alias for the binary Cartesian product.

swap(cp::CartesianProduct)

Return a new CartesianProduct object with the arguments swapped.

Input

• cp – Cartesian product of two sets

Output

A new CartesianProduct object with the arguments swapped.

dim(cp::CartesianProduct)

Return the dimension of a Cartesian product.

Input

• cp – Cartesian product

Output

The ambient dimension of the Cartesian product.

ρ(d::AbstractVector, cp::CartesianProduct)

Return the support function of a Cartesian product.

Input

• d – direction
• cp – Cartesian product

Output

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

σ(d::AbstractVector, cp::CartesianProduct)

Return the support vector of a Cartesian product.

Input

• d – direction
• cp – Cartesian product

Output

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

isbounded(cp::CartesianProduct)

Determine whether a Cartesian product is bounded.

Input

• cp – Cartesian product

Output

true iff both wrapped sets are bounded.

∈(x::AbstractVector, cp::CartesianProduct)

Check whether a given point is contained in a Cartesian product.

Input

• x – point/vector
• cp – Cartesian product

Output

true iff $x ∈ cp$.

isempty(cp::CartesianProduct)

Return if a Cartesian product is empty or not.

Input

• cp – Cartesian product

Output

true iff any of the sub-blocks is empty.

constraints_list(cp::CartesianProduct)

Return the list of constraints of a (polyhedral) Cartesian product.

Input

• cp – Cartesian product

Output

A list of constraints.

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.

linear_map(M::AbstractMatrix, cp::CartesianProduct)

Concrete linear map of a (polyhedral) Cartesian product.

Input

• M – matrix
• cp – Cartesian product of two sets

Output

A polytope if cp is bounded and a polyhedron otherwise.

Algorithm

We convert the Cartesian product to constraint representation and then call linear_map on the corresponding polyhedron.

This is a fallback implementation and it will fail if the wrapped sets are not polyhedral.

project(cp::CartesianProduct{N, IT, HT}, block::AbstractVector{Int};
        [kwargs...]) where {N, IT<:Interval, HT<:AbstractHyperrectangle{N}}

Concrete projection of a Cartesian product between an interval and a hyperrectangle.

Input

• cp – Cartesian product between an interval and a hyperrectangle
• block – block structure, a vector with the dimensions of interest

Output

A hyperrectangle representing the projection of the cartesian product cp on the dimensions specified by block.

project(cp::CartesianProduct{N, IT, ZT}, block::AbstractVector{Int};
        [kwargs...]) where {N, IT<:Interval, ZT<:AbstractZonotope{N}}

Concrete projection of the Cartesian product between an interval and a zonotopic set.

Input

• cp – Cartesian product between an interval and a zonotopic set
• block – block structure, a vector with the dimensions of interest

Output

A zonotope representing the projection of the cartesian product cp on the dimensions specified by block.

project(cp::CartesianProduct{N, IT, Union{VP1, VP2}},
        block::AbstractVector{Int};
        [kwargs...]) where {N, IT<:Interval, VP1<:VPolygon{N}, VP2<:VPolytope{N}}

Concrete projection of the Cartesian product between an interval and a set in vertex representation.

Input

• cp – Cartesian product between an interval and a VPolygon or a VPolytope
• block – block structure, a vector with the dimensions of interest

Output

A VPolytope representing the projection of the cartesian product cp on the dimensions specified by block.

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

Type that represents the Cartesian product of a finite number of sets.

Fields

• array – array of sets

Notes

The EmptySet is the absorbing element for CartesianProductArray.

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

Constructors:

• CartesianProductArray(array::Vector{<:LazySet}) – default constructor

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

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

dim(cpa::CartesianProductArray)

Return the dimension of a Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

The ambient dimension of the Cartesian product of a finite number of sets.

ρ(d::AbstractVector, cpa::CartesianProductArray)

Return the support function of a Cartesian product array.

Input

• d – direction
• cpa – Cartesian product array

Output

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

σ(d::AbstractVector, cpa::CartesianProductArray)

Support vector of a Cartesian product array.

Input

• d – direction
• cpa – Cartesian product array

Output

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

isbounded(cpa::CartesianProductArray)

Determine whether a Cartesian product of a finite number of sets is bounded.

Input

• cpa – Cartesian product of a finite number of sets

Output

true iff all wrapped sets are bounded.

∈(x::AbstractVector, cpa::CartesianProductArray)

Check whether a given point is contained in a Cartesian product of a finite number of sets.

Input

• x – point/vector
• cpa – Cartesian product array

Output

true iff $x ∈ \text{cpa}$.

isempty(cpa::CartesianProductArray)

Return if a Cartesian product is empty or not.

Input

• cp – Cartesian product

Output

true iff any of the sub-blocks is empty.

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

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.

linear_map(M::AbstractMatrix, cpa::CartesianProductArray)

Concrete linear map of a Cartesian product of a finite number of (polyhedral) sets.

Input

• M – matrix
• cpa – Cartesian product of a finite number of sets

Output

A polytope.

Algorithm

We check if the matrix is invertible. If so, we convert the Cartesian product to constraint representation. Otherwise, we convert the Cartesian product to vertex representation. In both cases, we then call linear_map on the resulting polytope.

array(cpa::CartesianProductArray)

Return the array of a Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

The array of a Cartesian product of a finite number of sets.

block_structure(cpa::CartesianProductArray{N}) where {N}

Returns an array containing the dimension ranges of each block in a CartesianProductArray.

Input

• cpa – Cartesian product array

Output

A vector of ranges

Example

julia> using LazySets: block_structure

julia> cpa = CartesianProductArray([BallInf(zeros(n), 1.0) for n in [3, 1, 2]]);

julia> block_structure(cpa)
3-element Array{UnitRange{Int64},1}:
 1:3
 4:4
 5:6

blocktodimension_indices(cpa::CartesianProductArray{N}, vars::Vector{Int}) where {N}

Returns a vector mapping block index i to tuple (f, l) such that either f = l = -1 or f is the first dimension index and l is the last dimension index of the i-th block, depending on whether one of the block's dimension indices is specified in vars.

Input

• cpa – Cartesian product array
• vars – list containing the variables of interest, sorted in ascending order

Output

(i) A vector of tuples, where values in tuple relate to range of dimensions in the i-th block.

(ii) Number of constrained blocks

Example

julia> using LazySets: block_to_dimension_indices

julia> cpa = CartesianProductArray([BallInf(zeros(n), 1.0) for n in [1, 3, 2, 3]]);

julia> m, k = block_to_dimension_indices(cpa, [2, 4, 8]);

julia> m
4-element Array{Tuple{Int64,Int64},1}:
 (-1, -1)
 (2, 4)
 (-1, -1)
 (7, 9)

julia> k
2

This vector represents the mapping "second block from dimension 2 to dimension 4, fourth block from dimension 7 to dimension 9." These blocks contain the dimensions specified in [2, 4, 8]. Number of constrained variables here is 2 (2nd and 4th blocks)

substituteblocks(lowdimcpa::CartesianProductArray{N}, origcpa::CartesianProductArray{N}, blocks::Vector{Tuple{Int,Int}}) where {N}

Return merged Cartesian Product Array between original CPA and some low-dimensional CPA, which represents updated subset of variables in specified blocks.

Input

• low_dim_cpa – low-dimensional cartesian product array
• orig_cpa – original high-dimensional Cartesian product array
• blocks – index of the first variable in each block of orig_cpa

Output

Merged cartesian product array.