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:

enter image description here

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:

enter image description here
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$:

enter image description here

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?

  • 1
    $\begingroup$ Yes, I know: what have you tried and where did you get stuck? This is just a cute real-live "problem" that I thought could be fun to think about in cookie season, especially for those who are thinkers rather than bakers. Have fun! $\endgroup$ – Raphael Dec 12 '14 at 19:52
  • 4
    $\begingroup$ Presumably you got stuck to the frosting. In the kitchen. *rimshot* $\endgroup$ – David Richerby Dec 12 '14 at 20:44

Let me answer your question partially for the hexagram case.

You can make the following tiling

$\hskip1.2in$enter image description here

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$enter image description here

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$enter image description here


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.

1st 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:

  • $\begingroup$ similar theory see also packing tetrahedrons by Chang/ NYT. conjecture (somewhat inspired by the article): for this specific problem, an irregular packing exists that is superior to any regular one. $\endgroup$ – vzn Dec 19 '14 at 5:07

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.

  • 1
    $\begingroup$ As it is, this is not an answer but a comment. Can you summarise what the cited book contains on the matter and how it may apply here? $\endgroup$ – Raphael Dec 23 '14 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.