Talk:Hyperplane separation theorem

Explanation of my partial revert

I did a partial revert of the recently added text. That because I find the new language too complicated. The separating axis theorem says that two convex bodies can be separated by a line. Once you have the line, you can of course project the two bodies onto the line perpendicular to it. But there is no need to state the definition in terms of the projection, that is just too complicated and does not add much.

This image has glitches.

I'd also like to note that the modified image, with the projection, does not render well, I see black rectangles on the screen, as seen on the right. That would need fixing before it can be used. Oleg Alexandrov (talk) 06:50, 8 January 2008 (UTC)

I think you are confusing separating axis and separating line. In practice, the separating axis theorem says that if two convex objects are not penetrating, there exists an axis for which the projection of the objects will not overlap. This is an important definition, because it suggests an algorithm for testing whether two convex solids intersect or not -- and, in fact, it's heavily used in computational geometry, including computer games. It is also an important definition, because no matter what the dimensionality, the separating axis is always an axis. For example, in 3D, there is still a separating axis. That axis is the dual of a separating plane.

When someone comes across the term "separating axis theorem," chances are pretty high that they did it because of some computational geometry need, the most common of which in practice is physical simulation such as found in games programming, and thus describing the actual separating axis and the property of the projection is necessary on the page. 75.144.241.102 (talk) 19:42, 8 January 2008 (UTC)

Btw: I generated the updated image in Inkscape. How can I make it not generate those artifacts for the labeling text?

The two formulations are trivially equivalent (if you are already familiar with it). And, "separating axis" does suggest more that the axis separates things, rather than the dual of the axis. In short, you do have a point, but I'd stick with the simpler formulation. Oleg Alexandrov (talk) 06:43, 10 January 2008 (UTC)

Well, I disagree -- a separating line is something that separates two objects, but a separating axis is the axis along which objects can be separated. I come to this from practical computational geometry, where those two definitions are the most natural. Also, presumably people using Wikipedia (instead of Mathworld or just a textbook) are not computational geometry mathematicians, and the duality between axis and hyperplane might not be immediately obvious. In fact, the reason I fixed the article was I sent someone here, and they didn't "get it." I updated the text to hopefully serve both purposes. I still need to know how to fix the illustration, though -- why are the Inkscape labels black? 66.253.99.66 (talk) 22:56, 10 January 2008 (UTC)

Wrong

I am sorry, but I belief this article is just plain wrong and did a good job in confusing me.

1.) The figure is wrong. The line show is not a separating axis. A separating axis is an axis on which the projections of the objects A and B do not overlap. If an axis with this property can be found the objects A and B are said to be non colliding if such an axis could not be found A and B are said to be colliding. There is an infinity of lines to check for collisions this way. The Separating Axis Theorem states that when such an axis exists, there also exist some with a specific property: the axis is orthogonal to either a face or edge of one of the objects. So the search space may be reduced to all orthogonal lines of all faces and edges in the scene.

The exact formulation is: "For a pair of non intersecting polytopes, there exists a separating axis that is orthognal to a facet of either polytope, or orthogonal to an edge from each polytope" cited from Gino van Bergens "Collision Detection in Interactive 3D Environments"

I am sorry that is all I can do for now. I hope some knowledgeable person will rewrite this article. I haven't the time and expertise to do that right now. In the meanwhile this article should be completely removed. False information is actually much worse than no information. For me that was an excellent lesson what is the difference between wikipedia and a proper book... sorry no offense but this article was part of lasting misunderstandig of what SAT means on my side. Sorry for posting anonymously, but I have never commited to wikipedia before.

Fair enough. As a mathematican, to me it makes more sense to talk about the line separating the two, not the axis on which to project, but I see your point. I replaced the picture. Oleg Alexandrov (talk) 05:05, 21 April 2008 (UTC)

The first statement of the theorem makes no sense to me: "given two convex shapes, there exists a line onto which their projections will be separate if and only if they are not intersecting." But if we are given the two shapes, they either are or are not intersecting, so if and only if can't come into it.

The second statement of the theorem, however, it perfectly clear. Could we just get rid of the first statement? Maproom (talk) 20:06, 4 December 2011 (UTC)

Re-reading the first statement of the theorem with a fresh clear mind, I figured out what it was struggling to say. I rewrote it to say that more clearly. Maproom (talk) 14:13, 8 December 2011 (UTC)

More Examples needed

I understand the separating axis theorem and the article didn't confuse me (although a link to some other article explaining the line/plane duality may be useful). But the line "If the cross products were not used, certain edge-on-edge non-colliding cases would be treated as colliding" seems quite ambiguous to me: do we need the cross products of all pairs of face normals (which would be quite a lot) or only some of them? and second: if we need edge normals as stated above in the discussion, which edge normals (in dimensions >2, each edge has infinitely many of them)? I ask because i can think of dozens of examples which are resolved by face normals, but none which need other axes (as long as the shapes don't have curved surfaces). So, whoever mentioned "certain edge-on-edge non-colliding cases", could you please give an example or a link?--Catskineater (talk) 09:26, 21 September 2008 (UTC)

Which cross products ?

For 3D, you talk about cross products for separating axis ... but which ones ? —Preceding unsigned comment added by Vanderfula (talk • contribs) 16:46, 26 January 2010 (UTC)

The cross products required are the face normals of one polyhedron crossed with each of the face normals of the other. For example, with 2 colliding 3D boxes, there are 3 axes each, and 9 pairs of cross products between the two of them, making 3+3+9=15 axes you must test before you can guarantee no collision. This is to ensure that no edge-edge collision occurs. If you feel it is necessary i can write that in the article with source later. --OrangeKyo (talk) 17:43, 2 February 2011 (UTC)

Proof

The proof doesn't seem to be complete. "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" is what we desire to prove. Why can we just state that it's obvious? Hechtlinger (talk) 17:49, 25 November 2012 (UTC)

The proof seems to have changed, but still looks incomplete in the case of open sets. How is it clear that there exists a convergent subsequence of hyperplanes? Is there a citation for this proof? We can at least be sure that a proof exists, since there is a nice one at http://www.ifp.illinois.edu/~angelia/L7_separationthms.pdf , but it is not as short. 24.0.248.75 (talk) 23:55, 18 November 2014 (UTC)

If we go to the projective space, the whole space of hyperplanes is compact, so there always exists a convergent subsequence. Alternatively, if projective spaces make you uncomfortable, consider a closed line segment connecting an arbitrary point in the first set to a point in the second set. The subset of the projective hyperplanes that intersect this line segment is closed and therefore still compact, and consists only of affine hyperplanes. —David Eppstein (talk) 08:19, 19 November 2014 (UTC)

The proof looks non-standard to me too. I think the standard proof uses the Hahn–Banach theorem. Since we are dealing with finite-dimensional vector spaces, there is no need for axiom of choice. -- Taku (talk) 01:21, 20 November 2014 (UTC)

Standard separation theorem

For arbitrary nonempty convex sets A, B in Rⁿ with empty intersection, there exist a non-constant linear function f and a number c such that $f(\cdot )\leq c$ on A and $f(\cdot )\geq c$ on B. This is called the standard separation theorem. Victor Klee, "Maximal separation theorems for convex sets", 1968. Boris Tsirelson (talk) 12:27, 29 March 2015 (UTC)

Now, thanks to Takuya Murata, I see this formulation in the article. But I do not understand, what happens to its proof. It seems to be claimed that the proof is here. But I do not see any proof valid without any topological assumptions (something open, something compact etc). Or do I miss some point? Boris Tsirelson (talk) 17:55, 30 March 2015 (UTC)

Yes, I rewrote the proof in order to address concerns raised in the section above; the new version doesn't have any gap in the proof. In the process, I also put the formulation of the theorem mentioned in this section with a textbook reference. It's actually an exercise problem, but if I didn't miss anything, the new proof works to prove this so-called standard separation theorem. Notice there is no closed, compact or open assumptions on the convex sets. -- Taku (talk) 18:43, 30 March 2015 (UTC)

Do you mean, the proof that contains the phrase " we can take an exhaustion K_n of K by closed convex subsets"? Boris Tsirelson (talk) 19:27, 30 March 2015 (UTC)

Yes. Maybe that part wasn't justified enough? -- Taku (talk) 19:44, 30 March 2015 (UTC)

Let K be, for example, the open disk (on the plane; or maybe on a plane in three-dim space) plus a non-Borel subset of the circle. In which sense can you exhaust it by closed subsets? Boris Tsirelson (talk) 21:29, 30 March 2015 (UTC)

Yes, I now see the issue. I reworded the proof a bit for now. If I can't (or anyone else) make that part more precise, I think I will add a note that it is not a full proof (only works with open or closed assumptions). -- Taku (talk) 22:24, 30 March 2015 (UTC)

Again with the caveat "if I didn't miss anything", I think this issue of exhaustion is fixed. -- Taku (talk) 23:26, 30 March 2015 (UTC)

"it is contained in some hyperplane and so we are also done"? Not clear. Do you mean linear of affine hyperplane? If it is contained in a hyperplane not containing 0, then we are done, indeed. Otherwise, what? You may do induction in dimension. By the induction hypothesis, we have a linear functional on the hyperplane; it remains to extend it (no matter how) to the whole space. And the basis, dimension one, is easy. Or, alternatively, you may use exhaustion, defined as follows: an increasing sequence of closed convex subsets whose union is dense in K. But existence of such sequence still needs a proof, including change of dimension if K has empty interior. Boris Tsirelson (talk) 05:42, 31 March 2015 (UTC)

A convex set with empty interior spans an affine space which has dimension less than that of the whole space; i.e., the convex set is contained in $\langle \cdot ,v\rangle =c$, v a normal vector (so nonzero). We can now repeat the same argument as before. (I agree that very last part needs to be made more clear and will do that.) -- Taku (talk) 11:52, 31 March 2015 (UTC)

Introduction

"and even two parallel hyperplanes in between them separated by a gap". Does this phrase really belong here? Unless the convex sets share a point, the existence of one hyperplane can be generalized to an infinite number of parallel hyperplanes between them, separated by a gap. But that's not an essential part of the theorem.

No. It may fail if their closures share a point. It also fails for the set of points (x,y) on the plane such that x>0 and xy>1 and the set of points (x,y) on the plane such that x>0 and y<0. Boris Tsirelson (talk) 15:31, 11 May 2015 (UTC)

Stated without proof or explanation

The article states:

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.

But no proof or explanation is provided for that assertion. Could this be explained? What does it mean by feature directions, and why does it suffice to check the normals of the faces as candidate separating axes? --pgimeno (talk) 21:32, 4 January 2016 (UTC)

Indeed, quite sketchy and unclear. Boris Tsirelson (talk) 22:02, 4 January 2016 (UTC)

Problems with proof

@TakuyaMurata and Tsirel: I have edited the article, making a couple changes. The second version mention'd in the introduction did not correspond exactly to the second version mention'd lower down. Also, I don't think the proof is good. First of all, why is it said that the interior of K can be exhausted by compact convex subsets "if the interior is nonempty"? It seems to me that it's true even if the interior is empty. And then I don't agree that the vectors $v_{n}$ will necessarily converge! It depends on the compact convex subsets that you use. And finally, I don't see why we need a separate, third case for when the interior of K is empty. Any comments or answers? Eric Kvaalen (talk) 09:46, 12 August 2016 (UTC)

About "if the interior is nonempty": otherwise, of course, the interior still can be exhausted by compact convex subsets, but this is helpless, since the empty interior fails to be dense in the convex set, and we cannot say "...and by continuity the same holds for all x in K". Boris Tsirelson (talk) 13:50, 13 August 2016 (UTC)

About "vectors $v_{n}$ will necessarily converge": who says so? Rather, "contains a convergent subsequence" (just because the sphere is compact). Boris Tsirelson (talk) 13:55, 13 August 2016 (UTC)

About the separate third case: but I don't see how to do it otherwise. Boris Tsirelson (talk) 13:57, 13 August 2016 (UTC)

Thanks, Boris. (I hadn't noticed that it said "a convergent subsequence".) Eric Kvaalen (talk) 11:21, 14 August 2016 (UTC)

Now Takuya Murata wrote that the version with compactness is the Hahn-Banach theorem. However, the unit ball is not compact in infinite dimension. Boris Tsirelson (talk) 04:56, 15 August 2016 (UTC)

I just meant the statement of Separation theorem I is true in infinite-dim (since it is exactly one formulation of the Hahn-Banach theore,). It's not about a unit ball (the theorem makes no mention of a unit ball). Am I missing something (which happens rather frequently)? -- Taku (talk) 08:09, 15 August 2016 (UTC)

Ah, yes, I see, you mean rather the Hahn–Banach separation theorem. Boris Tsirelson (talk) 08:32, 15 August 2016 (UTC)

When I put in a sentence sayin that it's not true in infinite dimensions, I was basin that on this sentence in the French article: "En revanche, en dimension infinie, on ne peut pas toujours construire un hyperplan fermé de séparation large : il existe un exemple de deux convexes fermés non vides et disjoints mais qui ne peuvent être séparés par un hyperplan fermé" (with a reference which I don't have). So is that wrong? I don't understand what they mean by a "hyperplan fermé" (a "closed hyperplane"). Eric Kvaalen (talk) 16:58, 15 August 2016 (UTC)

Also, I don't see why we need to use the interior of K. Why can't we say that K itself can be "exhausted" by an infinite series of convex, compact sets, and proceed from there? That would also cover the case where the interior of K is empty. Eric Kvaalen (talk) 16:58, 15 August 2016 (UTC)

Note that K itself need not be an F_σ set (try an open disk plus arbitrary subset of the circle). And, of course, the closure of K may contain zero. Boris Tsirelson (talk) 18:16, 15 August 2016 (UTC)

@Tsirel and TakuyaMurata: But are there really examples of sets A and B that would give a K like that? Eric Kvaalen (talk) 20:52, 15 August 2016 (UTC)

I do not know. But, who wants to go this harder way (even if possible) instead of the easier way written now? Boris Tsirelson (talk) 04:49, 16 August 2016 (UTC)

Well, here is another way. What we really need is a sequence of compact subsets of K whose union is dense in K (not necessarily equal K). This is easy: take a dense (in K) sequence of points of K, and consider the convex hull of the first n points of the sequence. Boris Tsirelson (talk) 05:47, 16 August 2016 (UTC)

@Tsirel: You're right. But actually, thinking about it a bit more, you will get such a K if A and B are themselves such disks. Eric Kvaalen (talk) 05:50, 16 August 2016 (UTC)

Yes, I see. Boris Tsirelson (talk) 06:41, 16 August 2016 (UTC)

But wait... Hmmm... Ridiculously, if both convex sets are contained in an affine subspace (of dimension <n), then the claim is trivial! Take a nonconstant linear functional whose restriction to the subspace is constant. Boris Tsirelson (talk) 06:08, 16 August 2016 (UTC)

@Tsirel: That's actually what our proof does – it puts the hyperplane right through the two sets. Eric Kvaalen (talk) 17:31, 22 August 2016 (UTC)

Really? "Finally, if K has empty interior, the affine set that it spans has dimension less than that of the whole space"; indeed, our proof finalizes it shortly; but I guess, one often does it otherwise: applies the already proved case to this affine set (instead of the given space), thus proving the stronger version. Boris Tsirelson (talk) 20:28, 22 August 2016 (UTC)

Now I'd say that the usual formulation does not deserve the name "separation". One should require that the linear functional is not constant on the union of the two given convex sets (not just on the whole space). But this is probably OriginalResearch. Boris Tsirelson (talk) 08:37, 16 August 2016 (UTC)

@Tsirel: I wouldn't call that original research. I think it's worth pointing out that the "separation" of the main theorem is so weak that it permits this. But of course, when you have two sets that are both on some hyperplane, there are also an infinite number of other hyperplanes that separate them. Eric Kvaalen (talk) 17:31, 22 August 2016 (UTC)

About the French article: maybe this happens because they treat two closed sets (no one being compact). Also: a closed hyperplane is a hyperplane L=const where L is not just algebraically linear, but also continuous. Boris Tsirelson (talk) 18:21, 15 August 2016 (UTC)

@Tsirel and TakuyaMurata: I see now that I put my comment about infinite dimensionality in the wrong place. I should put it higher, above the part on "Separation Theorem I". Eric Kvaalen (talk) 20:52, 15 August 2016 (UTC)

@Eric Kvaalen: There still seems to be a problem with the proof. I can accept (though I haven't thought clearly enough about why it is true) that we can express the interior of K as the union of the compact sets $K_{n}$, but why is it necessarily true that the subsequence limit v has $\langle x,v\rangle \geq 0$ for all x in the interior of K? Here's an example which makes me question this result. Let K be the rectangle in $\mathbb {R} ^{2}$ with vertices (-n,1), (-n,2), (n,1), (n,2) for some large n. Then we could end up with v being a vector close to (1,0), and if x is close to (-n,1), then $\langle x,v\rangle <0$. Is it perhaps the case that we want the $K_{n}$ to be a nested sequence of compact subsets? Is it always possible to find such a sequence whose limit/union is the interior of K? (I don't know.) If it is, then this would do the job. Julian Gilbey (talk) 23:47, 11 March 2020 (UTC)

Ah, yes, we can let $K_{n}$ be a nested sequence of compact subsets. We're working in $\mathbb {R} ^{n}$, which is second countable; we can use the basis consisting of balls with rational centres and rational radii. Then the interior of K consists of a countable union of such balls. An open ball can be written as a countable union of compact sets (just take closed balls with the same centre and radii $r(1-2^{-k})$ where r is the radius of the open ball and k=1, 2, 3, ...), so the interior of K can be expressed as a countable union of compact sets. Listing all of these sets as $K'_{r}$, r=1, 2, 3, ..., we then take $K_{n}=\bigcup _{r=1}^{n}K'_{r}$ since a finite union of compact sets is compact. I will tweak the proof to say nested sequence. Julian Gilbey (talk) 07:57, 12 March 2020 (UTC)

Yeah, Julian, I figured out that it must mean nested subsets yesterday, and now I see that you figured that out yourself. The part about why the interior of K is a union of compact sets seemed intuitively obvious to me yesterday, but I didn't see how to prove it, as you have now done. By the way, it wasn't I who put the proof in the article, it was Takuya Murata back in 2015. Boris Tsirelson might find this interesting as well. Eric Kvaalen (talk) 10:25, 13 March 2020 (UTC)

Reference to original source by Minkowski?

Since the HST is attributed to Hermann Minkowski, it would be natural to cite him in papers that use the theorem. But I have trouble finding the original presentation of the theorem and its proof. If anyone else has more success, this article would surely benefit from a proper citation too.37.44.138.134 (talk) 22:22, 12 December 2019 (UTC)

Use in collision detection section provides insufficient algorithm

In 3D space, testing face normals and cross products of edges is sufficient only when the two solids are not coplanar. As a counterexample, in the trivial case where all vertices are located on the xy plane, every face normal and cross product will be parallel to the z axis - the z axis will be the only axis checked for separation, and all points will be projected to 0 regardless of whether a collision exists. In this case, the cross product of the plane's normal and each individual edge must be tested instead.

A similar situation occurs (in 2D and 3D) when all vertices are collinear. In that case, it's sufficient to check the line on which all the vertices sit.

As far as I can tell, the algorithm as previously stated is sufficient when at least one vertex in either solid breaks the pattern. Amras0000 (talk) 22:28, 4 July 2022 (UTC)