Minkowski suma de dos discos

Question

Un disco abierto con el radio de $r$ centrada en $\mathbf{p}$ es $D(\mathbf{p}, r)=\{\mathbf{q} \mid d(\mathbf p, \mathbf q) < r\}$, y la suma de Minkowski de dos conjuntos de $A$ e $B$ es $A \oplus B=\{\mathbf p + \mathbf q \mid \mathbf p \in A, \mathbf q \in B \}$.

¿Cómo se puede demostrar que $D(\mathbf{a}, r_a) \oplus D(\mathbf{b}, r_b) = D(\mathbf{a} + \mathbf{b}, r_a + r_b)$?

Intento:

\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}

Y aquí me quedé atrapado. Lo mejor que puedo decir, ahora yo tendría que demostrar que $$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$ son paralelas.

Answer 1

En primer lugar, observa que el $D(p,r)= \{ p+ u \mid u \in D(0,r) \}$, por lo tanto

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

Por lo tanto, es suficiente para mostrar que $D(0,r_a)+D(0,r_b)=D(0,r_a+r_b)$. Pero $$\|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),$$

por lo $D(0,r_a)+D(0,r_b) \subset D(0,r_a+r_b)$. A continuación,

$$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)\},$$

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

Answer 2

Me gustaría seguir la siguiente ruta. Esperemos que sea lo más intuitiva.

Está claro que $$D(b, r_b)\oplus D(0, r_0)=D(b, r_b+r_0)$$ y que $$a+D(b, r)=D(a+b, r).$$ (Aquí se $a+ \text{"some set"}$ denota la traducción). Así que escribir $$D(a, r_a)=a+D(0, r_a).$$ Por lo tanto \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}

Answer 3

Para mostrar $A = B$ es generalmente el más fácil de dividir en dos partes $A \subseteq B$ e $A \supseteq B$.

En primer lugar, si $p \in D(a,r_a)$ e $q \in D(b,r_b)$ entonces $p + q \in D(a+b, r_a+r_b)$. Esto es sencillo con el triángulo de la desigualdad: $$|(p+q)-(a+b)| < |p-a| + |q-b|.$$

En segundo lugar, si $u \in D(a+b, r_a + r_b)$, entonces tenemos que encontrar un punto de $v$ tal que $v \in D(a,r_a)$ e $u-v \in D(b,r_b)$. Un buen candidato es la de dividir la distancia entre el $u$ e $a+b$ en relación $r_a : r_b$, que es (el $-b$ es para ajustar el centro del disco) $$v = \frac{r_a\cdot u + r_b \cdot (a+b)}{r_a + r_b}-b.$$

Ahora, $$|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$$

y

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

Espero que esta ayuda ;-)

Answer 4

Cómo sobre el uso de la desigualdad triangular ?

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

Sugerencia: utilice $a+(b-q)$.

Answer 5

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