# Cartesian product

## Binary Cartesian product (CartesianProduct)

`LazySets.CartesianProduct`

— Type`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, IntervalArithmetic.Interval{Float64}}, Interval{Float64, IntervalArithmetic.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])
```

`LinearAlgebra.:×`

— Method`×`

Unicode alias (`times`

) for the binary Cartesian product operator.

**Notes**

Write `\times[TAB]`

to enter this symbol.

`Base.:*`

— Method` *(X::LazySet, Y::LazySet)`

Alias for the binary Cartesian product.

`LazySets.swap`

— Method`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.

`LazySets.dim`

— Method`dim(cp::CartesianProduct)`

Return the dimension of a Cartesian product.

**Input**

`cp`

– Cartesian product

**Output**

The ambient dimension of the Cartesian product.

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

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

`LazySets.isbounded`

— Method`isbounded(cp::CartesianProduct)`

Check whether a Cartesian product is bounded.

**Input**

`cp`

– Cartesian product

**Output**

`true`

iff both wrapped sets are bounded.

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

`Base.isempty`

— Method`isempty(cp::CartesianProduct)`

Check whether a Cartesian product is empty.

**Input**

`cp`

– Cartesian product

**Output**

`true`

iff any of the sub-blocks is empty.

`LazySets.center`

— Method`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.

`LazySets.constraints_list`

— Method`constraints_list(cp::CartesianProduct)`

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

**Input**

`cp`

– polyhedral Cartesian product

**Output**

A list of constraints.

`LazySets.vertices_list`

— Method`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.

`LazySets.linear_map`

— Method`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.

`LazySets.volume`

— Method`volume(cp::CartesianProduct)`

Compute the volume of a Cartesian product.

**Input**

`cp`

– Cartesian product

**Output**

The volume.

`LazySets.project`

— Method```
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`

.

`LazySets.project`

— Method```
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`

.

`LazySets.project`

— Method```
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 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`

.

Inherited from `LazySet`

:

`norm`

`radius`

`diameter`

- [
`an_element`

](@ref an_element(::LazySet) `singleton_list`

## $n$-ary Cartesian product (CartesianProductArray)

`LazySets.CartesianProductArray`

— Type`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.

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

`LazySets.dim`

— Method`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.

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

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

`LazySets.isbounded`

— Method`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.

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

`Base.isempty`

— Method`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.

`LazySets.center`

— Method`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.

`LazySets.constraints_list`

— Method`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.

`LazySets.vertices_list`

— Method`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.

`LazySets.linear_map`

— Method`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.

`LazySets.array`

— Method`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.

`LazySets.volume`

— Method`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.

`LazySets.block_structure`

— Method`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
```

`LazySets.block_to_dimension_indices`

— Method```
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).

`LazySets.substitute_blocks`

— Method```
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.

Inherited from `LazySet`

:

`norm`

`radius`

`diameter`

- [
`an_element`

](@ref an_element(::LazySet) `singleton_list`