In geometry, the Minkowski sum 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:

${\displaystyle A+B=\{\mathbf {a} +\mathbf {b} \,|\,\mathbf {a} \in A,\ \mathbf {b} \in B\}}$

The Minkowski difference (also Minkowski subtraction, Minkowski decomposition, or geometric difference)^[1] is the corresponding inverse, where ${\displaystyle (A-B)}$ produces a set that could be summed with B to recover A. This is defined as the complement of the Minkowski sum of the complement of A with the reflection of B about the origin.^[2]

${\displaystyle -B=\{\mathbf {-b} \,|\,\mathbf {b} \in B\}}$

${\displaystyle A-B=(A^{\complement }+(-B))^{\complement }}$

This definition allows a symmetrical relationship between the Minkowski sum and difference. Note that alternately taking the sum and difference with B is not necessarily equivalent. The sum can fill gaps which the difference may not re-open, and the difference can erase small islands which the sum cannot recreate from nothing.

${\displaystyle (A-B)+B\subseteq A}$

${\displaystyle (A+B)-B\supseteq A}$

${\displaystyle A-B=(A^{\complement }+(-B))^{\complement }}$

${\displaystyle A+B=(A^{\complement }-(-B))^{\complement }}$

In 2D image processing the Minkowski sum and difference are known as dilation and erosion.

An alternative definition of the Minkowski difference is sometimes used for computing intersection of convex shapes.^[3] This is not equivalent to the previous definition, and is not an inverse of the sum operation. Instead it replaces the vector addition of the Minkowski sum with a vector subtraction. If the two convex shapes intersect, the resulting set will contain the origin.

${\displaystyle A-B=\{\mathbf {a} -\mathbf {b} \,|\,\mathbf {a} \in A,\ \mathbf {b} \in B\}=A+(-B)}$

The concept is named for Hermann Minkowski.

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 and the three interior points of that hexagon having integral coordinates.

For Minkowski addition, the zero set, ${\displaystyle \{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 .}$

For another example, consider the Minkowski sums of open or closed balls in the field ${\displaystyle \mathbb {K} ,}$ which is either the real numbers ${\displaystyle \mathbb {R} }$ or complex numbers ${\displaystyle \mathbb {C} .}$ If ${\displaystyle B_{r}:=\{s\in \mathbb {K}$ :|s|\leq r\}} is the closed ball of radius ${\displaystyle r\in [0,\infty ]}$ centered at ${\displaystyle 0}$ in ${\displaystyle \mathbb {K} }$ then for any ${\displaystyle r,s\in [0,\infty ],}$ ${\displaystyle B_{r}+B_{s}=B_{r+s}}$ and also ${\displaystyle cB_{r}=B_{|c|r}}$ will hold for any scalar ${\displaystyle c\in \mathbb {K} }$ such that the product ${\displaystyle |c|r}$ is defined (which happens when ${\displaystyle c\neq 0}$ or ${\displaystyle r\neq \infty }$). If ${\displaystyle r,s,}$ and ${\displaystyle c}$ are all non-zero then the same equalities would still hold had ${\displaystyle B_{r}}$ been defined to be the open ball, rather than the closed ball, centered at ${\displaystyle 0}$ (the non-zero assumption is needed because the open ball of radius ${\displaystyle 0}$ 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 any other set will be an open subset.

If ${\displaystyle G=\{(x,1/x):0\neq x\in \mathbb {R} \}}$ is the graph of ${\displaystyle f(x)={\frac {1}{x}}}$ and if and ${\displaystyle Y=\{0\}\times \mathbb {R} }$ is the ${\displaystyle y}$-axis in ${\displaystyle X=\mathbb {R} ^{2}}$ then the Minkowski sum of these two closed subsets of the plane is the open set ${\displaystyle G+Y=\{(x,y)\in \mathbb {R} ^{2}:x\neq 0\}=\mathbb {R} ^{2}\setminus Y}$ consisting of everything other than the ${\displaystyle y}$-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.

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

For all non-empty subsets ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$ 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:

${\textstyle \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.^[4][5]

If ${\displaystyle 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.^[6]

The figure to the right shows an example of a non-convex set for which ${\displaystyle A+A\subsetneq 2A.}$

An example in ${\displaystyle 1}$ dimension is: ${\displaystyle B=[1,2]\cup [4,5].}$ It can be easily calculated that ${\displaystyle 2B=[2,4]\cup [8,10]}$ but ${\displaystyle B+B=[2,4]\cup [5,7]\cup [8,10],}$ hence again ${\displaystyle B+B\subsetneq 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 ${\displaystyle K}$ is (the interior of) a curve of constant width, then the Minkowski sum of ${\displaystyle K}$ and of its ${\displaystyle 180^{\circ }}$ 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.^[7]

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.^[8]

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=\left\{z\in \mathbb {R} ^{n}\,|\,A\cap (z-B)\neq \emptyset \right\}.}$

Thus, the essential Minkowski sum is defined by

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

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^[11] defined the L^p Minkowski sum K +_p L 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 – Polytope combining two smaller polytopes
• Brunn–Minkowski theorem – theorem in geometryPages displaying wikidata descriptions as a fallback, an inequality on the volumes of Minkowski sums
• Convolution – Integral expressing the amount of overlap of one function as it is shifted over another
• Dilation – Operation in mathematical morphology
• Erosion – Basic operation in mathematical morphology
• Interval arithmetic – Method for bounding the errors of numerical computations
• Mixed volume (a.k.a. Quermassintegral or intrinsic volume)
• Parallel curve
• Shapley–Folkman lemma – Sums of sets of vectors are nearly convex
• Sumset – set of all possible sums of an element of set A and an element of set BPages displaying wikidata descriptions as a fallback
• Topological vector space#Properties – Vector space with a notion of nearness
• Zonotope – Convex polyhedron projected from hypercubePages displaying short descriptions of redirect targets