Packing an upwards equilateral triangle efficiently by downwards equilateral triangles

Question

Consider the problem of packing an upwards-pointing unit equilateral triangle "efficiently" by downwards-pointing equilateral triangles, where "efficiently" means that there is little wasted area relative to the perimeter of the triangles used in the packing. The $n^{th}$ generation of the Sierpinski triangle

packs all but $(3/4)^n$ of the area of the large upwards triangle by downwards triangles, at the cost of a net perimeter of $\asymp (3/2)^n$. Thus, if we let $\varepsilon$ denote the area not packed, then the perimeter of the triangles used in this construction is $\gg \varepsilon^{-\alpha}$ for $\alpha = \frac{\log (3/2)}{\log (4/3)} = 1.409\dots$.

My question is whether this phenomenon is general: given any finite collection of downward equilateral triangles in the upward unit equilateral triangle that is a packing (i.e., interiors are disjoint) and leaves an area of $\varepsilon$ not covered, is it true that the total perimeter of the triangles used is of the form $\gg \varepsilon^{-c}$ for some absolute constant $c>0$? For my application I do not need an optimal exponent $c$. [EDIT: as pointed out in answers, to make the answer positive for large $\varepsilon$, the outer triangle should also count towards the total perimeter.]

I think I can establish a bound of the form $\gg \log \frac{1}{\varepsilon}$ (roughly speaking, by arguing that every dyadic scale of triangles between $\varepsilon$ and $1$ has to contribute a constant amount of perimeter, otherwise there will be too much waste), but for my application I really need a polynomial lower bound (or maybe $\exp( (\log\log \frac{1}{\varepsilon})^C )$ for a large absolute constant $C$ might suffice). It's intuitively plausible to me that the Sierpinski packing is the "best" packing for this purpose, and that the smaller triangles really have to contribute more than a constant amount of perimeter, but I am finding it surprisingly tricky to locate a rigorous argument. Perhaps this sort of question has already been studied in the literature?

One can interpret this question as an exotic form of an isoperimetric inequality, where the region of interest is required to be a disjoint union of downwards pointing equilateral triangles in a fixed upward pointing triangle, but this question seems rather orthogonal to the usual theory of isoperimetric inequalities, so I don't believe that this interpretation is particularly fruitful.

Answer 1

Ok I think this is an argument that the perimeter at least $\varepsilon^{-c}$ for some sufficiently small $c$. To avoid special cases where $\varepsilon$ is large, we use the convention that we count the sides of the upwards-pointing triangle as part of the total perimeter.

Claim 1: Consider any packing as above. Let $p$ be the total perimeter of triangles, and let $s$ be the side-length of the smallest triangle. Then $s=O(\varepsilon/p).$

The proof idea is the following observation. For any downwards-pointing triangle $T$ consider the set of points at distance at most, say, $s/100$ from $T$. The majority of these points are not covered, and have $T$ their closest triangle. Summing this over all triangles gives $\varepsilon = \Omega(ps)$, or, equivalently, $s=O(\varepsilon/p)$.

Claim 2: $p\geq \varepsilon^{-c}$ for any sufficiently small $c>0$.

We prove this by induction on the number of triangles. With the convention that the borders of the upwards-pointing triangle are counted as part of the perimeter, the statement is clearly true for small $c>0$ for any packing of exactly one triangle, so the base case is clear.

Now suppose the inequality holds for all packings with up to $n$ triangles. Let $T_1, T_2, \dots, T_{n+1}$ denote a packing of $n+1$ triangles ordered in decreasing size. For any $1\leq i \leq n+1$, let $\varepsilon_i$ denote area not covered by the first $i$ triangles, $p_i$ the total perimeter of the first $i$ triangles, and $s_i$ the side length of the $i$:th triangle respectively.

By the induction hypothesis, we know that $p_n \geq \varepsilon_n^{-c}$. Hence $$ p_{n+1} \geq p_n+3s_{n+1} \geq \varepsilon_n^{-c} + 3s_{n+1},$$ and the claim follows if we can show that $ \varepsilon_n^{-c} + 3s_{n+1} \geq \varepsilon_{n+1}^{-c}.$ To evaluate this, observe that $$ \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}),$$ where the last step follows from the convexity of $(1+x)^{-c}$. Plugging this into the inequality above, it remains to show $3s_{n+1}\geq (\sqrt{3}/4)cs_{n+1}^2/\varepsilon_{n+1}^{1+c}$, or $4\sqrt{3} \geq cs_{n+1}/\varepsilon_{n+1}^{1+c}$.

Observe that we can assume that $\varepsilon_{n+1}/\varepsilon_n$ and $p_{n+1}/p_n$ are both $\Theta(1)$. The former is because, by Claim 1, $\varepsilon_{n+1}=\Omega(s_{n+1}p_{n+1})\geq \Omega(s_{n+1}^2).$ The latter is because $n\geq 1$ and triangles are ordered decreasingly. In particular, this lets us also assume that $p_{n+1}=\Theta(\varepsilon_{n+1}^{-c})$. So $cs_{n+1}/\varepsilon_{n+1}^{1+c}$ is up to a constant factor equal to $cs_{n+1}p_{n+1}/\varepsilon_{n+1}$, which by Claim 1 is $O(c)$. In particular, choosing $c>0$ sufficiently small, this expression is less than $4\sqrt{3}$, as desired.

Answer 2

OK, posting then.

I prefer to think of triangles pointing to the right in the triangle pointing to the left. Let $\delta=e^{-\sqrt{\log 1/\varepsilon}}$. For each small triangle $T$, let $I$ be the interval of length $\delta$ times the length of the projection of $T$ to the horizontal axis with the same endpoint. If the sum of lengths of $I$'s is noticeable, we are done.

Otherwise, for each $x$ not in the union of $I$'s, the intersections of the triangles with the corresponding vertical line form a system of intervals $J$ satisfying $\operatorname{dist}(J',J'')\ge \delta\min(|J'|,|J''|)$ and for many $x$ those intervals cover the cross-section up to $\varepsilon$ or so.

Now assume that we have $K=K(x)$ intervals in this system. All gaps are at most $\varepsilon$. Take every fifth gap and remove the adjacent interval of length $\le\varepsilon/\delta$. We'll remove a fixed portion of the intervals and the gaps will become $\le\varepsilon/\delta$ (well, $+2\varepsilon$, of course, but who cares?). Repeat for $\frac 12\sqrt{\log 1/\varepsilon}$ steps. Either we will be still left with something, in which case we have $K\ge e^{c\sqrt{\log 1/\varepsilon}}$ (at each step we remove a fixed portion of all remaining intervals), or we'll eliminate everything using only intervals of length $\sqrt\varepsilon$ or less, which results in $K\ge\varepsilon^{-1/2}$, which is even better (our intervals have to almost cover the cross-section). But then the total perimeter is at least $\int K(x)\,dx$ over the good set and we are done again.

There may be some room for improvement here, but that would require some more thinking :-)