Common Set Representations

Main module for LazySets.jl – a Julia package for calculus with convex sets.

ρ(d::AbstractVector{N}, S::LazySet)::N where {N<:Real}

Evaluate the support function of a set in a given direction.

Input

• d – direction

• S – convex set

Output

The support function of the set S for the direction d.

support_function

Alias for the support function ρ.

support_vector

Alias for the support vector σ.

Ball2{N<:AbstractFloat} <: AbstractPointSymmetric{N}

Type that represents a ball in the 2-norm.

Fields

• center – center of the ball as a real vector

• radius – radius of the ball as a real scalar ($≥ 0$)

Notes

Mathematically, a ball in the 2-norm is defined as the set

where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius. Here $‖ ⋅ ‖_2$ denotes the Euclidean norm (also known as 2-norm), defined as $‖ x ‖_2 = \left( \sum\limits_{i=1}^n |x_i|^2 \right)^{1/2}$ for any $x ∈ \mathbb{R}^n$.

Examples

Create a five-dimensional ball B in the 2-norm centered at the origin with radius 0.5:

julia> B = Ball2(zeros(5), 0.5)
LazySets.Ball2{Float64}([0.0, 0.0, 0.0, 0.0, 0.0], 0.5)
julia> dim(B)
5

Evaluate B's support vector in the direction $[1,2,3,4,5]$:

julia> σ([1.,2.,3.,4.,5.], B)
5-element Array{Float64,1}:
 0.06742
 0.13484
 0.20226
 0.26968
 0.3371

dim(S::AbstractPointSymmetric)::Int

Return the ambient dimension of a point symmetric set.

Input

• S – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::Ball2)::AbstractVector{<:AbstractFloat} where {N<:AbstractFloat}

Return the support vector of a 2-norm ball in a given direction.

Input

• d – direction

• B – ball in the 2-norm

Output

The support vector in the given direction. If the direction has norm zero, the origin is returned.

Notes

Let $c$ and $r$ be the center and radius of a ball $B$ in the 2-norm, respectively. For nonzero direction $d$ we have $σ(d, B) = c + r * (d / ‖d‖_2)$.

This function requires computing the 2-norm of the input direction, which is performed in the given precision of the numeric datatype of both the direction and the set. Exact inputs are not supported.

∈(x::AbstractVector{N}, B::Ball2{N})::Bool where {N<:AbstractFloat}

Check whether a given point is contained in a ball in the 2-norm.

Input

• x – point/vector

• B – ball in the 2-norm

Output

true iff $x ∈ B$.

Notes

This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.

Algorithm

Let $B$ be an $n$-dimensional ball in the 2-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $\left( ∑_{i=1}^n |c_i - x_i|^2 \right)^{1/2} ≤ r$.

Examples

julia> B = Ball2([1., 1.], sqrt(0.5))
LazySets.Ball2{Float64}([1.0, 1.0], 0.7071067811865476)
julia> ∈([.5, 1.6], B)
false
julia> ∈([.5, 1.5], B)
true

an_element(S::AbstractPointSymmetric{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric set.

Input

• S – point symmetric set

Output

The center of the point symmetric set.

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

center(B::Ball2{N})::Vector{N} where {N<:AbstractFloat}

Return the center of a ball in the 2-norm.

Input

• B – ball in the 2-norm

Output

The center of the ball in the 2-norm.

BallInf{N<:Real} <: AbstractHyperrectangle{N}

Type that represents a ball in the infinity norm.

Fields

• center – center of the ball as a real vector

• radius – radius of the ball as a real scalar ($≥ 0$)

Notes

Mathematically, a ball in the infinity norm is defined as the set

where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius. Here $‖ ⋅ ‖_∞$ denotes the infinity norm, defined as $‖ x ‖_∞ = \max\limits_{i=1,…,n} \vert x_i \vert$ for any $x ∈ \mathbb{R}^n$.

Examples

Create the two-dimensional unit ball and compute its support function along the positive $x=y$ direction:

julia> B = BallInf(zeros(2), 1.0)
LazySets.BallInf{Float64}([0.0, 0.0], 1.0)
julia> dim(B)
2
julia> ρ([1., 1.], B)
2.0

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::AbstractHyperrectangle{N}
 )::AbstractVector{N} where {N<:Real}

Return the support vector of a box-shaped set in a given direction.

Input

• d – direction

• B – box-shaped set

Output

The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.

∈(x::AbstractVector{N}, B::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a box-shaped set.

Input

• x – point/vector

• B – box-shaped set

Output

true iff $x ∈ B$.

Algorithm

Let $B$ be an $n$-dimensional box-shaped set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.

an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric polytope.

Input

• P – point symmetric polytope

Output

The center of the point symmetric polytope.

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

⊆(P::AbstractPolytope{N}, H::AbstractHyperrectangle, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• P – inner polytope

• H – outer hyperrectangle

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $P ⊆ H$

• If witness option is activated:

  • (true, []) iff $P ⊆ H$

  • (false, v) iff $P \not\subseteq H$ and $v ∈ P \setminus H$

Notes

This copy-pasted method just exists to avoid method ambiguities.

Algorithm

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

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

is_intersection_empty(H1::AbstractHyperrectangle{N},
                      H2::AbstractHyperrectangle{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether two hyperrectangles intersect, and if so, 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, v) iff $H1 ∩ H2 ≠ ∅$ and $v ∈ H1 ∩ H2$

  • (false, []) iff $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.

norm(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a box-shaped set.

Input

• B – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

The norm of a box-shaped set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume.

norm(S::LazySet, [p]::Real=Inf)

Return the norm of a convex set. It is the norm of the enclosing ball (of the given norm) of minimal volume.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

radius(B::BallInf, [p]::Real=Inf)::Real

Return the radius of a ball in the infinity norm.

Input

• B – ball in the infinity norm

• p – (optional, default: Inf) norm

Output

A real number representing the radius.

Notes

The radius is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center.

diameter(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a box-shaped set.

Input

• H – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

Notes

The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.

diameter(S::LazySet, [p]::Real=Inf)

Return the diameter of a convex set. It is the maximum distance between any two elements of the set, or, equivalently, the diameter of the enclosing ball (of the given norm) of minimal volume with the same center.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

vertices_list(B::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a box-shaped set.

Input

• B – box-shaped set

Output

A list of vertices.

Notes

For high dimensions, it is preferable to develop a vertex_iterator approach.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

center(B::BallInf{N})::Vector{N} where {N<:Real}

Return the center of a ball in the infinity norm.

Input

• B – ball in the infinity norm

Output

The center of the ball in the infinity norm.

radius_hyperrectangle(B::BallInf{N})::Vector{N} where {N<:Real}

Return the box radius of a infinity norm ball, which is the same in every dimension.

Input

• B – infinity norm ball

Output

The box radius of the ball in the infinity norm.

radius_hyperrectangle(B::BallInf{N}, i::Int)::N where {N<:Real}

Return the box radius of a infinity norm ball in a given dimension.

Input

• B – infinity norm ball

Output

The box radius of the ball in the infinity norm in the given dimension.

Ball1{N<:Real} <: AbstractPointSymmetricPolytope{N}

Type that represents a ball in the 1-norm, also known as Manhattan or Taxicab norm.

It is defined as the set

where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius.

Fields

• center – center of the ball as a real vector

• radius – radius of the ball as a scalar ($≥ 0$)

Examples

Unit ball in the 1-norm in the plane:

julia> B = Ball1(zeros(2), 1.)
LazySets.Ball1{Float64}([0.0, 0.0], 1.0)
julia> dim(B)
2

We evaluate the support vector in the East direction:

julia> σ([0.,1], B)
2-element Array{Float64,1}:
 0.0
 1.0

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::Ball1)::AbstractVector{N} where {N<:Real}

Return the support vector of a ball in the 1-norm in a given direction.

Input

• d – direction

• B – ball in the 1-norm

Output

Support vector in the given direction.

∈(x::AbstractVector{N}, B::Ball1{N})::Bool where {N<:Real}

Check whether a given point is contained in a ball in the 1-norm.

Input

• x – point/vector

• B – ball in the 1-norm

Output

true iff $x ∈ B$.

Notes

This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.

Algorithm

Let $B$ be an $n$-dimensional ball in the 1-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $∑_{i=1}^n |c_i - x_i| ≤ r$.

Examples

julia> B = Ball1([1., 1.], 1.);

julia> ∈([.5, -.5], B)
false
julia> ∈([.5, 1.5], B)
true

an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric polytope.

Input

• P – point symmetric polytope

Output

The center of the point symmetric polytope.

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

vertices_list(B::Ball1{N})::Vector{Vector{N}} where {N<:Real}

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.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

center(B::Ball1{N})::Vector{N} where {N<:Real}

Return the center of a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

The center of the ball in the 1-norm.

Ballp{N<:AbstractFloat} <: AbstractPointSymmetric{N}

Type that represents a ball in the p-norm, for $1 ≤ p ≤ ∞$.

It is defined as the set

where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius. Here $‖ ⋅ ‖_p$ for $1 ≤ p ≤ ∞$ denotes the vector $p$-norm, defined as $‖ x ‖_p = \left( \sum\limits_{i=1}^n |x_i|^p \right)^{1/p}$ for any $x ∈ \mathbb{R}^n$.

Fields

• p – norm as a real scalar

• center – center of the ball as a real vector

• radius – radius of the ball as a scalar ($≥ 0$)

Notes

The special cases $p=1$, $p=2$ and $p=∞$ fall back to the specialized types Ball1, Ball2 and BallInf, respectively.

Examples

A five-dimensional ball in the $p=3/2$ norm centered at the origin of radius 0.5:

julia> B = Ballp(3/2, zeros(5), 0.5)
LazySets.Ballp{Float64}(1.5, [0.0, 0.0, 0.0, 0.0, 0.0], 0.5)
julia> dim(B)
5

We evaluate the support vector in direction $[1,2,…,5]$:

julia> σ(1.:5, B)
5-element Array{Float64,1}:
 0.013516
 0.054064
 0.121644
 0.216256
 0.3379

dim(S::AbstractPointSymmetric)::Int

Return the ambient dimension of a point symmetric set.

Input

• S – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::Ballp)::AbstractVector{N} where {N<:AbstractFloat}

Return the support vector of a Ballp in a given direction.

Input

• d – direction

• B – ball in the p-norm

Output

The support vector in the given direction. If the direction has norm zero, the center of the ball is returned.

Algorithm

The support vector of the unit ball in the $p$-norm along direction $d$ is:

where $\tilde{v}_i = \frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $tilde{v}_i = 0$ otherwise, for all $i=1,…,n$, and $q$ is the conjugate number of $p$. By the affine transformation $x = r\tilde{x} + c$, one obtains that the support vector of $\mathcal{B}_p^n(c, r)$ is

where $v_i = c_i + r\frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $v_i = 0$ otherwise, for all $i = 1, …, n$.

∈(x::AbstractVector{N}, B::Ballp{N})::Bool where {N<:AbstractFloat}

Check whether a given point is contained in a ball in the p-norm.

Input

• x – point/vector

• B – ball in the p-norm

Output

true iff $x ∈ B$.

Notes

This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.

Algorithm

Let $B$ be an $n$-dimensional ball in the p-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $\left( ∑_{i=1}^n |c_i - x_i|^p \right)^{1/p} ≤ r$.

Examples

julia> B = Ballp(1.5, [1., 1.], 1.)
LazySets.Ballp{Float64}(1.5, [1.0, 1.0], 1.0)
julia> ∈([.5, -.5], B)
false
julia> ∈([.5, 1.5], B)
true

an_element(S::AbstractPointSymmetric{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric set.

Input

• S – point symmetric set

Output

The center of the point symmetric set.

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

center(B::Ballp{N})::Vector{N} where {N<:AbstractFloat}

Return the center of a ball in the p-norm.

Input

• B – ball in the p-norm

Output

The center of the ball in the p-norm.

HPolygon{N<:Real} <: AbstractHPolygon{N}

Type that represents a convex polygon in constraint representation whose edges are sorted in counter-clockwise fashion with respect to their normal directions.

Fields

• constraints_list – list of linear constraints, sorted by the angle

Notes

The default constructor assumes that the given list of edges is sorted. It does not perform any sorting. Use addconstraint! to iteratively add the edges in a sorted way.

• HPolygon(constraints_list::Vector{LinearConstraint{<:Real}}) – default constructor

• HPolygon() – constructor with no constraints

dim(P::AbstractPolygon)::Int

Return the ambient dimension of a polygon.

Input

• P – polygon

Output

The ambient dimension of the polygon, which is 2.

σ(d::AbstractVector{<:Real}, P::HPolygon{N})::Vector{N} where {N<:Real}

Return the support vector of a polygon in a given direction.

Input

• d – direction

• P – polygon in constraint representation

Output

The support vector in the given direction. The result is always one of the vertices; in particular, if the direction has norm zero, any vertex is returned.

Algorithm

Comparison of directions is performed using polar angles; see the overload of <= for two-dimensional vectors.

∈(x::AbstractVector{N}, P::AbstractHPolygon{N})::Bool where {N<:Real}

Check whether a given 2D point is contained in a polygon in constraint representation.

Input

• x – two-dimensional point/vector

• P – polygon in constraint representation

Output

true iff $x ∈ P$.

Algorithm

This implementation checks if the point lies on the outside of each edge.

an_element(P::AbstractHPolygon{N})::Vector{N} where {N<:Real}

Return some element of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

A vertex of the polygon in constraint representation (the first one in the order of the constraints).

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

vertices_list(P::AbstractHPolygon{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

List of vertices.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

tohrep(P::AbstractHPolygon{N})::AbstractHPolygon{N} where {N<:Real}

Build a contraint representation of the given polygon.

Input

• P – polygon in constraint representation

Output

The identity, i.e., the same polygon instance.

tovrep(P::AbstractHPolygon{N})::VPolygon{N} where {N<:Real}

Build a vertex representation of the given polygon.

Input

• P – polygon in constraint representation

Output

The same polygon but in vertex representation, a VPolygon.

addconstraint!(P::AbstractHPolygon{N},
               constraint::LinearConstraint{N})::Void where {N<:Real}

Add a linear constraint to a polygon in constraint representation, keeping the constraints sorted by their normal directions.

Input

• P – polygon in constraint representation

• constraint – linear constraint to add

Output

Nothing.

HPolygonOpt{N<:Real} <: AbstractHPolygon{N}

Type that represents a convex polygon in constraint representation whose edges are sorted in counter-clockwise fashion with respect to their normal directions. This is a refined version of HPolygon.

Fields

• constraints_list – list of linear constraints

• ind – index in the list of constraints to begin the search to evaluate the support function

Notes

This structure is optimized to evaluate the support function/vector with a large sequence of directions that are close to each other. The strategy is to have an index that can be used to warm-start the search for optimal values in the support vector computation.

The default constructor assumes that the given list of edges is sorted. It does not perform any sorting. Use addconstraint! to iteratively add the edges in a sorted way.

• HPolygonOpt(constraints_list::Vector{LinearConstraint{<:Real}}, ind::Int) – default constructor

• HPolygonOpt(constraints_list::Vector{LinearConstraint{<:Real}}) – constructor without index

• HPolygonOpt(H::HPolygon{<:Real}) – constructor from an HPolygon

dim(P::AbstractPolygon)::Int

Return the ambient dimension of a polygon.

Input

• P – polygon

Output

The ambient dimension of the polygon, which is 2.

σ(d::AbstractVector{<:Real}, P::HPolygonOpt{N})::Vector{N} where {N<:Real}

Return the support vector of an optimized polygon in a given direction.

Input

• d – direction

• P – optimized polygon in constraint representation

Output

The support vector in the given direction. The result is always one of the vertices; in particular, if the direction has norm zero, any vertex is returned.

Algorithm

Comparison of directions is performed using polar angles; see the overload of <= for two-dimensional vectors.

∈(x::AbstractVector{N}, P::AbstractHPolygon{N})::Bool where {N<:Real}

Check whether a given 2D point is contained in a polygon in constraint representation.

Input

• x – two-dimensional point/vector

• P – polygon in constraint representation

Output

true iff $x ∈ P$.

Algorithm

This implementation checks if the point lies on the outside of each edge.

an_element(P::AbstractHPolygon{N})::Vector{N} where {N<:Real}

Return some element of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

A vertex of the polygon in constraint representation (the first one in the order of the constraints).

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

vertices_list(P::AbstractHPolygon{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

List of vertices.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

tohrep(P::AbstractHPolygon{N})::AbstractHPolygon{N} where {N<:Real}

Build a contraint representation of the given polygon.

Input

• P – polygon in constraint representation

Output

The identity, i.e., the same polygon instance.

tovrep(P::AbstractHPolygon{N})::VPolygon{N} where {N<:Real}

Build a vertex representation of the given polygon.

Input

• P – polygon in constraint representation

Output

The same polygon but in vertex representation, a VPolygon.

addconstraint!(P::AbstractHPolygon{N},
               constraint::LinearConstraint{N})::Void where {N<:Real}

Add a linear constraint to a polygon in constraint representation, keeping the constraints sorted by their normal directions.

Input

• P – polygon in constraint representation

• constraint – linear constraint to add

Output

Nothing.

VPolygon{N<:Real} <: AbstractPolygon{N}

Type that represents a polygon by its vertices.

Fields

• vertices_list – the list of vertices

Notes

The constructor of VPolygon runs a convex hull algorithm, and the given vertices are sorted in counter-clockwise fashion. The constructor flag apply_convex_hull can be used to skip the computation of the convex hull.

• VPolygon(vertices_list::Vector{Vector{N}}; apply_convex_hull::Bool=true, algorithm::String="monotone_chain")

dim(P::AbstractPolygon)::Int

Return the ambient dimension of a polygon.

Input

• P – polygon

Output

The ambient dimension of the polygon, which is 2.

σ(d::AbstractVector{<:Real}, P::VPolygon{N})::Vector{N} where {N<:Real}

Return the support vector of a polygon in a given direction.

Input

• d – direction

• P – polygon in vertex representation

Output

The support vector in the given direction. If the direction has norm zero, the first vertex is returned.

Algorithm

This implementation performs a brute-force search, comparing the projection of each vector along the given direction. It runs in $O(n)$ where $n$ is the number of vertices.

Notes

For arbitrary points without structure this is the best one can do. However, a more efficient approach can be used if the vertices of the polygon have been sorted in counter-clockwise fashion. In that case a binary search algorithm can be used that runs in $O(\log n)$. See issue #40.

∈(x::AbstractVector{N}, P::VPolygon{N})::Bool where {N<:Real}

Check whether a given point is contained in a polygon in vertex representation.

Input

• x – point/vector

• P – polygon in vertex representation

Output

true iff $x ∈ P$.

Algorithm

This implementation exploits that the polygon's vertices are sorted in counter-clockwise fashion. Under this assumption we can just check if the vertex lies on the left of each edge, using the dot product.

Examples

julia> P = VPolygon([[2.0, 3.0], [3.0, 1.0], [5.0, 1.0], [4.0, 5.0]];
                    apply_convex_hull=false);

julia> ∈([4.5, 3.1], P)
false
julia> ∈([4.5, 3.0], P)
true
julia> ∈([4.4, 3.4], P)  #  point lies on the edge -> floating point error
false
julia> P = VPolygon([[2//1, 3//1], [3//1, 1//1], [5//1, 1//1], [4//1, 5//1]];
                     apply_convex_hull=false);

julia> ∈([44//10, 34//10], P)  #  with rational numbers the answer is correct
true

an_element(P::VPolygon{N})::Vector{N} where {N<:Real}

Return some element of a polygon in vertex representation.

Input

• P – polygon in vertex representation

Output

The first vertex of the polygon in vertex representation.

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

vertices_list(P::VPolygon{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a convex polygon in vertex representation.

Input

• P – a polygon vertex representation

Output

List of vertices.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

tohrep(P::VPolygon{N})::AbstractHPolygon{N} where {N<:Real}

Build a constraint representation of the given polygon.

Input

• P – polygon in vertex representation

Output

The same polygon but in constraint representation, an AbstractHPolygon.

tovrep(P::VPolygon{N})::VPolygon{N} where {N<:Real}

Build a vertex representation of the given polygon.

Input

• P – polygon in vertex representation

Output

The identity, i.e., the same polygon instance.

LinearConstraint{N<:Real}

Type that represents a linear constraint (a half-space) of the form $a⋅x ≤ b$.

Fields

• a – normal direction

• b – constraint

Examples

The set $y ≥ 0$ in the plane:

julia> LinearConstraint([0, -1.], 0.)
LazySets.LinearConstraint{Float64}([0.0, -1.0], 0.0)

Line{N<:Real}

Type that represents a line in 2D of the form $a⋅x = b$.

Fields

• a – normal direction

• b – constraint

Examples

The line $y = -x + 1$:

julia> Line([1., 1.], 1.)
LazySets.Line{Float64}([1.0, 1.0], 1.0)

intersection(L1::Line{N}, L2::Line{N})::Vector{N} where {N<:Real}

Return the intersection of two 2D lines.

Input

• L1 – first line

• L2 – second line

Output

If the lines are parallel or identical, the result is an empty vector. Otherwise the result is the only intersection point.

Examples

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

julia> intersection(Line([-1., 1.], 0.), Line([1., 1.], 1.))
2-element Array{Float64,1}:
 0.5
 0.5
julia> intersection(Line([1., 1.], 1.), Line([1., 1.], 1.))
0-element Array{Float64,1}

Hyperrectangle{N<:Real} <: AbstractHyperrectangle{N}

Type that represents a hyperrectangle.

A hyperrectangle is the Cartesian product of one-dimensional intervals.

Fields

• center – center of the hyperrectangle as a real vector

• radius – radius of the ball as a real vector, i.e., half of its width along each coordinate direction

Hyperrectangle(;kwargs...)

Construct a hyperrectangle from keyword arguments.

Input

• kwargs – keyword arguments; two combinations are allowed:

  1. center, radius – vectors

  2. high, low – vectors (if both center and radius are also defined, those are chosen instead)

Output

A hyperrectangle.

Examples

The following three constructions are equivalent:

julia> c = ones(2);

julia> r = [0.1, 0.2];

julia> l = [0.9, 0.8];

julia> h = [1.1, 1.2];

julia> H1 = Hyperrectangle(c, r)
LazySets.Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])
julia> H2 = Hyperrectangle(center=c, radius=r)
LazySets.Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])
julia> H3 = Hyperrectangle(low=l, high=h)
LazySets.Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::AbstractHyperrectangle{N}
 )::AbstractVector{N} where {N<:Real}

Return the support vector of a box-shaped set in a given direction.

Input

• d – direction

• B – box-shaped set

Output

The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.

∈(x::AbstractVector{N}, B::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a box-shaped set.

Input

• x – point/vector

• B – box-shaped set

Output

true iff $x ∈ B$.

Algorithm

Let $B$ be an $n$-dimensional box-shaped set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.

an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric polytope.

Input

• P – point symmetric polytope

Output

The center of the point symmetric polytope.

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

⊆(P::AbstractPolytope{N}, H::AbstractHyperrectangle, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• P – inner polytope

• H – outer hyperrectangle

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $P ⊆ H$

• If witness option is activated:

  • (true, []) iff $P ⊆ H$

  • (false, v) iff $P \not\subseteq H$ and $v ∈ P \setminus H$

Notes

This copy-pasted method just exists to avoid method ambiguities.

Algorithm

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

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

is_intersection_empty(H1::AbstractHyperrectangle{N},
                      H2::AbstractHyperrectangle{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether two hyperrectangles intersect, and if so, 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, v) iff $H1 ∩ H2 ≠ ∅$ and $v ∈ H1 ∩ H2$

  • (false, []) iff $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.

norm(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a box-shaped set.

Input

• B – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

The norm of a box-shaped set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume.

norm(S::LazySet, [p]::Real=Inf)

Return the norm of a convex set. It is the norm of the enclosing ball (of the given norm) of minimal volume.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

radius(H::Hyperrectangle, [p]::Real=Inf)::Real

Return the radius of a hyperrectangle.

Input

• H – hyperrectangle

• p – (optional, default: Inf) norm

Output

A real number representing the radius.

Notes

The radius is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center.

diameter(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a box-shaped set.

Input

• H – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

Notes

The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.

diameter(S::LazySet, [p]::Real=Inf)

Return the diameter of a convex set. It is the maximum distance between any two elements of the set, or, equivalently, the diameter of the enclosing ball (of the given norm) of minimal volume with the same center.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

vertices_list(B::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a box-shaped set.

Input

• B – box-shaped set

Output

A list of vertices.

Notes

For high dimensions, it is preferable to develop a vertex_iterator approach.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

center(H::Hyperrectangle{N})::Vector{N} where {N<:Real}

Return the center of a hyperrectangle.

Input

• H – hyperrectangle

Output

The center of the hyperrectangle.

radius_hyperrectangle(H::Hyperrectangle{N})::Vector{N} where {N<:Real}

Return the box radius of a hyperrectangle in every dimension.

Input

• H – hyperrectangle

Output

The box radius of the hyperrectangle.

radius_hyperrectangle(H::Hyperrectangle{N}, i::Int)::N where {N<:Real}

Return the box radius of a hyperrectangle in a given dimension.

Input

• H – hyperrectangle

Output

Zero.

high(H::Hyperrectangle{N})::Vector{N} where {N<:Real}

Return the higher coordinates of a hyperrectangle.

Input

• H – hyperrectangle

Output

A vector with the higher coordinates of the hyperrectangle, one entry per dimension.

low(H::Hyperrectangle{N})::Vector{N} where {N<:Real}

Return the lower coordinates of a hyperrectangle.

Input

• H – hyperrectangle

Output

A vector with the lower coordinates of the hyperrectangle, one entry per dimension.

EmptySet <: LazySet

Type that represents the empty set, i.e., the set with no elements.

dim(∅::EmptySet)

Return the dimension of the empty set, which is -1 by convention.

Input

• ∅ – an empty set

Output

-1 by convention.

σ(d, ∅)

Return the support vector of an empty set.

Input

• ∅ – an empty set

Output

An error.

∈(x::AbstractVector, ∅::EmptySet)::Bool

Check whether a given point is contained in an empty set.

Input

• x – point/vector

• ∅ – empty set

Output

The output is always false.

Examples

julia> ∈([1.0, 0.0], ∅)
false

an_element(∅::EmptySet)

Return some element of an empty set.

Input

• ∅ – empty set

Output

An error.

Singleton{N<:Real} <: AbstractSingleton{N}

Type that represents a singleton, that is, a set with a unique element.

Fields

• element – the only element of the set

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::AbstractHyperrectangle{N}
 )::AbstractVector{N} where {N<:Real}

Return the support vector of a box-shaped set in a given direction.

Input

• d – direction

• B – box-shaped set

Output

The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.

σ(d::AbstractVector{N}, S::AbstractSingleton{N})::Vector{N} where {N<:Real}

Return the support vector of a set with a single value.

Input

• d – direction

• S – set with a single value

Output

The support vector, which is the set's vector itself, irrespective of the given direction.

∈(x::AbstractVector{N}, B::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a box-shaped set.

Input

• x – point/vector

• B – box-shaped set

Output

true iff $x ∈ B$.

Algorithm

Let $B$ be an $n$-dimensional box-shaped set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.

∈(x::AbstractVector{N}, S::AbstractSingleton{N})::Bool where {N<:Real}

Check whether a given point is contained in a set with a single value.

Input

• x – point/vector

• S – set with a single value

Output

true iff $x ∈ S$.

Notes

This implementation performs an exact comparison, which may be insufficient with floating point computations.

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

⊆(P::AbstractPolytope{N}, H::AbstractHyperrectangle, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• P – inner polytope

• H – outer hyperrectangle

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $P ⊆ H$

• If witness option is activated:

  • (true, []) iff $P ⊆ H$

  • (false, v) iff $P \not\subseteq H$ and $v ∈ P \setminus H$

Notes

This copy-pasted method just exists to avoid method ambiguities.

Algorithm

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

⊆(S::AbstractSingleton{N}, set::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

• set – outer convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ⊆ \text{set}$

• If witness option is activated:

  • (true, []) iff $S ⊆ \text{set}$

  • (false, v) iff $S \not\subseteq \text{set}$ and $v ∈ S \setminus \text{set}$

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

⊆(S::AbstractSingleton{N}, set::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

• set – outer convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ⊆ \text{set}$

• If witness option is activated:

  • (true, []) iff $S ⊆ \text{set}$

  • (false, v) iff $S \not\subseteq \text{set}$ and $v ∈ S \setminus \text{set}$

is_intersection_empty(S::AbstractSingleton{N},
                      set::LazySet,
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a singleton and a convex set intersect, and if so, optionally compute a witness.

Input

• S – singleton

• set – convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(set::LazySet,
                      S::AbstractSingleton{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a convex set and a singleton intersect, and if so, optionally compute a witness.

Input

• set – convex set

• S – singleton

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(H1::AbstractHyperrectangle{N},
                      H2::AbstractHyperrectangle{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether two hyperrectangles intersect, and if so, 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, v) iff $H1 ∩ H2 ≠ ∅$ and $v ∈ H1 ∩ H2$

  • (false, []) iff $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.

is_intersection_empty(S::AbstractSingleton{N},
                      set::LazySet,
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a singleton and a convex set intersect, and if so, optionally compute a witness.

Input

• S – singleton

• set – convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(set::LazySet,
                      S::AbstractSingleton{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a convex set and a singleton intersect, and if so, optionally compute a witness.

Input

• set – convex set

• S – singleton

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(S1::AbstractSingleton{N},
                      S2::AbstractSingleton{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether two singletons intersect, and if so, 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, v) iff $S1 ∩ S2 ≠ ∅$ and v = element(S1)

  • (false, []) iff $S1 ∩ S2 = ∅$

Algorithm

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

norm(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a box-shaped set.

Input

• B – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

The norm of a box-shaped set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume.

norm(S::LazySet, [p]::Real=Inf)

Return the norm of a convex set. It is the norm of the enclosing ball (of the given norm) of minimal volume.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

diameter(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a box-shaped set.

Input

• H – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

Notes

The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.

diameter(S::LazySet, [p]::Real=Inf)

Return the diameter of a convex set. It is the maximum distance between any two elements of the set, or, equivalently, the diameter of the enclosing ball (of the given norm) of minimal volume with the same center.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

vertices_list(B::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a box-shaped set.

Input

• B – box-shaped set

Output

A list of vertices.

Notes

For high dimensions, it is preferable to develop a vertex_iterator approach.

vertices_list(S::AbstractSingleton{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a set with a single value.

Input

• S – set with a single value

Output

A list containing only a single vertex.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

center(S::AbstractSingleton{N})::Vector{N} where {N<:Real}

Return the center of a set with a single value.

Input

• S – set with a single value

Output

The only element of the set.

radius_hyperrectangle(S::AbstractSingleton{N})::Vector{N} where {N<:Real}

Return the box radius of a set with a single value in every dimension.

Input

• S – set with a single value

Output

The zero vector.

radius_hyperrectangle(S::AbstractSingleton{N}, i::Int)::N where {N<:Real}

Return the box radius of a set with a single value in a given dimension.

Input

• S – set with a single value

Output

Zero.

an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric polytope.

Input

• P – point symmetric polytope

Output

The center of the point symmetric polytope.

an_element(S::AbstractSingleton{N})::Vector{N} where {N<:Real}

Return some element of a set with a single value.

Input

• S – set with a single value

Output

The only element in the set.

element(S::Singleton{N})::Vector{N} where {N<:Real}

Return the element of a singleton.

Input

• S – singleton

Output

The element of the singleton.

element(S::Singleton{N}, i::Int)::N where {N<:Real}

Return the i-th entry of the element of a singleton.

Input

• S – singleton

• i – dimension

Output

The i-th entry of the element of the singleton.

ZeroSet{N<:Real} <: AbstractSingleton{N}

Type that represents the zero set, i.e., the set that only contains the origin.

Fields

• dim – the ambient dimension of this zero set

dim(Z::ZeroSet)::Int

Return the ambient dimension of this zero set.

Input

• Z – a zero set, i.e., a set that only contains the origin

Output

The ambient dimension of the zero set.

σ(d::AbstractVector{N}, Z::ZeroSet)::Vector{N} where {N<:Real}

Return the support vector of a zero set.

Input

• Z – a zero set, i.e., a set that only contains the origin

Output

The returned value is the origin since it is the only point that belongs to this set.

∈(x::AbstractVector{N}, B::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a box-shaped set.

Input

• x – point/vector

• B – box-shaped set

Output

true iff $x ∈ B$.

Algorithm

Let $B$ be an $n$-dimensional box-shaped set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.

∈(x::AbstractVector{N}, S::AbstractSingleton{N})::Bool where {N<:Real}

Check whether a given point is contained in a set with a single value.

Input

• x – point/vector

• S – set with a single value

Output

true iff $x ∈ S$.

Notes

This implementation performs an exact comparison, which may be insufficient with floating point computations.

∈(x::AbstractVector{N}, Z::ZeroSet{N})::Bool where {N<:Real}

Check whether a given point is contained in a zero set.

Input

• x – point/vector

• Z – zero set

Output

true iff $x ∈ Z$.

Examples

julia> Z = ZeroSet(2);

julia> ∈([1.0, 0.0], Z)
false
julia> ∈([0.0, 0.0], Z)
true

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

⊆(S::LazySet, H::AbstractHyperrectangle{N}, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• S – inner convex set

• H – outer hyperrectangle

• 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 \not\subseteq H$ and $v ∈ S \setminus H$

Algorithm

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

⊆(P::AbstractPolytope{N}, H::AbstractHyperrectangle, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Input

• P – inner polytope

• H – outer hyperrectangle

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $P ⊆ H$

• If witness option is activated:

  • (true, []) iff $P ⊆ H$

  • (false, v) iff $P \not\subseteq H$ and $v ∈ P \setminus H$

Notes

This copy-pasted method just exists to avoid method ambiguities.

Algorithm

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

⊆(S::AbstractSingleton{N}, set::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

• set – outer convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ⊆ \text{set}$

• If witness option is activated:

  • (true, []) iff $S ⊆ \text{set}$

  • (false, v) iff $S \not\subseteq \text{set}$ and $v ∈ S \setminus \text{set}$

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

⊆(S::AbstractSingleton{N}, set::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

• set – outer convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ⊆ \text{set}$

• If witness option is activated:

  • (true, []) iff $S ⊆ \text{set}$

  • (false, v) iff $S \not\subseteq \text{set}$ and $v ∈ S \setminus \text{set}$

is_intersection_empty(S::AbstractSingleton{N},
                      set::LazySet,
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a singleton and a convex set intersect, and if so, optionally compute a witness.

Input

• S – singleton

• set – convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(set::LazySet,
                      S::AbstractSingleton{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a convex set and a singleton intersect, and if so, optionally compute a witness.

Input

• set – convex set

• S – singleton

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(H1::AbstractHyperrectangle{N},
                      H2::AbstractHyperrectangle{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether two hyperrectangles intersect, and if so, 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, v) iff $H1 ∩ H2 ≠ ∅$ and $v ∈ H1 ∩ H2$

  • (false, []) iff $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.

is_intersection_empty(S::AbstractSingleton{N},
                      set::LazySet,
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a singleton and a convex set intersect, and if so, optionally compute a witness.

Input

• S – singleton

• set – convex set

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(set::LazySet,
                      S::AbstractSingleton{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether a convex set and a singleton intersect, and if so, optionally compute a witness.

Input

• set – convex set

• S – singleton

• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $S ∩ \operatorname{set} ≠ ∅$

• If witness option is activated:

  • (true, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S)

  • (false, []) iff $S ∩ \operatorname{set} = ∅$

Algorithm

$S ∩ \operatorname{set} ≠ ∅$ iff element(S) $∈ \operatorname{set}$.

is_intersection_empty(S1::AbstractSingleton{N},
                      S2::AbstractSingleton{N},
                      witness::Bool=false
                     )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

Check whether two singletons intersect, and if so, 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, v) iff $S1 ∩ S2 ≠ ∅$ and v = element(S1)

  • (false, []) iff $S1 ∩ S2 = ∅$

Algorithm

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

norm(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a box-shaped set.

Input

• B – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

The norm of a box-shaped set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume.

norm(S::LazySet, [p]::Real=Inf)

Return the norm of a convex set. It is the norm of the enclosing ball (of the given norm) of minimal volume.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

diameter(B::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a box-shaped set.

Input

• H – box-shaped set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

Notes

The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.

diameter(S::LazySet, [p]::Real=Inf)

Return the diameter of a convex set. It is the maximum distance between any two elements of the set, or, equivalently, the diameter of the enclosing ball (of the given norm) of minimal volume with the same center.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

vertices_list(B::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a box-shaped set.

Input

• B – box-shaped set

Output

A list of vertices.

Notes

For high dimensions, it is preferable to develop a vertex_iterator approach.

vertices_list(S::AbstractSingleton{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a set with a single value.

Input

• S – set with a single value

Output

A list containing only a single vertex.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

center(S::AbstractSingleton{N})::Vector{N} where {N<:Real}

Return the center of a set with a single value.

Input

• S – set with a single value

Output

The only element of the set.

radius_hyperrectangle(S::AbstractSingleton{N})::Vector{N} where {N<:Real}

Return the box radius of a set with a single value in every dimension.

Input

• S – set with a single value

Output

The zero vector.

radius_hyperrectangle(S::AbstractSingleton{N}, i::Int)::N where {N<:Real}

Return the box radius of a set with a single value in a given dimension.

Input

• S – set with a single value

Output

Zero.

an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric polytope.

Input

• P – point symmetric polytope

Output

The center of the point symmetric polytope.

an_element(S::AbstractSingleton{N})::Vector{N} where {N<:Real}

Return some element of a set with a single value.

Input

• S – set with a single value

Output

The only element in the set.

element(S::ZeroSet{N})::Vector{N} where {N<:Real}

Return the element of a zero set.

Input

• S – zero set

Output

The element of the zero set, i.e., a zero vector.

element(S::ZeroSet{N}, ::Int)::N where {N<:Real}

Return the i-th entry of the element of a zero set.

Input

• S – zero set

• i – dimension

Output

The i-th entry of the element of the zero set, i.e., 0.

Zonotope{N<:Real} <: AbstractPointSymmetricPolytope{N}

Type that represents a zonotope.

Fields

• center – center of the zonotope

• generators – matrix; each column is a generator of the zonotope

Notes

Mathematically, a zonotope is defined as the set

where $c \in \mathbb{R}^n$ is its center and $\{g_i\}_{i=1}^p$, $g_i \in \mathbb{R}^n$, is the set of generators. This characterization defines a zonotope as the finite Minkowski sum of line elements. Zonotopes can be equivalently described as the image of a unit infinity-norm ball in $\mathbb{R}^n$ by an affine transformation.

• Zonotope(center::AbstractVector{N}, generators::AbstractMatrix{N}) where {N<:Real}

• Zonotope(center::AbstractVector{N}, generators_list::AbstractVector{T} ) where {N<:Real, T<:AbstractVector{N}}

Examples

A two-dimensional zonotope with given center and set of generators:

julia> Z = Zonotope([1.0, 0.0], 0.1*eye(2))
LazySets.Zonotope{Float64}([1.0, 0.0], [0.1 0.0; 0.0 0.1])
julia> dim(Z)
2

Compute its vertices:

julia> vertices_list(Z)
4-element Array{Array{Float64,1},1}:
 [0.9, -0.1]
 [1.1, -0.1]
 [1.1, 0.1]
 [0.9, 0.1]

Evaluate the support vector in a given direction:

julia> σ([1., 1.], Z)
2-element Array{Float64,1}:
 1.1
 0.1

Alternative constructor: A zonotope in two dimensions with three generators:

julia> Z = Zonotope(ones(2), [[1., 0.], [0., 1.], [1., 1.]])
LazySets.Zonotope{Float64}([1.0, 1.0], [1.0 0.0 1.0; 0.0 1.0 1.0])
julia> Z.generators
2×3 Array{Float64,2}:
 1.0  0.0  1.0
 0.0  1.0  1.0

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{<:Real}, Z::Zonotope)::AbstractVector{<:Real}

Return the support vector of a zonotope in a given direction.

Input

• d – direction

• Z – zonotope

Output

Support vector in the given direction. If the direction has norm zero, the vertex with $ξ_i = 1 \ \ ∀ i = 1,…, p$ is returned.

∈(x::AbstractVector{N}, Z::Zonotope{N})::Bool where {N<:Real}

Check whether a given point is contained in a zonotope.

Input

• x – point/vector

• Z – zonotope

Output

true iff $x ∈ Z$.

Algorithm

This implementation poses the problem as a linear equality system and solves it using Base.:. A zonotope centered in the origin with generators $g_i$ contains a point $x$ iff $x = ∑_{i=1}^p ξ_i g_i$ for some $ξ_i \in [-1, 1]~~ ∀ i = 1,…, p$. Thus, we first ask for a solution and then check if it is in this Cartesian product of intervals.

Other algorithms exist which test the feasibility of an LP.

Examples

julia> Z = Zonotope([1.0, 0.0], 0.1*eye(2));

julia> ∈([1.0, 0.2], Z)
false
julia> ∈([1.0, 0.1], Z)
true

an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}

Return some element of a point symmetric polytope.

Input

• P – point symmetric polytope

Output

The center of the point symmetric polytope.

⊆(P::AbstractPolytope{N}, S::LazySet, witness::Bool=false
 )::Union{Bool,Tuple{Bool,Vector{N}}} where {N<:Real}

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

Output

• If witness option is deactivated: true iff $P ⊆ S$

• If witness option is activated:

  • (true, []) iff $P ⊆ S$

  • (false, v) iff $P \not\subseteq S$ and $v ∈ P \setminus S$

Algorithm

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

center(Z::Zonotope{N})::Vector{N} where {N<:Real}

Return the center of a zonotope.

Input

• Z – zonotope

Output

The center of the zonotope.

vertices_list(Z::Zonotope{N})::Vector{Vector{N}} where {N<:Real}

Return the vertices of a zonotope.

Input

• Z – zonotope

Output

List of vertices.

Notes

This implementation computes a convex hull.

For high dimensions, it would be preferable to develop a vertex_iterator approach.

singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}

Return the vertices of a polytopic as a list of singletons.

Input

• P – a polytopic set

Output

List containing a singleton for each vertex.

order(Z::Zonotope)::Rational

Return the order of a zonotope.

Input

• Z – zonotope

Output

A rational number representing the order of the zonotope.

Notes

The order of a zonotope is defined as the quotient of its number of generators and its dimension.