A tiling puzzle

June 12th, 2012 | Categories: general math, just for fun | Tags:

A friend recently asked me how to optimally tile the shape below on the plane such that no two instances touch.

How to tile this?

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.

  1. June 12th, 2012 at 12:58
    Reply | Quote | #1

    Here’s one solution, which is better than circle packing. Not sure if it’s the best though.


  2. June 12th, 2012 at 13:12
    Reply | Quote | #2

    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.

  3. June 12th, 2012 at 14:12
    Reply | Quote | #3

    Nice work both :)

  4. Szabolcs
    June 13th, 2012 at 14:05
    Reply | Quote | #4

    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).

  5. Szabolcs
    June 13th, 2012 at 14:06
    Reply | Quote | #5