Binary Functions on Sets

⊆(x::Interval, y::Interval)

Check whether an interval is contained in another interval.

Input

• x – interval

• y – interval

Output

true iff $x ⊆ y$.

is_subset(S::LazySet{N}, 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.

is_subset(S::LazySet{N}, 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.

is_subset(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$.

is_subset(P::AbstractPolytope{N}, S::LazySet{N}, [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_subset(S::LazySet{N}, 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.

is_subset(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$.

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

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

Input

• H1 – inner hyperrectangle

• H2 – outer 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 \not\subseteq 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.

is_subset(P::AbstractPolytope{N}, S::LazySet{N}, [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_subset(P::AbstractPolytope{N}, S::LazySet{N}, [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_subset(P::AbstractPolytope{N}, S::LazySet{N}, [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_subset(S::AbstractSingleton{N}, set::LazySet{N}, [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_subset(S::LazySet{N}, 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.

is_subset(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$.

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

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

Input

• H1 – inner hyperrectangle

• H2 – outer 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 \not\subseteq 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.

is_subset(P::AbstractPolytope{N}, S::LazySet{N}, [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_subset(S::AbstractSingleton{N}, set::LazySet{N}, [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_subset(S::AbstractSingleton{N},
          H::AbstractHyperrectangle{N},
          [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 hyperrectangle, and if not, optionally compute a witness.

Input

• S – inner set with a single value

• 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$

Notes

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

is_subset(S::LazySet{N}, 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.

is_subset(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$.

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

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

Input

• H1 – inner hyperrectangle

• H2 – outer 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 \not\subseteq 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.

is_subset(P::AbstractPolytope{N}, S::LazySet{N}, [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_subset(S::AbstractSingleton{N}, set::LazySet{N}, [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_subset(S::AbstractSingleton{N},
          H::AbstractHyperrectangle{N},
          [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 hyperrectangle, and if not, optionally compute a witness.

Input

• S – inner set with a single value

• 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$

Notes

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

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

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 \not\subseteq S2$ and $v ∈ S1 \setminus S2$

is_subset(B1::Ball2{N}, B2::Ball2{N}, [witness]::Bool=false
         )::Union{Bool, Tuple{Bool, Vector{N}}} where {N<:Real}

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 \not\subseteq B2$ and $v ∈ B1 \setminus B2$

Algorithm

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

is_subset(S::LazySet{N}, 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.

is_subset(B::Union{Ball2{N}, Ballp{N}},
          S::AbstractSingleton{N},
          [witness]::Bool=false
         )::Union{Bool, Tuple{Bool, Vector{N}}} where {N<:Real}

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

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

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

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

Check whether a singleton and a convex set do not intersect, and otherwise 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, []) iff $S ∩ \operatorname{set} = ∅$

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

Algorithm

$S ∩ \operatorname{set} = ∅$ iff element(S) $∉ \operatorname{set}$.

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

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

Input

• S – singleton

• H – hyperrectangle

• 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

$S ∩ H = ∅$ iff element(S) $∉ H$.

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

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

Check whether a convex set and a singleton do not intersect, and otherwise 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, []) iff $S ∩ \operatorname{set} = ∅$

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

Algorithm

$S ∩ \operatorname{set} = ∅$ iff element(S) $∉ \operatorname{set}$.

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

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

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

Check whether a singleton and a convex set do not intersect, and otherwise 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, []) iff $S ∩ \operatorname{set} = ∅$

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

Algorithm

$S ∩ \operatorname{set} = ∅$ iff element(S) $∉ \operatorname{set}$.

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

Check whether a convex set and a singleton do not intersect, and otherwise 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, []) iff $S ∩ \operatorname{set} = ∅$

  • (false, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S) $∈ 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 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.

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

Check whether a singleton and a convex set do not intersect, and otherwise 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, []) iff $S ∩ \operatorname{set} = ∅$

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

Algorithm

$S ∩ \operatorname{set} = ∅$ iff element(S) $∉ \operatorname{set}$.

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

Check whether a convex set and a singleton do not intersect, and otherwise 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, []) iff $S ∩ \operatorname{set} = ∅$

  • (false, v) iff $S ∩ \operatorname{set} ≠ ∅$ and v = element(S) $∈ 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 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$.

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

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

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

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

Input

• S – singleton

• H – hyperrectangle

• 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

$S ∩ H = ∅$ iff element(S) $∉ H$.

is_intersection_empty(Z::Zonotope{N}, H::Hyperplane{N}, witness::Bool=false
                     )::Union{Bool, Tuple{Bool, Vector{N}}} where {N<:Real}

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.

Notes

Witness production is currently not supported.

is_intersection_empty(H::Hyperplane{N}, Z::Zonotope{N}, witness::Bool=false
                     )::Union{Bool, Tuple{Bool, Vector{N}}} where {N<:Real}

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

Input

• H – hyperplane

• Z – zonotope

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

Output

• If witness option is deactivated: true iff $H ∩ Z = ∅$

• If witness option is activated:

  • (true, []) iff $H ∩ Z = ∅$

  • (false, v) iff $H ∩ Z ≠ ∅$ and $v ∈ H ∩ Z$

Algorithm

$H ∩ Z = ∅$ 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.

Notes

Witness production is currently not supported.

is_intersection_empty(B1::Ball2{N},
                      B2::Ball2{N},
                      witness::Bool=false
                     )::Union{Bool, Tuple{Bool,Vector{N}}} where {N<:Real}

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.

is_intersection_empty(ls1::LineSegment{N},
                      ls2::LineSegment{N},
                      witness::Bool=false
                     )::Union{Bool, Tuple{Bool, Vector{N}}} where {N<:Real}

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.

intersection(L1::Line{N}, L2::Line{N}
            )::Union{Singleton{N}, Line{N}, EmptySet{N}} where {N<:Real}

Return the intersection of two 2D lines.

Input

• L1 – first line

• L2 – second line

Output

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.

Examples

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

julia> intersection(Line([-1., 1.], 0.), Line([1., 1.], 1.))
LazySets.Singleton{Float64}([0.5, 0.5])
julia> intersection(Line([1., 1.], 1.), Line([1., 1.], 1.))
LazySets.Line{Float64,Array{Float64,1}}([1.0, 1.0], 1.0)

intersection(H1::AbstractHyperrectangle{N},
             H2::AbstractHyperrectangle{N}
            )::Union{<:Hyperrectangle{N}, EmptySet{N}} where {N<:Real}

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.