# A Small Result in Polygon Translational Containment

Given two polygons $P_1$ and $P_2$ and two vectors $t_1$ and $t_2$ let $P_1+t_1$ and $P_2 + t_2$ be the vector sum. That is $P_1 + t_1$ is the set $\{x \in \mathbb R^2 | x = a + t_1 \textrm{ where } a \in P_1\}$. Also let the Minkowski sum of two sets A and B be as follows $A \oplus B = \{a+b | a \in A, b \in B\}$. The following lemma is on page 6 of the paper “Translational Polygon Containment and Minimal Enclosure using Mathematical Programming” by V.J. Milenkovic and Karen Daniels

The lemma is as follows: The set $(P_1 + t_1)\cap(P_2 + t_2)$ is non-empty iff $t_2 - t_1 \in P_1 \oplus - P_2.$

To prove the lemma we note that $t_2 - t_1 \in P_1\oplus -P_2$ iff $t_2 - t_1 = a - b$ for some $a \in P_1$ and $b \in P_2$. It then follows that $b+t_2 = a+t_1$ for some $a \in P_1$ and $b \in P_2.$ Thus $b+t_2$ is a point in $P_2 + t_2$ and since $b+t_2 = a + t_1$ then $b+t_2$ is also a point in $P_1 + t_1$ hence $b +t_2$ is in $(P_1 + t_1)\cap(P_2+t_2.$

One question you might have is “what is the use of the lemma?”. The answer is that $(P_1+t_1)$ does not intersect $(P_2+t_2)$ iff $t_2 - t_1 \in \overline{P_1 \oplus -P_2}.$ Thus given two translations of $P_1$ and $P_2$ we have an algorithm for deciding if the translated polygons overlap.