¿La unión de dos conjuntos convexos es convexa?

Question

Sean A y B subconjuntos convexos de $\Bbb R^n$. La unión de A y B es el conjunto de todos los $\vec x$ tales que $\vec x$ se encuentra en un segmento de línea con un extremo en A y el otro en B. Me pregunto cómo demostrar que la unión de A y B es un conjunto convexo.

Answer 1

Sean $p_1$ y $p_2$ pertenecientes al join de $A$ y $B.$ $$\text {Sea } q=x p_1+(1-x)p_2 \text { con } x\in [0,1].$$ Existen $a_1\in A$ y $b_1\in B$ y $r_1\in [0,1]$ con $$p_1=r_1 a_1+(1-r_1)b_1.$$ Existen $a_2\in A$ y $b_2$ en $B$ y $r_2\in [0,1]$ con $$p_2=r_2 a_2+(1-r_2)b_2.$$ Dado que $A$ y $B$ son convexos, tenemos $$A\supset \{c a_1+(1-c)a_2 :c\in [0,1]\}$$ $$\text {y }\quad B\supset \{db_1+(1-d)b_2:d\in [0,1]\}.$$ Entonces si podemos encontrar $c,d,e\in [0,1]$ tales que $$\bullet \;q=e[c a_1+(1-c)a_2]+(1-e)[d b_1+(1-d)b_2],$$ entonces $q$ pertenece al join de $A$ y $B.$ $$\text {Ahora }\; q=x p_1+(1-x)p_2=x[r_1a_1+(1-r_1)b_1]+(1-x)[r_2a_2+(1-r_2)b_2].$$ Dejo a ustedes mostrar que existen $c,d,e\in [0,1]$ tales que $$x r_1=e c.$$ $$(1-x)r_2=e(1-c).$$ $$x(1-r_1)b_1=(1-e)d.$$ $$(1-x)(1-r_2)=(1-e)(1-d).$$ Entonces la ecuación $\bullet$ se cumple.

Answer 2

Utilizando la definición del conjunto convexo, para probar que dados dos puntos en la unión de dos conjuntos, el segmento de línea que conecta los dos puntos dados se encuentra completamente dentro de la unión.

Tienes seis casos:

1. Ambos puntos dados están en el conjunto A;
2. Ambos puntos dados están en el conjunto B;
3. Un punto está en el conjunto A y el otro punto está en el conjunto B
4. Un punto está en el conjunto A, el otro punto está en la unión pero no en el conjunto A o B;
5. Un punto está en el conjunto B, el otro punto está en la unión pero no en A ni en B;
6. Ambos puntos están en la unión pero no en A ni en B.

Los casos 1 y 2 son verdaderos según la definición del conjunto convexo. El caso 3 es verdadero debido a la definición de la unión de dos conjuntos. Para el caso 4, sea a el punto en el conjunto A, sea otro punto e en la unión pero no en el conjunto A o B, entonces sabemos que hay un punto u en el conjunto A y un punto v en el conjunto B, de modo que e está en el segmento de línea que conecta u y v. Ahora traza una línea desde a hasta u, extiende la línea av en ambos extremos para intersectar la frontera del conjunto A en p y q. Luego traza un segmento de línea desde p hasta e y desde q hasta e, tenemos un triángulo con vértices en p, q, e. Cualquier punto o en el segmento ae puede trazar una línea desde b hasta o y extenderla para cortar el segmento de línea pg en el conjunto A. Por lo tanto, el segmento de línea ae está en la unión.

El caso 5 es similar al caso 4.

El caso 6 es un caso interesante. Nombremos a estos dos puntos como o y p. Sabemos que hay un punto i en A y un punto j en B, tal que o está en el segmento de línea ij. Sabemos que hay un punto k en A y un punto l en B, tal que p está en el segmento de línea kl. Si los segmentos de línea ij y kl no se intersectan, entonces trazamos la línea ik en el conjunto A y el segmento de línea jl en el conjunto B. Cuatro segmentos de línea forman un cuadrilátero. Cualquier punto dentro del cuadrilátero está en algún segmento de línea con un punto en ik y otro punto en jl. Entonces, el segmento de línea op está en la unión.

Si los segmentos ij y kl se intersectan, entonces trazamos el segmento de línea il y jk, que no se intersectan entre sí. ij y kl son las líneas diagonales del cuadrilátero formado por ik, il, jl, ki. Claramente, cualquier punto en el segmento de línea op está dentro de este cuadrilátero. Cualquier punto en op puede estar en el segmento de línea conectando un punto en ik y un punto en jl.

(dibujar una imagen ayudaría)

Answer 3

Básicamente, esto se reduce al siguiente ejercicio de álgebra. Tomamos combinaciones convexas para representar cualquier $x$ en la unión: $$x_1=\alpha_1 a_1 + \beta_1 b_1$$ $$x_2=\alpha_2 a_2 + \beta_2 b_2$$ y luego hacemos una combinación convexa de esos: $$\kappa x_1+\gamma x_2=\kappa \alpha_1 a_1 + \kappa \beta_1 b_1 + \gamma \alpha_2 a_2 + \gamma \beta_2.$$ Luego, necesitamos representar esto como: $$\kappa \alpha_1 a_1 + \kappa \beta_1 b_1 + \gamma \alpha_2 a_2 + \gamma \beta_2=\alpha(\kappa_1 a_1 + \gamma_1 a_2)+\beta(\kappa_2 b_1 + \gamma_2 b_2)$$ para mostrar que cualquier suma convexa de dos puntos en nuestra unión se puede escribir como una suma convexa de dos puntos $\kappa_1 a_1 + \gamma_1 a_2\in A$ y $\kappa_2 b_1 + \gamma_2 b_2$. Entonces, necesitamos $$\alpha \kappa_1 = \alpha_1 \kappa$$ $$\alpha \gamma_1 = \alpha_2\gamma$$ $$\beta \kappa_2= \beta_1\kappa$$ $$\beta \gamma_2= \beta_2\gamma$$ que se ve bastante horrible, donde las variables de la izquierda son las que necesitamos y las de la derecha están fijas. Para aclarar esto, debo notar cómo he nombrado las variables: usé $\alpha$ y $\beta$ para indicar cualquier suma convexa "cruzando" del conjunto $A$ al conjunto $B$. Usé $\kappa$ y $\gamma$ para indicar sumas convexas dentro de $A$ o $B$ respectivamente, o de alguna manera "en esta dirección". Los subíndices indican a cuál de una suma convexa anidada pertenecen los índices, sin subíndice para la suma exterior. Se toma que $\alpha_i+\beta_i=1$ y $\kappa_i+\gamma_i=1$.

Sin embargo, podemos sumar las dos primeras ecuaciones para obtener una ecuación y las dos últimas ecuaciones para obtener otra, notando que $\kappa_1+\gamma_1=1$ y $\kappa_2+\gamma_2=1$. Esto da $$\alpha=\alpha_1\kappa + \alpha_2\gamma$$ $$\beta=\beta_1\kappa + \beta_2\gamma.$$ Fácilmente, luego dividimos las dos primeras ecuaciones por $\alpha$ para obtener $$\kappa_1=\frac{\alpha_1\kappa}{\alpha_1\kappa + \alpha_2\gamma}$$ $$\gamma_1=\frac{\alpha_2\gamma}{\alpha_1\kappa + \alpha_2\gamma}$$ y similarmente $$\kappa_2=\frac{\beta_1\kappa}{\beta_1\kappa + \beta_2\gamma}$$ $$\gamma_2=\frac{\beta_2\gamma}{\beta_1\kappa + \beta_2\gamma}.$$ Puedes convencerte de que cada grupo de estas ecuaciones en realidad forma los coeficientes de una combinación convexa (es decir, son no negativos y suman a $1$) y puedes verificar que satisfacen la igualdad deseada. Esta álgebra básicamente dice que un tetraedro es la unión de un par de aristas disjuntas, y que esto es suficiente para la convexidad.

Answer 4

Un enfoque ligeramente más conceptual para "la unión de dos segmentos es el tetraedro de sus extremos" es mostrar primero que la unión es asociativa (lo que significa manipular tres vértices en lugar de cuatro, por lo que es más fácil), y que la envoltura convexa de $s \cup \{a\}$ es la unión de ${a}$ y la envoltura convexa de $s$ (una vez más, solo dos combinaciones para tener en cuenta). Luego

$$\begin{eqnarray} \mathrm{Join}([a, b], [c, d]) & = & \mathrm{Join}(\mathrm{Join}(\{a\}, \{b\}), \mathrm{Hull} \{c, d\}) \\ & = & \mathrm{Join}(\{a\}, \mathrm{Join}(\{b\}, \mathrm{Hull}\{c, d\})) \\ & = & \mathrm{Join}(\{a\}, \mathrm{Hull}\{b, c, d\}) \\ & = & \mathrm{Hull}\{a, b, c, d\} \end{eqnarray}$$