Hyperplane separation theorem

Hyperplane separation theorem   (Redirected from Separating axis theorem) Jump to navigation Jump to search 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] Contents 1 Statements and proof 2 Converse of theorem 3 Counterexamples and uniqueness 4 Use in collision detection 5 See also 6 Notes 7 References 8 External links Statements and proof Hyperplane separation theorem[4] — Let A and B be two disjoint nonempty convex subsets of Rn. Then there exist a nonzero vector v and a real number c such that {displaystyle langle x,vrangle geq c,{text{ and }}langle y,vrangle leq c} for all x in A and y in B; i.e., the hyperplane {displaystyle langle cdot ,vrangle =c} , v the normal vector, separates A and B.

The proof is based on the following lemma: Lemma — Let {displaystyle K} be a nonempty closed convex subset of Rn. Then there exists a unique vector in {displaystyle K} of minimum norm (length).

Proof of lemma: Let {displaystyle delta =inf{|x|:xin K}.} Let {displaystyle x_{j}} be a sequence in {displaystyle K} such that {displaystyle |x_{j}|to delta } . Note that {displaystyle (x_{i}+x_{j})/2} is in {displaystyle K} since {displaystyle K} is convex and so {displaystyle |x_{i}+x_{j}|^{2}geq 4delta ^{2}} . Since {displaystyle |x_{i}-x_{j}|^{2}=2|x_{i}|^{2}+2|x_{j}|^{2}-|x_{i}+x_{j}|^{2}leq 2|x_{i}|^{2}+2|x_{j}|^{2}-4delta ^{2}to 0} as {displaystyle i,jto infty } , {displaystyle x_{i}} is a Cauchy sequence and so has limit x in {displaystyle K} . It is unique since if y is in {displaystyle K} and has norm δ, then {displaystyle |x-y|^{2}leq 2|x|^{2}+2|y|^{2}-4delta ^{2}=0} and x = y. {displaystyle square } Proof of theorem: Given disjoint nonempty convex sets A, B, let {displaystyle K=A+(-B)={x-ymid xin A,yin B}.} Since {displaystyle -B} is convex and the sum of convex sets is convex, {displaystyle K} is convex. By the lemma, the closure {displaystyle {overline {K}}} of {displaystyle K} , which is convex, contains a vector {displaystyle v} of minimum norm. Since {displaystyle {overline {K}}} is convex, for any {displaystyle n} in {displaystyle K} , the line segment {displaystyle v+t(n-v),,0leq tleq 1} lies in {displaystyle {overline {K}}} and so {displaystyle |v|^{2}leq |v+t(n-v)|^{2}=|v|^{2}+2tlangle v,n-vrangle +t^{2}|n-v|^{2}} .

For {displaystyle 0c_{2},{text{ and }}langle y,vrangle c,{text{ and }}langle y,vrangle 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 {displaystyle c} such that {displaystyle langle x,vrangle >c,{text{ and }}langle y,vrangle 0,ygeq 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.

See also Dual cone Farkas's lemma Kirchberger's theorem Optimal control 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. 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. External links Collision detection and response show vte Functional analysis (topics – glossary) show vte Topological vector spaces (TVSs) Categories: Theorems in convex geometryHermann Minkowski