Cartesian product

Binary Cartesian product (CartesianProduct)

LazySets.CartesianProductType
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 ∈ \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

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])
source
LinearAlgebra.:×Method
×(X::LazySet, Y::LazySet)

Alias for the binary Cartesian product.

Notes

The function symbol can be typed via \times[TAB].

source
Base.:*Method
    *(X::LazySet, Y::LazySet)

Alias for the binary Cartesian product.

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

source
LazySets.dimMethod
dim(cp::CartesianProduct)

Return the dimension of a Cartesian product.

Input

  • cp – Cartesian product

Output

The ambient dimension of the Cartesian product.

source
LazySets.ρMethod
ρ(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.

source
LazySets.σMethod
σ(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.

source
LazySets.isboundedMethod
isbounded(cp::CartesianProduct)

Check whether a Cartesian product is bounded.

Input

  • cp – Cartesian product

Output

true iff both wrapped sets are bounded.

source
Base.:∈Method
∈(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$.

source
Base.isemptyMethod
isempty(cp::CartesianProduct)

Check whether a Cartesian product is empty.

Input

  • cp – Cartesian product

Output

true iff any of the sub-blocks is empty.

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

source
LazySets.constraints_listMethod
constraints_list(cp::CartesianProduct)

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

Input

  • cp – polyhedral Cartesian product

Output

A list of constraints.

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

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

source
LazySets.volumeMethod
volume(cp::CartesianProduct)

Compute the volume of a Cartesian product.

Input

  • cp – Cartesian product

Output

The volume.

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

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

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

source

Inherited from LazySet:

$n$-ary Cartesian product (CartesianProductArray)

LazySets.CartesianProductArrayType
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.

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

Alias for the n-ary Cartesian product.

Notes

The function symbol can be typed via \times[TAB].

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

Alias for the n-ary Cartesian product.

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

source
LazySets.ρMethod
ρ(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.

source
LazySets.σMethod
σ(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.

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

source
Base.:∈Method
∈(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}$.

source
Base.isemptyMethod
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.

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

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

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

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

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

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

source
LazySets.block_structureMethod
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
source
LazySets.block_to_dimension_indicesMethod
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).

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

source

Inherited from LazySet: