= Minkowski addition
{c}
{title2=$A+B$}
{wiki}
= Minkowski sum
{c}
{synonym}
The <Minkowski sum> of <subsets> $A,B$ of a <vector space> collects the result of <vector addition> for every possible pair:
$$
A+B=\{a+b:a\in A,\ b\in B\}=\bigcup_{b\in B}(A+b).
$$
Think of fixing a point $b$ of $B$, making a <translation> of the whole of $A$ by $b$, and then taking the <union> of these copies over every $b\in B$. The points of $B$ specify displacement <vectors>; they need not be the centre of a shape. <Minkowski addition> applies to nonconvex <sets> too. It is different from <set union>: for $A=B=\{0,1\}$ on the real line, $A\cup B=\{0,1\}$ but $A+B=\{0,1,2\}$.
For axis-aligned <rectangles> in the <Euclidean plane>, the coordinate <intervals> add separately:
$$
([0,a]\times[0,b])+([0,c]\times[0,d])=[0,a+c]\times[0,b+d],\qquad a,b,c,d>0.
$$
Every coordinate between $0$ and $a+c$ can be split into one coordinate in $[0,a]$ and another in $[0,c]$, and likewise for the vertical coordinate. Thus a $2\times1$ <rectangle> plus a $1\times2$ <rectangle> gives a $3\times3$ <square> of <area> $9$, although the two input <areas> total only $4$. The <Minkowski sum> adds possible displacements, so its <area> need not be the sum of input <areas>.
For closed <Euclidean disks> $D_r=\{x\in\mathbb R^2:\|x\|\leq r\}$ centred at the origin, the <triangle inequality> gives $D_r+D_s\subseteq D_{r+s}$. Conversely, if $r+s>0$, split any $x\in D_{r+s}$ as $x=rx/(r+s)+sx/(r+s)$. Therefore $D_r+D_s=D_{r+s}$, including the case $r=s=0$. Disks of <radii> $1$ and $2$ give a <disk> of <radius> $3$, with <areas> $\pi,4\pi,9\pi$. For <disks> with centres $u,v$, the resulting centre is $u+v$. These two examples lead to the root-of-<area> comparison in the <Brunn-Minkowski theorem>.
\Image[/minkowski-pairwise-sums-and-root-areas.png]
{title=<Minkowski addition> of two <rectangles> and of two closed <disks>: exact toy shapes, sample displacement arrows, and the square-root-of-<area> comparison}
<Minkowski addition> is commutative and associative because <vector addition> is. Its identity is the <singleton> $\{0\}$, and $A+\varnothing=\varnothing$. For displacement <vectors> $u,v$ and $t>0$, <translations> and <uniform dilations> satisfy
$$
(A+u)+(B+v)=(A+B)+(u+v),\qquad t(A+B)=tA+tB,
$$
where $tA=\{ta:a\in A\}$ uses <scalar multiplication>. A <Minkowski sum> of <convex sets> is <convex>: a <line segment> between $a_1+b_1$ and $a_2+b_2$ is obtained by adding the corresponding points of the <line segments> in $A$ and $B$. Closure requires care; see <sum of two closed sets need not be closed> and <sum of a compact set and a closed set>.
Back to article page
