How many cookies in the cookie box? -- Tiling stars

Question

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit in one layer:

Almost! Is there a way they could have fit? How well can we tile stars, anyway? Given that these are regular six-pointed stars, we could certainly use the well-known hexagon tilings as an approximation, like so:

^{Messed up the one to the upper right, whoops.}

But is this optimal? There's plenty of room between the tips.

For this consideration, let us restrict ourselves to rectangular boxes and six-pointed, regular stars, i.e. there are thirty degrees (or $\frac{\pi}{6}$) between every tips and its neighbour nooks. The stars are characterised by the inner radius $r_i$ and outer radius $r_o$:

^[source]

Note that we have hexagons for $r_i = \frac{\sqrt{3}}{2} \cdot r_o$ and hexagrams for $r_i = \frac{1}{\sqrt{3}} \cdot r_o$. I think it's reasonable to consider these the extremes (for cookies) and restrict ourselves to the range in between, i.e. $\frac{r_i}{r_0} \in \Bigl[\frac{1}{\sqrt{3}}, \frac{\sqrt{3}}{2}\Bigr]$.

My cookies have $r_i \approx 17\mathrm{mm}$ and $r_o \approx 25\mathrm{mm}$ ignoring imperfections -- I was going for taste, not form for once!

What is an optimal tiling for stars as characterised above? If there is no static best tiling, is there an algorithm to find a good one efficiently?

Answer 1

Let me answer your question partially for the hexagram case.

You can make the following tiling

$\hskip1.2in$

By this you will cover 12/14=6/7 of the plane (count the triangles in the dashed quadrilateral).

Is this optimal? I would think so. Although I am not giving a proof I will provide some arguments. One can ask, how good we can fill the space (triangle) in between the pointy spikes. In the above tiling we fill half of it. Can we do better?

$\hskip20mm$

It is possible that two hexagram will intersect this space, but then they cover very little of its area (without proof). If there is only one hexagram intersecting I assume that its tip touches the concave corner of the other hexagram as depicted in the picture. If this would not be the case we can improve by moving the intersecting hexagram to this corner (again no proof here). Under these assumptions it is not hard to see that the case where there is side-to-side contact maximizes the intersection. If you do the math, then you will find out that the area of the intersection equals $$\frac{\sec ^2(x)}{2 \sqrt{3} \tan (x)+2}.$$

The plot of this function looks like this and shows that our intuition was right.

$\hskip30mm$

Answer 2

the following is not offered as a definitive or specific/ superior attack on this possibly unexpectedly complex problem but as additional scientific/ theoretical angles/ general study not covered so far.

1^st this general area is known/ classified as "bin packing" and this is a 2d case. there are some famous proofs from mathematics that are related eg the 3d case of Keplers inquiry into sphere packing which was an open problem for centuries and "recently" solved with computer proof by Hales. an example 2d case that is used daily in industry is for optimizing chip layouts. obviously this is different than the problem but can point to some of the complexity of these types of problems. for example there does not seem to be any theory that requires/ indicates that a 2d case would be simpler than a 3d case. also note that a simple rectangular boundary does not necessarily help simplify the solution other than say, a polygonal boundary.

there could be an analytic solution possible if some kind of basic definition/ scheme of "regular tiling" was given in the problem statement such as placement on a grid etc. in which case calculus equations might be derivable and an optimum findable.

the conditions of the problem (maybe counterintuitively) do not seem to lead to an analytic optimal solution. this may be surprising to some but very similar problems of tiling the plane are known to be undecidable (this was a famous result years ago and there are many references and even ongoing research). a key difference between the decidable (solvable/ analytic) and undecidable problems is whether the tiling is "regular". the problem above refers to "regular stars" but does not refer to "regular tiling". the other current answer assumes a kind of regular tiling or order, but note that even defining "regular tiling" can be very tricky formally/ mathematically.

problems such as this are generally quite amenable to genetic algorithms. such an algorithm can find "very good" packings which are unlikely to be improved by much, and perhaps some bounds can be placed on their optimality via very ingenious methods (ie must be within a small error percent of optimal), but cannot prove any are optimal.

here are some refs found that are generally directly applicable:

• example use of genetic algorithms. On genetic algorithms for the packing of polygons / Jacobs

• Algorithms for Geometric Packing and Scaling Problems Phd thesis / Michael Formann 1992, 92p, sec 3.6 Scaling Star shaped x-monotone Objects p30

• GEOMETRIC BIN PACKING ALGORITHM FOR ARBITRARY SHAPES / ARFATH PASHA 2003 Graduate Thesis 87p

• this stackexchange question is close also. packing arbitrary polygons within an arbitrary boundary. it is for arbitrary boundaries

Answer 3

While this particular problem probably has not been studied, such questions have been asked by Laszlo Fejes Toth and are known as packing problems. I strongly recommend the third chapter of the Pach-Agarwal book.