# Cartesian product

## Binary Cartesian product (CartesianProduct)

`LazySets.CartesianProduct`

— Type`CartesianProduct{N, S1<:ConvexSet{N}, S2<:ConvexSet{N}} <: ConvexSet{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 `\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`

exactly 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 constructor × (`times`

) for the binary Cartesian product operator.

**Notes**

Write `\times[TAB]`

to enter this symbol.

`Base.:*`

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

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 of two sets

**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)`

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.

`LazySets.σ`

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

`LazySets.isbounded`

— Method`isbounded(cp::CartesianProduct)`

Determine 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)`

Return if a Cartesian product is empty or not.

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

– Cartesian product

**Output**

A list of constraints.

`LazySets.vertices_list`

— Method```
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};
[backend]=get_exponential_backend()) where {N}
```

Return the list of vertices of a (polytopic) exponential map.

**Input**

`em`

– exponential map`backend`

– (optional; default:`get_exponential_backend()`

) exponentiation backend

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

.

`LazySets.linear_map`

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

`LazySets.project`

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

.

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

.

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

.

Inherited from `ConvexSet`

:

`norm`

`radius`

`diameter`

- [
`an_element`

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

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

`LazySets.CartesianProductArray`

— TypeCartesianProductArray{N, S<:ConvexSet{N}} <: ConvexSet{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{<:ConvexSet})`

– default constructor`CartesianProductArray([n]::Int=0, [N]::Type=Float64)`

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

`LazySets.dim`

— Methoddim(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.

`LazySets.ρ`

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

`LazySets.σ`

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

`LazySets.isbounded`

— Methodisbounded(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.

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

**Output**

`true`

iff $x ∈ \text{cpa}$.

`Base.isempty`

— Methodisempty(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.

`LazySets.center`

— Method`center(cpa::CartesianProductArray)`

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

**Input**

`cpa`

– Cartesian product array of centrally-symmetric sets

**Output**

The center of the Cartesian product array.

`LazySets.constraints_list`

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

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

`LazySets.vertices_list`

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

```
vertices_list(em::ExponentialMap{N};
[backend]=get_exponential_backend()) where {N}
```

Return the list of vertices of a (polytopic) exponential map.

**Input**

`em`

– exponential map`backend`

– (optional; default:`get_exponential_backend()`

) exponentiation backend

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

.

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

`LazySets.array`

— Methodarray(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.

`LazySets.block_structure`

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

`LazySets.block_to_dimension_indices`

— Methodblock*to*dimension_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 Vector{Tuple{Int64, Int64}}:
(-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)

`LazySets.substitute_blocks`

— Methodsubstitute*blocks(low*dim*cpa::CartesianProductArray{N}, orig*cpa::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.

Inherited from `ConvexSet`

: