Minkowski addition

In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors "A" and "B" in Euclidean space is formed by adding each vector in "A" to each vector in "B", i.e., the set
Analogously, the Minkowski difference (or geometric difference) is defined using the complement operation as
In general formula_3. For instance, in a one-dimensional case formula_4 and formula_5 the Minkowski difference formula_6, whereas formula_7
In a two-dimensional case, Minkowski difference is closely related to erosion (morphology) in image processing.
The concept is named for Hermann Minkowski.
Example.
For example, if we have two sets "A" and "B", each consisting of three position vectors (informally, three points), representing the vertices of two triangles in formula_8, with coordinates
and
then their Minkowski sum is
which comprises the vertices of a hexagon.
For Minkowski addition, the , formula_12 containing only the zero vector, 0, is an identity element: for every subset "S" of a vector space,
The empty set is important in Minkowski addition, because the empty set annihilates every other subset: for every subset "S" of a vector space, its sum with the empty set is empty:
For another example, consider the Minkowski sums of open or closed balls in the field formula_15 which is either the real numbers formula_16 or complex numbers formula_17 If formula_18 is the closed ball of radius formula_19 centered at formula_20 in formula_21 then for any formula_22 formula_23 and also formula_24 will hold for any scalar formula_25 such that the product formula_26 is defined (which happens when formula_27 or formula_28). If formula_29 and formula_30 are all non-zero then the same equalities would still hold had formula_31 been defined to be the open ball, rather than the closed ball, centered at formula_20 (the non-zero assumption is needed because the open ball of radius formula_20 is the empty set). The Minkowski sum of a closed ball and an open ball is an open ball. More generally, the Minkowski sum of an open subset with other set will be an open subset. 
If formula_34 is the graph of formula_35 and if and formula_36 is the formula_37-axis in formula_38 then the Minkowski sum of these two closed subsets of the plane is the open set formula_39 consisting of everything other than the formula_37-axis. This shows that the Minkowski sum of two closed sets is not necessarily a closed set. However, the Minkowski sum of two closed subsets will be a closed subset if at least one of these sets is also a compact subset.
Convex hulls of Minkowski sums.
Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition: 
This result holds more generally for any finite collection of non-empty sets:
In mathematical terminology, the operations of Minkowski summation and of forming convex hulls are commuting operations.
If formula_45 is a convex set then formula_46 is also a convex set; furthermore 
for every formula_48. Conversely, if this "distributive property" holds for all non-negative real numbers, formula_49, then the set is convex.
The figure to the right shows an example of a non-convex set for which formula_50
An example in formula_51 dimension is: formula_52 It can be easily calculated that formula_53 but formula_54 hence again formula_55
Minkowski sums act linearly on the perimeter of two-dimensional convex bodies: the perimeter of the sum equals the sum of perimeters. Additionally, if formula_56 is (the interior of) a curve of constant width, then the Minkowski sum of formula_56 and of its formula_58 rotation is a disk. These two facts can be combined to give a short proof of Barbier's theorem on the perimeter of curves of constant width.
Applications.
Minkowski addition plays a central role in mathematical morphology. It arises in the brush-and-stroke paradigm of 2D computer graphics (with various uses, notably by Donald E. Knuth in Metafont), and as the solid sweep operation of 3D computer graphics. It has also been shown to be closely connected to the Earth mover's distance, and by extension, optimal transport.
Motion planning.
Minkowski sums are used in motion planning of an object among obstacles. They are used for the computation of the configuration space, which is the set of all admissible positions of the object. In the simple model of translational motion of an object in the plane, where the position of an object may be uniquely specified by the position of a fixed point of this object, the configuration space are the Minkowski sum of the set of obstacles and the movable object placed at the origin and rotated 180 degrees.
Numerical control (NC) machining.
In numerical control machining, the programming of the NC tool exploits the fact that the Minkowski sum of the cutting piece with its trajectory gives the shape of the cut in the material.
3D solid modeling.
In OpenSCAD Minkowski sums are used to outline a shape with another shape creating a composite of both shapes.
Aggregation theory.
Minkowski sums are also frequently used in aggregation theory when individual objects to be aggregated are characterized via sets.
Collision detection.
Minkowski sums, specifically Minkowski differences, are often used alongside GJK algorithms to compute collision detection for convex hulls in physics engines.
Algorithms for computing Minkowski sums.
Planar case.
Two convex polygons in the plane.
For two convex polygons and in the plane with and vertices, their Minkowski sum is a convex polygon with at most + vertices and may be computed in time O( + ) 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 angle. Let us merge the ordered sequences of the directed edges from and into a single ordered sequence . Imagine that these edges are solid arrows which can be moved freely while keeping them parallel to their original direction. Assemble these arrows in the order of the sequence 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 and .
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)2).
Essential Minkowski sum.
There is also a notion of the essential Minkowski sum +e of two subsets of Euclidean space. The usual Minkowski sum can be written as
Thus, the essential Minkowski sum is defined by
where "μ" denotes the "n"-dimensional Lebesgue measure. The reason for the term "essential" is the following property of indicator functions: while
it can be seen that
where "ess sup" denotes the essential supremum.
"Lp" Minkowski sum.
For "K" and "L" compact convex subsets in formula_63, the Minkowski sum can be described by the support function of the convex sets:
For "p ≥ 1", Firey defined the Lp Minkowski sum of compact convex sets "K" and "L" in formula_63 containing the origin as
By the Minkowski inequality, the function "h" is again positive homogeneous and convex and hence the support function of a compact convex set. This definition is fundamental in the "L"p Brunn-Minkowski theory.