Regardless of dimensionality, the separating axis is always a line.įor example, in 3D, the space is separated by planes, but the separating axis is perpendicular to the separating plane. SAT suggests an algorithm for testing whether two convex solids intersect or not. Two convex objects do not overlap if there exists a line (called axis) onto which the two objects' projections do not overlap. The separating axis theorem (SAT) says that: 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. In the second version, it may or may not be unique. In the first version of the theorem, evidently the separating hyperplane is never unique. For example, A can be a closed square and B can be an open square that touches A. (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. 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. The Hahn–Banach separation theorem generalizes the result to topological vector spaces.Ī related result is the supporting hyperplane theorem. The hyperplane separation theorem is due to Hermann Minkowski. 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. In another version, if both disjoint convex sets are open, then there is a hyperplane in between them, but not necessarily any gap. 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. There are several rather similar versions. ![]() Since the plane shares a point with $cl(K_1)$ or $cl(K_2)$ only when $\lambda$ is zero or one, and the or is exclusive, then it separates the two sets properly.In geometry, the hyperplane separation theorem is a theorem about disjoint convex sets in n-dimensional Euclidean space. However these two conditions simply mean that the plane defined as $(z_1-z_2)\cdot w = (z_1-z_2)\cdot z$ separates $cl(K_1)$ and $cl(K_2)$. Where I have used in the last line that $(z_1-z_2)\cdot(y-z_2) \leq 0$ and the norm being non-negative and $\lambda \geq 0$. Where I have used in the last line that $(z_2-z_1)\cdot(x-z_1) \leq 0$ and the norm being non-negative and $\lambda \geq 0$. Having these results we want to show that $(z_2-z_1)\cdot(x-z) \leq 0, \forall x \in cl(K_1)$: You have the minimizers $z_1 \in \partial K_1 ,z_2 \in \partial K_2$, but from their definition and the definition of projection, you have that the projection of $z_1$ onto $cl(K_2)$ is $z_2$ and the projection of $z_2$ onto $cl(K_1)$ is $z_1$.Īpplying the projection theorem to $z_1,z_2$ we get: ![]() Thus if you pick any point $z = (1-\lambda)z_1+\lambda z_2$, and use $z_1-z_2$ as the hyperplane normal, then $(y-z)\cdot(z_1-z_2)\leq 0$ and $(x-z)\cdot(z_1-z_2)\geq 0$ and the inequality is strict for $\lambda \in (0,1)$ since the sets are disjoint.Įdit2: Fixed proper/strong separation mistake. To see why your assumption is correct, you can use the projection theorem. So yes you can pick it to be orthogonal to that line, but you can also pick a hyperplane that is not orthogonal and it still may separate them porperly as long as it fulfills the above requirements in the theorem (basically what you require is unnecessarily strong). Then the hyperplane separating them has $v$ as normal. Then you can use the theorem stating that: if $C,D$ are non-empty sets in $\mathbb$$ Edit: never mind, your sets are disjoint, so they can be separated properly.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |