Minkowski addition

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.