Given two convex polygons A, B, we can define Minkowski sum, as A + B = {a + b: a $\in$ A, b $\in$ B}, where a + b vector sum. Prove that:

for every external perpendicular u to an edge of A, there exists an external perpendicular to an edge of A + B, which will be parallel to u.


I know that the external perpendicular has maximum inner product for points that lie in that edge of the polygon, i.e. = max <=> p $\in$ edge.

enter image description here

So now, I assume I have an edge a of A and $\overline{b}$ = {b $\in$ B | $u^T$ to be max}.

Because B is convex, $\overline{b}$ will be a point or an edge. If it is a point a + $\overline{b}$ = a, u $\bot$ a and $u^T$(a + $\overline{b}$) = $u^Ta $+ $u^t$$\overline{b}$.

If a is not an edge, then there will be points outside of the polygon, which are going to maximize the inner product.

I am not sure if I am in the right track..any ideas? Please teach me how to fish, don't just hand me the fish! :)

  • $\begingroup$ Do you know that, the Minkowski sum of two convex polygons is obtained by intertwinning the edges of these polygons taking them in the order of their normal angle ? See fig. 2.2 of the following document (in French). On the side of computer implementations www-i2.informatik.rwth-aachen.de/i2/fileadmin/user_upload/…. $\endgroup$ – Jean Marie Mar 23 '16 at 17:07
  • $\begingroup$ @JeanMarie thanks for the comment, but I am still unable to follow, I mean I am looking at the figure, but I can't get the point! Can you please expand on this? :) $\endgroup$ – gsamaras Mar 23 '16 at 22:01
  • $\begingroup$ I mean I understand that what I need to prove stands, from the Minkowski sum pictures (en.wikipedia.org/wiki/Minkowski_addition) and my intuition is clear on this. I just do not know how to prove it @JeanMarie. $\endgroup$ – gsamaras Mar 24 '16 at 0:10
  • $\begingroup$ What is an "external perpendicular" in this context? I can't seem to find the terminology used anywhere else. My first guess is that it's the same as a normal vector, but I don't understand the "maximum inner product" characterization. $\endgroup$ – Benjamin Bray Jun 10 '17 at 20:51

First of all, a good reference (CGal s a very powerful library ) : http://doc.cgal.org/latest/Minkowski_sum_2/

I think the point is that you have to revert the definition of a convex polygon:

There is a perfect equivalence between two convex polygon definitions: through a list of points or through a set of vectors (sorted by their polar angle)

  • Being given a list of points $P_k$, the associated set of vectors is $P_{k+1}-P_k=\overrightarrow{P_kP_{k+1}}$ (it is a kind of derivative, denoted $\partial P$, part of a vast theory called "homology" ).

  • in a reverse way, being given a list of vectors $V_k$ (sorted by their polar angle), one takes an arbitrary origin point $P_1$, then $P_2=P_1+V_1$, $P_3=P_2+V_2$, etc.

The second way gives an immediate definition: the Minkowski sum of 2 polygons is the polygon associated with the (sorted) union of the list of vectors of the 2 polygons.

Philosophical note: It wouldn't be the first time in mathematics that a definition and a property take advantage to be interchanged...

  • $\begingroup$ I know about CGAL, I have used it: gsamaras.wordpress.com/projects/#PIP, but now I approached the problem from a completely theoretical point of view, thankS! $\endgroup$ – gsamaras Mar 24 '16 at 21:35

The proof you suggest is on the right track and I believe it works in general. Notice that $$\max_{a \in A , b \in B} \space u^\top ( a + b ) = \max_{a \in A} u^\top a + \max_{b \in B} u^\top b $$

In the general case where $u$ is perpendicular to some facet on $A$, the extremal set on $B$ will be a vertex, and that translated facet will be a facet of $A \bigoplus B$.

In the other cases where the extremal set on $B$ is not a vertex, the corresponding facet in $A \bigoplus B$ will be the Minkowski sum of the extremal facets, but that it is still perpendicular to $u$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.