Complexity of 2D-Minkowski sum of non-convex polygons

Question

I have read that the complexity of computing the Minkowski-Sum of $2$ non-convex polygons (through convex decomposition) is $O(m^2 n^2)$, where $m$ and $n$ is the number of vertices of each polygon. How can we prove this? I managed to prove that convex + convex has complexity $O(m+n)$ and convex + non-convex is $O(mn)$, but I got stuck on the last case. Any hint would be appreciated.

Answer 1

See Eli Fogel's slides. and be enlightened.

Answer 2

To supplement Igor's link with a paper citation:

Agarwal, Pankaj K., Eyal Flato, and Dan Halperin. "Polygon decomposition for efficient construction of Minkowski sums." Computational Geometry 21, no. 1-2 (2002): 39-61.

---

         

---