Particionamiento $\mathbb{R}^d$ con dos conjuntos convexos

Question

El problema de rompecabezas es:

Encontrar dos conjuntos convexos en el espacio Euclidiano, $A, B\subseteq\mathbb{R}^d$, de tal manera que el número de componentes conectados de $\mathbb{R}^d\setminus (A\cup B)$ es el máximo alcanzable.

Estoy interesado en las dos pruebas de la parte superior-límites y establece que lograr el-límite superior.

He encontrado dos conjuntos convexos en $\mathbb{R}^2$ que cree $5$ este tipo de componentes, y la conjetura de que el máximo en $d$-dimensiones de la es $2d+1$.

Ejemplo:

las líneas $x=0$, $y=0$ en $\mathbb{R}^2$ rendimiento $4$ de los componentes conectados, cada uno de los cuadrantes.

Answer 1

Aquí está cómo obtener $2d+1$ componentes:

Para $d=1$, vamos a $A_1=[-1,0)$ $B_1=(0,1]$

Supongamos que hemos encontrado $A_{d-1}$, $B_{d-1}$ que producen $2d-1$ componentes en $d-1$ dimensiones. Deje $$\begin{align}A_d&=\{\,(x_1,\ldots,x_d):0<x_d\le1\,\}\cup A_{d-1}\times\{0\},\\B_d&=\{\,(x_1,\ldots,x_d):-1\le x_d<0\,\}\cup B_{d-1}\times\{0\}.\end{align}$$ A continuación, $\mathbb R^d\setminus(A_d\cup B_d)$ tiene dos componentes "$x_d>1$" y "$x_d<-1$" así como el $2d-1$ componentes de las dimensiones inferiores de la solución en el "$x_d=0$ hyperplane.

---

Podemos mostrar que $2d+1$ es óptimo por inducción en $d$: Supongamos que tenemos para algunos $d\ge 2$ dos subconjuntos convexos $A,B\subseteq \mathbb R^d$ tal que $\mathbb R^d\setminus (A\cup B)$ $m$ componentes $C_1,\ldots,C_m$. Vamos a exponer un hyperplane $H\cong \mathbb R^{d-1}$ tal que al menos el $m-2$ de la $C_i$ se cruzan $H$. A continuación, $A\cap H$ $B\cap H$ son convexas subconjuntos tales que el complemento de su unión tiene al menos $m-2$ componentes.

Lema. Deje $U$ libre halfspace con límite de $H$ y tales que $U\cap B=\emptyset$, $H\cap (A\setminus B)\ne\emptyset$. A continuación, entre las $C_i$ $C_i\cap U\ne\emptyset$ hay un con $C_i\cap H=\emptyset$.

Prueba. Deje $a\in H\cap (A\setminus B)$ $c,c'\in U$ pertenecen a los distintos componentes del complemento. Luego, en el avión $\pi$ determinado por $a,c,c'$ tenemos la situación de la siguiente imagen (donde la línea negra es $H\cap \pi$):

Con el fin de evitar que $c,c'$ están conectados a través de la ruta verde, debe ser un punto de $a'\in A$ sobre la parte superior de la línea de segmento (en paralelo a $H$). A continuación, $A\cap \pi$ está confinado al área sombreada de azul. Vemos que los componentes de $c$ $c'$ ambos se cruzan $H\cap \pi$ en un intervalo. Pero en la mayoría de uno de estos puede ser $\subseteq B$ debido a que están separados por $a\notin B$. $_\square$

Corolario. Si $H$ es un hyperplane tal que $A$ está contenida en un y $B$ contenida en el otro cerrado halfspace determinada por $H$ $H$ intersecta al menos $m-2$ de la $C_i$.

Prueba. El lema como se indica y con $A,B$ intercambiado muestra que cada uno de los dos halfspaces puede contener más de un componente que no se intersectan $H$. $_\square$

La proposición. Deje $\ell$ ser una línea que interseca al menos tres de las $C_i$. A continuación, un hyperplane intersección de al menos $m-2$ de la $C_i$ existe.

Prueba. Deje $c,c',c''$ puntos $\ell$ pertenecientes a diferentes $C_i$,$c'$$c$$c''$. Luego wlog. la línea abierta segmento de $cc'$ intersecta $A$ (al menos) un punto de $a$ y el segmento de la línea de $c'c'$ intersecta $B$ (al menos) un punto de $b$.

Existe halfspace $U_A$$c\in\partial U_A$$A\subseteq \overline{U_A}$. De forma similar, tenemos $U_A'$$c'\in\partial U_A'$$A\subseteq \overline{U_A'}$; y $U_B'$$c'\in\partial U_B'$$B\subseteq \overline{U_B'}$; y $U_B''$$c''\in\partial U_B''$$B\subseteq \overline{U_B''}$.

Caso 1: Tenemos $\ell\subset \partial U_A'$. Suponga $B$ intersecta $U_A'$. A continuación, en el plano a través de la $\ell$ y un punto de $b'\in B\cap U_A'$ tenemos esta situación:

Aquí $A$ se limita a la zona azul y $B$ hasta el azul más rojo de la zona, por lo que $c$ $c'$ están conectados. Llegamos a la conclusión de que $B\cap U_A'=\emptyset$. Pero luego nos encontramos en la situación de la conclusión, y se hace.

Caso 2: Tenemos $\ell\subset\partial U_B'$. Este es simétrica a la del caso 1.

Caso 3: Tenemos que $\partial U_A', \partial U_B'$ se cruzan $\ell$ transversalmente y son iguales. A continuación, $A$ $B$ debe ser posterior a la espalda, es decir, estamos una vez más en la situación de los corolario.

Caso 4: Tenemos que $\partial U_A', \partial U_B'$ se cruzan $\ell$ transversalmente y son diferentes. Esto implica que $U_A'\cap U_B'\ne \emptyset$. Podemos suponer también que el $\partial U_A$ $\partial U_B''$ se cruzan $\ell $ transversalmente ya que de lo contrario podríamos haber como bien $U_A'=U_A$ o $U_B=U_B''$. Entonces, en el plano de la $\pi$ a través de $\ell$ y un punto de $\in U_A'\cap U_B'$ estamos en esta situación:

[a continuación]

Answer 2

Lo siento, me he dado cuenta de que nunca me puso el ejemplo de 5 componentes conectados. Aquí es en la notación con respecto a $\mathbb{R}\times\mathbb{R}$:

$$ A=\big((-\infty,\infty)\times (0,1]\big)\bigcup \big(\{0\}\times\{0\}\big)$$

$$B=\big((-\infty,\infty)\times[-1,0)\big)\bigcup \big(\{1\}\times\{0\}\big)$$

La unión formas de dos bandas paralelas separadas por una línea con dos puntos en ella. Así que en términos del problema de los componentes conectados son los exteriores de ambos lados de las tiras, los dos rayos en el interior y en el segmento $(0,1)\times\{0\}$.