Half-space (HalfSpace)

LazySets.HalfSpaceModule.HalfSpaceType
HalfSpace{N, VN<:AbstractVector{N}} <: AbstractPolyhedron{N}

Type that represents a (closed) half-space of the form $a⋅x ≤ b$.

Fields

  • a – normal direction (non-zero)
  • b – constraint

Examples

The half-space $x + 2y - z ≤ 3$:

julia> HalfSpace([1, 2, -1.], 3.)
HalfSpace{Float64, Vector{Float64}}([1.0, 2.0, -1.0], 3.0)

To represent the set $y ≥ 0$ in the plane, we can rearrange the expression as $0x - y ≤ 0$:

julia> HalfSpace([0, -1.], 0.)
HalfSpace{Float64, Vector{Float64}}([0.0, -1.0], 0.0)
source

Operations

LazySets.API.an_elementMethod
an_element(hs::HalfSpace)

Return some element of a half-space.

Input

  • hs – half-space

Output

An element on the defining hyperplane.

source
LazySets.API.complementMethod
complement(H::HalfSpace)

Return the complement of a half-space.

Input

  • H – half-space

Output

The half-space that is complementary to H. If $H: ⟨ a, x ⟩ ≤ b$, then this function returns the half-space $H′: ⟨ a, x ⟩ ≥ b$. (Note that complementarity is understood in a relaxed sense, since the intersection of $H$ and $H′$ is non-empty).

source
LazySets.constrained_dimensionsMethod
constrained_dimensions(hs::HalfSpace)

Return the indices in which a half-space is constrained.

Input

  • hs – half-space

Output

A vector of ascending indices i such that the half-space is constrained in dimension i.

Examples

A 2D half-space with constraint $x_1 ≥ 0$ is only constrained in dimension 1.

source
LazySets.API.constraints_listMethod
constraints_list(hs::HalfSpace)

Return the list of constraints of a half-space.

Input

  • hs – half-space

Output

A singleton list containing the half-space.

source
LazySets.API.dimMethod
dim(hs::HalfSpace)

Return the dimension of a half-space.

Input

  • hs – half-space

Output

The ambient dimension of the half-space.

source
Base.isemptyMethod
isempty(hs::HalfSpace)

Check if a half-space is empty.

Input

  • hs – half-space

Output

false.

source
LazySets.API.isuniversalFunction
isuniversal(hs::HalfSpace, [witness]::Bool=false)

Check whether a half-space is universal.

Input

  • P – half-space
  • witness – (optional, default: false) compute a witness if activated

Output

  • If witness option is deactivated: false
  • If witness option is activated: (false, v) where $v ∉ P$

Algorithm

Witness production falls back to an_element(::Hyperplane).

source
LinearAlgebra.normalizeMethod
normalize(hs::HalfSpace{N}, p::Real=N(2)) where {N}

Normalize a half-space.

Input

  • hs – half-space
  • p – (optional, default: 2) norm

Output

A new half-space whose normal direction $a$ is normalized, i.e., such that $‖a‖_p = 1$ holds.

source
Base.randMethod
rand(::Type{HalfSpace}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random half-space.

Input

  • HalfSpace – type for dispatch
  • 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 half-space.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1. Additionally, the constraint a is nonzero.

source
ReachabilityBase.Arrays.distanceMethod
distance(x::AbstractVector, H::HalfSpace{N}) where {N}

Compute the distance between point x and half-space H with respect to the Euclidean norm.

Input

  • x – vector
  • H – half-space

Output

A scalar representing the distance between point x and half-space H.

source
Base.:∈Method
∈(x::AbstractVector, hs::HalfSpace)

Check whether a given point is contained in a half-space.

Input

  • x – point/vector
  • hs – half-space

Output

true iff $x ∈ hs$.

Algorithm

We just check if $x$ satisfies $a⋅x ≤ b$.

source
LazySets.HalfSpaceModule.halfspace_leftMethod
halfspace_left(p::AbstractVector, q::AbstractVector)

Return a half-space describing the 'left' of a two-dimensional line segment through two points.

Input

  • p – first point
  • q – second point

Output

The half-space whose boundary goes through the two points p and q and which describes the left-hand side of the directed line segment pq.

Algorithm

The half-space $a⋅x ≤ b$ is calculated as a = [dy, -dx], where $d = (dx, dy)$ denotes the line segment pq, i.e., $\vec{d} = \vec{p} - \vec{q}$, and b = dot(p, a).

Examples

The left half-space of the "east" and "west" directions in two-dimensions are the upper and lower half-spaces:

julia> using LazySets: halfspace_left

julia> halfspace_left([0.0, 0.0], [1.0, 0.0])
HalfSpace{Float64, Vector{Float64}}([0.0, -1.0], 0.0)

julia> halfspace_left([0.0, 0.0], [-1.0, 0.0])
HalfSpace{Float64, Vector{Float64}}([0.0, 1.0], 0.0)

We create a box from the sequence of line segments that describe its edges:

julia> H1 = halfspace_left([-1.0, -1.0], [1.0, -1.0]);

julia> H2 = halfspace_left([1.0, -1.0], [1.0, 1.0]);

julia> H3 = halfspace_left([1.0, 1.0], [-1.0, 1.0]);

julia> H4 = halfspace_left([-1.0, 1.0], [-1.0, -1.0]);

julia> H = HPolygon([H1, H2, H3, H4]);

julia> B = BallInf([0.0, 0.0], 1.0);

julia> B ⊆ H && H ⊆ B
true
source
LazySets.HalfSpaceModule.halfspace_rightMethod
halfspace_right(p::AbstractVector, q::AbstractVector)

Return a half-space describing the 'right' of a two-dimensional line segment through two points.

Input

  • p – first point
  • q – second point

Output

The half-space whose boundary goes through the two points p and q and which describes the right-hand side of the directed line segment pq.

Algorithm

See the documentation of halfspace_left.

source
LazySets.HalfSpaceModule.iscomplementMethod
iscomplement(H1::HalfSpace{N}, H2::HalfSpace) where {N}

Check if two half-spaces complement each other.

Input

  • H1 – half-space
  • H2 – half-space

Output

true iff H1 and H2 are complementary, i.e., have opposite normal directions and identical boundaries (defining hyperplanes).

source
LazySets.API.projectMethod
project(H::HalfSpace, block::AbstractVector{Int}; [kwargs...])

Concrete projection of a half-space.

Input

  • H – half-space
  • block – block structure, a vector with the dimensions of interest

Output

A set representing the projection of the half-space H on the dimensions specified by block.

Algorithm

If the unconstrained dimensions of H are a subset of the block variables, the projection is applied to the normal direction of H. Otherwise, the projection results in the universal set.

The latter can be seen as follows. Without loss of generality consider projecting out a single and constrained dimension $xₖ$ (projecting out multiple dimensions can be modeled by repeatedly projecting out one dimension). We can write the projection as an existentially quantified linear constraint:

\[ ∃xₖ: a₁x₁ + … + aₖxₖ + … + aₙxₙ ≤ b\]

Since $aₖ ≠ 0$, there is always a value for $xₖ$ that satisfies the constraint for any valuation of the other variables.

Examples

Consider the half-space $x + y + 0⋅z ≤ 1$, whose ambient dimension is 3. The (trivial) projection in the three dimensions using the block of variables [1, 2, 3] is:

julia> H = HalfSpace([1.0, 1.0, 0.0], 1.0)
HalfSpace{Float64, Vector{Float64}}([1.0, 1.0, 0.0], 1.0)

julia> project(H, [1, 2, 3])
HalfSpace{Float64, Vector{Float64}}([1.0, 1.0, 0.0], 1.0)

Projecting along dimensions 1 and 2 only:

julia> project(H, [1, 2])
HalfSpace{Float64, Vector{Float64}}([1.0, 1.0], 1.0)

For convenience, one can use project(H, constrained_dimensions(H)) to return the half-space projected on the dimensions where it is constrained:

julia> project(H, constrained_dimensions(H))
HalfSpace{Float64, Vector{Float64}}([1.0, 1.0], 1.0)

If a constrained dimension is projected, we get the universal set of the dimension corresponding to the projection.

julia> project(H, [1, 3])
Universe{Float64}(2)

julia> project(H, [1])
Universe{Float64}(1)
source
LazySets.API.ρMethod
ρ(d::AbstractVector, hs::HalfSpace)

Evaluate the support function of a half-space in a given direction.

Input

  • d – direction
  • hs – half-space

Output

The support function of the half-space. Unless the direction is (a multiple of) the normal direction of the half-space, the result is Inf.

source
LazySets.API.σMethod
σ(d::AbstractVector, hs::HalfSpace)

Return the support vector of a half-space in a given direction.

Input

  • d – direction
  • hs – half-space

Output

The support vector in the given direction, which is only defined in the following two cases:

  1. The direction has norm zero.
  2. The direction is (a multiple of) the normal direction of the half-space.

In both cases the result is any point on the boundary (the defining hyperplane). Otherwise this function throws an error.

source
LazySets.API.translateMethod
translate(hs::HalfSpace, v::AbstractVector; [share]::Bool=false)

Translate (i.e., shift) a half-space by a given vector.

Input

  • hs – half-space
  • v – translation vector
  • share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Output

A translated half-space.

Notes

The normal vectors of the half-space (vector a in a⋅x ≤ b) is shared with the original half-space if share == true.

Algorithm

A half-space $a⋅x ≤ b$ is transformed to the half-space $a⋅x ≤ b + a⋅v$. In other words, we add the dot product $a⋅v$ to $b$.

source

Inherited from LazySet:

Inherited from AbstractPolyhedron: