Minkowski Sums of Monotone and General Simple Polygons

Let P be a simple polygon with m edges, which is the disjoint union of k simple polygons, all monotone in a common direction u, and let Q be another simple polygon with n edges, which is the disjoint union of ℓ simple polygons, all monotone in a common direction v. We show that the combinatorial complexity of the Minkowski sum P ⊕ Q is O(kℓmnα(min{m,n})), where α(·) is the inverse Ackermann function. Some structural properties of the case k = ℓ = 1 have been (implicitly) studied in [17]. We rederive these properties using a different proof, apply them to obtain the above complexity bound for k = ℓ = 1, obtain several additional properties of the sum for this special case, and then use them to derive the general bound.