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])

convert(::Type{Interval}, X::LazySet)

Convert a one-dimensional convex set to an interval.

Input

• Interval – interval target type
• X – one-dimensional convex set

Output

An interval.

Examples

julia> convert(Interval, Hyperrectangle([0.5], [0.5]))
Interval{Float64}([0, 1])

convert(::Type{IntervalArithmetic.Interval}, X::LazySet)

Convert a convex set to an Interval from IntervalArithmetic.

Input

• Interval – target type, from IntervalArithmetic
• X – convex set

Output

An IntervalArithmetic.Interval.

convert(::Type{Interval}, x::IntervalArithmetic.Interval)

Convert an Interval from IntervalArithmetic to an Interval in LazySets.

Input

• Interval – target type
• x – interval (IntervalArithmetic.Interval)

Output

A LazySets.Interval.

an_element(x::Interval)

Return some element of an interval.

Input

• x – interval

Output

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

center(x::Interval)

Return the center of an interval.

Input

• x – interval

Output

The center, or midpoint, of x.

center(H::Interval, i::Int)

Return the center along a given dimension of a interval.

Input

• x – interval
• i – dimension of interest

Output

The center along a given dimension 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.

constraints_list(x::Interval)

Return the list of constraints of an interval.

Input

• x – interval

Output

The list of constraints of the interval represented as two one-dimensional half-spaces.

diameter(x::Interval, [p]::Real=Inf)

Compute the diameter of an interval, defined as $‖b - a‖$ in the $p`-norm, where$a$(resp.$b``) are the minimum (resp. maximum) value of the interval.

Input

• x – interval
• p – (optional, default: Inf) norm (ignored)

Output

A real number representing the diameter.

Notes

In one dimension, all p-norms are identical.

dim(x::Interval)

Return the ambient dimension of an interval.

Input

• x – interval

Output

$1$.

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(::Type{Interval}; [N]::Type{<:Real}=Float64, [dim]::Int=1,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random interval.

Input

• Interval – type for dispatch
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 1) dimension
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random interval.

Algorithm

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

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

Concrete rectification of an interval.

Input

• x – interval

Output

The Interval that corresponds to the rectification of x.

Notes

Note that the result is an Interval even if the set becomes a singleton (which is the case if the original interval was nonpositive).

reflect(x::Interval)

Concrete reflection of a interval x, resulting in the reflected set -x.

Input

• x – interval

Output

The Interval representing -x.

Algorithm

If $x = [a, b]$, then $-x = [-b, -a]$.

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

Return the list of vertices of an interval.

Input

• x – interval

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

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

Check whether a given point is contained in an interval.

Input

• v – point/vector
• x – interval

Output

true iff $v ∈ x$.

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

Concrete linear map of an interval.

Input

• M – matrix
• 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.

scale(α::Real, x::Interval)

Concrete scaling of an interval.

Input

• α – scalar
• x – interval

Output

The interval obtained by scaling the given interval.

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.

ρ(d::AbstractVector, x::Interval)

Evaluate the support function of an interval in a given direction.

Input

• d – direction
• x – interval

Output

Evaluation of the support function in the given direction.

σ(d::AbstractVector, x::Interval)

Return the support vector of an interval in a given direction.

Input

• d – direction
• x – interval

Output

The support vector in the given direction.

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

Translate (i.e., shift) an interval by a given vector.

Input

• x – interval
• v – translation vector

Output

A translated interval.

Algorithm

We add the vector to the left and right of the interval.

Notes

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

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

Compute the set difference between two intervals.

Input

• X – first interval
• Y – second interval

Output

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

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

Algorithm

Let $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);

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

intersection(x::Interval, y::Interval)

Compute the intersection of two intervals.

Input

• x – interval
• y – interval

Output

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

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

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

Input

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

Output

• If witness option is deactivated: true iff $I1 ∩ I2 = ∅$
• If witness option is activated:
  • (true, []) iff $I1 ∩ I2 = ∅$
  • (false, v) iff $I1 ∩ I2 ≠ ∅$ and $v ∈ I1 ∩ I2$

Algorithm

$I1 ∩ I2 ≠ ∅$ iff there is a gap between the left-most point of the second interval and the 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.

⊆(x::Interval, y::Interval, [witness]::Bool=false)

Check whether an interval is contained in another interval.

Input

• x – inner interval
• y – outer interval
• witness – (optional, default: false) compute a witness if activated

Output

true iff $x ⊆ y$.

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

Compute the Minkowski difference of two intervals.

Input

• I1 – interval
• I2 – interval

Output

An Interval that corresponds to the Minkowski difference of I1 minus I2, or an EmptySet if the difference is empty.

minkowski_sum(x::Interval, y::Interval)

Concrete Minkowski sum of a pair of intervals.

Input

• x – interval
• y – interval

Output

An Interval corresponding to the Minkowski sum of x and y.

Algorithm

The implementation takes the sum of x and y following the rules of interval arithmetic.

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.