Hyperplane separation theorem

Hyperplane separation theorem
	Illustration of the hyperplane separation theorem.
Type	Theorem
Field	Convex geometry; Topological vector spaces; Collision detection;
Conjectured by	Hermann Minkowski
Open problem	No
Generalizations	Hahn–Banach separation theorem

In geometry, the hyperplane separation theorem is a theorem about disjoint convex sets in n-dimensional Euclidean space. There are several rather similar versions. In one version of the theorem, if both these sets are closed and at least one of them is compact, then there is a hyperplane in between them and even two parallel hyperplanes in between them separated by a gap. In another version, if both disjoint convex sets are open, then there is a hyperplane in between them, but not necessarily any gap. An axis which is orthogonal to a separating hyperplane is a separating axis, because the orthogonal projections of the convex bodies onto the axis are disjoint.

The hyperplane separation theorem is due to Hermann Minkowski. The Hahn–Banach separation theorem generalizes the result to topological vector spaces.

A related result is the supporting hyperplane theorem.

In the context of support-vector machines, the optimally separating hyperplane or maximum-margin hyperplane is a hyperplane which separates two convex hulls of points and is equidistant from the two.^[1]^[2]^[3]

Statements and proof

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

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

for all $x$ in $A$ and $y$ in $B$ ; i.e., the hyperplane $\langle \cdot ,v\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, $\langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle <c$ .

The proof is based on the following lemma:

Lemma—Let $K$ be a nonempty closed convex subset of $\mathbb {R} ^{n}$ . Then there exists a unique vector in $K$ of minimum norm (length).

Proof of lemma

Let $x_{0}\in K$ , then let $r=\|x_{0}\|$ . Define closed ball $B$ centered on origin with radius $r$ , then $B\cap K$ is compact and contains a minimizer of the function $x\mapsto \|x\|$ . This is the minimum norm vector. It is unique, since if there are two minimizers, then their mid-point has an even smaller norm. $\square$

Proof of theorem

We first prove the second case.

WLOG, $A$ is compact.

For each point $x\in \mathbb {R} ^{n}$ , define the projection function $p(x):=\arg \min _{y\in B}\|y-x\|$ . Since $B$ is closed and convex, $p$ is well-defined by the lemma. Since the norm satisfies triangle inequality, $p$ is continuous.

Since $A$ is compact, by the lemma, there exists some $a_{0}$ that minimizes $\|p(a)-a\|$ . Let $b_{0}:=p(a_{0})$ . Since $a_{0}\not \in B$ , we have $b_{0}\neq a_{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 bisecting perpendicular hyperplane to $[a_{0},b_{0}]$ satisfies 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 $c_{A}:=\langle v,a_{0}\rangle <c_{B}:=\langle v,b_{0}\rangle$ , such that $L_{A}=\{x:\langle v,x\rangle =c_{A}\},L_{B}=\{x:\langle v,x\rangle =c_{B}\}$ . Our claim is that $\forall a\in A,\langle a,v\rangle \leq c_{A}$ and $\forall b\in B,\langle b,v\rangle \leq c_{B}$ .

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

Now for the first case.

Approximate both $A,B$ from the inside by $A_{1}\subseteq A_{2}\subseteq \cdots \subseteq A$ and $B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B$ , such that each $A_{k},B_{k}$ is closed and compact. 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 $\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 $v_{k}\to v$ . Let $c_{A}:=\sup _{a\in A}\langle v,a\rangle ,c_{B}:=\inf _{b\in B}\langle v,b\rangle$ . We claim that $c_{A}\leq c_{B}$ , thus separating $A,B$ .

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

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.^[5]

The above proof also proves the first version of the theorem mentioned in the lead (to see it, note that $K$ in the proof is closed under the hypothesis of the theorem below.)

Separation theorem I— Let $A$ and $B$ be two disjoint nonempty closed convex sets, one of which is compact. Then there exist a nonzero vector $v$ and real numbers $c_{1}<c_{2}$ such that

\langle x,v\rangle >c_{2}\,{\text{ and }}\langle y,v\rangle <c_{1}

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

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

We also have:

Separation theorem II— 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

\langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle \leq 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

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

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

This follows from the standard version since the separating hyperplane cannot intersect the interiors of the convex sets.

Converse of 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.

Counterexamples and uniqueness

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=\{(x,y):x\leq 0\}

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

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

Use in collision detection

The separating axis theorem (SAT) says that:

Two convex objects do not overlap if there exists a line (called axis) onto which the two objects' projections do not overlap.

SAT suggests an algorithm for testing whether two convex solids intersect or not.

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.^[6]

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

Notes

^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2008). The Elements of Statistical Learning : Data Mining, Inference, and Prediction (PDF) (Second ed.). New York: Springer. pp. 129–135.
^ Witten, Ian H.; Frank, Eibe; Hall, Mark A.; Pal, Christopher J. (2016). Data Mining: Practical Machine Learning Tools and Techniques (Fourth ed.). Morgan Kaufmann. pp. 253–254. ISBN 9780128043578.
^ Deisenroth, Marc Peter; Faisal, A. Aldo; Ong, Cheng Soon (2020). Mathematics for Machine Learning. Cambridge University Press. pp. 337–338. ISBN 978-1-108-45514-5.
^ Boyd & Vandenberghe 2004, Exercise 2.22.
^ Haïm Brezis, Analyse fonctionnelle : théorie et applications, 1983, remarque 4, p. 7.
^ "Advanced vector math".

References

Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3.
Golshtein, E. G.; Tretyakov, N.V. (1996). Modified Lagrangians and monotone maps in optimization. New York: Wiley. p. 6. ISBN 0-471-54821-9.{{cite book}}: CS1 maint: publisher location (link)
Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Nondifferentiable and two-level mathematical programming. Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1.{{cite book}}: CS1 maint: publisher location (link)

External links

Collision detection and response

[1] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2008). The Elements of Statistical Learning : Data Mining, Inference, and Prediction (PDF) (Second ed.). New York: Springer. pp. 129–135.

[2] Witten, Ian H.; Frank, Eibe; Hall, Mark A.; Pal, Christopher J. (2016). Data Mining: Practical Machine Learning Tools and Techniques (Fourth ed.). Morgan Kaufmann. pp. 253–254. ISBN 9780128043578.

[3] Deisenroth, Marc Peter; Faisal, A. Aldo; Ong, Cheng Soon (2020). Mathematics for Machine Learning. Cambridge University Press. pp. 337–338. ISBN 978-1-108-45514-5.

[4] Boyd & Vandenberghe 2004, Exercise 2.22.

[5] Haïm Brezis, Analyse fonctionnelle : théorie et applications, 1983, remarque 4, p. 7.

[6] "Advanced vector math".

[1]

[2]

[3]

[4]

[5]

[6]

v t e Topological vector spaces (TVSs)
Basic concepts	Banach space Completeness Continuous linear operator Linear functional Fréchet space Linear map Locally convex space Metrizability Operator topologies Topological vector space Vector space
Main results	Anderson–Kadec Banach–Alaoglu Closed graph theorem F. Riesz's Hahn–Banach (hyperplane separation Vector-valued Hahn–Banach) Open mapping (Banach–Schauder) Bounded inverse Uniform boundedness (Banach–Steinhaus)
Maps	Bilinear operator form Linear map Almost open Bounded Continuous Closed Compact Densely defined Discontinuous Topological homomorphism Functional Linear Bilinear Sesquilinear Norm Seminorm Sublinear function Transpose
Types of sets	Absolutely convex/disk Absorbing/Radial Affine Balanced/Circled Banach disks Bounding points Bounded Complemented subspace Convex Convex cone (subset) Linear cone (subset) Extreme point Pre-compact/Totally bounded Prevalent/Shy Radial Radially convex/Star-shaped Symmetric
Set operations	Affine hull (Relative) Algebraic interior (core) Convex hull Linear span Minkowski addition Polar (Quasi) Relative interior
Types of TVSs	Asplund B-complete/Ptak Banach (Countably) Barrelled BK-space (Ultra-) Bornological Brauner Complete Convenient (DF)-space Distinguished F-space FK-AK space FK-space Fréchet tame Fréchet Grothendieck Hilbert Infrabarreled Interpolation space K-space LB-space LF-space Locally convex space Mackey (Pseudo)Metrizable Montel Quasibarrelled Quasi-complete Quasinormed (Polynomially Semi-) Reflexive Riesz Schwartz Semi-complete Smith Stereotype (B Strictly Uniformly) convex (Quasi-) Ultrabarrelled Uniformly smooth Webbed With the approximation property
Category