# Binary Functions on Sets

This section of the manual describes the binary functions for set types.

## Cartesian product

`LazySets.cartesian_product`

— Method`cartesian_product(P1::VPolytope, P2::VPolytope; [backend]=nothing)`

Compute the Cartesian product of two polytopes in V-representation.

**Input**

`P1`

– polytope`P2`

– another polytope`backend`

– (optional, default:`nothing`

) the polyhedral computations backend

**Output**

The `VPolytope`

obtained by the concrete Cartesian product of `P1`

and `P2`

.

**Notes**

For further information on the supported backends see Polyhedra's documentation.

`LazySets.cartesian_product`

— Method`cartesian_product(X::ConvexSet, Y::ConvexSet; [backend]=nothing, [algorithm]::String="vrep")`

Compute the Cartesian product of two sets.

**Input**

`X`

– set`Y`

– another set`backend`

– (optional, default:`nothing`

) the polyhedral computations backend`algorithm`

– (optional, default: "hrep") the method used to transform each set`X`

and`Y`

before taking the Cartesian product; choose between: - "vrep" (use the vertex representation) - "hrep" (use the constraint representation) - "hrep_polyhedra" (use the constraint representation and`Polyhedra`

)

**Output**

The `VPolytope`

(if `"vrep"`

was used) or `HPolytope`

(if `"hrep"`

or `"hrep_polyhedra"`

was used) obtained by the concrete Cartesian product of `X`

and `Y`

.

**Notes**

For further information on the supported backends see Polyhedra's documentation.

If `X`

can be converted to a one-dimensional interval and the vertices of `Y`

are available use `algorithm="vrep"`

.

## Check for emptiness of intersection

`is_intersection_empty`

can be used as an alternative name to `isdisjoint`

.

`Base.isdisjoint`

— Function`isdisjoint(X::ConvexSet, Y::ConvexSet, witness::Bool=false)`

Check whether two sets do not intersect, and otherwise optionally compute a witness.

**Input**

`X`

– set`Y`

– another set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ∩ Y = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $X ∩ Y = ∅$`(false, v)`

iff $X ∩ Y ≠ ∅$ and $v ∈ X ∩ Y$

**Algorithm**

This is a fallback implementation that computes the concrete intersection, `intersection`

, of the given sets.

A witness is constructed using the `an_element`

implementation of the result.

`Base.isdisjoint`

— Function```
isdisjoint(H1::AbstractHyperrectangle,
H2::AbstractHyperrectangle,
witness::Bool=false
)
```

Check whether two hyperrectangles do not intersect, and otherwise optionally compute a witness.

**Input**

`H1`

– first hyperrectangle`H2`

– second hyperrectangle`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $H1 ∩ H2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $H1 ∩ H2 = ∅$`(false, v)`

iff $H1 ∩ H2 ≠ ∅$ and $v ∈ H1 ∩ H2$

**Algorithm**

$H1 ∩ H2 ≠ ∅$ iff $|c_2 - c_1| ≤ r_1 + r_2$, where $≤$ is taken component-wise.

A witness is computed by starting in one center and moving toward the other center for as long as the minimum of the radius and the center distance. In other words, the witness is the point in `H1`

that is closest to the center of `H2`

.

`Base.isdisjoint`

— Function`isdisjoint(X::ConvexSet, S::AbstractSingleton, witness::Bool=false)`

Check whether a convex set and a singleton do not intersect, and otherwise optionally compute a witness.

**Input**

`X`

– convex set`S`

– singleton`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ∩ X = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $S ∩ X = ∅$`(false, v)`

iff $S ∩ X ≠ ∅$ and`v`

=`element(S)`

$∈ S ∩ X$

**Algorithm**

$S ∩ X = ∅$ iff `element(S)`

$∉ X$.

`Base.isdisjoint`

— Function```
isdisjoint(H::AbstractHyperrectangle,
S::AbstractSingleton,
witness::Bool=false
)
```

Check whether a hyperrectangle and a singleton do not intersect, and otherwise optionally compute a witness.

**Input**

`H`

– hyperrectangle`S`

– singleton`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $H ∩ S = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $H ∩ S = ∅$`(false, v)`

iff $H ∩ S ≠ ∅$ and`v`

=`element(S)`

$∈ H ∩ S$

**Algorithm**

$H ∩ S = ∅$ iff `element(S)`

$∉ H$.

`Base.isdisjoint`

— Function```
isdisjoint(S1::AbstractSingleton,
S2::AbstractSingleton,
witness::Bool=false
)
```

Check whether two singletons do not intersect, and otherwise optionally compute a witness.

**Input**

`S1`

– first singleton`S2`

– second singleton`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S1 ∩ S2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $S1 ∩ S2 = ∅$`(false, v)`

iff $S1 ∩ S2 ≠ ∅$ and`v`

=`element(S1)`

$∈ S1 ∩ S2$

**Algorithm**

$S1 ∩ S2 = ∅$ iff $S1 ≠ S2$.

`Base.isdisjoint`

— Function`isdisjoint(Z::AbstractZonotope, H::Union{Hyperplane, Line2D}, witness::Bool=false)`

Check whether a zonotope and a hyperplane do not intersect, and otherwise optionally compute a witness.

**Input**

`Z`

– zonotope`H`

– hyperplane`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $Z ∩ H = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $Z ∩ H = ∅$`(false, v)`

iff $Z ∩ H ≠ ∅$ and $v ∈ Z ∩ H$

**Algorithm**

$Z ∩ H = ∅$ iff $(b - a⋅c) ∉ \left[ ± ∑_{i=1}^p |a⋅g_i| \right]$, where $a$, $b$ are the hyperplane coefficients, $c$ is the zonotope's center, and $g_i$ are the zonotope's generators.

For witness production we fall back to a less efficient implementation for general sets as the first argument.

`Base.isdisjoint`

— Function`isdisjoint(B1::Ball2, B2::Ball2, witness::Bool=false)`

Check whether two balls in the 2-norm do not intersect, and otherwise optionally compute a witness.

**Input**

`B1`

– first ball in the 2-norm`B2`

– second ball in the 2-norm`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $B1 ∩ B2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $B1 ∩ B2 = ∅$`(false, v)`

iff $B1 ∩ B2 ≠ ∅$ and $v ∈ B1 ∩ B2$

**Algorithm**

$B1 ∩ B2 = ∅$ iff $‖ c_2 - c_1 ‖_2 > r_1 + r_2$.

A witness is computed depending on the smaller/bigger ball (to break ties, choose `B1`

for the smaller ball) as follows.

- If the smaller ball's center is contained in the bigger ball, we return it.
- Otherwise start in the smaller ball's center and move toward the other center until hitting the smaller ball's border. In other words, the witness is the point in the smaller ball that is closest to the center of the bigger ball.

`Base.isdisjoint`

— Function```
isdisjoint(ls1::LineSegment,
ls2::LineSegment,
witness::Bool=false
)
```

Check whether two line segments do not intersect, and otherwise optionally compute a witness.

**Input**

`ls1`

– first line segment`ls2`

– second line segment`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $ls1 ∩ ls2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $ls1 ∩ ls2 = ∅$`(false, v)`

iff $ls1 ∩ ls2 ≠ ∅$ and $v ∈ ls1 ∩ ls2$

**Algorithm**

The algorithm is inspired from here, which again is the special 2D case of a 3D algorithm by Ronald Goldman's article on the *Intersection of two lines in three-space* in Graphics Gems, Andrew S. (ed.), 1990.

We first check if the two line segments are parallel, and if so, if they are collinear. In the latter case, we check containment of any of the end points in the other line segment. Otherwise the lines are not parallel, so we can solve an equation of the intersection point, if it exists.

`Base.isdisjoint`

— Function```
isdisjoint(X::ConvexSet,
hp::Union{Hyperplane, Line2D},
[witness]::Bool=false
)
```

Check whether a compact set an a hyperplane do not intersect, and otherwise optionally compute a witness.

**Input**

`X`

– compact set`hp`

– hyperplane`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ∩ hp = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $X ∩ hp = ∅$`(false, v)`

iff $X ∩ hp ≠ ∅$ and $v ∈ X ∩ hp$

**Notes**

We assume that `X`

is compact. Otherwise, the support vector queries may fail.

**Algorithm**

A compact convex set intersects with a hyperplane iff the support function in the negative resp. positive direction of the hyperplane's normal vector $a$ is to the left resp. right of the hyperplane's constraint $b$:

\[-ρ(-a) ≤ b ≤ ρ(a)\]

For witness generation, we compute a line connecting the support vectors to the left and right, and then take the intersection of the line with the hyperplane. We follow this algorithm for the line-hyperplane intersection.

`Base.isdisjoint`

— Function`isdisjoint(X::ConvexSet, hs::HalfSpace, [witness]::Bool=false)`

Check whether a compact set an a half-space do not intersect, and otherwise optionally compute a witness.

**Input**

`X`

– compact set`hs`

– half-space`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ∩ hs = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $X ∩ hs = ∅$`(false, v)`

iff $X ∩ hs ≠ ∅$ and $v ∈ X ∩ hs$

**Notes**

We assume that `X`

is compact. Otherwise, the support vector queries may fail.

**Algorithm**

A compact convex set intersects with a half-space iff the support vector in the negative direction of the half-space's normal vector $a$ is contained in the half-space: $σ(-a) ∈ hs$. The support vector is thus also a witness.

Optional keyword arguments can be passed to the `ρ`

function. In particular, if `X`

is a lazy intersection, options can be passed to the line search algorithm.

`Base.isdisjoint`

— Function`isdisjoint(hs1::HalfSpace, hs2::HalfSpace, [witness]::Bool=false)`

Check whether two half-spaces do not intersect, and otherwise optionally compute a witness.

**Input**

`hs1`

– half-space`hs2`

– half-space`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $hs1 ∩ hs2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $hs1 ∩ hs2 = ∅$`(false, v)`

iff $hs1 ∩ hs2 ≠ ∅$ and $v ∈ hs1 ∩ hs2$

**Algorithm**

Two half-spaces do not intersect if and only if their normal vectors point in the opposite direction and there is a gap between the two defining hyperplanes.

The latter can be checked as follows: Let $hs_1 : a_1⋅x = b_1$ and $hs2 : a_2⋅x = b_2$. Then we already know that $a_2 = -k⋅a_1$ for some positive scaling factor $k$. Let $x_1$ be a point on the defining hyperplane of $hs_1$. We construct a line segment from $x_1$ to the point $x_2$ on the defining hyperplane of $hs_2$ by shooting a ray from $x_1$ with direction $a_1$. Thus we look for a factor $s$ such that $(x_1 + s⋅a_1)⋅a_2 = b_2$. This gives us $s = (b_2 - x_1⋅a_2) / (-k a_1⋅a_1)$. The gap exists if and only if $s$ is positive.

If the normal vectors do not point in opposite directions, then the defining hyperplanes intersect and we can produce a witness as follows. All points $x$ in this intersection satisfy $a_1⋅x = b_1$ and $a_2⋅x = b_2$. Thus we have $(a_1 + a_2)⋅x = b_1+b_2$. We now find a dimension where $a_1 + a_2$ is non-zero, say, $i$. Then the result is a vector with one non-zero entry in dimension $i$, defined as $[0, …, 0, (b_1 + b_2)/(a_1[i] + a_2[i]), 0, …, 0]$. Such a dimension $i$ always exists.

`Base.isdisjoint`

— Function```
isdisjoint(P::AbstractPolyhedron,
X::ConvexSet,
witness::Bool=false;
solver=nothing
)
```

Check whether two polyhedra do not intersect.

**Input**

`P`

– polyhedron`X`

– another set (see the Notes section below)`witness`

– (optional, default:`false`

) compute a witness if activated`solver`

– (optional, default:`nothing`

) the backend used to solve the linear program`algorithm`

– (optional, default:`"exact"`

) algorithm keyword, one of: *`"exact" (exact, uses a feasibility LP) *`

"sufficient" (sufficient, uses half-space checks)

**Output**

- If
`witness`

option is deactivated:`true`

iff $P ∩ X = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $P ∩ X = ∅$`(false, v)`

iff $P ∩ X ≠ ∅$ and $v ∈ P ∩ X$

**Notes**

For `algorithm == "exact"`

, we assume that `constraints_list(X)`

is defined. For `algorithm == "sufficient"`

, witness production is not supported.

For `solver == nothing`

we fall back to `default_lp_solver(N)`

.

**Algorithm**

For `algorithm == "exact"`

, see `isempty(P::HPoly, ::Bool)`

.

For `algorithm == "sufficient"`

, we rely on the intersection check between the set `X`

and each constraint in `P`

. This means one support function evaluation of `X`

for each constraint of `P`

. With the sufficiency algorithm, this function may return `false`

even in the case where the intersection is empty. On the other hand, if the algorithm returns `true`

, then it is guaranteed that the intersection is empty.

`Base.isdisjoint`

— Function`isdisjoint(cup::UnionSet, X::ConvexSet, [witness]::Bool=false)`

Check whether a union of two convex sets and another set do not intersect.

**Input**

`cup`

– union of two convex sets`X`

– another set

**Output**

`true`

iff $\text{cup} ∩ X = ∅$.

`Base.isdisjoint`

— Function`isdisjoint(cup::UnionSetArray, X::ConvexSet, [witness]::Bool=false)`

Check whether a union of a finite number of convex sets and another set do not intersect.

**Input**

`cup`

– union of a finite number of convex sets`X`

– another set

**Output**

`true`

iff $\text{cup} ∩ X = ∅$.

`Base.isdisjoint`

— Function`isdisjoint(U::Universe, X::ConvexSet, [witness]::Bool=false)`

Check whether a universe and another set do not intersect.

**Input**

`U`

– universe`X`

– another set

**Output**

`true`

iff $X ≠ ∅$.

`Base.isdisjoint`

— Function`isdisjoint(C::Complement, X::ConvexSet, [witness]::Bool=false)`

Check whether the complement of a convex set and another set do not intersect.

**Input**

`C`

– complement of a convex set`X`

– convex set

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ∩ C = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $X ∩ C = ∅$`(false, v)`

iff $X ∩ C ≠ ∅$ and $v ∈ X ∩ C$

**Algorithm**

We fall back to `X ⊆ C.X`

, which can be justified as follows:

\[ X ∩ Y^C = ∅ ⟺ X ⊆ Y\]

`Base.isdisjoint`

— Function```
isdisjoint(Z1::AbstractZonotope, Z2::AbstractZonotope,
witness::Bool=false)
```

Check whether two zonotopes do not intersect, and otherwise optionally compute a witness.

**Input**

`Z1`

– zonotope`Z2`

– zonotope`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $Z1 ∩ Z2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $Z1 ∩ Z2 = ∅$`(false, v)`

iff $Z1 ∩ Z2 ≠ ∅$ and $v ∈ Z1 ∩ Z2$

**Algorithm**

$Z1 ∩ Z2 = ∅$ iff $c_1 - c_2 ∉ Z(0, (g_1, g_2))$ where $c_i$ and $g_i$ are the center and generators of zonotope `Zi`

and $Z(c, g)$ represents the zonotope with center $c$ and generators $g$.

`Base.isdisjoint`

— Function`isdisjoint(I1::Interval, I2::Interval, witness::Bool=false)`

Check whether two intervals do not intersect, and otherwise optionally compute a witness.

**Input**

`I1`

– first interval`I2`

– second interval`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $I1 ∩ I2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $I1 ∩ I2 = ∅$`(false, v)`

iff $I1 ∩ I2 ≠ ∅$ and $v ∈ I1 ∩ I2$

**Algorithm**

$I1 ∩ I2 ≠ ∅$ iff there is a gap between the left-most point of the second interval and the left-most point of the first interval, or vice-versa.

A witness is computed by taking the maximum over the left-most points of each interval, which is guaranteed to belong to the intersection.

`Base.isdisjoint`

— Method`isdisjoint(cpa::CartesianProductArray, P::AbstractPolyhedron)`

Check whether a polytopic Cartesian product array intersects with a polyhedron.

**Input**

`cpa`

– Cartesian product array of polytopes`P`

– polyhedron

**Output**

`true`

iff $\text{cpa} ∩ Y = ∅$.

**Algorithm**

We first identify the blocks of `cpa`

in which `P`

is constrained. Then we project `cpa`

to those blocks and convert the result to an `HPolytope`

`Q`

. Finally we determine whether `Q`

and the projected `P`

intersect.

`Base.isdisjoint`

— Method`isdisjoint(X::CartesianProductArray, Y::CartesianProductArray)`

Check whether two Cartesian products of a finite number of convex sets do not intersect.

**Input**

`X`

– Cartesian product array of convex sets`Y`

– Cartesian product array of convex sets

**Output**

`true`

iff $X ∩ Y = ∅$.

`Base.isdisjoint`

— Function```
isdisjoint(cpa::CartesianProductArray,
H::AbstractHyperrectangle,
[witness]::Bool=false)
```

Check whether a Cartesian product of a finite number of convex sets and a hyperrectangular set do not intersect, and otherwise optionally compute a witness.

**Input**

`cpa`

– Cartesian product of a finite number of convex sets`H`

– hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $cpa ∩ H = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $cpa ∩ H = ∅$`(false, v)`

iff $cpa ∩ H ≠ ∅$ and $v ∈ cpa ∩ H$

**Algorithm**

The sets `cpa`

and `H`

are disjoint if and only if at least one block of `cpa`

and the corresponding projection of `H`

are disjoint. We perform these checks sequentially.

`Base.isdisjoint`

— Function`isdisjoint(L1::Line2D, L2::Line2D, witness::Bool=false)`

Check whether two two-dimensional lines do not intersect.

**Input**

`L1`

– line`L2`

– line

**Output**

- If
`witness`

option is deactivated:`true`

iff $L1 ∩ L2 = ∅$ - If
`witness`

option is activated:`(true, [])`

iff $L1 ∩ L2 = ∅$`(false, v)`

iff $L1 ∩ L2 ≠ ∅$ and $v ∈ L1 ∩ L2$

## Convex hull

`LazySets.convex_hull`

— Method```
convex_hull(X::ConvexSet{N}, Y::ConvexSet{N}; [algorithm]=nothing,
[backend]=nothing, [solver]=nothing) where {N}
```

Compute the convex hull of the given convex sets.

**Input**

`X`

– convex set`Y`

– convex set`algorithm`

– (optional, default:`nothing`

) the convex-hull algorithm`backend`

– (optional, default:`nothing`

) backend for polyhedral computations (used for higher-dimensional sets)`solver`

– (optional, default:`nothing`

) the linear-programming solver used in the backend

**Output**

If the input sets are one-dimensional, the result is an `Interval`

. If the input sets are two-dimensional, the result is a `VPolygon`

. Otherwise the result is a `VPolytope`

.

**Algorithm**

One-dimensional sets are resolved by using `overapproximate`

with an `Interval`

(which is exact). For higher-dimensional sets, we compute the vertices of both `X`

and `Y`

using `vertices_list`

and then compute the convex hull of the union of those vertices.

`LazySets.convex_hull`

— Method```
convex_hull(P1::HPoly, P2::HPoly;
[backend]=default_polyhedra_backend(P1))
```

Compute the convex hull of the set union of two polyhedra in H-representation.

**Input**

`P1`

– polyhedron`P2`

– another polyhedron`backend`

– (optional, default:`default_polyhedra_backend(P1)`

) the polyhedral computations backend

**Output**

The `HPolyhedron`

(resp. `HPolytope`

) obtained by the concrete convex hull of `P1`

and `P2`

.

**Notes**

For performance reasons, it is suggested to use the `CDDLib.Library()`

backend for the `convex_hull`

.

For further information on the supported backends see Polyhedra's documentation.

`LazySets.convex_hull`

— Method`convex_hull(P1::VPolytope, P2::VPolytope; [backend]=nothing)`

Compute the convex hull of the set union of two polytopes in V-representation.

**Input**

`P1`

– polytope`P2`

– another polytope`backend`

– (optional, default:`nothing`

) the polyhedral computations backend

**Output**

The `VPolytope`

obtained by the concrete convex hull of `P1`

and `P2`

.

**Notes**

This function takes the union of the vertices of each polytope and then relies on a concrete convex hull algorithm. For low dimensions, a specialized implementation for polygons is used. For higher dimensions, `convex_hull`

relies on the polyhedral backend that can be specified using the `backend`

keyword argument.

For performance reasons, it is suggested to use the `CDDLib.Library()`

backend.

`LazySets.convex_hull`

— Method`convex_hull(P::VPolygon, Q::VPolygon; [algorithm]::String="monotone_chain")`

Return the convex hull of two polygons in vertex representation.

**Input**

`P`

– polygon in vertex representation`Q`

– another polygon in vertex representation`algorithm`

– (optional, default: "monotone_chain") the algorithm used to compute the convex hull

**Output**

A new polygon such that its vertices are the convex hull of the given two polygons.

**Algorithm**

A convex hull algorithm is used to compute the convex hull of the vertices of the given input polygons `P`

and `Q`

; see `?convex_hull`

for details on the available algorithms. The vertices of the output polygon are sorted in counter-clockwise fashion.

`LazySets.convex_hull`

— Method```
convex_hull(points::Vector{VN};
[algorithm]=nothing,
[backend]=nothing,
[solver]=nothing
) where {N, VN<:AbstractVector{N}}
```

Compute the convex hull of the given points.

**Input**

`points`

– list of vectors`algorithm`

– (optional, default:`nothing`

) the convex-hull algorithm; see below for valid options`backend`

– (optional, default:`nothing`

) polyhedral computation backend for higher-dimensional point sets`solver`

– (optional, default:`nothing`

) the linear-programming solver used in the backend

**Output**

The convex hull as a list of vectors with the coordinates of the points.

**Algorithm**

A pre-processing step treats the cases with up to two points for one dimension and up to four points for two dimensions. For more points in one resp. two dimensions, we use more general algorithms.

For the one-dimensional case we return the minimum and maximum points, in that order.

The two-dimensional case is handled with a planar convex hull algorithm. The following algorithms are available:

`"monotone_chain"`

– compute the convex hull of points in the plane using Andrew's monotone chain method`"monotone_chain_sorted"`

– the same as`"monotone_chain"`

but assuming that the points are already sorted in counter-clockwise fashion

See the reference docstring of each of those algorithms for details.

The higher dimensional case is treated using the concrete polyhedra library `Polyhedra`

, that gives access to libraries such as `CDDLib`

and `ConvexHull.jl`

. These libraries can be chosen from the `backend`

argument.

**Notes**

For the in-place version use `convex_hull!`

instead of `convex_hull`

.

**Examples**

Compute the convex hull of a random set of points:

```
julia> points = [randn(2) for i in 1:30]; # 30 random points in 2D
julia> hull = convex_hull(points);
julia> typeof(hull)
Vector{Vector{Float64}} (alias for Array{Array{Float64, 1}, 1})
```

`convex_hull(U::UnionSetArray{N, PT}; kwargs...) where {N, PT<:AbstractPolytope{N}}`

Compute the convex hull of a union of a finite number of polytopes.

**Input**

`U`

– UnionSetArray of polytopes

**Output**

A list of the vertices of the convex hull.

`LazySets.convex_hull`

— Method```
convex_hull(points::Vector{VN};
[algorithm]=nothing,
[backend]=nothing,
[solver]=nothing
) where {N, VN<:AbstractVector{N}}
```

Compute the convex hull of the given points.

**Input**

`points`

– list of vectors`algorithm`

– (optional, default:`nothing`

) the convex-hull algorithm; see below for valid options`backend`

– (optional, default:`nothing`

) polyhedral computation backend for higher-dimensional point sets`solver`

– (optional, default:`nothing`

) the linear-programming solver used in the backend

**Output**

The convex hull as a list of vectors with the coordinates of the points.

**Algorithm**

A pre-processing step treats the cases with up to two points for one dimension and up to four points for two dimensions. For more points in one resp. two dimensions, we use more general algorithms.

For the one-dimensional case we return the minimum and maximum points, in that order.

The two-dimensional case is handled with a planar convex hull algorithm. The following algorithms are available:

`"monotone_chain"`

– compute the convex hull of points in the plane using Andrew's monotone chain method`"monotone_chain_sorted"`

– the same as`"monotone_chain"`

but assuming that the points are already sorted in counter-clockwise fashion

See the reference docstring of each of those algorithms for details.

The higher dimensional case is treated using the concrete polyhedra library `Polyhedra`

, that gives access to libraries such as `CDDLib`

and `ConvexHull.jl`

. These libraries can be chosen from the `backend`

argument.

**Notes**

For the in-place version use `convex_hull!`

instead of `convex_hull`

.

**Examples**

Compute the convex hull of a random set of points:

```
julia> points = [randn(2) for i in 1:30]; # 30 random points in 2D
julia> hull = convex_hull(points);
julia> typeof(hull)
Vector{Vector{Float64}} (alias for Array{Array{Float64, 1}, 1})
```

`convex_hull(U::UnionSetArray{N, PT}; kwargs...) where {N, PT<:AbstractPolytope{N}}`

Compute the convex hull of a union of a finite number of polytopes.

**Input**

`U`

– UnionSetArray of polytopes

**Output**

A list of the vertices of the convex hull.

`LazySets.monotone_chain!`

— Function```
monotone_chain!(points::Vector{VN}; sort::Bool=true
) where {N, VN<:AbstractVector{N}}
```

Compute the convex hull of points in the plane using Andrew's monotone chain method.

**Input**

`points`

– list of 2D vectors; is sorted in-place inside this function`sort`

– (optional, default:`true`

) flag for sorting the vertices lexicographically; sortedness is required for correctness

**Output**

List of vectors containing the 2D coordinates of the corner points of the convex hull.

**Notes**

For large sets of points, it is convenient to use static vectors to get maximum performance. For information on how to convert usual vectors into static vectors, see the type `SVector`

provided by the StaticArrays package.

**Algorithm**

This function implements Andrew's monotone chain convex hull algorithm to construct the convex hull of a set of $n$ points in the plane in $O(n \log n)$ time. For further details see Monotone chain

## Intersection of two sets

`LazySets.intersection`

— Method`intersection(S::AbstractSingleton, X::ConvexSet)`

Return the intersection of a singleton with another set.

**Input**

`S`

– singleton`X`

– another set

**Output**

If the sets intersect, the result is `S`

. Otherwise, the result is the empty set.

`LazySets.intersection`

— Method`intersection(L1::Line2D, L2::Line2D)`

Return the intersection of two two-dimensional lines.

**Input**

`L1`

– first line`L2`

– second line

**Output**

Three outcomes are possible:

- If the lines are identical, the result is the first line.
- If the lines are parallel and not identical, the result is the empty set.
- Otherwise the result is the only intersection point.

**Algorithm**

We first check whether the lines are parallel. If not, we use Cramer's rule to compute the intersection point.

**Examples**

The line $y = -x + 1$ intersected with the line $y = x$:

```
julia> intersection(Line2D([-1., 1.], 0.), Line2D([1., 1.], 1.))
Singleton{Float64, Vector{Float64}}([0.5, 0.5])
julia> intersection(Line2D([1., 1.], 1.), Line2D([1., 1.], 1.))
Line2D{Float64, Vector{Float64}}([1.0, 1.0], 1.0)
```

`LazySets.intersection`

— Method`intersection(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)`

Return the intersection of two hyperrectangles.

**Input**

`H1`

– first hyperrectangle`H2`

– second hyperrectangle

**Output**

If the hyperrectangles do not intersect, the result is the empty set. Otherwise the result is the hyperrectangle that describes the intersection.

**Algorithm**

In each isolated direction `i`

we compute the rightmost left border and the leftmost right border of the hyperrectangles. If these borders contradict, then the intersection is empty. Otherwise the result uses these borders in each dimension.

`LazySets.intersection`

— Method`intersection(x::Interval, y::Interval)`

Return the intersection of two intervals.

**Input**

`x`

– first interval`y`

– second interval

**Output**

If the intervals do not intersect, the result is the empty set. Otherwise the result is the interval that describes the intersection.

`LazySets.intersection`

— Method`intersection(X::Interval, hs::HalfSpace)`

Compute the intersection of an interval and a half-space.

**Input**

`X`

– interval`hs`

– half-space

**Output**

If the sets do not intersect, the result is the empty set. If the interval is fully contained in the half-space, the result is the original interval. Otherwise the result is the interval that describes the intersection.

**Algorithm**

We first handle the special case that the normal vector `a`

of `hs`

is close to zero. Then we distinguish the cases that `hs`

is a lower or an upper bound.

`LazySets.intersection`

— Method`intersection(X::Interval, hp::Hyperplane)`

Compute the intersection of an interval and a hyperplane.

**Input**

`X`

– interval`hp`

– hyperplane

**Output**

If the sets do not intersect, the result is the empty set. Otherwise the result is the singleton that describes the intersection.

`LazySets.intersection`

— Method`intersection(X::Interval, Y::ConvexSet)`

Compute the intersection of an interval and a convex set.

**Input**

`X`

– interval`Y`

– convex set

**Output**

If the sets do not intersect, the result is the empty set. Otherwise the result is the interval that describes the intersection, which may be of type `Singleton`

if the intersection is very small.

`LazySets.intersection`

— Method`intersection(P1::AbstractHPolygon, P2::AbstractHPolygon; [prune]::Bool=true)`

Return the intersection of two polygons in constraint representation.

**Input**

`P1`

– first polygon`P2`

– second polygon`prune`

– (optional, default:`true`

) flag for removing redundant constraints

**Output**

If the polygons do not intersect, the result is the empty set. Otherwise the result is the polygon that describes the intersection.

**Algorithm**

We just combine the constraints of both polygons. To obtain a linear-time algorithm, we interleave the constraints. If there are two constraints with the same normal vector, we choose the tighter one.

Redundancy of constraints is checked with `remove_redundant_constraints!(::AbstractHPolygon)`

.

`LazySets.intersection`

— Method```
intersection(P1::AbstractPolyhedron{N},
P2::AbstractPolyhedron{N};
[backend]=default_lp_solver(N),
[prune]::Bool=true) where {N}
```

Compute the intersection of two polyhedra.

**Input**

`P1`

– polyhedron`P2`

– polyhedron`backend`

– (optional, default:`default_lp_solver(N)`

) the LP solver used for the removal of redundant constraints; see the`Notes`

section below for details`prune`

– (optional, default:`true`

) flag for removing redundant constraints

**Output**

An `HPolyhedron`

resulting from the intersection of `P1`

and `P2`

, with the redundant constraints removed, or an empty set if the intersection is empty. If one of the arguments is a polytope, the result is an `HPolytope`

instead.

**Notes**

The default value of the solver backend is `default_lp_solver(N)`

and it is used to run a feasiblity LP to remove the redundant constraints of the intersection.

If you want to use the `Polyhedra`

library, pass an appropriate backend. For example, to use the default Polyhedra library use `default_polyhedra_backend(P)`

or use `CDDLib.Library()`

for the CDD library.

There are some shortcomings of the removal of constraints using the default Polyhedra library; see e.g. #1038 and Polyhedra#146. It is safer to check for emptiness of intersection before calling this function in those cases.

**Algorithm**

This implementation unifies the constraints of the two sets obtained from the `constraints_list`

method.

`LazySets.intersection`

— Method```
intersection(P1::Union{VPolygon, VPolytope}, P2::Union{VPolygon, VPolytope};
[backend]=nothing,
[prunefunc]=(X -> removevredundancy!(X; ztol=_ztol(eltype(P1)))))
```

Compute the intersection of two polytopes in vertex representation.

**Input**

`P1`

– polytope in vertex representation`P2`

– polytope in vertex representation`backend`

– (optional, default:`nothing`

) the backend for polyhedral computations`prunefunc`

– (optional, default:`(X -> removevredundancy!(X; ztol=_ztol(eltype(P1))))!`

) function to prune the vertices of the result

**Output**

A `VPolytope`

.

`LazySets.intersection`

— Method`intersection(P1::VPolygon, P2::VPolygon; apply_convex_hull::Bool=true)`

Compute the intersection of two polygons in vertex representation.

**Input**

`P1`

– polygon in vertex representation`P2`

– polygon in vertex representation`apply_convex_hull`

– (default, optional:`true`

) use the flag to skip the computation of the convex hull in the resulting`VPolygon`

**Output**

A `VPolygon`

or an `EmptySet`

if the intersection is empty.

**Algorithm**

This function applies the Sutherland–Hodgman polygon clipping algorithm. The implementation is based on the one found in rosetta code.

`LazySets.intersection`

— Method`intersection(cup::UnionSet, X::ConvexSet)`

Return the intersection of a union of two convex sets and another convex set.

**Input**

`cup`

– union of two convex sets`X`

– convex set

**Output**

The union of the pairwise intersections, expressed as a `UnionSet`

. If one of those sets is empty, only the other set is returned.

`LazySets.intersection`

— Method`intersection(cup::UnionSetArray, X::ConvexSet)`

Return the intersection of a union of a finite number of convex sets and another convex set.

**Input**

`cup`

– union of a finite number of convex sets`X`

– convex set

**Output**

The union of the pairwise intersections, expressed as a `UnionSetArray`

.

`LazySets.intersection`

— Method`intersection(U::Universe, X::ConvexSet)`

Return the intersection of a universe and a convex set.

**Input**

`U`

– universe`X`

– convex set

**Output**

The set `X`

.

`LazySets.intersection`

— Method`intersection(P::AbstractPolyhedron, rm::ResetMap)`

Return the intersection of a polyhedron and a polyhedral reset map.

**Input**

`P`

– polyhedron`rm`

– polyhedral reset map

**Output**

A polyhedron.

**Notes**

We assume that `rm`

is polyhedral, i.e., has a `constraints_list`

method defined.

`LazySets.intersection`

— Method` intersection(X::CartesianProductArray, Y::CartesianProductArray)`

Return the intersection between cartesian products of a finite number of convex sets.

**Input**

`X`

– cartesian product of a finite number of convex sets`Y`

– cartesian product of a finite number of convex sets

**Output**

The decomposed set which represents concrete intersection between `X`

and `Y`

**Algorithm**

This algorithm intersect corresponding blocks between sets.

`LazySets.intersection`

— Method`intersection(L::LinearMap, S::ConvexSet)`

Return the intersection of a lazy linear map and a convex set.

**Input**

`L`

– linear map`S`

– convex set

**Output**

The polytope obtained by the intersection of `l.M * L.X`

and `S`

.

`LazySets.intersection`

— Method`intersection(cpa::CartesianProductArray, P::AbstractPolyhedron)`

Compute the intersection of a Cartesian product of a finite number of polyhedral sets with a polyhedron.

**Input**

`cpa`

– Cartesian product of a finite number of polyhedral sets`P`

– polyhedron

**Output**

A Cartesian product of a finite number of polyhedral sets. See the *Algorithm* section below for details about the structure.

**Notes**

The restriction to polyhedral sets in `cpa`

only applies to the blocks that are actually intersected with `P`

(see the *Algorithm* section below for details). All other blocks are not considered by the intersection and remain identical.

**Algorithm**

The underlying idea of the algorithm is to exploit the unconstrained dimensions of `P`

. Without loss of generality, assume that `cpa`

has the structure $X × Y × Z$ such that only the dimensions of $Y$ are constrained in $P$, and denoting a suitable projection of $P$ to the dimensions of $Y$ with $P|_Y$, we have the following equivalence:

\[ (X × Y × Z) ∩ P = X × (Y ∩ P|_Y) × Z\]

Note that $Y$ may still consist of many blocks. However, due to the structural restriction of a Cartesian product, we cannot break down this set further even if $P|_Y$ is still unconstrained in some dimensions of blocks in $Y$. This would require a restructuring of the dimensions. Consider this example:

\[ Y := [0, 1] × [1, 2] × [2, 3] P|_Y := x₁ + x₃ ≤ 2 Y ∩ P|_Y = 0 ≤ x₁ ∧ 1 ≤ x₂ ≤ 2 ∧ 2 ≤ x₃ ∧ x₁ + x₃ ≤ 2\]

Even though the constraints of dimension $x₂$ are decoupled from the rest, due to the last constraint the Cartesian product cannot be broken down further. In particular, the result $Y ∩ P|_Y$ is a polyhedron in this implementation.

Now we explain the implementation of the above idea. We first identify the dimensions in which `P`

is constrained. Then we identify the block dimensions of $X × Y × Z$ such that $Y$ has minimal dimension. Finally, we convert $Y$ to a polyhedron and intersect it with a suitable projection of `P`

.

`LazySets.intersection`

— Method`intersection(a::LineSegment, b::Line2D)`

Compute the intersection of a line and a line segment in two dimensions.

**Input**

`a`

– LineSegment`b`

– Line2D

**Output**

If the sets do not intersect, the result is the empty set. Otherwise the result is the singleton or line segment that describes the intersection.

`LazySets.intersection`

— Method`intersection(a::LineSegment, b::LineSegment)`

Return the intersection of two two-dimensional line segments.

**Input**

`a`

– first line segment`b`

– second line segment

**Output**

A singleton, line segment or the empty set depending on the result of the intersection.

**Notes**

If the line segments cross, or are parallel and have one point in common, that point is returned.

If the line segments are parallel and have a line segment in common, that segment is returned.

Otherwise, if there is no intersection, an empty set is returned.

`LazySets.intersection`

— Method```
intersection(Z::AbstractZonotope{N}, H::HalfSpace{N};
[backend]=default_lp_solver(N), [prune]::Bool=true) where {N}
```

Return the intersection between a zonotopic set and a halfspace.

**Input**

`Z`

– zonotopic set`H`

– half-space`backend`

– (optional, default:`default_lp_solver(N)`

) the LP solver used for the removal of redundant constraints`prune`

– (optional, default:`true`

) flag for removing redundant constraints

**Output**

If the sets do not intersect, the output is the empty set, if the zonotopic set is fully contained in the halfspace, the zonotopic set is returned, otherwise the output is the concrete intersection between `Z`

and `H`

.

**Algorithm**

First there is a disjointness test, if that is false, there is an inclusion test, if that is false then the concrete intersection is computed.

## Minkowski sum

`LazySets.minkowski_sum`

— Method```
minkowski_sum(P::ConvexSet, Q::ConvexSet;
[backend]=nothing,
[algorithm]=nothing,
[prune]=true)
```

Concrete Minkowski sum for a pair of lazy sets using their constraint representation.

**Input**

`P`

– lazy set`Q`

– another lazy set`backend`

– (optional, default:`nothing`

) polyhedral computations backend`algorithm`

– (optional, default:`nothing`

) algorithm to compute the elimination of variables; available options are`Polyhedra.FourierMotzkin`

,`Polyhedra.BlockElimination`

, and`Polyhedra.ProjectGenerators`

`prune`

– (optional, default:`true`

) if`true`

, apply a post-processing algorithm to remove redundant constraints

**Output**

In two dimensions the result is a `VPolygon`

. In higher dimensions, the result is an `HPolytope`

if both `P`

and `Q`

are bounded, and an `HPolyhedron`

otherwise.

**Notes**

This function requires that the list of constraints of both lazy sets `P`

and `Q`

can be obtained. After obtaining the respective lists of constraints, the `minkowski_sum`

function for polyhedral sets is used. For details see `minkowski_sum(::VPolytope, ::VPolytope)`

.

This method requires to load the packages `Polyhedra`

and `CDDLib`

, like so:

```
julia> using LazySets, Polyhedra, CDDLib
julia> ...
julia> minkowski_sum(P, Q)
```

`LazySets.minkowski_sum`

— Method```
minkowski_sum(P::AbstractPolyhedron, Q::AbstractPolyhedron;
[backend]=nothing,
[algorithm]=nothing,
[prune]=true)
```

Compute the Minkowski sum between two polyhedra in constraint representation.

**Input**

`P`

– polyhedron in constraint representation`Q`

– another polyhedron in constraint representation`backend`

– (optional, default:`nothing`

) polyhedral computations backend`algorithm`

– (optional, default:`nothing`

) algorithm to compute the elimination of variables; available options are`Polyhedra.FourierMotzkin`

,`Polyhedra.BlockElimination`

, and`Polyhedra.ProjectGenerators`

`prune`

– (optional, default:`true`

) if`true`

, apply a post-processing algorithm to remove redundant constraints

**Output**

A polyhedron in H-representation that corresponds to the Minkowski sum of `P`

and `Q`

.

**Notes**

This method requires to load the packages `Polyhedra`

and `CDDLib`

, like so:

```
julia> using LazySets, Polyhedra, CDDLib
julia> ...
julia> minkowski_sum(P, Q)
```

**Algorithm**

This function implements the concrete Minkowski sum by projection and variable elimination as detailed in [1]. The idea is that if we write $P$ and $Q$ in *simple H-representation*, that is, $P = \{x ∈ \mathbb{R}^n : Ax ≤ b \}$ and $Q = \{x ∈ \mathbb{R}^n : Cx ≤ d \}$, then their Minkowski sum can be seen as the projection onto the first $n$-dimensional coordinates of the polyhedron

\[ \begin{pmatrix} 0 & A \ C & -C \end{pmatrix} \binom{x}{y} ≤ inom{b}{d}\]

This is seen by noting that $P ⊕ Q$ corresponds to the set of points $x ∈ \mathbb{R}^n$ such that $x = y + z$ with $Ay ≤ b$ and $Cz ≤ d$; hence it follows that $Ay ≤ b$ and $C(x-y) ≤ d$, and the inequality displayed above follows by considering the $2n$-dimensional space $\binom{x}{y}$. The reduction from $2n$ to $n$ variables is performed using an elimination algorithm as described next.

The elimination of variables depends on the concrete polyhedra library `Polyhedra`

, which itself uses `CDDLib`

for variable elimination. The available algorithms are:

`Polyhedra.FourierMotzkin`

– computation of the projection by computing the H-representation and applying the Fourier-Motzkin elimination algorithm to it`Polyhedra.BlockElimination`

– computation of the projection by computing the H-representation and applying the block elimination algorithm to it`Polyhedra.ProjectGenerators`

– computation of the projection by computing the V-representation

[1] Kvasnica, Michal. "Minkowski addition of convex polytopes." (2005): 1-10.

`LazySets.minkowski_sum`

— Method```
minkowski_sum(P1::VPolytope, P2::VPolytope;
[apply_convex_hull]=true,
[backend]=nothing,
[solver]=nothing)
```

Compute the Minkowski sum between two polytopes in vertex representation.

**Input**

`P1`

– polytope`P2`

– another polytope`apply_convex_hull`

– (optional, default:`true`

) if`true`

, post-process the pairwise sums using a convex hull algorithm`backend`

– (optional, default:`nothing`

) the backend for polyhedral computations used to post-process with a convex hull; see`default_polyhedra_backend(P1)`

`solver`

– (optional, default:`nothing`

) the backend used to solve the linear program; see`default_lp_solver_polyhedra(N)`

**Output**

A new polytope in vertex representation whose vertices are the convex hull of the sum of all possible sums of vertices of `P1`

and `P2`

.

`LazySets.minkowski_sum`

— Method`minkowski_sum(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)`

Concrete Minkowski sum of a pair of hyperrectangular sets.

**Input**

`H1`

– hyperrectangular set`H2`

– hyperrectangular set

**Output**

A `Hyperrectangle`

corresponding to the concrete Minkowski sum of `H1`

and `H2`

.

**Algorithm**

The resulting hyperrectangle is obtained by summing up the centers and radiuses of `H1`

and `H2`

.

`LazySets.minkowski_sum`

— Method`minkowski_sum(Z1::AbstractZonotope, Z2::AbstractZonotope)`

Concrete Minkowski sum of a pair of zonotopic sets.

**Input**

`Z1`

– zonotopic set`Z2`

– zonotopic set

**Output**

A `Zonotope`

corresponding to the concrete Minkowski sum of `Z1`

and `Z2`

.

**Algorithm**

The resulting zonotope is obtained by summing up the centers and concatenating the generators of `Z1`

and `Z2`

.

`LazySets.minkowski_sum`

— Method`minkowski_sum(P::VPolygon, Q::VPolygon)`

The Minkowski Sum of two polygon in vertex representation.

**Input**

`P`

– polygon in vertex representation`Q`

– another polygon in vertex representation

**Output**

A polygon in vertex representation.

**Algorithm**

We treat each edge of the polygons as a vector, attaching them in polar order (attaching the tail of the next vector to the head of the previous vector). The resulting polygonal chain will be a polygon, which is the Minkowski sum of the given polygons. This algorithm assumes that the vertices of P and Q are sorted in counter-clockwise fashion and has linear complexity O(m+n) where m and n are the number of vertices of P and Q respectively.

`LazySets.minkowski_sum`

— Method`minkowski_sum(PZ::DensePolynomialZonotope, Z::AbstractZonotope)`

Return the Minkowski sum of a polynomial zonotope and a usual zonotopic set.

**Input**

`PZ`

– polynomial zonotope`Z`

– usual zonotopic set

**Output**

A polynomial zonotope whose center is the sum of the centers of `PZ`

and `Z`

and whose generators are the concatenation of the generators of `PZ`

and `Z`

.

`LazySets.minkowski_sum`

— Method`minkowski_sum(x::Interval, y::Interval)`

Concrete Minkowski sum of a pair of intervals.

**Input**

`x`

– hyperrectangular set`y`

– hyperrectangular set

**Output**

An `Interval`

corresponding to the concrete Minkowski sum of `x`

and `y`

.

**Algorithm**

The function takes the sum of `x`

and `y`

following the rules of interval arithmetic.

`LazySets.minkowski_sum`

— Method`minkowski_sum(X::AbstractSingleton, Y::AbstractSingleton)`

Concrete Minkowski sum of a pair of singletons.

**Input**

`X`

– singleton`Y`

– singleton

**Output**

A singleton

**Algorithm**

The singleton obtained by summing the elements in `X`

and `Y`

.

## Minkowski difference

`LazySets.minkowski_difference`

— Method`minkowski_difference(P::ConvexSet, Q::ConvexSet)`

Concrete Minkowski difference (geometric difference) for a pair of convex sets.

**Input**

`P`

– polytopic set`Q`

– compact convex set that is subtracted from`P`

**Output**

An `HPolytope`

that corresponds to the Minkowski difference of `P`

minus `Q`

if `P`

is bounded, and an `HPolyhedron`

if `P`

is unbounded.

**Notes**

This function requires that the list of constraints of the set `P`

is available and that the set `Q`

is bounded.

**Algorithm**

This function implements Theorem 2.3 in [1], which we state next.

Suppose $P$ is a polyhedron

\[P = \{z ∈ ℝ^n: sᵢᵀz ≤ rᵢ,~i = 1, …, N\}.\]

where $sᵢ ∈ ℝ^n, sᵢ ≠ 0$, and $rᵢ ∈ ℝ$. Assume $ρ(sᵢ,Q)$ is defined for $i = 1, …, N$. Then,

\[P ⊖ Q = \{z ∈ ℝ^n: sᵢᵀz ≤ rᵢ - ρ(sᵢ,Q),~i = 1, …, N\}.\]

where $⊖$ is defined as $P ⊖ Q = \{z ∈ ℝ^n: z + v ∈ P ~∀~v ∈ Q\}$ and is called the *Minkowski difference* (also referenced as *Pontryagin difference*, or geometric difference). It is denoted in [1] as the operation `P ~ Q`

.

[1] Ilya Kolmanovsky and Elmer G. Gilbert (1997). *Theory and computation of disturbance invariant sets for discrete-time linear systems.* Mathematical Problems in Engineering Volume 4, Issue 4, Pages 317-367.

`LazySets.pontryagin_difference`

— Function`pontryagin_difference(P::ConvexSet, Q::ConvexSet)`

An alias for the function `minkowski_difference`

.

**Notes**

Due to inconsistent naming conventions, both the name *Minkowski difference* and *Pontryagin difference* are used to refer to the geometric difference of two sets.

## Subset check

`Base.issubset`

— Function`issubset(X::ConvexSet, Y::ConvexSet, [witness]::Bool=false, args...)`

Alias for `⊆`

(inclusion check).

**Input**

`X`

– set`Y`

– set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ Y$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ Y$`(false, v)`

iff $X ⊈ Y$ and $v ∈ X \setminus Y$

**Notes**

For more documentation see `⊆`

.

`Base.:⊆`

— Function`⊆(X::ConvexSet, P::ConvexSet, [witness]::Bool=false)`

Check whether a set is contained in a polyhedral set, and if not, optionally compute a witness.

**Input**

`X`

– inner set`Y`

– outer polyhedral set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ X \setminus P$

**Notes**

We require that `constraints_list(P)`

is available.

**Algorithm**

We check inclusion of `X`

in every constraint of `P`

.

`Base.:⊆`

— Function`⊆(S::ConvexSet, H::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a convex set is contained in a hyperrectangular set, and if not, optionally compute a witness.

**Input**

`S`

– inner convex set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ⊆ H$ - If
`witness`

option is activated:`(true, [])`

iff $S ⊆ H$`(false, v)`

iff $S ⊈ H$ and $v ∈ S \setminus H$

**Algorithm**

$S ⊆ H$ iff $\operatorname{ihull}(S) ⊆ H$, where $\operatorname{ihull}$ is the interval hull operator.

`Base.:⊆`

— Function```
⊆(P::AbstractPolytope, S::ConvexSet, [witness]::Bool=false;
algorithm=_default_issubset(P, S))
```

Check whether a polytope is contained in a convex set, and if not, optionally compute a witness.

**Input**

`P`

– inner polytope`S`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated`algorithm`

– (optional, default:`"constraints"`

if the constraints list of`S`

is available, otherwise`"vertices"`

) algorithm for the inclusion check; available options are:`"constraints"`

, using the list of constraints of`P`

and support function evaluations of`S`

`"vertices"`

, using the list of vertices of`P`

and membership evaluations of`S`

**Output**

- If
`witness`

option is deactivated:`true`

iff $P ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $P ⊆ S$`(false, v)`

iff $P ⊈ S$ and $v ∈ P \setminus S$

**Algorithm**

Since $S$ is convex, $P ⊆ S$ iff $v_i ∈ S$ for all vertices $v_i$ of $P$.

`Base.:⊆`

— Function`⊆(X::ConvexSet, P::ConvexSet, [witness]::Bool=false)`

Check whether a set is contained in a polyhedral set, and if not, optionally compute a witness.

**Input**

`X`

– inner set`Y`

– outer polyhedral set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ X \setminus P$

**Notes**

We require that `constraints_list(P)`

is available.

**Algorithm**

We check inclusion of `X`

in every constraint of `P`

.

`⊆(S::ConvexSet, H::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a convex set is contained in a hyperrectangular set, and if not, optionally compute a witness.

**Input**

`S`

– inner convex set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ⊆ H$ - If
`witness`

option is activated:`(true, [])`

iff $S ⊆ H$`(false, v)`

iff $S ⊈ H$ and $v ∈ S \setminus H$

**Algorithm**

$S ⊆ H$ iff $\operatorname{ihull}(S) ⊆ H$, where $\operatorname{ihull}$ is the interval hull operator.

```
⊆(P::AbstractPolytope, S::ConvexSet, [witness]::Bool=false;
algorithm=_default_issubset(P, S))
```

Check whether a polytope is contained in a convex set, and if not, optionally compute a witness.

**Input**

`P`

– inner polytope`S`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated`algorithm`

– (optional, default:`"constraints"`

if the constraints list of`S`

is available, otherwise`"vertices"`

) algorithm for the inclusion check; available options are:`"constraints"`

, using the list of constraints of`P`

and support function evaluations of`S`

`"vertices"`

, using the list of vertices of`P`

and membership evaluations of`S`

**Output**

- If
`witness`

option is deactivated:`true`

iff $P ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $P ⊆ S$`(false, v)`

iff $P ⊈ S$ and $v ∈ P \setminus S$

**Algorithm**

Since $S$ is convex, $P ⊆ S$ iff $v_i ∈ S$ for all vertices $v_i$ of $P$.

`⊆(X::ConvexSet, P::AbstractPolyhedron, [witness]::Bool=false)`

Check whether a convex set is contained in a polyhedron, and if not, optionally compute a witness.

**Input**

`X`

– inner convex set`P`

– outer polyhedron (including a half-space)`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ P \setminus X$

**Algorithm**

Since $X$ is convex, we can compare the support function of $X$ and $P$ in each direction of the constraints of $P$.

For witness generation, we use the support vector in the first direction where the above check fails.

`Base.:⊆`

— Method`⊆(X::ConvexSet, P::ConvexSet, [witness]::Bool=false)`

Check whether a set is contained in a polyhedral set, and if not, optionally compute a witness.

**Input**

`X`

– inner set`Y`

– outer polyhedral set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ X \setminus P$

**Notes**

We require that `constraints_list(P)`

is available.

**Algorithm**

We check inclusion of `X`

in every constraint of `P`

.

`⊆(S::ConvexSet, H::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a convex set is contained in a hyperrectangular set, and if not, optionally compute a witness.

**Input**

`S`

– inner convex set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ⊆ H$ - If
`witness`

option is activated:`(true, [])`

iff $S ⊆ H$`(false, v)`

iff $S ⊈ H$ and $v ∈ S \setminus H$

**Algorithm**

$S ⊆ H$ iff $\operatorname{ihull}(S) ⊆ H$, where $\operatorname{ihull}$ is the interval hull operator.

```
⊆(P::AbstractPolytope, S::ConvexSet, [witness]::Bool=false;
algorithm=_default_issubset(P, S))
```

Check whether a polytope is contained in a convex set, and if not, optionally compute a witness.

**Input**

`P`

– inner polytope`S`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated`algorithm`

– (optional, default:`"constraints"`

if the constraints list of`S`

is available, otherwise`"vertices"`

) algorithm for the inclusion check; available options are:`"constraints"`

, using the list of constraints of`P`

and support function evaluations of`S`

`"vertices"`

, using the list of vertices of`P`

and membership evaluations of`S`

**Output**

- If
`witness`

option is deactivated:`true`

iff $P ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $P ⊆ S$`(false, v)`

iff $P ⊈ S$ and $v ∈ P \setminus S$

**Algorithm**

Since $S$ is convex, $P ⊆ S$ iff $v_i ∈ S$ for all vertices $v_i$ of $P$.

`⊆(X::ConvexSet, P::AbstractPolyhedron, [witness]::Bool=false)`

Check whether a convex set is contained in a polyhedron, and if not, optionally compute a witness.

**Input**

`X`

– inner convex set`P`

– outer polyhedron (including a half-space)`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ P \setminus X$

**Algorithm**

Since $X$ is convex, we can compare the support function of $X$ and $P$ in each direction of the constraints of $P$.

For witness generation, we use the support vector in the first direction where the above check fails.

`⊆(Z::AbstractZonotope, H::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a zonotopic set is contained in a hyperrectangular set.

**Input**

`Z`

– inner zonotopic set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

`true`

iff $Z ⊆ H$ otherwise `false`

**Algorithm**

Algorithm based on Lemma 3.1 of [1]

[1] Mitchell, I. M., Budzis, J., & Bolyachevets, A. (2019, April). Invariant, viability and discriminating kernel under-approximation via zonotope scaling. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control (pp. 268-269).

`Base.:⊆`

— Function`⊆(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a given hyperrectangular set is contained in another hyperrectangular set, and if not, optionally compute a witness.

**Input**

`H1`

– inner hyperrectangular set`H2`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $H1 ⊆ H2$ - If
`witness`

option is activated:`(true, [])`

iff $H1 ⊆ H2$`(false, v)`

iff $H1 ⊈ H2$ and $v ∈ H1 \setminus H2$

**Algorithm**

$H1 ⊆ H2$ iff $c_1 + r_1 ≤ c_2 + r_2 ∧ c_1 - r_1 ≥ c_2 - r_2$ iff $r_1 - r_2 ≤ c_1 - c_2 ≤ -(r_1 - r_2)$, where $≤$ is taken component-wise.

`Base.:⊆`

— Function`⊆(X::ConvexSet, P::AbstractPolyhedron, [witness]::Bool=false)`

Check whether a convex set is contained in a polyhedron, and if not, optionally compute a witness.

**Input**

`X`

– inner convex set`P`

– outer polyhedron (including a half-space)`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ P \setminus X$

**Algorithm**

Since $X$ is convex, we can compare the support function of $X$ and $P$ in each direction of the constraints of $P$.

For witness generation, we use the support vector in the first direction where the above check fails.

`Base.:⊆`

— Function`⊆(S::AbstractSingleton, X::ConvexSet, [witness]::Bool=false)`

Check whether a given set with a single value is contained in a convex set, and if not, optionally compute a witness.

**Input**

`S`

– inner set with a single value`X`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ⊆ X$ - If
`witness`

option is activated:`(true, [])`

iff $S ⊆ X$`(false, v)`

iff $S ⊈ X$ and $v ∈ S \setminus X$

`Base.:⊆`

— Function`⊆(X::ConvexSet, P::ConvexSet, [witness]::Bool=false)`

Check whether a set is contained in a polyhedral set, and if not, optionally compute a witness.

**Input**

`X`

– inner set`Y`

– outer polyhedral set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ X \setminus P$

**Notes**

We require that `constraints_list(P)`

is available.

**Algorithm**

We check inclusion of `X`

in every constraint of `P`

.

`⊆(S::ConvexSet, H::AbstractHyperrectangle, [witness]::Bool=false)`

**Input**

`S`

– inner convex set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ⊆ H$ - If
`witness`

option is activated:`(true, [])`

iff $S ⊆ H$`(false, v)`

iff $S ⊈ H$ and $v ∈ S \setminus H$

**Algorithm**

`⊆(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a given hyperrectangular set is contained in another hyperrectangular set, and if not, optionally compute a witness.

**Input**

`H1`

– inner hyperrectangular set`H2`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $H1 ⊆ H2$ - If
`witness`

option is activated:`(true, [])`

iff $H1 ⊆ H2$`(false, v)`

iff $H1 ⊈ H2$ and $v ∈ H1 \setminus H2$

**Algorithm**

$H1 ⊆ H2$ iff $c_1 + r_1 ≤ c_2 + r_2 ∧ c_1 - r_1 ≥ c_2 - r_2$ iff $r_1 - r_2 ≤ c_1 - c_2 ≤ -(r_1 - r_2)$, where $≤$ is taken component-wise.

```
⊆(P::AbstractPolytope, S::ConvexSet, [witness]::Bool=false;
algorithm=_default_issubset(P, S))
```

Check whether a polytope is contained in a convex set, and if not, optionally compute a witness.

**Input**

`P`

– inner polytope`S`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated`algorithm`

– (optional, default:`"constraints"`

if the constraints list of`S`

is available, otherwise`"vertices"`

) algorithm for the inclusion check; available options are:`"constraints"`

, using the list of constraints of`P`

and support function evaluations of`S`

`"vertices"`

, using the list of vertices of`P`

and membership evaluations of`S`

**Output**

- If
`witness`

option is deactivated:`true`

iff $P ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $P ⊆ S$`(false, v)`

iff $P ⊈ S$ and $v ∈ P \setminus S$

**Algorithm**

Since $S$ is convex, $P ⊆ S$ iff $v_i ∈ S$ for all vertices $v_i$ of $P$.

`⊆(X::ConvexSet, P::AbstractPolyhedron, [witness]::Bool=false)`

Check whether a convex set is contained in a polyhedron, and if not, optionally compute a witness.

**Input**

`X`

– inner convex set`P`

– outer polyhedron (including a half-space)`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ P \setminus X$

**Algorithm**

`⊆(S::AbstractSingleton, X::ConvexSet, [witness]::Bool=false)`

Check whether a given set with a single value is contained in a convex set, and if not, optionally compute a witness.

**Input**

`S`

– inner set with a single value`X`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ⊆ X$ - If
`witness`

option is activated:`(true, [])`

iff $S ⊆ X$`(false, v)`

iff $S ⊈ X$ and $v ∈ S \setminus X$

`⊆(Z::AbstractZonotope, H::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a zonotopic set is contained in a hyperrectangular set.

**Input**

`Z`

– inner zonotopic set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

`true`

iff $Z ⊆ H$ otherwise `false`

**Algorithm**

Algorithm based on Lemma 3.1 of [1]

[1] Mitchell, I. M., Budzis, J., & Bolyachevets, A. (2019, April). Invariant, viability and discriminating kernel under-approximation via zonotope scaling. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control (pp. 268-269).

`Base.:⊆`

— Function`⊆(S1::AbstractSingleton, S2::AbstractSingleton, witness::Bool=false)`

Check whether a given set with a single value is contained in another set with a single value, and if not, optionally compute a witness.

**Input**

`S1`

– inner set with a single value`S2`

– outer set with a single value`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S1 ⊆ S2$ iff $S1 == S2$ - If
`witness`

option is activated:`(true, [])`

iff $S1 ⊆ S2$`(false, v)`

iff $S1 ⊈ S2$ and $v ∈ S1 \setminus S2$

`Base.:⊆`

— Function```
⊆(B1::Ball2, B2::Ball2{N}, [witness]::Bool=false
) where {N<:AbstractFloat}
```

Check whether a ball in the 2-norm is contained in another ball in the 2-norm, and if not, optionally compute a witness.

**Input**

`B1`

– inner ball in the 2-norm`B2`

– outer ball in the 2-norm`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $B1 ⊆ B2$ - If
`witness`

option is activated:`(true, [])`

iff $B1 ⊆ B2$`(false, v)`

iff $B1 ⊈ B2$ and $v ∈ B1 \setminus B2$

**Algorithm**

$B1 ⊆ B2$ iff $‖ c_1 - c_2 ‖_2 + r_1 ≤ r_2$

`Base.:⊆`

— Function`⊆(B::Union{Ball2, Ballp}, S::AbstractSingleton, witness::Bool=false)`

Check whether a ball in the 2-norm or p-norm is contained in a set with a single value, and if not, optionally compute a witness.

**Input**

`B`

– inner ball in the 2-norm or p-norm`S`

– outer set with a single value`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $B ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $B ⊆ S$`(false, v)`

iff $B ⊈ S$ and $v ∈ B \setminus S$

`Base.:⊆`

— Function`⊆(L::LineSegment, S::ConvexSet, witness::Bool=false)`

Check whether a line segment is contained in a convex set, and if not, optionally compute a witness.

**Input**

`L`

– inner line segment`S`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $L ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $L ⊆ S$`(false, v)`

iff $L ⊈ S$ and $v ∈ L \setminus S$

**Algorithm**

Since $S$ is convex, $L ⊆ S$ iff $p ∈ S$ and $q ∈ S$, where $p, q$ are the end points of $L$.

`Base.:⊆`

— Function`⊆(X::ConvexSet, P::ConvexSet, [witness]::Bool=false)`

Check whether a set is contained in a polyhedral set, and if not, optionally compute a witness.

**Input**

`X`

– inner set`Y`

– outer polyhedral set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ X \setminus P$

**Notes**

We require that `constraints_list(P)`

is available.

**Algorithm**

We check inclusion of `X`

in every constraint of `P`

.

`⊆(S::ConvexSet, H::AbstractHyperrectangle, [witness]::Bool=false)`

**Input**

`S`

– inner convex set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $S ⊆ H$ - If
`witness`

option is activated:`(true, [])`

iff $S ⊆ H$`(false, v)`

iff $S ⊈ H$ and $v ∈ S \setminus H$

**Algorithm**

```
⊆(P::AbstractPolytope, S::ConvexSet, [witness]::Bool=false;
algorithm=_default_issubset(P, S))
```

Check whether a polytope is contained in a convex set, and if not, optionally compute a witness.

**Input**

`P`

– inner polytope`S`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated`algorithm`

– (optional, default:`"constraints"`

if the constraints list of`S`

is available, otherwise`"vertices"`

) algorithm for the inclusion check; available options are:`"constraints"`

, using the list of constraints of`P`

and support function evaluations of`S`

`"vertices"`

, using the list of vertices of`P`

and membership evaluations of`S`

**Output**

- If
`witness`

option is deactivated:`true`

iff $P ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $P ⊆ S$`(false, v)`

iff $P ⊈ S$ and $v ∈ P \setminus S$

**Algorithm**

Since $S$ is convex, $P ⊆ S$ iff $v_i ∈ S$ for all vertices $v_i$ of $P$.

`⊆(X::ConvexSet, P::AbstractPolyhedron, [witness]::Bool=false)`

Check whether a convex set is contained in a polyhedron, and if not, optionally compute a witness.

**Input**

`X`

– inner convex set`P`

– outer polyhedron (including a half-space)`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ P$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ P$`(false, v)`

iff $X ⊈ P$ and $v ∈ P \setminus X$

**Algorithm**

`⊆(L::LineSegment, S::ConvexSet, witness::Bool=false)`

Check whether a line segment is contained in a convex set, and if not, optionally compute a witness.

**Input**

`L`

– inner line segment`S`

– outer convex set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $L ⊆ S$ - If
`witness`

option is activated:`(true, [])`

iff $L ⊆ S$`(false, v)`

iff $L ⊈ S$ and $v ∈ L \setminus S$

**Algorithm**

Since $S$ is convex, $L ⊆ S$ iff $p ∈ S$ and $q ∈ S$, where $p, q$ are the end points of $L$.

`⊆(Z::AbstractZonotope, H::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a zonotopic set is contained in a hyperrectangular set.

**Input**

`Z`

– inner zonotopic set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

`true`

iff $Z ⊆ H$ otherwise `false`

**Algorithm**

Algorithm based on Lemma 3.1 of [1]

[1] Mitchell, I. M., Budzis, J., & Bolyachevets, A. (2019, April). Invariant, viability and discriminating kernel under-approximation via zonotope scaling. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control (pp. 268-269).

`Base.:⊆`

— Method`⊆(x::Interval{N}, y::Interval, [witness]::Bool=false) where {N}`

Check whether an interval is contained in another interval.

**Input**

`x`

– interval`y`

– interval`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

`true`

iff $x ⊆ y$.

`Base.:⊆`

— Function`⊆(x::Interval, U::UnionSet, [witness]::Bool=false)`

Check whether an interval is contained in the union of two sets.

**Input**

`x`

– interval`U`

– union of two sets

**Output**

`true`

iff `x ⊆ U`

.

**Notes**

This implementation assumes that `U`

is a union of one-dimensional convex sets. Since these are equivalent to intervals, we convert to `Interval`

s.

**Algorithm**

Let $U = a ∪ b$ where $a$ and $b$ are intervals and assume that the lower bound of $a$ is to the left of $b$. If the lower bound of $x$ is to the left of $a$, we have a counterexample. Otherwise we compute the set difference $y = x \ a$ and check whether $y ⊆ b$ holds.

`Base.:⊆`

— Function`⊆(∅::EmptySet, X::ConvexSet, witness::Bool=false)`

Check whether an empty set is contained in another set.

**Input**

`∅`

– empty set`X`

– another set`witness`

– (optional, default:`false`

) compute a witness if activated (ignored, just kept for interface reasons)

**Output**

`true`

.

`Base.:⊆`

— Function`⊆(X::ConvexSet, ∅::EmptySet, [witness]::Bool=false)`

Check whether a set is contained in an empty set.

**Input**

`X`

– another set`∅`

– empty set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

`true`

iff `X`

is empty.

**Algorithm**

We rely on `isempty(X)`

for the emptiness check and on `an_element(X)`

for witness production.

`Base.:⊆`

— Function`⊆(cup::UnionSet, X::ConvexSet, [witness]::Bool=false)`

Check whether a union of two convex sets is contained in another set.

**Input**

`cup`

– union of two convex sets`X`

– another set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $\text{cup} ⊆ X$ - If
`witness`

option is activated:`(true, [])`

iff $\text{cup} ⊆ X$`(false, v)`

iff $\text{cup} \not\subseteq X$ and $v ∈ \text{cup} \setminus X$

`Base.:⊆`

— Function`⊆(cup::UnionSetArray, X::ConvexSet, [witness]::Bool=false)`

Check whether a union of a finite number of convex sets is contained in another set.

**Input**

`cup`

– union of a finite number of convex sets`X`

– another set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $\text{cup} ⊆ X$ - If
`witness`

option is activated:`(true, [])`

iff $\text{cup} ⊆ X$`(false, v)`

iff $\text{cup} \not\subseteq X$ and $v ∈ \text{cup} \setminus X$

`Base.:⊆`

— Function`⊆(X::ConvexSet, U::Universe, [witness]::Bool=false)`

Check whether a convex set is contained in a universe.

**Input**

`U`

– universe`X`

– convex set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

- If
`witness`

option is activated:`(true, [])`

`Base.:⊆`

— Function`⊆(U::Universe, X::ConvexSet, [witness]::Bool=false)`

Check whether a universe is contained in another convex set, and otherwise optionally compute a witness.

**Input**

`U`

– universe`X`

– convex set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $U ⊆ X$ - If
`witness`

option is activated:`(true, [])`

iff $U ⊆ X$`(false, v)`

iff $U \not\subseteq X$ and $v ∈ U \setminus X$

**Algorithm**

We fall back to `isuniversal(X)`

.

`Base.:⊆`

— Function`⊆(X::ConvexSet, C::Complement, [witness]::Bool=false)`

Check whether a convex set is contained in the complement of another convex set, and otherwise optionally compute a witness.

**Input**

`X`

– convex set`C`

– complement of a convex set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ C$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ C$`(false, v)`

iff $X \not\subseteq C$ and $v ∈ X \setminus C$

**Algorithm**

We fall back to `isdisjoint(X, C.X)`

, which can be justified as follows.

\[ X ⊆ Y^C ⟺ X ∩ Y = ∅\]

`Base.:⊆`

— Function```
⊆(X::CartesianProduct, Y::CartesianProduct, [witness]::Bool=false;
check_block_equality::Bool=true)
```

Check whether a Cartesian product of two convex sets is contained in another Cartesian product of two convex sets, and otherwise optionally compute a witness.

**Input**

`X`

– Cartesian product of two convex sets`Y`

– Cartesian product of two convex sets`witness`

– (optional, default:`false`

) compute a witness if activated`check_block_equality`

– (optional, default:`true`

) flag for checking that the block structure of the two sets is identical

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ Y$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ Y$`(false, v)`

iff $X \not\subseteq Y$ and $v ∈ X \setminus Y$

**Notes**

This algorithm requires that the two Cartesian products share the same block structure. If `check_block_equality`

is activated, we check this property and, if it does not hold, we use a fallback implementation based on conversion to constraint representation (assuming that the sets are polyhedral).

**Algorithm**

We check for inclusion for each block of the Cartesian products.

For witness production, we obtain a witness in one of the blocks. We then construct a high-dimensional witness by obtaining any point in the other blocks (using `an_element`

) and concatenating these points.

`Base.:⊆`

— Function```
⊆(X::CartesianProductArray, Y::CartesianProductArray, [witness]::Bool=false;
check_block_equality::Bool=true)
```

Check whether a Cartesian product of finitely many convex sets is contained in another Cartesian product of finitely many convex sets, and otherwise optionally compute a witness.

**Input**

`X`

– Cartesian product of finitely many convex sets`Y`

– Cartesian product of finitely many convex sets`witness`

– (optional, default:`false`

) compute a witness if activated`check_block_equality`

– (optional, default:`true`

) flag for checking that the block structure of the two sets is identical

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊆ Y$ - If
`witness`

option is activated:`(true, [])`

iff $X ⊆ Y$`(false, v)`

iff $X \not\subseteq Y$ and $v ∈ X \setminus Y$

**Notes**

This algorithm requires that the two Cartesian products share the same block structure. If `check_block_equality`

is activated, we check this property and, if it does not hold, we use a fallback implementation based on conversion to constraint representation (assuming that the sets are polyhedral).

**Algorithm**

We check for inclusion for each block of the Cartesian products.

For witness production, we obtain a witness in one of the blocks. We then construct a high-dimensional witness by obtaining any point in the other blocks (using `an_element`

) and concatenating these points.

`Base.:⊆`

— Function`⊆(Z::AbstractZonotope, H::AbstractHyperrectangle, [witness]::Bool=false)`

Check whether a zonotopic set is contained in a hyperrectangular set.

**Input**

`Z`

– inner zonotopic set`H`

– outer hyperrectangular set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

`true`

iff $Z ⊆ H$ otherwise `false`

**Algorithm**

Algorithm based on Lemma 3.1 of [1]

`IntervalArithmetic.:⊂`

— Function`⊂(X::ConvexSet{N}, Y::ConvexSet, [witness]::Bool=false) where {N}`

Strict inclusion check.

**Input**

`X`

– first set`Y`

– second set`witness`

– (optional, default:`false`

) compute a witness if activated

**Output**

- If
`witness`

option is deactivated:`true`

iff $X ⊂ Y$ - If
`witness`

option is activated:`(true, v)`

iff $X ⊂ Y$ and $v ∈ Y \setminus X$`(false, [])`

iff not $X ⊂ Y$

**Algorithm**

We check inclusion of `X`

in `Y`

and then check inclusion of `Y`

in `X`

:

\[X ⊂ Y \Leftrightarrow X ⊆ Y \land ¬ (Y ⊆ X)\]

## Set difference

`Base.:\`

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

Convenience alias for set difference.

**Input**

`X`

– a set`Y`

– another set

**Output**

The set difference between `X`

and `Y`

.

**Notes**

If `X`

and `Y`

are intervals, `X \ Y`

is used in some libraries to denote the left division, as the example below shows. However, it should not be confused with the *set difference*. For example,

```
julia> X = Interval(0, 2); Y = Interval(1, 4);
julia> X \ Y # computing the set difference
Interval{Float64, IntervalArithmetic.Interval{Float64}}([0, 1])
julia> X.dat \ Y.dat # computing the left division
[0.5, ∞]
```

`LazySets.difference`

— Method`difference(I1::IN, I2::IN) where {N, IN<:Interval{N}}`

Return the set difference between the given intervals.

The set difference is defined as:

\[ I₁ \setminus I₂ = \{x: x ∈ I₁ \text{ and } x ∉ I₂ \}\]

The backslash symbol, `\`

, can be used as an alias.

**Input**

`I1`

– first interval`I2`

– second interval

**Output**

Depending on the position of the intervals, the output is one of the following:

- An
`EmptySet`

. - An
`Interval`

. - A
`UnionSet`

of two`Interval`

sets.

**Algorithm**

Let $I₁ = [a, b]$ and $I₂ = [c, d]$ be intervals. Their set difference is $I₁ \setminus I₂ = \{x: x ∈ I₁ \text{ and } x ∉ I₂ \}$ and depending on their position three different results may occur:

- If $I₁$ and $I₂$ do not overlap, i.e. if their intersection is empty, then the set difference is just $I₁$.
- Otherwise, let
`I₁₂ = I₁ ∩ I₂`

and assume that it is not empty, then either $I₁₂$ splits`I₁`

into one interval or into two intervals. The latter case happens when the inclusion is strict on both ends of $I₂$.

To check for strict inclusion, we assume that the inclusion is strict and then check if the resulting intervals that cover `I₁`

(one to its left and one to its right, let them be `Ileft`

and `Iright`

), obtained by intersection with `I₂`

, are flat or not. Three cases may arise:

- If both
`Ileft`

and`Iright`

are flat then it means that`I₁ = I₂`

, then the set difference is the empty set. - If only
`Ileft`

is flat, then the remaining interval not covered by`I₂`

is`Iright`

. In a similar manner, if only`Iright`

is flat, then`Ileft`

is returned. - Finally, if none of the intervals is flat, then
`I₂`

is strictly contained in`I₁`

and the set union of`Ileft`

and`Iright`

is returned.

`LazySets.difference`

— Method`difference(X::AbstractHyperrectangle{N}, Y::AbstractHyperrectangle{N}) where {N}`

Return the set difference between the given hyperrectangular sets.

**Input**

`X`

– first hyperrectangular set`Y`

– second hyperrectangular set

The set difference is defined as:

\[ X \setminus Y = \{x: x ∈ X \text{ and } x ∉ Y \}\]

**Output**

A `UnionSetArray`

consisting of the union of hyperrectangles. Note that this union is in general not convex.

**Algorithm**

This function calls the implementation in `IntervalArithmetic.setdiff`

.

**Notes**

The backslash symbol, `\`

, can be used as an alias.

## Distance

`ReachabilityBase.Arrays.distance`

— Method`distance(S::AbstractSingleton, X::ConvexSet; [p]::Real=2.0)`

Compute the distance between the singleton `S`

and the set `X`

with respect to the given `p`

-norm.

**Input**

`S`

– singleton, i.e., a set with one element`X`

– set`p`

– (optional, default:`2.0`

) the`p`

-norm used;`p = 2.0`

corresponds to the usual Euclidean norm

**Output**

A scalar representing the distance between the element wrapped by `S`

and the set `X`

.

`ReachabilityBase.Arrays.distance`

— Method```
distance(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle;
[p]::Real=2)
```

Compute the standard distance between two hyperrectangular sets, defined as

\[ \inf_{x \in H_1, y \in H_2} \{ d(x, y) \}.\]

**Input**

`H1`

– hyperrectangular set`H2`

– hyperrectangular set`p`

– (optional; default:`2`

) value of the $p$-norm

**Output**

The distance, which is zero if the sets intersect and otherwise the $p$-norm of the shortest line segment between any pair of points.

**Notes**

See also `hausdorff_distance`

for an alternative distance notion.