Editing Minkowski addition (section)

== Algorithms for computing Minkowski sums ==
[[File:Shapley–Folkman lemma.svg|thumb|upright=1.4| alt=Minkowski addition of four line-segments. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. The right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.
| Minkowski addition and convex hulls. The sixteen dark-red points (on the right) form the Minkowski sum of the four non-convex sets (on the left), each of which consists of a pair of red points. Their convex hulls (shaded pink) contain plus-signs (+): The right plus-sign is the sum of the left plus-signs.
]]

=== Planar case ===
==== Two convex polygons in the plane ====
For two [[convex polygon]]s {{var|P}} and {{var|Q}} in the plane with {{var|m}} and {{var|n}} vertices, their Minkowski sum is a convex polygon with at most {{var|m}} + {{var|n}} vertices and may be computed in time O({{var|m}} + {{var|n}}) by a very simple procedure, which may be informally described as follows. Assume that the edges of a polygon are given and the direction, say, counterclockwise, along the polygon boundary. Then it is easily seen that these edges of the convex polygon are ordered by [[polar coordinate system|polar angle]]. Let us [[Merge algorithm|merge the ordered sequences]] of the directed edges from {{var|P}} and {{var|Q}} into a single ordered sequence {{var|S}}. Imagine that these edges are solid [[arrow]]s which can be moved freely while keeping them parallel to their original direction. Assemble these arrows in the order of the sequence {{var|S}} by attaching the tail of the next arrow to the head of the previous arrow. It turns out that the resulting [[polygonal chain]] will in fact be a convex polygon which is the Minkowski sum of {{var|P}} and {{var|Q}}.

==== Other ====
If one polygon is convex and another one is not, the complexity of their Minkowski sum is O(''nm''). If both of them are nonconvex, their Minkowski sum complexity is O((''mn'')<sup>2</sup>).