Hyperrectangles (AbstractHyperrectangle)

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

Among other functions, the following functions are then automatically defined:

• isflat(::AbstractHyperrectangle) – check whether the hyperrectangle's radius is zero in some dimension
• radius_hyperrectangle(::AbstractHyperrectangle, i::Int) – return the hyperrectangle's radius in the i-th 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

radius_hyperrectangle(H::AbstractHyperrectangle)

Return the hyperrectangle radius of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

The hyperrectangle radius of H, which is a full-dimensional vector.

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

constraints_list(X::LazySet)

Compute a list of linear constraints of a polyhedral set.

Input

• X – polyhedral set

Output

A list of the linear constraints of X.

Extended help

constraints_list(H::AbstractHyperrectangle)

Output

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

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.

ngens(Z::AbstractZonotope)

Return the number of generators of a zonotopic set.

Input

• Z – zonotopic set

Output

An integer representing the number of generators.

Extended help

ngens(H::AbstractHyperrectangle)

Algorithm

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

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

Return the norm of a set.

Input

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

Output

A real number representing the norm.

Notes

The norm of a set is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.

Extended help

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

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

radius(X::LazySet, [p]::Real=Inf)

Return the radius of a set.

Input

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

Output

A real number representing the radius.

Notes

The radius of a set is the radius of the enclosing ball (of the given $p$-norm) of minimal volume with the same center.

Extended help

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

Notes

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

radius_hyperrectangle(H::AbstractHyperrectangle, i::Int)

Return the hyperrectangle radius of a hyperrectangular set in a given dimension.

Input

• H – hyperrectangular set
• i – dimension

Output

The hyperrectangle radius of H in dimension i.

rectify(X::LazySet)

Compute the rectification of a set.

Input

• X – set

Output

A set representing the rectification of X.

Extended help

rectify(H::AbstractHyperrectangle)

Output

A Hyperrectangle.

reflect(X::LazySet)

Compute the reflection of a set in the origin.

Input

• X – set

Output

A set representing the reflection $-X$.

Extended help

reflect(H::AbstractHyperrectangle)

Output

A Hyperrectangle.

Algorithm

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

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(H::AbstractHyperrectangle; kwargs...)

Notes

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.

volume(X::LazySet)

Compute the volume, or Lebesgue measure, of a set.

Input

• X – set

Output

A real number representing the Lebesgue measure of X.

Notes

The Lebesgue measure has the following common special cases:

• In 1D, it coincides with the length.
• In 2D, it coincides with the area (see also area).
• In 3D, it coincides with the volume.

In higher dimensions, it is also known as the hypervolume or simply volume.

Extended help

volume(H::AbstractHyperrectangle)

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

∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

∈(x::AbstractVector, H::AbstractHyperrectangle)

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

split(H::AbstractHyperrectangle, num_blocks::AbstractVector{Int})

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.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

A convenience alias support_vector is also available.

Extended help

σ(d::AbstractVector, H::AbstractHyperrectangle)

Notes

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.

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::AbstractHyperrectangle, Y::AbstractHyperrectangle)

Output

A UnionSetArray consisting of the union of hyperrectangles. Note that this union is in general not convex.

Algorithm

This implementation uses IntervalArithmetic.setdiff.

intersection(X::LazySet, Y::LazySet)

Compute the intersection of two sets.

Input

• X – set
• Y – set

Output

A set representing the intersection $X ∩ Y$.

Notes

The intersection of two sets $X$ and $Y$ is defined as

\[ X ∩ Y = \{x \mid x ∈ X \text{ and } x ∈ Y\}.\]

intersection(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)

Compute the intersection of two hyperrectangular sets.

Input

• H1 – hyperrectangular set
• H2 – hyperrectangular set

Output

If the hyperrectangular sets 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 hyperrectangular sets. If these borders contradict, then the intersection is empty. Otherwise the resulting hyperrectangle uses these borders in each dimension.

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(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle,
           [witness]::Bool=false)

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.

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

Check whether a set is a subset of another set, 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 issubset is also available.

Extended help

⊆(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle,
  [witness]::Bool=false)

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.

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 = \{z \mid \{z\} ⊕ Y ⊆ X\}\]

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(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)

Output

A Hyperrectangle, or an EmptySet if the difference is empty.

minkowski_sum(X::LazySet, Y::LazySet)

Compute the Minkowski sum of two sets.

Input

• X – set
• Y – set

Output

A set representing the Minkowski sum $X ⊕ Y$.

Notes

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

\[ X ⊕ Y = \{x + y \mid x ∈ X, y ∈ Y\}.\]

Extended help

minkowski_sum(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)

Algorithm

The resulting hyperrectangle is obtained by summing up the centers and radii.