Hyperplane separation theorem

{{math_theorem|name=Hyperplane separation theorem|Let A and B be two disjoint nonempty convex subsets of \R^n. Then there exist a nonzero vector v and a real number c such that :\langle x, v \rangle \ge c \, \text{ and } \langle y, v \rangle \le 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_1 \, \text{ and } \langle y, v \rangle for some c_1 > c_2 }} In all cases, assume A, B to be disjoint, nonempty, and convex subsets of \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. 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 proof|title=Proof of lemma|proof= Let a\in A and b \in B be any pair of points, and let r_1 = \|b - a\|. 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 \cap \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 \|a_0 - b_0\| is the minimum over all pairs of points in A \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 \times B. Suppose for contradiction that there exist points a' and b' such that \|a' - b'\| . Then in particular, \|a' - b'\| , and by the triangle inequality, \|a - b'\| \le \|a' - b'\| + \|a - a'\| . Therefore b' is contained in S, which contradicts the fact that a_0 and b_0 had minimum distance over A \times S. \square }} A and B be two disjoint, closed, convex sets, and suppose that A is compact. Then A and B have a closest pair of points p and q. (The distance function d(p,B) is a continuous function that vanishes only on B, and since A is compact, it must have a positive minimum p on A.) Then any hyperplane H which is perpendicular to the segment I(p,q) from p to q, and which meets the interior of this segment, must separate A from B. For the second version of the theorem, suppose that A and B are disjoint, convex, and open. Then they can be exhausted by sequences of compact, convex subsets A^n and B^n. The first version of the theorem supplies a sequence of separating hyperplanes H^n which must have a subsequence that converges to a hyperplane H. This hyperplane must separate A from B--> {{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 \in A and b_0 \in B of minimum distance to each other. Since A and B are disjoint, we have a_0 \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 c_A := \langle v, a_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 v, a\rangle \leq c_A and \forall b\in B, \langle v, b\rangle \geq c_B. Suppose for contradiction that there is some point a\in A such that \langle v,a\rangle > c_A. Then since the gradient of the function f(z) = \|z - b_0\|^2 is given by \nabla f(z) = 2(z - b_0), it follows that the directional derivative \nabla_{a - a_0}f(a_0) has the same sign as \langle a - a_0, 2(a_0 - b_0) \rangle = -2 \langle a - a_0, v \rangle, which is negative. So for sufficiently small \epsilon > 0, the point a' = a_0 + \epsilon(a - a_0) satisfies f(a') , which contradicts the choice of a_0 since a' \in A by convexity. A similar argument shows \forall b\in B, \langle v, b\rangle \geq c_B. Now for the first case. Approach 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, and the unions are the relative interiors \mathrm{relint}(A), \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 \langle v_k, A_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. }} A, B, let :K = A + (-B) = \{ x - y \mid x \in A, y \in B \}. Since -B is convex and the sum of convex sets is convex, K is convex. By the lemma, the closure \overline{K} of K, which is convex, contains a vector v of minimum norm. Since \overline{K} is convex, for any n in K, the line segment :v + t(n - v), \, 0 \le t \le 1 lies in \overline{K} and so :|v|^2 \le |v + t(n - v)|^2 = |v|^2 + 2 t \langle v, n - v \rangle + t^2|n-v|^2. For 0 , we thus have: :0 \le 2 \langle v, n \rangle - 2 |v|^2 + t|n-v|^2 and letting t \to 0 gives: \langle n, v \rangle \ge |v|^2. Hence, for any x in A and y in B, we have: \langle x - y, v \rangle \ge |v|^2. Thus, if v is nonzero, the proof is complete since :\inf_{x \in A} \langle x, v \rangle \ge |v|^2 + \sup_{y \in B} \langle y, v \rangle. More generally (covering the case v = 0), let us first take the case when the interior of K is nonempty. The interior can be exhausted by a nested sequence of nonempty compact convex subsets K_1\subset K_2\subset K_3\subset\cdots (namely, put K_j \equiv [-j,j]^n \cap \{ x \in \text{int}(K) : d(x, (\text{int}(K))^c) \ge \frac{1}{j} \} ). Since 0 is not in K, each K_n contains a nonzero vector v_n of minimum length and by the argument in the early part, we have: \langle x, v_n \rangle \ge 0 for any x \in K_n. We can normalize the v_n's to have length one. Then the sequence v_n contains a convergent subsequence (because the n-sphere is compact) with limit v, which is nonzero. We have \langle x, v \rangle \ge 0 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 \langle \cdot, v \rangle = c; thus, \langle x, v \rangle \ge c for all x in K and we finish the proof as before. \square }} --> Since a separating hyperplane cannot intersect the interiors of open convex sets, we have a corollary: {{math_theorem :\langle x, v \rangle > c \, \text{ and } \langle y, v \rangle \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 :\langle x, v \rangle>c \, \text{ and } \langle y, v \rangle for all x in A and y in B. }} == Case with possible intersections ==

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 :\langle x, v \rangle \ge c \, \text{ and } \langle y, v \rangle \le c }} in particular, we have the supporting hyperplane theorem. {{Math proof|title=Proof|proof= If the affine span of A is not all of \mathbb{R}^n, then extend the affine span to a supporting hyperplane. Else, \mathrm{relint}(A) = \mathrm{int}(A) is disjoint from \mathrm{relint}(\{a_0\}) = \{a_0\}, so apply the above theorem. }} == 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 \le 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. The horn angle provides a good counterexample to many hyperplane separations. For example, in \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 a closed convex polyhedron then such a separation exists. == More variants ==

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. ==Use in collision detection==

In collision detection, the hyperplane separation theorem is usually used in the following form: 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. For increased efficiency, parallel axes may be calculated as a single axis. ==See also ==