Empaquetar eficientemente un triángulo equilátero hacia arriba con triángulos equiláteros hacia abajo

Question

Considere el problema de empaquetar eficientemente un triángulo equilátero unitario apuntando hacia arriba con triángulos equiláteros apuntando hacia abajo, donde "eficientemente" significa que hay poco área desperdiciada en relación con el perímetro de los triángulos utilizados en el empaque. La $n^{th}$ generación del triángulo de Sierpinski

empaqueta todo excepto $(3/4)^n$ del área del triángulo grande hacia arriba con triángulos hacia abajo, a costa de un perímetro neto de $\asymp (3/2)^n$. Por lo tanto, si dejamos que $\varepsilon$ denote el área no empacada, entonces el perímetro de los triángulos utilizados en esta construcción es $\gg \varepsilon^{-\alpha}$ para $\alpha = \frac{\log (3/2)}{\log (4/3)} = 1.409\dots$.

Mi pregunta es si este fenómeno es general: dados cualquier colección finita de triángulos equiláteros hacia abajo en el triángulo equilátero unitario hacia arriba que es un empaque (es decir, interiores son disjuntos) y deja un área de $\varepsilon$ no cubierta, ¿es cierto que el perímetro total de los triángulos utilizados es de la forma $\gg \varepsilon^{-c}$ para alguna constante absoluta $c>0$? Para mi aplicación no necesito un exponente óptimo $c$. [EDIT: como se señala en respuestas, para que la respuesta sea positive para $\varepsilon$ grande, el triángulo exterior también debería contar hacia el perímetro total.]

Pienso que puedo establecer un límite de la forma $\gg \log \frac{1}{\varepsilon}$ (en términos generales, argumentando que cada escala díadica de triángulos entre $\varepsilon$ y $1$ tiene que contribuir una cantidad constante de perímetro, de lo contrario habrá demasiado desperdicio), pero para mi aplicación realmente necesito un límite inferior polinómico (o tal vez $\exp( (\log\log \frac{1}{\varepsilon})^C )$ para una gran constante absoluta $C$ podría ser suficiente). Me parece intuitivamente plausible que el empaque de Sierpinski es el mejor empaque para este propósito, y que los triángulos más pequeños realmente tienen que contribuir más que una cantidad constante de perímetro, pero me resulta sorprendentemente difícil encontrar un argumento riguroso. Quizás este tipo de pregunta ya ha sido estudiada en la literatura?

Se puede interpretar esta pregunta como una forma exótica de una desigualdad isoperimétrica, donde se requiere que la región de interés sea una unión disjunta de triángulos equiláteros apuntando hacia abajo en un triángulo equilátero apuntando hacia arriba fijo, pero esta pregunta parece bastante ortogonal a la teoría usual de desigualdades isoperimétricas, por lo que no creo que esta interpretación sea particularmente fructífera.

Answer 1

De acuerdo, publicando entonces.

Prefiero pensar en triángulos apuntando hacia la derecha en el triángulo que apunta hacia la izquierda. Deja $\delta=e^{-\sqrt{\log 1/\varepsilon}}$. Para cada pequeño triángulo $T$, deja que $I$ sea el intervalo de longitud $\delta$ veces la longitud de la proyección de $T$ en el eje horizontal con el mismo punto final. Si la suma de las longitudes de los $I$ es notable, entonces hemos terminado.

De lo contrario, para cada $x$ que no esté en la unión de los $I$, las intersecciones de los triángulos con la línea vertical correspondiente forman un sistema de intervalos $J$ que satisface $\operatorname{dist}(J',J'')\ge \delta\min(|J'|,|J''|)$ y para muchos $x$ esos intervalos cubren la sección transversal hasta $\varepsilon$ más o menos.

Ahora supongamos que tenemos $K=K(x)$ intervalos en este sistema. Todas las brechas son como máximo de $\varepsilon$. Toma cada quinta brecha y elimina el intervalo adyacente de longitud $\le\varepsilon/\delta$. Eliminaremos una porción fija de los intervalos y las brechas serán como máximo de $\le\varepsilon/\delta$ (bueno, $+2\varepsilon$, por supuesto, pero ¿a quién le importa?). Repite por $\frac 12\sqrt{\log 1/\varepsilon}$ pasos. O bien aún nos quedará algo, en cuyo caso tendremos $K\ge e^{c\sqrt{\log 1/\varepsilon}}$ (en cada paso eliminamos una porción fija de todos los intervalos restantes), o eliminaremos todo usando solo intervalos de longitud $\sqrt\varepsilon$ o menos, lo que resulta en $K\ge\varepsilon^{-1/2}$, lo cual es aún mejor (nuestros intervalos casi tienen que cubrir la sección transversal). Pero entonces el perímetro total es al menos $\int K(x)\,dx$ sobre el conjunto bueno y hemos terminado de nuevo.

Puede haber margen para mejorar aquí, pero eso requeriría un poco más de pensamiento :-)

Answer 2

Ok creo que este es un argumento que al menos el perímetro es de $\varepsilon^{-c}$ para algún $c$ suficientemente pequeño. Para evitar casos especiales donde $\varepsilon$ es grande, usamos la convención de contar los lados del triángulo que señala hacia arriba como parte del perímetro total.

Afirmación 1: Considera cualquier empaque como se describe arriba. Sea $p$ el perímetro total de los triángulos, y sea $s$ la longitud del lado del triángulo más pequeño. Entonces $s=O(\varepsilon/p)$.

La idea de la prueba es la siguiente observación. Para cualquier triángulo que señala hacia abajo $T$, considera el conjunto de puntos a una distancia al menos, digamos, $s/100$ de $T$. La mayoría de estos puntos no están cubiertos, y tienen a $T$ como su triángulo más cercano. Sumando esto sobre todos los triángulos da $\varepsilon = \Omega(ps)$, o, equivalentemente, $s=O(\varepsilon/p)$.

Afirmación 2: $p\geq \varepsilon^{-c}$ para cualquier $c>0$ suficientemente pequeño.

Probamos esto por inducción en el número de triángulos. Con la convención de que los bordes del triángulo que señala hacia arriba se cuentan como parte del perímetro, la afirmación es claramente cierta para $c>0$ pequeño para cualquier empaque de exactamente un triángulo, por lo que el caso base es claro.

Ahora supongamos que la desigualdad se cumple para todos los empaques con hasta $n$ triángulos. Sea $T_1, T_2, \dots, T_{n+1}$ un empaque de $n+1$ triángulos ordenados de mayor a menor tamaño. Para cualquier $1\leq i \leq n+1$, sea $\varepsilon_i$ el área no cubierta por los primeros $i$ triángulos, $p_i$ el perímetro total de los primeros $i$ triángulos, y $s_i$ la longitud del lado del $i$-ésimo triángulo respectivamente.

Por la hipótesis de inducción, sabemos que $p_n \geq \varepsilon_n^{-c}$. Por lo tanto $$ p_{n+1} \geq p_n+3s_{n+1} \geq \varepsilon_n^{-c} + 3s_{n+1},$$ y la afirmación se cumple si podemos demostrar que $ \varepsilon_n^{-c} + 3s_{n+1} \geq \varepsilon_{n+1}^{-c}.$ Para evaluar esto, observa que $$ \varepsilon_n^{-c} = (\varepsilon_{n+1}+(\sqrt{3}/4)s_{n+1}^2)^{-c}\geq \varepsilon_{n+1}^{-c}(1-(\sqrt{3}/4)cs_{n+1}^2/\varepsilon_{n+1}),$$ donde el último paso sigue de la convexidad de $(1+x)^{-c}$. Sustituyendo esto en la desigualdad anterior, queda por demostrar $3s_{n+1}\geq (\sqrt{3}/4)cs_{n+1}^2/\varepsilon_{n+1}^{1+c}$, o $4\sqrt{3} \geq cs_{n+1}/\varepsilon_{n+1}^{1+c}$.

Observa que podemos asumir que $\varepsilon_{n+1}/\varepsilon_n$ y $p_{n+1}/p_n$ son ambos $\Theta(1)$. Lo primero es porque, por la Afirmación 1, $\varepsilon_{n+1}=\Omega(s_{n+1}p_{n+1})\geq \Omega(s_{n+1}^2).$ Lo segundo es porque $n\geq 1$ y los triángulos están ordenados de manera decreciente. En particular, esto nos permite también asumir que $p_{n+1}=\Theta(\varepsilon_{n+1}^{-c})$. Entonces $cs_{n+1}/\varepsilon_{n+1}^{1+c}$ es, hasta un factor constante, igual a $cs_{n+1}p_{n+1}/\varepsilon_{n+1}$, que por la Afirmación 1 es $O(c)$. En particular, eligiendo $c>0$ suficientemente pequeño, esta expresión es menor que $4\sqrt{3}$, como se deseaba.