# Proof of Separating Axis Theorem for polygons

One well-known special case of the Hyperplane Separation Theorem (Separating Axis Theorem) states:

Let $A, B \subset \mathbb{R}^2$ be convex polygons. Then $A \cap B = \emptyset$ if and only if there is a straight line $L$, such that $A \subset L^-$ and $B \subset L^+$

…where $L^-$ and $L^+$ are the open half-planes formed by $L$.

In other words: two convex polygons do not collide if and only if you can draw a straight line between them.

When reading articles about collision detection in computer science, you often find the following, stronger version:

Let $A, B \subset \mathbb{R}^2$ be convex polygons. Then $A \cap B = \emptyset$ if and only if there is a straight line $L$ parallel to one of $A$'s or $B$'s edges, such that $A \subset L^-$ and $B \subset L^+$.

However, I haven't found any proof for this second version anywhere. I'd also think that the generalization is true for $\mathbb{R}^n$ with $n \ge 1$, but I have no idea how to approach this. Anyone?

• A typically proof relies on drawing $L$ perpendicular to the shortest line segment connecting $A$ and $B$. You only need to cover the case where that line segment connects two extreme points. – LinAlg Jan 24 '17 at 22:58
• @LinAlg Intuitively that is clear. However, the proof is non-trivial, particularly the case where we're dealing with edges and vertexes in $\mathbb R^n$ – ThomasR Jan 24 '17 at 23:07
• I agree that the case where that line segment connects two extreme points is not trivial. – LinAlg Jan 24 '17 at 23:20
• I got the outline of a proof for $\mathbb R^2$, but it's too long to write down here. – ThomasR Jan 24 '17 at 23:22

I think this is an interesting question.

However, the result is not true for dimension $n\geq 3$. Consider the following counter example for $n=3$.

The counter example is probably best seen using the picture, although I can provide the half-space description if necessary. The counter example is two prisms with rotated squares as a base. They are situated in such a way that any half space defining one contains points of the other. Therefore, the conclusion is false.

Moreover, this can be generalized by taking $n$-dimensional cubic-prisms and orient them in this way (here an $n$-dimensional cubic-prism has a $n-1$ dimensional cube as it's base).

Also, it sounds like you have a solution for dimension 2. In light of how the conclusion is false for higher dimensions, I do not believe that such a solution will be simple in the sense that it avoids using geometry in 2 dimensions.

• Perhaps I do not understand the question correctly, but what about the plane $P=\{x_3=k\}$, a horizontal plane that sits between the two prisms. Isn't $P$ parallel to the top face of the top prism, while separating the two? – Yacoub Kureh Jan 27 '17 at 19:26
• @YacoubKureh That is true, but I think we can tilt the topmost surface such that its extension intersects the other prism. And also tilt the bottommost surface. – ThomasR Jan 27 '17 at 19:30
• "I do not believe that such a solution will be simple in the sense that it avoids using geometry in 2 dimensions" - Correct. – ThomasR Jan 27 '17 at 19:33
• What if we're not looking for a plane parallel to one of the surfaces, but for a plane parallel to one of the edges, regardles of $n$? – ThomasR Jan 27 '17 at 19:37
• @ThomasR what does it mean to be parallel to an edge in higher dimensions? Typically parallel is in reference to $(n-1)$ dimensional objects, but an edge no longer becomes $(n-1)$ dimensional after $n\geq 3$. – JSP Jan 27 '17 at 20:24

Great question! it's amazing how many people claim this but without any argument or proof. I couldn't find any proof of it online but I did find a proof myself. I reformulated the theorem so it is correct in $n$ dimensions, and then extracted the original theorem from it in the $2D$ case.

Theorem (general): let $A, B \subset \mathbb{R}^n$ be 2 convex compact polytopes such that $A\cap B = \emptyset$, then there exists a separating hyperplane with normal vector orthogonal to one of the facets of the Minkowski sum $A+(-B)$

To make it easier on terminology I will work in $\mathbb{R}^2$ here, but the proof works exactly the same way for any other $n$ (just different words)

Theorem (2D): let $A, B \subset \mathbb{R}^2$ be 2 convex compact polygons such that $A\cap B = \emptyset$, then there exists a separating line with normal vector orthogonal to one of the sides the Minkowski sum $A+(-B)$

Proof:

Step 1, choosing the axis: Denote $K := A+(-B)$. $K$ is itself a compact convex polygon. We can extend each of its sides to a line. Since K is convex it will always be completely in 1 of the 2 halfplanes given by such a line. K is even equal to the intersection of all these halfplanes. (this is one of the definitions of a convex polygon). write $$K = \bigcap_i H_i$$ where the $H_i$ are these halfplanes. Since $A\cap B=\emptyset$ we have $0\notin K$. This implies $0\notin H_i$ for some $i$. This $H_i$ was derived from a line $l$ that was the extention of one of the sides of $K$. Now take $v \in l$ such that $\lVert v \rVert = \inf_{x\in l} \lVert x\rVert$. This vector exists because of the Hilbert projection theorem. Note that, since $0\not\in l$, we have $v\ne 0$.

Step 2, orthogonality: Take a unit vector $w$ in the direction of $l$ (in $n$-D: orthogonal to the normal of $l$). We then have that $v-aw \in l$ for all $a \in \Bbb R$, and because $v$ has minimal norm: \begin{align*} \lVert v \rVert ^2 & \leq \lVert v - aw\rVert ^2\\ & = \langle v- aw,v-aw\rangle\\ &= \lVert v \rVert ^2 - 2 a \langle v,w \rangle + a^2\\ \end{align*} Now, let $a = \langle v,w\rangle$ then we have $$\lVert v\rVert ^2 \leq \lVert v\rVert ^2 - \langle v,w \rangle ^2$$ so $\langle v,w\rangle = 0$ and $v$ is orthogonal to $l$.

Step 3, separation: Take a look at the proof of the hyperplane separation theorem given here. If we prove that $$\lVert v \rVert ^2 \leq \lVert v + t(x-v) \rVert^2$$ for all $t\in [0,1]$ and for all $x\in K$, then the rest of the proof can be done exactly the same. Ask me if you want me to explicitly write it down here but it's lengthy. To show the desired inequality, remember that $0$ is on the other side of $l$ than $K$. since a halfplane is convex, $v + t(x-v)$ will be on the same side of $l$ as $K$. This means that the line segment connecting $0$ and $v + t(x-v)$ will intersect $l$ at some point $s$, where $$\lVert s\rVert \leq \lVert v + t(x-v) \rVert$$ Now because $s\in l$ we have $\lVert v\rVert \leq \lVert s \rVert$ and we are done.

Your version of the theorem follows from this because in 2D, the Minkowski sum of 2 polygons can be obtained just by sliding arroud the edges of the original polygons. This is no longer true in 3D or higher so that explains the counter example given in the other answer that looked like this:

However, the modified theorem does hold in 3D and higher, so we need to look at the Minkowski sum. Call the bottom object $A$ and the top one $B$, then $A+(-B)$ will look like this:

This Minkowski sum does provide a separating axis orthogonal to its top facet.

• Thanks for that! A few remarks: 1) Is "hyperplane with normal vector orthogonal to one of the facets" any different from "hyperplane parallel to one of the facets"? 2) I don't understand your argument in Step 2 ("in $n$-D: orthogonal to the normal of $l$") If I'm not mistaken, $l$ is a hyperplane and $w\in l$ will do, and is required to conclude $v−aw\in l$. 3) Your argument "remember that 0 is on the other side of $l$ than $K$" in step 3 is not correct. Looking at your second illustration, $l$ might be any facet of $K$, but only one of them satisfies your condition. – ThomasR Apr 2 '17 at 17:54
• I assume you meant $\langle x, v \rangle + c \geq 0$ for some positive c? Then yes that's what you need to prove, and like many proofs in this area, it is intuitively clear but a proof does not easily follow form the intuition so it feels like a trick, I agree. But how would you prove it without this trick? (I'm always interested in a more intuitive or elegant proof) And altough I'm not claiming that you have to interpolate like that, I do want to note that if you can't, the theorem is false. – Jens Renders Jun 13 '17 at 22:01
• @BenBray Ah yes I agree. I guess you just want to fill in t = 0 but that wont work with the algebraic simplyfication before (cancelling a t). Maybe the algebra can be done differently so you don't need to cancel a t. I atleast don't know sorry :) – Jens Renders Jun 13 '17 at 22:31
• Right, exactly: Choose $v$ to be the vector in $H_i$ of smallest norm. This vector necessarily lies on $\ell$, but I don't think that fact is used in orthogonality or separation. For orthogonality, the proof should be the same, and for separation, the argument is simplified to just "for any $x \in K \subset H_i$, the interpolated point $v + t(x-v) \in H_i$ by convexity, so the inequality holds by minimality of $v$." Does this argument work or am I missing something? – Ben Bray Jun 16 '17 at 22:25
• @BenBray You are right! The reason I put it this is because I am more used to working with an affine subspace, ie a translated subvectorspace, instead of a halfspace, but you are right it does work the way you said. – Jens Renders Jun 16 '17 at 22:37