Hyperplanes and Polytopes

An affine set carries an explicit, parametric description: a point plus a span. Hyperplanes are better handled implicitly, as the solution set of a single equation. That equation is the vanishing of a linear functional, and the implicit form is what makes hyperplanes separate sets and bound polytopes.¹

Hyperplanes as level sets

A linear functional on ${\mathbb{R}}^n$ is a linear transformation $f:{\mathbb{R}}^n\to \mathbb{R}$. For a scalar $d$, write $[f:d]$ for the set where $f$ takes the value $d$:

The standard matrix of $f$ is a $1\times n$ matrix $A=[a_1{a}_2\cdots a_n]$, so $f(\mathbf{x})=A\mathbf{x}=\mathbf{n}\cdot \mathbf{x}$ for the vector $\mathbf{n}$ with the same entries. Two implicit descriptions of a line in ${\mathbb{R}}^2$ and a plane in ${\mathbb{R}}^3$ fit this pattern:

• In ${\mathbb{R}}^2$, the line $x-4y=13$ is $[f:13]$ for $f(x,y)=x-4y$.
• In ${\mathbb{R}}^3$, the plane $5x-2y+3z=21$ is $[g:21]$ for $g(x,y,z)=5x-2y+3z$.

For a nonzero functional, $\mathrm{rank}A=1$, so $\dim \mathrm{Nul}A=n-1$ by the rank theorem. The set $[f:0]=\mathrm{Nul}A$ is therefore a hyperplane through the origin, and every level set $[f:d]$ is a parallel translate of it: if $\mathbf{p}$ is any point with $f(\mathbf{p})=d$, then

Writing $f(\mathbf{x})=\mathbf{n}\cdot \mathbf{x}$ shows $[f:0]$ is the orthogonal complement of $\mathrm{Span}\{\mathbf{n}\}$. The vector $\mathbf{n}$ is normal to the hyperplane and to all of its parallel translates, even though $\mathbf{n}\cdot \mathbf{x}=d\ne 0$ on those translates. When $f(\mathbf{x})=\mathbf{n}\cdot \mathbf{x}$, the vector $\mathbf{n}$ is the gradient of $f$.

Converting an explicit line into implicit form means finding the normal, then the constant.

Every hyperplane admits this description, which is the content of the next theorem.

Given a hyperplane $H$, pick $\mathbf{p}\in H$ and set $H_0=H-\mathbf{p}$, an $(n-1)$-dimensional subspace. Any vector $\mathbf{n}$ orthogonal to $H_0$ defines $f(\mathbf{x})=\mathbf{n}\cdot \mathbf{x}$; then $[f:0]$ is a hyperplane containing $H_0$, hence equal to it by dimension, and $d=f(\mathbf{p})$ gives $H=[f:0]+\mathbf{p}=[f:d]$.

Translating a hyperplane shifts its constant.

Separation

A hyperplane splits ${\mathbb{R}}^n$ into two closed half-spaces. Writing $f(A)\le d$ to mean $f(\mathbf{x})\le d$ for every $\mathbf{x}\in A$, the hyperplane $H=[f:d]$ separates sets $A$ and $B$ if $f(A)\le d$ and $f(B)\ge d$, or the reverse. Replacing the weak inequalities by strict ones gives strict separation. Strict separation forces the sets to be disjoint; ordinary separation does not, since two externally tangent circles share their common tangent line.

Two theorems give conditions for strict separation. Both turn a geometric question about sets into an algebraic one about their convex hulls.

The convex-hull separation theorem follows from the compact–closed separation theorem applied to the compact convex hulls. If $H=[f:d]$ strictly separates $A$ and $B$ with $f(A)<d<f(B)$, then for any convex combination $\mathbf{x}=\sum c_i{\mathbf{x}}_i$ of points of $A$,

so $f(\mathrm{conv}A)<d$, and likewise $f(\mathrm{conv}B)>d$. The functional that separates the sets separates their hulls.

Disjointness alone is not enough for closed convex sets that are both unbounded. The region above a hyperbola and its horizontal asymptote are disjoint closed convex sets that no line strictly separates, since they approach each other without limit. Compactness of one set, as in the compact–closed separation theorem, rules this out.

Polytopes

A polytope in ${\mathbb{R}}^n$ is the convex hull of a finite set of points. In ${\mathbb{R}}^2$ a polytope is a polygon, in ${\mathbb{R}}^3$ a polyhedron. Its structure is described through supporting hyperplanes.

Let $S$ be a compact convex set. A nonempty subset $F⊊S$ is a face of $S$ if there is a hyperplane $H=[f:d]$ with $F=S\cap H$ and $f(S)\le d$ (or $f(S)\ge d$); the hyperplane $H$ is a supporting hyperplane, touching $S$ without cutting into it. A face of dimension $k$ is a $k$-face. For a polytope:

• Vertex: a $0$-face.
• Edge: a $1$-face.
• Facet: an $(n-1)$-face, one dimension below the polytope.

A cube shows the three low-dimensional cases at once. Slide a plane toward the cube until it just touches: depending on orientation, the contact $H\cap S$ is a square facet, an edge, or a single vertex.

Vertices carry the essential information because they are the extreme points. A point $\mathbf{p}$ in a convex set $S$ is an extreme point if it is not in the interior of any segment lying in $S$: whenever $\mathbf{p}\in \overline{\mathbf{xy}}$ with $\mathbf{x},\mathbf{y}\in S$, either $\mathbf{p}=\mathbf{x}$ or $\mathbf{p}=\mathbf{y}$. The set of extreme points is the profile of $S$. The profile of a polygon is its vertices; the profile of a closed disk is its boundary circle; an open set and a half-space have empty profile.

The extreme points are thus the smallest set whose hull recovers $S$. For a polytope that set is finite, and a linear functional is pinned to it.

If ${\mathbf{v}}_0$ maximizes $f$, write it as a convex combination of extreme points ${\mathbf{v}}_0=\sum c_i{\mathbf{v}}_i$. Were $f({\mathbf{v}}_i)<m$ for every extreme point, linearity would give $f({\mathbf{v}}_0)=\sum c_{i}f({\mathbf{v}}_i)<m$, contradicting $f({\mathbf{v}}_0)=m$. So some extreme point attains $m$.

A polytope has two dual descriptions: explicitly as the convex hull of its vertices, and implicitly as the intersection of finitely many closed half-spaces $A\mathbf{x}\le \mathbf{b}$. Passing between them is a standard computation.

Every vertex is a candidate location for the optimum of a linear objective, which is the geometric core of linear programming: a linear functional on a polytope attains its extremes at vertices, so an optimizer walks from vertex to vertex along edges. The curved boundaries excluded by finite set of points call for a different construction, the Bézier curves built from control points.