Minkowski addition

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 ${\displaystyle \mathbb {R} ^{2}}$, with coordinates

${\displaystyle A=\{(1,0),(0,1),(0,-1)\}}$

and

${\displaystyle B=\{(0,0),(1,1),(1,-1)\}}$

then their Minkowski sum is

${\displaystyle A+B=\{(1,0),(2,1),(2,-1),(0,1),(1,2),(1,0),(0,-1),(1,0),(1,-2)\}}$

which comprises the vertices of a hexagon.

For Minkowski addition, the zero set, {0}, containing only the zero vector, 0, is an identity element: for every subset S of a vector space,

${\displaystyle S+\{0\}=S.}$

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:

${\displaystyle S+\emptyset =\emptyset .}$

In the convex hull of the red set, each blue point is a convex combination of some red points.

Minkowski addition of sets. The sum of the squares Q₁=[0,1]² and Q₂=[1,2]² is the square Q₁+Q₂=[1,3]².

Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition:

• For all non-empty subsets S₁ and S₂ of a real vector space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls:

${\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2}).}$

This result holds more generally for any finite collection of non-empty sets:

${\displaystyle \operatorname {Conv} \left(\sum {S_{n}}\right)=\sum \operatorname {Conv} (S_{n}).}$

In mathematical terminology, the operations of Minkowski summation and of forming convex hulls are commuting operations.[2][3]

If S is a convex set then ${\displaystyle \mu S+\lambda S}$ is also a convex set; furthermore

${\displaystyle \mu S+\lambda S=(\mu +\lambda )S}$

for every ${\displaystyle \mu ,\lambda \geq 0}$. Conversely, if this "distributive property" holds for all non-negative real numbers, ${\displaystyle \mu ,\lambda }$, then the set is convex.[4]

The figure shows an example of a non-convex set for which A + A ⊋ 2A.

An example of a non-convex set such that A + A ≠ 2A

An example in 1 dimension is: B=[1,2]∪[4,5]. It can be easily calculated that 2B=[2,4]∪[8,10] but B+B=[2,4]∪[5,7]∪[8,10], hence again B+B ⊋ 2B.

Minkowski sums act linearly on the perimeter of two-dimensional convex bodies: the perimeter of the sum equals the sum of perimeters. Additionally, if K is (the interior of) a curve of constant width, then the Minkowski sum of K and of its 180° 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.[5]

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.[6]

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

${\displaystyle A+B=\{z\in \mathbb {R} ^{n}\,|\,A\cap (z-B)\neq \emptyset \}.}$

Thus, the essential Minkowski sum is defined by

${\displaystyle A+_{\mathrm {e} }B=\{z\in \mathbb {R} ^{n}\,|\,\mu \left[A\cap (z-B)\right]>0\},}$

where μ denotes the n-dimensional Lebesgue measure. The reason for the term "essential" is the following property of indicator functions: while

${\displaystyle 1_{A\,+\,B}(z)=\sup _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

it can be seen that

${\displaystyle 1_{A\,+_{\mathrm {e} }\,B}(z)=\mathop {\mathrm {ess\,sup} } _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

where "ess sup" denotes the essential supremum.

For K and L compact convex subsets in ${\displaystyle \mathbb {R} ^{n}}$, the Minkowski sum can be described by the support function of the convex sets:

${\displaystyle h_{K+L}=h_{K}+h_{L}.}$

For p ≥ 1, Firey[9] defined the L^p Minkowski sum K+_pL of compact convex sets K and L in ${\displaystyle \mathbb {R} ^{n}}$ containing the origin as

${\displaystyle h_{K+_{p}L}^{p}=h_{K}^{p}+h_{L}^{p}.}$

By the Minkowski inequality, the function h_K+pL 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.

• Blaschke sum
• Brunn–Minkowski theorem, an inequality on the volumes of Minkowksi sums
• Convolution
• Dilation
• Erosion
• Interval arithmetic
• Mixed volume (a.k.a. Quermassintegral or intrinsic volume)
• Parallel curve
• Shapley–Folkman lemma
• Topological vector space#Properties
• Zonotope

• Arrow, Kenneth J.; Hahn, Frank H. (1980). General competitive analysis. Advanced textbooks in economics. 12 (reprint of (1971) San Francisco, CA: Holden-Day, Inc. Mathematical economics texts. 6 ed.). Amsterdam: North-Holland. ISBN 978-0-444-85497-1. MR 0439057.
• Gardner, Richard J. (2002), "The Brunn-Minkowski inequality", Bull. Amer. Math. Soc. (N.S.), 39 (3): 355–405 (electronic), doi:10.1090/S0273-0979-02-00941-2
• Green, Jerry; Heller, Walter P. (1981). "1 Mathematical analysis and convexity with applications to economics". In Arrow, Kenneth Joseph; Intriligator, Michael D (eds.). Handbook of mathematical economics, Volume I. Handbooks in economics. 1. Amsterdam: North-Holland Publishing Co. pp. 15–52. doi:10.1016/S1573-4382(81)01005-9. ISBN 978-0-444-86126-9. MR 0634800.
• Henry Mann (1976), Addition Theorems: The Addition Theorems of Group Theory and Number Theory (Corrected reprint of 1965 Wiley ed.), Huntington, New York: Robert E. Krieger Publishing Company, ISBN 978-0-88275-418-5 – via http://www.krieger-publishing.com/subcats/MathematicsandStatistics/mathematicsandstatistics.html
• Rockafellar, R. Tyrrell (1997). Convex analysis. Princeton landmarks in mathematics (Reprint of the 1979 Princeton mathematical series 28 ed.). Princeton, NJ: Princeton University Press. pp. xviii+451. ISBN 978-0-691-01586-6. MR 1451876.
• Nathanson, Melvyn B. (1996), Additive Number Theory: Inverse Problems and Geometry of Sumsets, GTM, 165, Springer, Zbl 0859.11003.
• Oks, Eduard; Sharir, Micha (2006), "Minkowski Sums of Monotone and General Simple Polygons", Discrete and Computational Geometry, 35 (2): 223–240, doi:10.1007/s00454-005-1206-y.
• Schneider, Rolf (1993), Convex bodies: the Brunn-Minkowski theory, Cambridge: Cambridge University Press.
• Tao, Terence & Vu, Van (2006), Additive Combinatorics, Cambridge University Press.
• Mayer, A.; Zelenyuk, V. (2014). "Aggregation of Malmquist productivity indexes allowing for reallocation of resources". European Journal of Operational Research. 238 (3): 774–785. doi:10.1016/j.ejor.2014.04.003.
• Zelenyuk, V (2015). "Aggregation of scale efficiency". European Journal of Operational Research. 240 (1): 269–277. doi:10.1016/j.ejor.2014.06.038.

• "Minkowski addition", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Howe, Roger (1979), On the tendency toward convexity of the vector sum of sets, Cowles Foundation discussion papers, 538, Cowles Foundation for Research in Economics, Yale University
• Minkowski Sums, in Computational Geometry Algorithms Library
• The Minkowski Sum of Two Triangles and The Minkowski Sum of a Disk and a Polygon by George Beck, The Wolfram Demonstrations Project.
• Minkowski's addition of convex shapes by Alexander Bogomolny: an applet
• Wikibooks:OpenSCAD User Manual/Transformations#minkowski by Marius Kintel: Application