Hyperplane separation theorem
In geometry, the hyperplane separation theorem is either of two theorems about disjoint convex sets in n-dimensional Euclidean space. In the first 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 the second 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.
A related result is the supporting hyperplane theorem. In geometry, a maximum-margin hyperplane is a hyperplane which separates two 'clouds' of points and is at equal distance from the two. The margin between the hyperplane and the clouds is maximal. See the article on Support Vector Machines for more details.
Statements and proof
The proof is based on the following lemma:
Proof of lemma: Let Let be a sequence in K such that . Note that is in K since K is convex and so . Since
as , is a Cauchy sequence and so has limit x in K. It is unique since if y is in K and has norm δ, thenand x = y.
Proof of theorem: Given disjoint nonempty convex sets A, B, let
Since is convex and the sum of convex sets is convex, K is convex. By the lemma, the closure of K, which is convex, contains a vector v of minimum norm. Since is convex, for any x in K, the line segment
lies in and so
For , we thus have:
and letting gives: . Hence, for any x in A and y in B, we have: . Thus, if v is nonzero, the proof is complete since
In general, if the interior of K is nonempty, then it can be exhausted by compact convex subsets . Since 0 is not in K, each contains a nonzero vector of minimum length and by the argument in the early part, we have: for any . We also normalize them to have length one; then the sequence contains a convergent subsequence with limit v, which has length one and is nonzero. We have for any x in the interior of K and by continuity the same holds for all x in K. We now finish the proof as before. Finally, if K has empty interior, the affine set that it spans has dimension less than that of the whole space. Consequently K is contained in some hyperplane ; thus, for all x in K and we finish the proof as before.
The above proof also proves the first version of the theorem mentioned in the lede (to see it, note that K is closed under the hypothesis below.)
Here, the compactness in the hypothesis cannot be relaxed; see an example in the next section. Also,
This follows from the standard version since the separating hyperplane cannot intersect the interiors of the convex sets.
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:
(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 directions is used as a separating axis, as well as the cross products. Note that this yields possible separating axes, not separating lines/planes.
If the cross products were not used, certain edge-on-edge non-colliding cases would be treated as colliding. For increased efficiency, parallel axes may be calculated as a single axis.
- Boyd–Vandenberghe, Exercise 2.22.
- Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3.
- Golshtein, E. G.; Tretyakov, N.V.; translated by 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.