Half-space (HalfSpace)

LazySets.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 have to rearrange the expression as $0x - y ≤ 0$:

julia> HalfSpace([0, -1.], 0.)
HalfSpace{Float64, Vector{Float64}}([0.0, -1.0], 0.0)
source
LazySets.dimMethod
dim(hs::HalfSpace)

Return the dimension of a half-space.

Input

  • hs – half-space

Output

The ambient dimension of the half-space.

source
LazySets.ρ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. If the set is unbounded in the given direction, the result is Inf.

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

Return the support vector of a half-space.

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 the half-space's normal direction.

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

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.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
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
LinearAlgebra.normalizeMethod
normalize(hs::HalfSpace{N}, p=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
LazySets.isboundedMethod
isbounded(hs::HalfSpace)

Determine whether a half-space is bounded.

Input

  • hs – half-space

Output

false.

source
LazySets.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 isuniversal(::Hyperplane).

source
Base.isemptyMethod
isempty(hs::HalfSpace)

Return if a half-space is empty or not.

Input

  • hs – half-space

Output

false.

source
LazySets.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.constraints_listMethod
constraints_list(A::AbstractMatrix{N}, b::AbstractVector)

Convert a matrix-vector representation to a linear-constraint representation.

Input

  • A – matrix
  • b – vector

Output

A list of linear constraints.

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 $x1 ≥ 0$ is constrained in dimension 1 only.

source
LazySets.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 halfspace (vector a in a⋅x ≤ b) is shared with the original halfspace 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
LazySets.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 implementation is simple: the half-space $a⋅x ≤ b$ is calculated as a = [dy, -dx], where $d = (dx, dy)$ denotes the line segment pq, that is, $\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.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.tosimplehrepMethod
tosimplehrep(constraints::AbstractVector{LC};
             [n]::Int=0) where {N, LC<:LinearConstraint{N}}

Return the simple H-representation $Ax ≤ b$ from a list of linear constraints.

Input

  • constraints – a list of linear constraints
  • n – (optional; default: 0) dimension of the constraints

Output

The tuple (A, b) where A is the matrix of normal directions and b is the vector of offsets.

Notes

The parameter n can be used to create a matrix with no constraints but a non-zero dimension.

source
LazySets.remove_redundant_constraintsFunction
remove_redundant_constraints(constraints::AbstractVector{<:LinearConstraint{N}};
                             backend=default_lp_solver(N)) where {N}

Remove the redundant constraints of a given list of linear constraints.

Input

  • constraints – list of constraints
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

The list of constraints with the redundant ones removed, or an empty set if the constraints are infeasible.

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:LinearConstraint}) for details.

source
remove_redundant_constraints(P::HPoly{N};
                             backend=default_lp_solver(N)) where {N}

Remove the redundant constraints in a polyhedron in H-representation.

Input

  • P – polyhedron
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

A polyhedron equivalent to P but with no redundant constraints, or an empty set if P is detected to be empty, which may happen if the constraints are infeasible.

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:LinearConstraint}) for details.

source
LazySets.remove_redundant_constraints!Function
remove_redundant_constraints!(constraints::AbstractVector{<:LinearConstraint{N}};
                              backend=default_lp_solver(N)) where {N}

Remove the redundant constraints of a given list of linear constraints; the list is updated in-place.

Input

  • constraints – list of constraints
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

true if the function was successful and the list of constraints constraints is modified by removing the redundant constraints, and false only if the constraints are infeasible.

Notes

Note that the result may be true even if the constraints are infeasible. For example, $x ≤ 0 && x ≥ 1$ will return true without removing any constraint. To check if the constraints are infeasible, use isempty(HPolyhedron(constraints)).

Algorithm

If there are m constraints in n dimensions, this function checks one by one if each of the m constraints is implied by the remaining ones.

To check if the k-th constraint is redundant, an LP is formulated using the constraints that have not yet being removed. If, at an intermediate step, it is detected that a subgroup of the constraints is infeasible, this function returns false. If the calculation finished successfully, this function returns true.

For details, see Fukuda's Polyhedra FAQ.

source
remove_redundant_constraints!(P::AbstractHPolygon)

Remove all redundant constraints of a polygon in constraint representation.

Input

  • P – polygon in constraint representation

Output

The same polygon with all redundant constraints removed.

Notes

Since we only consider bounded polygons and a polygon needs at least three constraints to be bounded, we stop removing redundant constraints if there are three or less constraints left. This means that for non-bounded polygons the result may be unexpected.

Algorithm

We go through all consecutive triples of constraints and check if the one in the middle is redundant. For this we assume that the constraints are sorted.

source
remove_redundant_constraints!(P::HPoly{N};
                              backend=default_lp_solver(N)) where {N}

Remove the redundant constraints in a polyhedron in H-representation; the polyhedron is updated in-place.

Input

  • P – polyhedron
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

true if the method was successful and the polyhedron P is modified by removing its redundant constraints, and false if P is detected to be empty, which may happen if the constraints are infeasible.

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:LinearConstraint}) for details.

source
LazySets.complementMethod
complement(H::HalfSpace)

Return the complement of a half-space.

Input

  • H – halfspace

Output

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

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

Concrete projection of a half-space.

Input

  • H – set
  • 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 a projection onto a single and constrained dimension $xₖ$ (projections in multiple dimensions can be modeled as repeated one-dimensional projections). 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 is achieved letting the block of variables to be [1, 2, 3]:

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)

In general, use the call syntax project(H, constrained_dimensions(H)) to return the half-space projected on the dimensions where it is constrained only:

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

Inherited from ConvexSet: