# Half-space (HalfSpace)

`LazySets.HalfSpace`

— Type`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)
```

`LazySets.LinearConstraint`

— Type`LinearConstraint`

Alias for `HalfSpace`

`LazySets.dim`

— Method`dim(hs::HalfSpace)`

Return the dimension of a half-space.

**Input**

`hs`

– half-space

**Output**

The ambient dimension of the half-space.

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

.

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

- The direction has norm zero.
- 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.

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

`LazySets.an_element`

— Method`an_element(hs::HalfSpace)`

Return some element of a half-space.

**Input**

`hs`

– half-space

**Output**

An element on the defining hyperplane.

`Base.rand`

— Method```
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.

`LinearAlgebra.normalize`

— Method`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.

`LazySets.isbounded`

— Method`isbounded(hs::HalfSpace)`

Determine whether a half-space is bounded.

**Input**

`hs`

– half-space

**Output**

`false`

.

`LazySets.isuniversal`

— Function`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)`

.

`Base.isempty`

— Method`isempty(hs::HalfSpace)`

Return if a half-space is empty or not.

**Input**

`hs`

– half-space

**Output**

`false`

.

`LazySets.constraints_list`

— Method`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.

`LazySets.constraints_list`

— Method`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.

`LazySets.constrained_dimensions`

— Method`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.

`LazySets.translate`

— Method`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$.

`LazySets.halfspace_left`

— Method`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
```

`LazySets.halfspace_right`

— Method`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`

.

`LazySets.tosimplehrep`

— Method```
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.

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

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

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

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

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

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

`LazySets.complement`

— Method`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).

`LazySets.project`

— Method`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)
```

`ReachabilityBase.Arrays.distance`

— Method`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`

.

Inherited from `ConvexSet`

: