Half-space (HalfSpace)

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)

LinearConstraint

Alias for HalfSpace

an_element(hs::HalfSpace)

Return some element of a half-space.

Input

• hs – half-space

Output

An element on the defining hyperplane.

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

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.

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.

dim(hs::HalfSpace)

Return the dimension of a half-space.

Input

• hs – half-space

Output

The ambient dimension of the half-space.

isbounded(hs::HalfSpace)

Check whether a half-space is bounded.

Input

• hs – half-space

Output

false.

isempty(hs::HalfSpace)

Check if a half-space is empty.

Input

• hs – half-space

Output

false.

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

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.

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.

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.

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

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

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.

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

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)

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

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

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