Problem:
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.
Attempt:
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.
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! :)
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...