Polyhedra and Half-Spaces

A half-space in $\mathbb{R}^n$ is the set of all points satisfying a single linear inequality:

$$H = \{\mathbf{x} \in \mathbb{R}^n : \mathbf{a}^T \mathbf{x} \leq b\},$$

where $\mathbf{a} \in \mathbb{R}^n$ is a nonzero vector and $b \in \mathbb{R}$ is a scalar.

The boundary of $H$ is the hyperplane

$$\{\mathbf{x} \in \mathbb{R}^n : \mathbf{a}^T \mathbf{x} = b\},$$

which slices $\mathbb{R}^n$ into two opposite half-spaces. The inequality $\mathbf{a}^T \mathbf{x} \geq b$ defines the half-space on the other side of the same hyperplane.

For example, consider the half-space in $\mathbb{R}^2$ defined by $2x_1 + 3x_2 \leq 6$. The origin $\mathbf{x} = (0,0)$ lies inside this half-space because

$$2(0) + 3(0) = 0 \leq 6.$$

The point $(4, 1)$ does not, because $2(4) + 3(1) = 11 \not\leq 6$.

To test whether any point $\mathbf{x}$ lies in a half-space, simply substitute its components into $\mathbf{a}^T \mathbf{x}$ and check the inequality.