Partición de un objeto convexo sin dañar los subconjuntos convexos existentes

Question

$C$ es una figura plana convexa y $C_1,\dots,C_n$ son subconjuntos convexos de $C$ así:

A partición que preserva la convexidad de $C$ es una partición $C=E_1\cup\dots\cup E_N$ , , tal que $N\geq n$ El $E_i$ son figuras convexas disjuntas, y para cada $i=1,\dots,n$ : $C_i\subseteq E_i$ es decir, cada figura existente está contenida en una única figura nueva, así:

Por cada $C,C_1,\dots,C_n$ , dejemos que $F(C,C_1,\dots,C_n)$ sea la cardinalidad más pequeña $N$ de una partición que conserva la convexidad.

Por cada $n$ , dejemos que $G(n)$ sea el mayor valor de $F(C,C_1,\dots,C_n)$ para todas las combinaciones de $C,C_1,\dots,C_n$ .

¿Qué es la $G(n)$ ?

• Obviamente $G(1)=1$ .
• Por el teorema de separación de medio plano, $G(2)=2$ .
• Por la figura anterior, $G(3)\geq 4$ aparentemente no existe ninguna partición que preserve la convexidad con $N=3$ .

¿Qué más se puede decir sobre $G(n)$ ?

Observación: Le pregunté a un pregunta similar en cstheory.SE . Allí, $C$ y todos sus subconjuntos eran rectángulos paralelos a los ejes. En ese caso, encontré un algoritmo que demuestra $G(n)\leq 3n+1$ .

Answer 1

Creo que el número de agujeros no es mayor que dos veces el número de conjuntos $C_i$ .

Obsérvese que los conjuntos $C_i$ puede ampliarse a $E_i$ de manera que todos los agujeros sean convexos (véase la página 8 del artículo de Rom Pinchasi, On the perimeter of $k$ cuerpos convexos disjuntos por pares contenidos en un conjunto convexo en el plano. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf ). Pensemos en $C_i$ como sobre conjuntos ya ampliados.

Cada lado de un agujero está formado por uno de los $C_i$ -s. Llamemos a dos conjuntos $C_i$ y $C_j$ vecinos si forman dos lados adyacentes de algún agujero. Nótese que:

• A cada agujero le corresponden al menos 3 pares de vecinos, ya que cada agujero tiene al menos 3 lados.
• A cada par de vecinos $C_i,C_j$ corresponden como máximo a dos agujeros -ya que todos esos agujeros deben tener un lado colineal con el segmento en el que los límites de $C_i$ y $C_j$ se cruzan.

Por lo tanto, el número de agujeros es como máximo 2/3 del número de pares de vecinos.

La relación "vecino" define un grafo plano con $V=n$ vértices. Fórmula de Euler implica que en un grafo plano (con al menos 3 vértices) el número de aristas está acotado por: $E\leq 3V-6$ . Por lo tanto, el número de agujeros es como máximo $2n-4$ . Por lo tanto, $G(n)\leq 3n-4$ .

El límite inferior da el embaldosado que se muestra en la figura:

En el embaldosado infinito, cada hexágono toca 6 agujeros y cada agujero toca 3 hexágonos, por lo que el número de agujeros es exactamente $2n$ . En el embaldosado finito, el número de agujeros es menor, ya que los agujeros cercanos al límite pueden unirse a sus hexágonos vecinos. Por tanto, el número de agujeros es $2n-o(n)$ y $G(n)\geq 3n-o(n)$ .