4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Electro Jul 16 '13 at 13:10
  • $\begingroup$ Minkowski sum is not defined in any metric space, a structure of vector space is needed. $\endgroup$ – Seirios Jul 16 '13 at 13:15
  • $\begingroup$ Whoops, I meant vector space equipped with a metric. $\endgroup$ – Electro Jul 16 '13 at 13:18
  • $\begingroup$ You can easily find a counterexample using SNCF metric: en.wikipedia.org/wiki/Metric_space#Examples_of_metric_spaces $\endgroup$ – Seirios Jul 16 '13 at 19:50
2
$\begingroup$

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 ;-)

$\endgroup$
1
$\begingroup$

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{equation}\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} \end{equation}

$\endgroup$
0
$\begingroup$

How about using triangular inequality ?

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

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

$\endgroup$
0
$\begingroup$

$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)$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.