Hyperplane separation theorem

{{math_theorem|name=Hyperplane separation theorem{{harvnb|Boyd|Vandenberghe|2004|loc=Exercise 2.22.}}|Let $A$ and $B$ be two disjoint nonempty convex subsets of $\backslash R^n$. Then there exist a nonzero vector $v$ and a real number $c$ such that

:$\backslash langle\; x,\; v\; \backslash rangle\; \backslash ge\; c\; \backslash ,\; \backslash text\{\; and\; \}\; \backslash langle\; y,\; v\; \backslash rangle\; \backslash le\; c$

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

If both sets are closed, and at least one of them is compact, then the separation can be strict, that is, for some $c\_1\; >\; c\_2$

}}

In all cases, assume $A,\; B$ to be disjoint, nonempty, and convex subsets of $\backslash R^n$. The summary of the results are as follows:

The number of dimensions must be finite. In infinite-dimensional spaces there are examples of two closed, convex, disjoint sets which cannot be separated by a closed hyperplane (a hyperplane where a continuous linear functional equals some constant) even in the weak sense where the inequalities are not strict.Haïm Brezis, Functional Analysis, Sobolev Spaces and Partial Differential Equations, 2011, Remark 4, p. 7.

Here, the compactness in the hypothesis cannot be relaxed; see an example in the section Counterexamples and uniqueness. This version of the separation theorem does generalize to infinite-dimension; the generalization is more commonly known as the Hahn–Banach separation theorem.

The proof is based on the following lemma:

{{math_theorem|name=Lemma|Let $A$ and $B$ be two disjoint closed subsets of $\backslash R^n$, and assume $A$ is compact. Then there exist points $a\_0\; \backslash in\; A$ and $b\_0\; \backslash in\; B$ minimizing the distance $\backslash |a\; -\; b\backslash |$ over $a\; \backslash in\; A$ and $b\; \backslash in\; B$.}}

{{Math proof|title=Proof of lemma|proof=

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

}}

File:Separating Hyperplanes Theorem.png

{{Math proof|title=Proof of theorem|proof= We first prove the second case. (See the diagram.)

WLOG, $A$ is compact. By the lemma, there exist points $a\_0\; \backslash in\; A$ and $b\_0\; \backslash in\; B$ of minimum distance to each other.

Since $A$ and $B$ are disjoint, we have $a\_0\; \backslash neq\; b\_0$. Now, construct two hyperplanes $L\_A,\; L\_B$ perpendicular to line segment $[a\_0,\; b\_0]$, with $L\_A$ across $a\_0$ and $L\_B$ across $b\_0$. We claim that neither $A$ nor $B$ enters the space between $L\_A,\; L\_B$, and thus the perpendicular hyperplanes to $(a\_0,\; b\_0)$ satisfy the requirement of the theorem.

Algebraically, the hyperplanes $L\_A,\; L\_B$ are defined by the vector $v:=\; b\_0\; -\; a\_0$, and two constants , such that $L\_A\; =\; \backslash \{x:\; \backslash langle\; v,\; x\backslash rangle\; =\; c\_A\backslash \},\; L\_B\; =\; \backslash \{x:\; \backslash langle\; v,\; x\backslash rangle\; =\; c\_B\backslash \}$. Our claim is that $\backslash forall\; a\backslash in\; A,\; \backslash langle\; v,\; a\backslash rangle\; \backslash leq\; c\_A$ and $\backslash forall\; b\backslash in\; B,\; \backslash langle\; v,\; b\backslash rangle\; \backslash geq\; c\_B$.

Suppose there is some $a\backslash in\; A$ such that $\backslash langle\; v,\; a\backslash rangle\; >\; c\_A$, then let $a\text{'}$ be the foot of perpendicular from $b\_0$ to the line segment $[a\_0,\; a]$. Since $A$ is convex, $a\text{'}$ is inside $A$, and by planar geometry, $a\text{'}$ is closer to $b\_0$ than $a\_0$, contradiction. Similar argument applies to $B$.

Now for the first case.

Approach both $A,\; B$ from the inside by $A\_1\; \backslash subseteq\; A\_2\; \backslash subseteq\; \backslash cdots\; \backslash subseteq\; A$ and $B\_1\; \backslash subseteq\; B\_2\; \backslash subseteq\; \backslash cdots\; \backslash subseteq\; B$, such that each $A\_k,\; B\_k$ is closed and compact, and the unions are the relative interiors $\backslash mathrm\{relint\}(A),\; \backslash mathrm\{relint\}(B)$. (See relative interior page for details.)

Now by the second case, for each pair $A\_k,\; B\_k$ there exists some unit vector $v\_k$ and real number $c\_k$, such that .

Since the unit sphere is compact, we can take a convergent subsequence, so that $v\_k\; \backslash to\; v$. Let $c\_A\; :=\; \backslash sup\_\{a\backslash in\; A\}\; \backslash langle\; v,\; a\backslash rangle,\; c\_B\; :=\; \backslash inf\_\{b\backslash in\; B\}\; \backslash langle\; v,\; b\backslash rangle$. We claim that $c\_A\; \backslash leq\; c\_B$, thus separating $A,\; B$.

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

}}

Since a separating hyperplane cannot intersect the interiors of open convex sets, we have a corollary:

{{math_theorem

| name = Separation theorem I|Let $A$ and $B$ be two disjoint nonempty convex sets. If $A$ is open, then there exist a nonzero vector $v$ and real number $c$ such that

:$\backslash langle\; x,\; v\; \backslash rangle\; >\; c\; \backslash ,\; \backslash text\{\; and\; \}\; \backslash langle\; y,\; v\; \backslash rangle\; \backslash le\; c$

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

:

for all $x$ in $A$ and $y$ in $B$.

}}

If the sets $A,\; B$ have possible intersections, but their relative interiors are disjoint, then the proof of the first case still applies with no change, thus yielding:

{{math_theorem

| name = Separation theorem II|Let $A$ and $B$ be two nonempty convex subsets of $\backslash R^n$ with disjoint relative interiors. Then there exist a nonzero vector $v$ and a real number $c$ such that

:$\backslash langle\; x,\; v\; \backslash rangle\; \backslash ge\; c\; \backslash ,\; \backslash text\{\; and\; \}\; \backslash langle\; y,\; v\; \backslash rangle\; \backslash le\; c$

}}

in particular, we have the supporting hyperplane theorem.

{{Math theorem

| math_statement = if $A$ is a convex set in $\backslash mathbb\{R\}^n,$ and $a\_0$ is a point on the boundary of $A$, then there exists a supporting hyperplane of $A$ containing $a\_0$.

| name = Supporting hyperplane theorem

}}

{{Math proof|title=Proof|proof=

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

}}

Note that the existence of a hyperplane that only "separates" two convex sets in the weak sense of both inequalities being non-strict obviously does not imply that the two sets are disjoint. Both sets could have points located on the hyperplane.

File:Separating axis theorem2.svg

If one of A or B is not convex, then there are many possible counterexamples. For example, A and B could be concentric circles. A more subtle counterexample is one in which A and B are both closed but neither one is compact. For example, if A is a closed half plane and B is bounded by one arm of a hyperbola, then there is no strictly separating hyperplane:

:$A\; =\; \backslash \{(x,y)\; :\; x\; \backslash le\; 0\backslash \}$

:$B\; =\; \backslash \{(x,y)\; :\; x\; >\; 0,\; y\; \backslash geq\; 1/x\; \backslash \}.\backslash$

(Although, by an instance of the second theorem, there is a hyperplane that separates their interiors.) Another type of counterexample has A compact and B open. For example, A can be a closed square and B can be an open square that touches A.

In the first version of the theorem, evidently the separating hyperplane is never unique. In the second version, it may or may not be unique. Technically a separating axis is never unique because it can be translated; in the second version of the theorem, a separating axis can be unique up to translation.

The horn angle provides a good counterexample to many hyperplane separations. For example, in $\backslash R^2$, the unit disk is disjoint from the open interval $((1,\; 0),\; (1,1))$, but the only line separating them contains the entirety of $((1,\; 0),\; (1,1))$. This shows that if $A$ is closed and $B$ is relatively open, then there does not necessarily exist a separation that is strict for $B$. However, if $A$ is closed polytope then such a separation exists.

Farkas' lemma and related results can be understood as hyperplane separation theorems when the convex bodies are defined by finitely many linear inequalities.

More results may be found.{{Cite book |last=Stoer |first=Josef |url=https://link.springer.com/book/10.1007/978-3-642-46216-0 |title=Convexity and Optimization in Finite Dimensions I |last2=Witzgall |first2=Christoph |publisher=Springer Berlin, Heidelberg |year=1970 |isbn=978-3-642-46216-0 |at=(2.12.9) |language=en |doi=10.1007/978-3-642-46216-0}}

In collision detection, the hyperplane separation theorem is usually used in the following form:

{{math_theorem

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

}}

Regardless of dimensionality, the separating axis is always a line.

For example, in 3D, the space is separated by planes, but the separating axis is perpendicular to the separating plane.

The separating axis theorem can be applied for fast collision detection between polygon meshes. Each face's normal or other feature direction is used as a separating axis. Note that this yields possible separating axes, not separating lines/planes.

In 3D, using face normals alone will fail to separate some edge-on-edge non-colliding cases. Additional axes, consisting of the cross-products of pairs of edges, one taken from each object, are required.{{Cite web|url=https://docs.godotengine.org/en/stable/tutorials/math/vectors_advanced.html#collision-detection-in-3d|title = Advanced vector math}}

For increased efficiency, parallel axes may be calculated as a single axis.

• Dual cone
• Farkas's lemma
• Kirchberger's theorem
• Optimal control

{{reflist}}

• {{cite book|title=Convex Optimization | first1=Stephen P. |last1=Boyd |first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3 | url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf }}
• {{cite book

| last = Golshtein

| first = E. G.

|author2=Tretyakov, N.V.

| title = Modified Lagrangians and monotone maps in optimization

| publisher = New York: Wiley

| date = 1996

| isbn = 0-471-54821-9

| page = 6

}}

• {{cite book

| last = Shimizu

| first = Kiyotaka |author2=Ishizuka, Yo |author3=Bard, Jonathan F.

| title = Nondifferentiable and two-level mathematical programming

| publisher = Boston: Kluwer Academic Publishers

| date = 1997

| isbn = 0-7923-9821-1

| page = 19

}}

• {{cite book

| last = Soltan

| first = V.

| title = Support and separation properties of convex sets in finite dimension

| publisher = Extracta Math. Vol. 36, no. 2, 241-278

| year = 2021

}}

• [http://www.metanetsoftware.com/technique/tutorialA.html Collision detection and response]

{{Functional analysis}}

{{Topological vector spaces}}

{{DEFAULTSORT:Separating Axis Theorem}}

Category:Theorems in convex geometry

Category:Hermann Minkowski

Category:Linear functionals

fr:Séparation des convexes