Hyperplane separation theorem

• Convex geometry
• Topological vector spaces
• Collision detection

Hyperplane separation theorem^[4] — Let ${\displaystyle A}$ and ${\displaystyle B}$ be two disjoint nonempty convex subsets of ${\displaystyle \mathbb {R} ^{n}}$. Then there exist a nonzero vector ${\displaystyle v}$ and a real number ${\displaystyle c}$ such that

${\displaystyle \langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c}$

for all ${\displaystyle x}$ in ${\displaystyle A}$ and ${\displaystyle y}$ in ${\displaystyle B}$; i.e., the hyperplane ${\displaystyle \langle \cdot ,v\rangle =c}$, ${\displaystyle v}$ the normal vector, separates ${\displaystyle A}$ and ${\displaystyle B}$.

If both sets are closed, and at least one of them is compact, then the separation can be strict, that is, ${\displaystyle \langle x,v\rangle >c_{1}\,{\text{ and }}\langle y,v\rangle <c_{2}}$ for some ${\displaystyle c_{1}>c_{2}}$

Lemma — Let ${\displaystyle A}$ and ${\displaystyle B}$ be two disjoint closed subsets of ${\displaystyle \mathbb {R} ^{n}}$, and assume ${\displaystyle A}$ is compact. Then there exist points ${\displaystyle a_{0}\in A}$ and ${\displaystyle b_{0}\in B}$ minimizing the distance ${\displaystyle \|a-b\|}$ over ${\displaystyle a\in A}$ and ${\displaystyle b\in B}$.

Let ${\displaystyle a\in A}$ and ${\displaystyle b\in B}$ be any pair of points, and let ${\displaystyle r_{1}=\|b-a\|}$. Since ${\displaystyle A}$ is compact, it is contained in some ball centered on ${\displaystyle a}$; let the radius of this ball be ${\displaystyle r_{2}}$. Let ${\displaystyle S=B\cap {\overline {B_{r_{1}+r_{2}}(a)}}}$ be the intersection of ${\displaystyle B}$ with a closed ball of radius ${\displaystyle r_{1}+r_{2}}$ around ${\displaystyle a}$. Then ${\displaystyle S}$ is compact and nonempty because it contains ${\displaystyle b}$. Since the distance function is continuous, there exist points ${\displaystyle a_{0}}$ and ${\displaystyle b_{0}}$ whose distance ${\displaystyle \|a_{0}-b_{0}\|}$ is the minimum over all pairs of points in ${\displaystyle A\times S}$. It remains to show that ${\displaystyle a_{0}}$ and ${\displaystyle b_{0}}$ in fact have the minimum distance over all pairs of points in ${\displaystyle A\times B}$. Suppose for contradiction that there exist points ${\displaystyle a'}$ and ${\displaystyle b'}$ such that ${\displaystyle \|a'-b'\|<\|a_{0}-b_{0}\|}$. Then in particular, ${\displaystyle \|a'-b'\|<r_{1}}$, and by the triangle inequality, ${\displaystyle \|a-b'\|\leq \|a'-b'\|+\|a-a'\|<r_{1}+r_{2}}$. Therefore ${\displaystyle b'}$ is contained in ${\displaystyle S}$, which contradicts the fact that ${\displaystyle a_{0}}$ and ${\displaystyle b_{0}}$ had minimum distance over ${\displaystyle A\times S}$. ${\displaystyle \square }$

We first prove the second case. (See the diagram.)

WLOG, ${\displaystyle A}$ is compact. By the lemma, there exist points ${\displaystyle a_{0}\in A}$ and ${\displaystyle b_{0}\in B}$ of minimum distance to each other. Since ${\displaystyle A}$ and ${\displaystyle B}$ are disjoint, we have ${\displaystyle a_{0}\neq b_{0}}$. Now, construct two hyperplanes ${\displaystyle L_{A},L_{B}}$ perpendicular to line segment ${\displaystyle [a_{0},b_{0}]}$, with ${\displaystyle L_{A}}$ across ${\displaystyle a_{0}}$ and ${\displaystyle L_{B}}$ across ${\displaystyle b_{0}}$. We claim that neither ${\displaystyle A}$ nor ${\displaystyle B}$ enters the space between ${\displaystyle L_{A},L_{B}}$, and thus the perpendicular hyperplanes to ${\displaystyle (a_{0},b_{0})}$ satisfy the requirement of the theorem.

Algebraically, the hyperplanes ${\displaystyle L_{A},L_{B}}$ are defined by the vector ${\displaystyle v:=b_{0}-a_{0}}$, and two constants ${\displaystyle c_{A}:=\langle v,a_{0}\rangle <c_{B}:=\langle v,b_{0}\rangle }$, such that ${\displaystyle L_{A}=\{x:\langle v,x\rangle =c_{A}\},L_{B}=\{x:\langle v,x\rangle =c_{B}\}}$. Our claim is that ${\displaystyle \forall a\in A,\langle v,a\rangle \leq c_{A}}$ and ${\displaystyle \forall b\in B,\langle v,b\rangle \geq c_{B}}$.

Suppose there is some ${\displaystyle a\in A}$ such that ${\displaystyle \langle v,a\rangle >c_{A}}$, then let ${\displaystyle a'}$ be the foot of perpendicular from ${\displaystyle b_{0}}$ to the line segment ${\displaystyle [a_{0},a]}$. Since ${\displaystyle A}$ is convex, ${\displaystyle a'}$ is inside ${\displaystyle A}$, and by planar geometry, ${\displaystyle a'}$ is closer to ${\displaystyle b_{0}}$ than ${\displaystyle a_{0}}$, contradiction. Similar argument applies to ${\displaystyle B}$.

Now for the first case.

Approach both ${\displaystyle A,B}$ from the inside by ${\displaystyle A_{1}\subseteq A_{2}\subseteq \cdots \subseteq A}$ and ${\displaystyle B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B}$, such that each ${\displaystyle A_{k},B_{k}}$ is closed and compact, and the unions are the relative interiors ${\displaystyle \mathrm {relint} (A),\mathrm {relint} (B)}$. (See relative interior page for details.)

Now by the second case, for each pair ${\displaystyle A_{k},B_{k}}$ there exists some unit vector ${\displaystyle v_{k}}$ and real number ${\displaystyle c_{k}}$, such that ${\displaystyle \langle v_{k},A_{k}\rangle <c_{k}<\langle v_{k},B_{k}\rangle }$.

Since the unit sphere is compact, we can take a convergent subsequence, so that ${\displaystyle v_{k}\to v}$. Let ${\displaystyle c_{A}:=\sup _{a\in A}\langle v,a\rangle ,c_{B}:=\inf _{b\in B}\langle v,b\rangle }$. We claim that ${\displaystyle c_{A}\leq c_{B}}$, thus separating ${\displaystyle A,B}$.

Assume not, then there exists some ${\displaystyle a\in A,b\in B}$ such that ${\displaystyle \langle v,a\rangle >\langle v,b\rangle }$, then since ${\displaystyle v_{k}\to v}$, for large enough ${\displaystyle k}$, we have ${\displaystyle \langle v_{k},a\rangle >\langle v_{k},b\rangle }$, contradiction.

Separation theorem I — Let ${\displaystyle A}$ and ${\displaystyle B}$ be two disjoint nonempty convex sets. If ${\displaystyle A}$ is open, then there exist a nonzero vector ${\displaystyle v}$ and real number ${\displaystyle c}$ such that

${\displaystyle \langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle \leq c}$

for all ${\displaystyle x}$ in ${\displaystyle A}$ and ${\displaystyle y}$ in ${\displaystyle B}$. If both sets are open, then there exist a nonzero vector ${\displaystyle v}$ and real number ${\displaystyle c}$ such that

${\displaystyle \langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle <c}$

for all ${\displaystyle x}$ in ${\displaystyle A}$ and ${\displaystyle y}$ in ${\displaystyle B}$.

Separation theorem II — Let ${\displaystyle A}$ and ${\displaystyle B}$ be two nonempty convex subsets of ${\displaystyle \mathbb {R} ^{n}}$ with disjoint relative interiors. Then there exist a nonzero vector ${\displaystyle v}$ and a real number ${\displaystyle c}$ such that

${\displaystyle \langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c}$

Supporting hyperplane theorem — if ${\displaystyle A}$ is a convex set in ${\displaystyle \mathbb {R} ^{n},}$ and ${\displaystyle a_{0}}$ is a point on the boundary of ${\displaystyle A}$, then there exists a supporting hyperplane of ${\displaystyle A}$ containing ${\displaystyle a_{0}}$.

If the affine span of ${\displaystyle A}$ is not all of ${\displaystyle \mathbb {R} ^{n}}$, then extend the affine span to a supporting hyperplane. Else, ${\displaystyle \mathrm {relint} (A)=\mathrm {int} (A)}$ is disjoint from ${\displaystyle \mathrm {relint} (\{a_{0}\})=\{a_{0}\}}$, so apply the above theorem.

Separating axis theorem — Two closed convex objects are disjoint if there exists a line ("separating axis") onto which the two objects' projections are disjoint.