Cartesian Decomposition

decompose(S::LazySet{N},
          partition::AbstractVector{<:AbstractVector{Int}},
          block_options) where {N}

Decompose a high-dimensional set into a Cartesian product of overapproximations of the projections over the specified subspaces.

Input

• S – set
• partition – vector of blocks (i.e., of vectors of integers) (see the Notes below)
• block_options – mapping from block indices in partition to a corresponding overapproximation option; we only require access via [⋅] (but see also the Notes below)

Output

A CartesianProductArray containing the low-dimensional approximated projections.

Algorithm

For each block a specific project method is called, dispatching on the corresponding overapproximation option.

Notes

The argument partition deserves some explanation. Typically, the list of blocks should form a partition of the set $\{1, …, n\}$ represented as a list of consecutive blocks, where $n$ is the ambient dimension of set S.

However, technically there is no problem if the blocks are not consecutive, blocks are missing, blocks occur more than once, or blocks are overlapping. The resulting set must be interpreted with care in such cases (e.g., it will not necessarily be an overapproximation of S).

For convenience, the argument block_options can also be given as a single option instead of a mapping, which is then interpreted as the option for all blocks.

Examples

The argument block_options supports different options: one can specify the target set, the degree of accuracy, and template directions. These options are exemplified below, where we use the following example.

julia> S = Ball2(zeros(4), 1.0);  # set to be decomposed (4D 2-norm unit ball)

julia> P2d = [1:2, 3:4];  # a partition with two blocks, each of size two

julia> P1d = [[1], [2], [3], [4]];  # a partition with four blocks, each of size one

Different set types

We can decompose using polygons in constraint representation:

julia> Y = decompose(S, P2d, HPolygon);

julia> all(ai isa HPolygon for ai in Y)
true

For decomposition into 1D subspaces, we can use Interval:

julia> Y = decompose(S, P1d, Interval);

julia> all(ai isa Interval for ai in Y)
true

However, if you need to specify different set types for different blocks, the interface presented so far does not apply. See the paragraph Advanced input for different block approximations below for how to do that.

Refining the decomposition: $ε$-close approximation

The $ε$ option can be used to refine a decomposition, i.e., obtain a more accurate result. We use the Iterative refinement algorithm from the Approximations module.

To illustrate this, consider again the set S from above. We decompose into two 2D polygons. Using smaller $ε$ implies a better precision, thus more constraints in each 2D decomposition. In the following example, we look at the number of constraints in the first block.

julia> d(ε, bi) = array(decompose(S, P2d, (HPolygon => ε)))[bi]
d (generic function with 1 method)

julia> [length(constraints_list(d(ε, 1))) for ε in [Inf, 0.1, 0.01]]
3-element Vector{Int64}:
  4
  8
 32

Refining the decomposition: template polyhedra

Another way to refine a decomposition is by using template polyhedra. The idea is to specify a set of template directions and then compute on each block the polytopic overapproximation obtained by evaluating the support function of the given input set over the template directions.

For example, octagonal 2D approximations of the set S are obtained with:

julia> B = decompose(S, P2d, OctDirections);

julia> length(B.array) == 2 && all(dim(bi) == 2 for bi in B.array)
true

See Template directions for the available template directions. Note that, in contrast to the polygonal $ε$-close approximation from above, this method can be applied to blocks of any size.

julia> B = decompose(S, [1:4], OctDirections);

julia> length(B.array) == 1 && dim(B.array[1]) == 4
true

Advanced input for different block approximations

Instead of defining the approximation option uniformly for each block, we can define different approximations for different blocks. For this purpose, the argument block_options can also be a mapping from block index (in the partition) to the corresponding approximation option.

For example, we can approximate the first block with a Hyperrectangle and the second block with $ε$-close approximation for $ε = 0.1$:

julia> res = array(decompose(S, P2d, Dict(1 => Hyperrectangle, 2 => 0.1)));

julia> typeof(res[1]), typeof(res[2])
(Hyperrectangle{Float64, Vector{Float64}, Vector{Float64}}, HPolygon{Float64, Vector{Float64}})

decompose(S::LazySet, block_options; [block_size]::Int=1)

Decompose a high-dimensional set into a Cartesian product of overapproximations of the projections over uniformly-sized subspaces.

Input

• S – set
• block_options – overapproximation option or mapping from block indices to a corresponding overapproximation option
• block_size – (optional; default: 1) size of the blocks

Output

A CartesianProductArray containing the low-dimensional approximated projections.