Minkowski addition ($A+B$)

The Minkowski sum of subsets $A,B$ of a vector space collects the result of vector addition for every possible pair: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: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\times 1$ rectangle plus a $1\times 2$ rectangle gives a $3\times 3$ 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:\Vert x\Vert \le 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.

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

Suppose a robot occupies a closed set $R\subseteq {\mathbb{R}}^n$ relative to its chosen reference point, and a closed obstacle occupies $O$. Keep the robot's orientation fixed and allow only translations. At reference position $q$, its occupied set is $q+R$. If touching counts as collision, the forbidden positions in this configuration space are exactlyThe minus sign reflects the robot through its reference origin: solving $q+r=o$ gives $q=o-r$. Thus collision checking for a moving shape becomes checking whether one point lies in a fixed Minkowski sum. Steven M. LaValle derives this translational configuration space construction in Planning Algorithms, section 4.3.2, equation 4.37 and Example 4.13.

For a concrete toy example, take the robot rectangle $R=[0,2]\times [0,1]$ with its reference point at the lower-left corner, and obstacle rectangle $O=[4,6]\times [2,4]$. Their collision region is the rectangleFor example, $q=(3,3/2)$ is forbidden: $q+R=[3,5]\times [3/2,5/2]$ meets $O$ in $[4,5]\times [2,5/2]$, of area $1/2$. At $q=(2,1)$ there is just corner contact, which our convention also forbids. Using $O+R=[4,8]\times [2,5]$ instead would wrongly miss both reference positions. Only when $R=-R$, as for an origin-centred disk, does the reflection leave the robot set unchanged.

The same calculation handles bounded additive uncertainty. If the actual reference position is $q+e$ for any $e\in E$, the union of possible occupied sets is $q+(E+R)$. There exists an allowed error causing contact exactly whenConsequently avoiding this set guarantees avoidance for every $e\in E$ in this model. For $E=[-\epsilon ,\epsilon {]}^2$, the example's forbidden region becomes $[2-\epsilon ,6+\epsilon ]\times [1-\epsilon ,4+\epsilon ]$, with area $(4+2\epsilon )(3+2\epsilon )$. Here $-E=E$ because the error bounds are symmetric; a one-sided error set must still be negated. This is a worst-case geometric bound, not a probability of collision. Rotating the robot requires an orientation-dependent Minkowski sum for each orientation.

In $\mathbb{R}$, the sets $X=\{n:n\ge 1\}$ and $Y=\{-n+1/n:n\ge 1\}$ are closed because their points have no finite accumulation point. Their Minkowski sum contains $1/n\to 0$ but does not contain zero, since $m-n+1/n=0$ has no positive-integer solution. Compactness of one summand is a useful sufficient condition missing from this counterexample.

In Euclidean space, a Minkowski sum of a compact set $X$ and a closed set $Y$ is closed. From any convergent sequence $x_j+y_j$, extract a convergent subsequence of $x_j$ using compactness. The corresponding $y_j$ then converges to the difference of the two limits, which lies in $Y$. If $Y$ is also bounded, the sum is bounded and therefore compact.

Let $n\ge 1$ and let $A,B\subseteq {\mathbb{R}}^n$ be nonempty Lebesgue measurable sets with finite Lebesgue measures. Assume that $A+B$ is also a Lebesgue measurable set; its measure may be infinite. ThenHere ${\lambda }_n$ denotes $n$-dimensional Lebesgue measure in Euclidean space. Nonempty compact sets and nonempty open sets of finite measure satisfy the measurability assumptions. Measurability of arbitrary summands alone does not guarantee measurability of their Minkowski sum. The theorem does not require convexity. See R. J. Gardner, The Brunn-Minkowski Inequality (2002), Theorem 4.1 and the following remarks.

The $n$th root converts a volume into a quantity that scales like a length: uniform dilation gives ${\lambda }_n(tA{)}^{1/n}=t{\lambda }_n(A{)}^{1/n}$ for $t>0$. In the Euclidean plane the theorem compares square roots of areas, not the areas themselves. For the two rectangles above it reads $3\ge \sqrt{2}+\sqrt{2}=2\sqrt{2}$. Equivalently their sum has area $9\ge 8$. For the two disks, it reads $3\sqrt{\pi }=\sqrt{\pi }+2\sqrt{\pi }$, an equality. These are exact geometric examples, not measured data.

Applying the theorem to the scaled sets gives, whenever that sum is a Lebesgue measurable set,For convex bodies, this means the root-volume of the interpolated shape lies above the straight line between the input root-volumes. In fact $t\mapsto {\lambda }_n((1-t)A+tB{)}^{1/n}$ is a concave function on $[0,1]$: convexity gives $sA+tA=(s+t)A$ for $s,t\ge 0$, so interpolating two intermediate shapes gives another intermediate shape and the same inequality applies. The beauty is that no particular boundary shape appears in the bound: possible pointwise displacements force a minimum amount of space.

For convex bodies $A,B$, equality holds exactly when they are homothetic convex bodies, meaning $B=v+sA$ for some vector $v$ and $s>0$. This equality qualification is part of the Brunn-Minkowski theorem for convex bodies. ^[ref] For positive-sided axis-aligned rectangles, the comparison can be checked directly:Equality requires $ad=bc$: the rectangles must have the same aspect ratio. Our $2\times 1$ and $1\times 2$ rectangles do not. All positive-radius disks are homothetic convex bodies, explaining their equality.

Do not apply that equality criterion without its hypotheses. If $A=\{a\}$, its Lebesgue measure is zero and $A+B$ is a translation of $B$, so equality holds even for nonconvex $B$. Also, changing a summand on a null set can change the measure of its Minkowski sum: in one dimension, $A=[0,1]\cup \{3\}$ and $B=[0,1]$ both have measure $1$, but $A+B=[0,2]\cup [3,4]$ has measure $3$. Removing the single extra point restores equality with sum measure $2$. Thus merely being equal almost everywhere to homothetic convex bodies is not a sufficient equality test for arbitrary sets.

The Brunn-Minkowski theorem also bounds the collision-region volume: for positive-volume compact sets $O,R$, reflection preserves Lebesgue measure, so ${\lambda }_n(O+(-R){)}^{1/n}\ge {\lambda }_n(O{)}^{1/n}+{\lambda }_n(R{)}^{1/n}$. In the toy collision example this gives area at least $(2+\sqrt{2}{)}^2=6+4\sqrt{2}\approx 11.657$, compared with the exact area $12$. A lower bound alone does not identify safe reference positions; the actual Minkowski sum supplies those.