Minkowski addition

In mathematics, the sumset of two subsets $A$ and $B$ of an (additive) abelian group is formed by adding each element of $A$ to each element of $B$ : $A+B=\{a+b\mid a\in A,\ b\in B\}.$

In geometry, the Minkowski sum of two subsets $A$ and $B$ of a Euclidean space is the set of the points whose position vectors form the sumset of the position vectors of $A$ and $B$ . The Minkowski sum depends on the choice of an origin in the Euclidean space. As a change of origin amounts to translate the Minkowski sum, the Minkowski sum is defined up to a translation, and its shape and orientation are well defined.

The Minkowski difference (also Minkowski subtraction, Minkowski decomposition, or geometric difference) is the corresponding inverse, where ${\textstyle (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.

${\begin{aligned}-B&=\{\mathbf {-b} \,|\,\mathbf {b} \in B\}\\A-B&=(A^{\complement }+(-B))^{\complement }\end{aligned}}$

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.

${\begin{aligned}(A-B)+B&\subseteq A\\(A+B)-B&\supseteq A\\A-B&=(A^{\complement }+(-B))^{\complement }\\A+B&=(A^{\complement }-(-B))^{\complement }\\\end{aligned}}$

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

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

The concept is named for Hermann Minkowski.