Interval

Interval{N} <: AbstractHyperrectangle{N}

Type representing an interval on the real line. Mathematically, it is of the form

\[[a, b] := \{ a ≤ x ≤ b \} ⊆ ℝ.\]

Fields

• dat – data container for the given interval

Notes

This type relies on the IntervalArithmetic.jl library for representation of intervals and arithmetic operations.

Examples

Unidimensional intervals are symbolic representations of a real closed interval.

We can create intervals in different ways. The simplest way is to pass a pair of numbers:

julia> x = Interval(0.0, 1.0)
Interval{Float64}([0, 1])

A 2-vector is also possible:

julia> x = Interval([0.0, 1.0])
Interval{Float64}([0, 1])

An interval can also be constructed from an IntervalArithmetic.Interval. Note that if the package IntervalArithmetic is loaded in the current scope, you have to prepend the package names to Intervals since there is a name conflict otherwise.

julia> using IntervalArithmetic
WARNING: using IntervalArithmetic.Interval in module Main conflicts with an existing identifier.

julia> x = LazySets.Interval(IntervalArithmetic.Interval(0.0, 1.0))
Interval{Float64}([0, 1])

julia> dim(x)
1

julia> center(x)
1-element Vector{Float64}:
 0.5

The usual pairwise arithmetic operators - and * are interpreted in the standard way known in interval arithmetic, so the results are Intervals. Note that + is generally used for the lazy Minkowksi sum in this library.

Intervals of other numeric types can be created as well, e.g., a rational interval:

julia> Interval(0//1, 2//1)
Interval{Rational{Int64}}([0//1, 2//1])

an_element(X::LazySet)

Return some element of a nonempty set.

Input

• X – set

Output

An element of X unless X is empty.

Extended help

an_element(x::Interval)

Algorithm

Return the left border (low(x)) of the interval.

chebyshev_center_radius(x::Interval; [kwargs]...)

Compute the Chebyshev center and the corresponding radius of an interval.

Input

• x – interval
• kwargs – further keyword arguments (ignored)

Output

The pair (c, r) where c is the Chebyshev center of x and r is the radius of the largest ball with center c enclosed by x.

Notes

The Chebyshev center of an interval is just the center of the interval.

isflat(x::Interval)

Check whether an interval is flat, i.e., whether its extreme values coincide.

Input

• x – interval

Output

true if the interval is flat and false otherwise.

Notes

For robustness with respect to floating-point inputs, this function relies on the result of isapproxzero when applied to the diameter of the interval. In other words, this function depends on the absolute zero tolerance ABSZTOL.

ngens(x::Interval)

Return the number of generators of an interval.

Input

• x – interval

Output

The number of generators.

Algorithm

An interval has either one generator, or zero generators if it is a degenerated interval of diameter zero.

radius_hyperrectangle(x::Interval)

Return the box radius of an interval in every dimension.

Input

• x – interval

Output

The box radius of the interval (a one-dimensional vector).

radius_hyperrectangle(x::Interval{N}, i::Int) where {N}

Return the box radius of an interval in a given dimension.

Input

• x – interval
• i – dimension index (must be 1)

Output

The box radius in the given dimension.

rand(T::Type{<:LazySet}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing
    )

Create a random set of the given set type.

Input

• T – set type
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random set of the given set type.

Extended help

rand(::Type{Interval}; [N]::Type{<:Real}=Float64, [dim]::Int=1,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Notes

All numbers are normally distributed with mean 0 and standard deviation 1.

rectify(X::LazySet)

Compute the rectification of a set.

Input

• X – set

Output

A set representing the rectification of X.

Extended help

rectify(x::Interval{N}) where {N}

Output

An Interval, even if it represents a singleton only containing the origin (which is the case if the original interval was nonpositive).

vertices_list(X::LazySet)

Compute a list of vertices of a polytopic set.

Input

• X – polytopic set

Output

A list of the vertices of X.

Extended help

vertices_list(x::Interval; kwargs...)

Output

The list of vertices of the interval, which are two one-dimensional vectors, or just one if the interval is degenerate (the endpoints match within the working tolerance).

linear_map(M::AbstractMatrix, X::LazySet)

Compute the linear map $M · X$.

Input

• M – matrix
• X – set

Output

A set representing the linear map $M · X$.

Extended help

linear_map(M::AbstractMatrix, x::Interval)

Output

Either an interval or a zonotope, depending on the leading dimension (i.e., the number of rows) of M:

• If size(M, 1) == 1, the output is an Interval obtained by scaling x by the matrix M.
• If size(M, 1) ≠ 1, the output is a Zonotope with center M * center(x) and the single generator M * g, where g = (high(x)-low(x))/2.

split(x::Interval, k)

Partition an interval into k uniform sub-intervals.

Input

• x – interval
• k – number of sub-intervals, possibly wrapped in a vector of length 1

Output

A list of k Intervals.

translate(X::LazySet, v::AbstractVector)

Compute the translation of a set with a vector.

Input

• X – set
• v – vector

Output

A set representing $X + \{v\}$.

Extended help

translate(x::Interval, v::AbstractVector)

Notes

An in-place version is not available because the IntervalArithmetic.Interval type is immutable.

difference(X::LazySet, Y::LazySet)

Compute the set difference of two sets.

Input

• X – set
• Y – set

Output

A set representing the difference $X ∖ Y$.

Notes

The set difference is defined as:

\[ X ∖ Y = \{x \mid x ∈ X \text{ and } x ∉ Y \}\]

Extended help

difference(X::Interval{N}, Y::Interval) where {N}

Output

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

• An EmptySet.
• An Interval.
• A UnionSet of two Interval sets.

Algorithm

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

• If $X$ and $Y$ do not overlap, i.e., if their intersection is empty, then the set difference is just $X$.
• Otherwise, let $Z = X ∩ Y ≠ ∅$, then $Z$ splits $X$ into either one or two intervals. The latter case happens when the bounds of $Y$ are strictly contained in $X$.

To check for strict inclusion, we assume that the inclusion is strict and then check whether the resulting intervals that cover $X$ (one to its left and one to its right, let them be L and R), obtained by intersection with $Y$, are flat. Three cases may arise:

• If both L and R are flat then $X = Y$ and the result is the empty set.
• If only L is flat, then the result is R, the remaining interval not covered by $Y$. Similarly, if only R is flat, then the result is L.
• Finally, if none of the intervals is flat, then $Y$ is strictly contained in $X$ and the set union of L and R is returned.

Examples

julia> X = Interval(0, 2); Y = Interval(1, 4); Z = Interval(2, 3);

julia> difference(X, X)
∅(1)

julia> difference(X, Y)
Interval{Float64}([0, 1])

julia> difference(Y, Z)
UnionSet{Float64, Interval{Float64}, Interval{Float64}}(Interval{Float64}([1, 2]), Interval{Float64}([3, 4]))

isdisjoint(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether two sets are disjoint (i.e., do not intersect), and optionally compute a witness.

Input

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

Output

• If the witness option is deactivated: true iff $X ∩ Y = ∅$
• If the witness option is activated:
  • (true, []) iff $X ∩ Y = ∅$
  • (false, v) iff $X ∩ Y ≠ ∅$ for some $v ∈ X ∩ Y$

Notes

The convenience alias is_intersection_empty is also available.

Extended help

isdisjoint(I1::Interval, I2::Interval, [witness]::Bool=false)

Algorithm

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

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

minkowski_difference(X::LazySet, Y::LazySet)

Compute the Minkowski difference of two sets.

Input

• X – set
• Y – set

Output

A set representing the Minkowski difference $X ⊖ Y$.

Notes

The Minkowski difference of two sets $X$ and $Y$ is defined as

\[ X ⊖ Y = \{x \mid x + y ∈ X ~∀~y ∈ Y\}\]

The convenience alias pontryagin_difference is also available.

There is some inconsistency in the literature regarding the naming conventions. In this library, both Minkowski difference and Pontryagin difference refer to the geometric difference of two sets.

Extended help

minkowski_difference(I1::Interval, I2::Interval)

Output

An Interval, or an EmptySet if the difference is empty.

plot_recipe(x::Interval{N}, [ε]=zero(N)) where {N}

Convert an interval to a pair (x, y) of points for plotting.

Input

• x – interval
• ε – (optional, default: 0) ignored, used for dispatch

Output

A pair (x, y) of two points that can be plotted.

Notes

We consider the interval as a line segment with y coordinate equal to zero.

min(x::Interval)

Return the lower component of an interval.

Input

• x – interval

Output

The lower (lo) component of the interval (a number).

max(x::Interval)

Return the higher or upper component of an interval.

Input

• x – interval

Output

The higher (hi) component of the interval (a number).

fast_interval_pow(a::IntervalArithmetic.Interval, n::Int)

Compute the nth power of an interval without using correct rounding.

Input

• a – interval (from IntervalArithmetic.jl)
• n – integer

Output

A non-rigorous approximation of a^n.

Notes

For a rigorous approximation with correct rounding, use a^n from IntervalArithmetic.jl.