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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s