Cartesian product

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

Type that represents the Cartesian product of two sets, i.e., the set

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

If $X ⊆ ℝ^n$ and $Y ⊆ ℝ^m$, then $Z$ is $n+m$-dimensional.

Fields

• X – first set
• Y – second set

Notes

See also CartesianProductArray for an implementation of a Cartesian product of more than two sets.

The EmptySet is the almost absorbing element for CartesianProduct (except that the dimension is adapted).

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 of 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 \times<tab>).

julia> I1 = Interval(0, 1);

julia> I2 = Interval(2, 4);

julia> I12 = I1 × I2;

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

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

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

×(X::LazySet, Y::LazySet)

Alias for the binary Cartesian product.

Notes

The function symbol can be typed via \times<tab>.

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

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)

Evaluate the support function of a Cartesian product.

Input

• d – direction
• cp – Cartesian product

Output

The evaluation of 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 a support vector of a Cartesian product.

Input

• d – direction
• cp – Cartesian product

Output

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

isbounded(cp::CartesianProduct)

Check 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)

Check whether a Cartesian product is empty.

Input

• cp – Cartesian product

Output

true iff any of the sub-blocks is empty.

center(cp::CartesianProduct)

Return the center of a Cartesian product of centrally-symmetric sets.

Input

• cp – Cartesian product of centrally-symmetric sets

Output

The center of the Cartesian product.

constraints_list(cp::CartesianProduct)

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

Input

• cp – polyhedral Cartesian product

Output

A list of constraints.

vertices_list(cp::CartesianProduct)

Return the list of vertices of a (polytopic) Cartesian product.

Input

• cp – polytopic 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.

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

Concrete linear map of a (polyhedral) Cartesian product.

Input

• M – matrix
• cp – Cartesian product

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 will fail if the wrapped sets are not polyhedral.

volume(cp::CartesianProduct)

Compute the volume of a Cartesian product.

Input

• cp – Cartesian product

Output

The volume.

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

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

Input

• cp – Cartesian product of 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 of an interval and a zonotopic set.

Input

• cp – Cartesian product of 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,<:Interval,<:Union{VPolygon,VPolytope}
        block::AbstractVector{Int};
        [kwargs...]) where {N}

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

Input

• cp – Cartesian product of 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 Cartesian product preserves convexity: if the set arguments are convex, then their Cartesian product is convex as well.

×(X::LazySet, Xs::LazySet...)
×(Xs::Vector{<:LazySet})

Alias for the n-ary Cartesian product.

Notes

The function symbol can be typed via \times<tab>.

    *(X::LazySet, Xs::LazySet...)
    *(Xs::Vector{<:LazySet})

Alias for the n-ary Cartesian product.

dim(cpa::CartesianProductArray)

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

Input

• cpa – Cartesian product of a finite number of sets

Output

The ambient dimension of the Cartesian product of a finite number of sets, or 0 if there is no set in the array.

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

Evaluate the support function of a Cartesian product of a finite number of sets.

Input

• d – direction
• cpa – Cartesian product of a finite number of sets

Output

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

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

Compute a support vector of a Cartesian product of a finite number of sets.

Input

• d – direction
• cpa – Cartesian product 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 product sets.

isbounded(cpa::CartesianProductArray)

Check 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 of a finite number of sets

Output

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

isempty(cpa::CartesianProductArray)

Check whether a Cartesian product of a finite number of sets is empty.

Input

• cpa – Cartesian product of a finite number of sets

Output

true iff any of the sub-blocks is empty.

center(cpa::CartesianProductArray)

Compute the center of a Cartesian product of a finite number of centrally-symmetric sets.

Input

• cpa – Cartesian product of a finite number of centrally-symmetric sets

Output

The center of the Cartesian product of a finite number of sets.

constraints_list(cpa::CartesianProductArray)

Compute a list of constraints of a (polyhedral) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product of a finite number of sets

Output

A list of constraints.

vertices_list(cpa::CartesianProductArray)

Compute a list of vertices of a (polytopic) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product of a finite number of sets

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.

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 polyhedron or polytope.

array(cpa::CartesianProductArray)

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

Input

• cpa – Cartesian product of a finite number of sets

Output

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

volume(cpa::CartesianProductArray)

Compute the volume of a Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product of a finite number of sets

Output

The volume.

block_structure(cpa::CartesianProductArray)

Compute an array containing the dimension ranges of each block of a Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product of a finite number of sets

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 Vector{UnitRange{Int64}}:
 1:3
 4:4
 5:6

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

Compute 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 of a finite number of sets
• vars – list containing the variables of interest, sorted in ascending order

Output

(i) A vector of pairs, where each pair corresponds to the range of dimensions in the i-th block.

(ii) The 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 Vector{Tuple{Int64, Int64}}:
 (-1, -1)
 (2, 4)
 (-1, -1)
 (7, 9)

julia> k
2

The vector m 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 vars=[2, 4, 8]. The number of constrained blocks is k = 2 (2nd and 4th blocks).

substitute_blocks(low_dim_cpa::CartesianProductArray{N},
                  orig_cpa::CartesianProductArray{N},
                  blocks::Vector{Tuple{Int, Int}}) where {N}

Return a Cartesian product of a finite number of sets (CPA) obtained by merging an original CPA with a low-dimensional CPA, which represents the updated subset of variables in the specified blocks.

Input

• low_dim_cpa – low-dimensional Cartesian product of a finite number of sets
• orig_cpa – original high-dimensional Cartesian product of a finite number of sets
• blocks – index of the first variable in each block of orig_cpa

Output

The merged Cartesian product.