What is first edge position in the Minkowski sum of two convex polygons in the plane?

Question

I am trying to understand the informal algorithm of the Minkowski sum of two convex polygons in the plane as described here:

Then I tried to apply this method of the Minkowski sum in the example illustrated by wikipedia with two triangle (you can see the images if you scroll the Wikipage up, in the right side of the page there are two red triangles and the result of the sum on the top of them)

Applying the method a got this:

My question: if the first edge (ordered by polar angles illustrated by the image above) is the one that was defined by vertices (0,-1),(1,0) from polygon A, why the vertice with the lowest value in Y axis in the Wikipedia's result of the sum is (1,-2) instead of (0,-1) ?

Actually my question is: with this informal method, How do I know where to place the first edge? Or Maybe my order isn't good? Because if I start with edge (0,1),(0,-1) from Polygon A everything goes fine.

Thanks for your help.

Answer 1

Mathematically speaking, there is no "first" point in the Minkowski sum. However, if you're writing an algorithm to compute the Minkowski sum $A \oplus B$ of two convex polygons $A = \mathrm{conv}\{ a_1, \dots, a_m \} \subset \mathbb{R}^2$ and $B = \mathrm{conv}\{ b_1, \dots, b_n \} \subset \mathbb{R}^2$ given their vertices, you certainly need to start somewhere.

We know that $A \oplus B$ is the convex hull of the Minkowski sum of the two vertex sets, which justifies computing the sum using only the vertex sets. I don't know of a formal proof for the algorithm described on the Wikipedia page you linked, but it makes intuitive sense. A slower method would be to compute the sum of all $n \cdot m$ pairs of vertices from $A$ and $B$, then take the convex hull of the resulting points.

The Wikipedia algorithm tries to avoid computing these points by stepping along the boundary of $A+B$. The Minkowski sum has $n + m$ vertices, so it's clear that some of the $n \cdot m$ points computed by the naive algorithm must lie on the interior. Therefore, it's not enough to just pick two points at random to start from--we need to ensure the point we choose is on the boundary.

One way to do this, as suggested by this page, is to find the vertices in each shape with the smallest $y$ values and add them together. This point is guaranteed to be on the boundary of the sum because any other $a_i + b_j$ has a larger $y$ value. From here, you can step along the edges of the polygon as described in the article. This method has the additional benefit that angles work out nicely.

You could also start from any other vertex of the Minkowski sum. You could generalize the method above by using support functions to find extreme points for both shapes in any given direction; adding them together gives an extreme point on the sum.