Editing Minkowski addition (section)

=== 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>).