Hyperrectangles (AbstractHyperrectangle)

A hyperrectangle is a special centrally symmetric polytope with axis-aligned facets.

LazySets.AbstractHyperrectangleType
AbstractHyperrectangle{N} <: AbstractZonotope{N}

Abstract type for hyperrectangular sets.

Notes

See Hyperrectangle for a standard implementation of this interface.

Every concrete AbstractHyperrectangle must define the following functions:

  • radius_hyperrectangle(::AbstractHyperrectangle) – return the hyperrectangle's radius, which is a full-dimensional vector

  • radius_hyperrectangle(::AbstractHyperrectangle, i::Int) – return the hyperrectangle's radius in the i-th dimension

  • isflat(::AbstractHyperrectangle) – check whether the hyperrectangle's radius is zero in some dimension

Every hyperrectangular set is also a zonotopic set; see AbstractZonotope.

The subtypes of AbstractHyperrectangle (including abstract interfaces):

julia> subtypes(AbstractHyperrectangle)
5-element Vector{Any}:
 AbstractSingleton
 BallInf
 Hyperrectangle
 Interval
 SymmetricIntervalHull
source

This interface defines the following functions:

LazySets.□Method
□(c, r)

Convenience constructor of Hyperrectangles or BallInfs depending on the type of r.

Input

  • c – center
  • r – radius (either a vector for Hyperrectangle or a number for BallInf)

Output

A Hyperrectangles or BallInfs depending on the type of r.

Notes

The function symbol can be typed via \square[TAB].

source
LinearAlgebra.normFunction
norm(H::AbstractHyperrectangle, [p]::Real=Inf)

Return the norm of a hyperrectangular set.

The norm of a hyperrectangular set is defined as the norm of the enclosing ball of the given $p$-norm, of minimal volume, that is centered in the origin.

Input

  • H – hyperrectangular set
  • p – (optional, default: Inf) norm

Output

A real number representing the norm.

Algorithm

Recall that the norm is defined as

\[‖ X ‖ = \max_{x ∈ X} ‖ x ‖_p = max_{x ∈ \text{vertices}(X)} ‖ x ‖_p.\]

The last equality holds because the optimum of a convex function over a polytope is attained at one of its vertices.

This implementation uses the fact that the maximum is attained in the vertex $c + \text{diag}(\text{sign}(c)) r$ for any $p$-norm. Hence it suffices to take the $p$-norm of this particular vertex. This statement is proved below. Note that, in particular, there is no need to compute the $p$-norm for each vertex, which can be very expensive.

If $X$ is a hyperrectangle and the $n$-dimensional vectors center and radius of the hyperrectangle are denoted $c$ and $r$ respectively, then reasoning on the $2^n$ vertices we have that:

\[\max_{x ∈ \text{vertices}(X)} ‖ x ‖_p = \max_{α_1, …, α_n ∈ \{-1, 1\}} (|c_1 + α_1 r_1|^p + ... + |c_n + α_n r_n|^p)^{1/p}.\]

The function $x ↦ x^p$, $p > 0$, is monotonically increasing and thus the maximum of each term $|c_i + α_i r_i|^p$ is given by $|c_i + \text{sign}(c_i) r_i|^p$ for each $i$. Hence, $x^* := \text{argmax}_{x ∈ X} ‖ x ‖_p$ is the vertex $c + \text{diag}(\text{sign}(c)) r$.

source
IntervalArithmetic.radiusFunction
radius(H::AbstractHyperrectangle, [p]::Real=Inf)

Return the radius of a hyperrectangular set.

Input

  • H – hyperrectangular set
  • 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. It is the same for all corners of a hyperrectangular set.

source
LazySets.σMethod
σ(d::AbstractVector, H::AbstractHyperrectangle)

Return a support vector of a hyperrectangular set in a given direction.

Input

  • d – direction
  • H – hyperrectangular set

Output

A support vector in the given direction.

If the direction vector is zero in dimension $i$, the result will have the center's coordinate in that dimension. For instance, for the two-dimensional infinity-norm ball, if the direction points to the right, the result is the vector [1, 0] in the middle of the right-hand facet.

If the direction has norm zero, the result can be any point in H. The default implementation returns the center of H.

source
LazySets.ρMethod
ρ(d::AbstractVector, H::AbstractHyperrectangle)

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

Input

  • d – direction
  • H – hyperrectangular set

Output

The evaluation of the support function in the given direction.

source
Base.:∈Method
∈(x::AbstractVector, H::AbstractHyperrectangle)

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

Input

  • x – point/vector
  • H – hyperrectangular set

Output

true iff $x ∈ H$.

Algorithm

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

source
LazySets.vertices_listMethod
vertices_list(H::AbstractHyperrectangle; kwargs...)

Return the list of vertices of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

A list of vertices. Zeros in the radius are correctly handled, i.e., the result does not contain any duplicate vertices.

Algorithm

First we identify the dimensions where H is flat, i.e., its radius is zero. We also compute the number of vertices that we have to create.

Next we create the vertices. We do this by enumerating all vectors v of length n (the dimension of H) with entries -1/0/1 and construct the corresponding vertex as follows:

\[ \text{vertex}(v)(i) = \begin{cases} c(i) + r(i) & v(i) = 1 \\ c(i) & v(i) = 0 \\ c(i) - r(i) & v(i) = -1. \end{cases}\]

For enumerating the vectors v, we modify the current v from left to right by changing entries -1 to 1, skipping entries 0, and stopping at the first entry 1 (but changing it to -1). This way we only need to change the vertex in those dimensions where v has changed, which usually is a smaller number than n.

source
LazySets.constraints_listMethod
constraints_list(H::AbstractHyperrectangle{N}) where {N}

Return the list of constraints of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

A list of $2n$ linear constraints, where $n$ is the dimension of H.

source
constraints_list(U::Universe{N}) where {N}

Return the list of constraints defining a universe.

Input

  • U – universe

Output

The empty list of constraints, as the universe is unconstrained.

source
LazySets.highMethod
high(H::AbstractHyperrectangle)

Return the higher coordinates of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

A vector with the higher coordinates of the hyperrectangular set.

source
LazySets.highMethod
high(H::AbstractHyperrectangle, i::Int)

Return the higher coordinate of a hyperrectangular set in a given dimension.

Input

  • H – hyperrectangular set
  • i – dimension of interest

Output

The higher coordinate of the hyperrectangular set in the given dimension.

source
LazySets.lowMethod
low(H::AbstractHyperrectangle)

Return the lower coordinates of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

A vector with the lower coordinates of the hyperrectangular set.

source
LazySets.lowMethod
low(H::AbstractHyperrectangle, i::Int)

Return the lower coordinate of a hyperrectangular set in a given dimension.

Input

  • H – hyperrectangular set
  • i – dimension of interest

Output

The lower coordinate of the hyperrectangular set in the given dimension.

source
Base.extremaMethod
extrema(H::AbstractHyperrectangle)

Return the lower and higher coordinates of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

The lower and higher coordinates of the set.

Notes

The result is equivalent to (low(H), high(H)).

source
Base.extremaMethod
extrema(H::AbstractHyperrectangle, i::Int)

Return the lower and higher coordinate of a hyperrectangular set in a given dimension.

Input

  • H – hyperrectangular set
  • i – dimension of interest

Output

The lower and higher coordinate of the set in the given dimension.

Notes

The result is equivalent to (low(H, i), high(H, i)).

source
LazySets.isflatMethod
isflat(H::AbstractHyperrectangle)

Check whether a hyperrectangular set is flat, i.e., whether its radius is zero in some dimension.

Input

  • H – hyperrectangular set

Output

true iff the hyperrectangular set is flat.

Notes

For robustness with respect to floating-point inputs, this function relies on the result of isapproxzero when applied to the radius in some dimension. Hence this function depends on the absolute zero tolerance ABSZTOL.

source
Base.splitMethod
split(H::AbstractHyperrectangle{N},
      num_blocks::AbstractVector{Int}) where {N}

Partition a hyperrectangular set into uniform sub-hyperrectangles.

Input

  • H – hyperrectangular set
  • num_blocks – number of blocks in the partition for each dimension

Output

A list of Hyperrectangles.

source
LazySets.generatorsMethod
generators(H::AbstractHyperrectangle)

Return an iterator over the generators of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

An iterator over the generators of H.

source
LazySets.genmatMethod

genmat(H::AbstractHyperrectangle)

Return the generator matrix of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

A matrix where each column represents one generator of H.

source
LazySets.ngensMethod
ngens(H::AbstractHyperrectangle{N}) where {N}

Return the number of generators of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

The number of generators.

Algorithm

A hyperrectangular set has one generator for each non-flat dimension.

source
ReachabilityBase.Arrays.rectifyMethod
rectify(H::AbstractHyperrectangle)

Concrete rectification of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

The Hyperrectangle that corresponds to the rectification of H.

source
LazySets.volumeMethod
volume(H::AbstractHyperrectangle)

Return the volume of a hyperrectangular set.

Input

  • H – hyperrectangular set

Output

The volume of $H$.

Algorithm

The volume of the $n$-dimensional hyperrectangle $H$ with radius vector $r$ is $2ⁿ ∏ᵢ rᵢ$ where $rᵢ$ denotes the $i$-th component of $r$.

source
ReachabilityBase.Arrays.distanceMethod
distance(x::AbstractVector, H::AbstractHyperrectangle{N};
         [p]::Real=N(2)) where {N}

Compute the distance between a point x and a hyperrectangular set H with respect to the given p-norm.

Input

  • x – point/vector
  • H – hyperrectangular set

Output

A scalar representing the distance between point x and hyperrectangle H.

source
LazySets.reflectMethod
reflect(H::AbstractHyperrectangle)

Concrete reflection of a hyperrectangular set H, resulting in the reflected set -H.

Input

  • H – hyperrectangular set

Output

A Hyperrectangle representing -H.

Algorithm

If $H$ has center $c$ and radius $r$, then $-H$ has center $-c$ and radius $r$.

source

Implementations

Concrete set representations:

Lazy set operations: