# Minkowski sum of two disks

An open disk with radius $r$ centered at $\mathbf{p}$ is $D(\mathbf{p}, r)=\{\mathbf{q} \mid d(\mathbf p, \mathbf q) < r\}$, and the Minkowski sum of two sets $A$ and $B$ is $A \oplus B=\{\mathbf p + \mathbf q \mid \mathbf p \in A, \mathbf q \in B \}$.

How can you show that $D(\mathbf{a}, r_a) \oplus D(\mathbf{b}, r_b) = D(\mathbf{a} + \mathbf{b}, r_a + r_b)$?

Attempt:

\begin{align} D(\mathbf{a}, r_a) \oplus D(\mathbf{b}, r_b) &= \{\mathbf p + \mathbf q \mid \mathbf p \in D(\mathbf{a}, r_a), \mathbf q \in D(\mathbf{b}, r_b) \} \\&= \{\mathbf p + \mathbf q \mid \mathbf p \in \{\mathbf{x} \mid d(\mathbf a, \mathbf x) < r_a\}, \mathbf q \in \{\mathbf{y} \mid d(\mathbf b, \mathbf y) < r_b\} \\&= \{\mathbf p + \mathbf q \mid d(\mathbf a, \mathbf p) < r_a, d(\mathbf b, \mathbf q) < r_b \} \end{align}

And here I got stuck. As best as I can tell, now I would need to prove that $$d(\mathbf a, \mathbf p) < r_a, d(\mathbf b, \mathbf q) < r_b \iff d(\mathbf a + \mathbf b, \mathbf p + \mathbf q) < r_a + r_b$$ but this seems false to me. I tried adding the two inequalities together, but that doesn't seem to give me that condition unless $\mathbf a - \mathbf p$ and $\mathbf b - \mathbf q$ are parallel.

First, notice that $D(p,r)= \{ p+ u \mid u \in D(0,r) \}$, hence

$$D(a,r_a)+D(b,r_b)= \{ a+b+u+v \mid u \in D(0,r_a), v \in D(0,r_b)\}.$$

Therefore, it is sufficient to show that $D(0,r_a)+D(0,r_b)=D(0,r_a+r_b)$. But $$\|u+v\| \leq \|u \| + \|v\| <r_a+r_b, \ \text{if} \ u \in D(0,r_a) \ \text{and} \ v \in D(0,r_b),$$

so $D(0,r_a)+D(0,r_b) \subset D(0,r_a+r_b)$. Then,

$$D(0,r_a+r_b)= \{ (r_a+r_b)u \mid u \in D(0,1) \}= \{\underset{\in D(0,r_a)}{\underbrace{r_au}} + \underset{\in D(0,r_b)}{\underbrace{r_bu}} \mid u \in D(0,1)\},$$

so $D(0,r_a+r_b) \subset D(0,r_a)+D(0,r_b)$.

• Thanks. I don't suppose it is to possible to generalize this proof to metric spaces, rather than just normed vector spaces? I've had a go at it, but I didn't get very far. – Electro Jul 16 '13 at 13:10
• Minkowski sum is not defined in any metric space, a structure of vector space is needed. – Seirios Jul 16 '13 at 13:15
• Whoops, I meant vector space equipped with a metric. – Electro Jul 16 '13 at 13:18
• You can easily find a counterexample using SNCF metric: en.wikipedia.org/wiki/Metric_space#Examples_of_metric_spaces – Seirios Jul 16 '13 at 19:50

To show $A = B$ it is usually the easiest to split into two parts $A \subseteq B$ and $A \supseteq B$.

First, if $p \in D(a,r_a)$ and $q \in D(b,r_b)$ then $p + q \in D(a+b, r_a+r_b)$. This is simple using the triangle inequality: $$|(p+q)-(a+b)| < |p-a| + |q-b|.$$

Secondly, if $u \in D(a+b, r_a + r_b)$, then we need to find a point $v$ such that $v \in D(a,r_a)$ and $u-v \in D(b,r_b)$. A good candidate is to split the distance between $u$ and $a+b$ in ratio $r_a : r_b$, that is (the $-b$ is to adjust for the center of the disk) $$v = \frac{r_a\cdot u + r_b \cdot (a+b)}{r_a + r_b}-b.$$

Now, $$|v-a| = \left|\frac{r_a\cdot u + r_b \cdot (a+b)}{r_a + r_b}-b-a\right| = r_a\frac{|u-(a+b)|}{r_a+r_b}\leq r_a$$

and

$$|(u-v)-b| = \left|\frac{r_b\cdot u -r_b\cdot(a+b)}{r_a + r_b}+b-b\right| = r_b\frac{|u-(a+b)|}{r_a+r_b}\leq r_b.$$

I hope this helps ;-)

I would take the following route. Hopefully it is more intuitive.

It is clear that $$D(b, r_b)\oplus D(0, r_0)=D(b, r_b+r_0)$$ and that $$a+D(b, r)=D(a+b, r).$$ (Here $a+ \text{"some set"}$ denotes translation). So we write $$D(a, r_a)=a+D(0, r_a).$$ Therefore $$\begin{split} D(a, r_a)\oplus D(b, r_b) &= [a+D(0, r_a)]\oplus D(b, r_b) \\ &=a+[D(0, r_a)\oplus D(b, r_b)]\\ &=a+ D(b, r_a+r_b) \\ &= D(a+b, r_a+r_b). \end{split}$$

How about using triangular inequality ?

$$d(u,w) \leq d(u,v) + d(v, w)$$

Hint: use $a+(b-q)$.

$D(\mathbf{a},r_a)\oplus D(\mathbf{b},r_b)=\{\mathbf{p}+\mathbf{q}|d(\mathbf{a},\mathbf{p})<r_a,d(\mathbf{b},\mathbf{q})<r_b\}$

$D(\mathbf{a}+\mathbf{b},r_a+r_b)=\{\mathbf{s}|d(\mathbf{a}+\mathbf{b},\mathbf{s})<r_a+r_b\}$

$\forall \mathbf{p} \in D(\mathbf{a},r_a) \forall \mathbf{q}\in D(\mathbf{b},r_b) \exists \mathbf{s}=\mathbf{p}+\mathbf{q} \in D(\mathbf{a}+\mathbf{b},r_a+r_b)$ $d(\mathbf{a},\mathbf{p})<r_a, d(\mathbf{b},\mathbf{q})<r_b \Rightarrow d(\mathbf{a+b},\mathbf{p+q})=d(\mathbf{a+b-q},\mathbf{p}) \leq d(\mathbf{a},\mathbf{p})+d(\mathbf{a},\mathbf{a+b-q})=d(\mathbf{a},\mathbf{p})+d(\mathbf{q},\mathbf{b})<r_a+r_b$

$\forall \mathbf{s} \in D(\mathbf{a}+\mathbf{b},r_a+r_b) \exists \mathbf{p}\in D(\mathbf{a},r_a), \mathbf{q}\in D(\mathbf{b},r_b), \mathbf{s=p+q}$ $\mathbf{p}=\mathbf{a}+(\mathbf{s-(a+b)}) r_a/(r_a+r_b)$, $\mathbf{q}=\mathbf{b}+(\mathbf{s-(a+b)}) r_b/(r_a+r_b)$

• If you could add some words that would be nice. – user1337 Jul 16 '13 at 10:20