A tiling puzzle
A friend recently asked me how to optimally tile the shape below on the plane such that no two instances touch.
Off the top off my head I suggested considering the minimal enclosing circle and then pack hexagonally but he thinks one could do better. I thought I’d ask on here to see what others might come up with.
Here’s one solution, which is better than circle packing. Not sure if it’s the best though.
http://jchase.com/mathclass/tiling%20problem.pdf
You should be able to do better by arranging them in rows where each is rotated by 22.5deg from the adjacent ones then compressing along the rows until they almost touch. This will reuse some of the space between the “fingers”. The problem with compressing in the other direction is that the diagonally adjacent stars may interfere.
I don’t know if this is optimal, but it seems more efficient than a hexagonal arrangement of bounding circles.
Nice work both :)
Getting the *optimal* solution (and proving that it’s indeed optimal) is often not easy. One approach is to simulate “shaking” the elements while simultaneously compressing them, e.g. see here: http://www.nature.com/nature/journal/v462/n7274/full/nature08641.html The densest packing might not be a periodic tiling in some cases (it may be a quasicrystal).
See also here: http://physics.aps.org/articles/v3/37