Penrose Tiles

How do you tile a plane in such a way that its aperiodic? This means that although there may be local symmetries, the overall pattern has no specific patch is ever repeated. This is in contrast to classic square and triangular tile systems that have repeatable patches as they cover the infinite plane.

The Penrose tiles were discovered in 1974 by Roger Penrose. Later, in 1984, it was demonstrated that when these tiles were fit together using a simple rule set, they will cover an infinite plane in an infinite number of arrangements without ever repeating.

There are two types of Penrose tiles: Dart & Kite, and Rhombs. Both of these use decoration rules for determining where a tile can be placed. Unfortunately, I can't reproduce either set without mangling the angles which are important.

Because of the difficulty explaining the Dart & Kite, I shall focus on the Rhombs. The narrow rhomb has angles of 144^o and 36^o. The thick rhomb has angles of 108^o and 72^o. Alone, these two tiles can be placed in periodic patterns, it is the tiles and the rules that make up Penrose tiles. The obtuse angle on the narrow rhombs are both decorated differently with matching decorations on the acute angles on the thick rhomb. When placing tiles, the decorations must match up.

It has been proven that Penrose tiles can be colored with three colors such that no two adjacent tiles have these same color.

Apparently this method of tiling was once used to pattern Kleenex toilet paper, much to Penrose's chagrin.

From News of the Weird:

In April (1997), Sir Roger Penrose, a British math professor who has worked with Stephen Hawking on such topics as relativity, black holes, and whether time has a beginning, filed a copyright infringement lawsuit against the Kimberly-Clark Corporation, which Penrose said copied a pattern he created (a pattern demonstrating that "a nonrepeating pattern could exist in nature") for its Kleenex quilted toilet paper. Penrose said he doesn't like litigation but, "When it comes to the population of Great Britain being invited by a multinational to wipe their bottoms on what appears to be the work of a Knight of the Realm, then a last stand must be taken".

One way to think of Penrose tilings is as projections of particular sets of points in a higher dimensional space onto a 2D plane. It's easiest to see how this works by looking at an analogous projection from 2D onto a 1D space.

Imagine we have a lattice, consisting of all the points on the plane with integer coordinates. We pick a point to start from, and draw a straight diagonal line in some direction:

   .     .     .     .     .     .     .     .     .    _.
                                                     _.'
                                                 _,~'
   .     .     .     .     .     .     .     _,~'  .     .
                                          _.'
                                      _,~'
   .     .     .     .     .     ._,~' .     .     .     .
                               _.'
                           _,~'
   .     .     .     . _,~'.     .     .     .     .     .
                    _.'
                _,~'
   .     .  _,~;     .     .     .     .     .     .     .
         _.'
     _,~'
  .~'    .     .     .     .     .     .     .     .     .

Now, we draw vertical and horizontal lines connecting points which are near the line in a sort of staircase pattern, following the rule of drawing towards the line until we cross it, then changing direction at the next available point (we only draw to the right and upwards):

   .     .     .     .     .     .     .     .     ._____!
                                                   ! _.'
                                                 _,+'
   .     .     .     .     .     .     .______,~'__!     .
                                       !  _.'
                                      _+~'
   .     .     .     .     ._____._,~'_!     .     .     .
                           !   _.'
                           !,~'
   .     .     ._____.___~'!     .     .     .     .     .
               !    _.'
               !_,~'
   .     .___,~!     .     .     .     .     .     .     .
         !.'
     _,~'!
  .~'____!     .     .     .     .     .     .     .     .

Next, we project our steps onto the diagonal line, using differently coloured lines for the vertical and horizontal components:

  ___.__.___.__.___.___.__.___.___.__.___.___.__.___.__...

Unless the diagonal is at exactly 45 degrees, the projections of the vertical and horizontal parts of the steps will have different lengths. In the example, the projections of the vertical lines are shorter, since the angle is less than 45 degrees (from the x axis).

What we're really doing is collecting the set of all the points included in the space generated by sweeping the centre of an upright unit square along the line. We then use the orthogonal projections of these points onto the line (the points on the diagonal at which a line to the nearest integer point is at 90 degrees) as the vertices of our 1D "tiles", the different coloured lines.

Now, notice that if we pick our direction so that the diagonal goes exactly through another dot (as well as the one we started with) then the pattern of the colours on our projection will repeat infinitely. If we imagine the line at the other dot, it will look just the same as it did at our first dot, so there must be a corresponding "other dot" further up the line ... and so on, ad infinitum. Since the line is symmetric under translation between the two dots, the tiling pattern must always start to repeat at the next dot the line passes through.

Lines that go exactly through more than one dot must have gradients which are rational numbers - they can be expressed as an exact fraction: x/y, where x and y are the coordinates of the second dot, taking the first as the origin.

It follows from these considerations that if we specify the gradient is an irrational number, it will only go exactly through one dot (at the start), and the pattern of colours on the projection will never repeat exactly, though it's true that any finite section we pick from the line will have a pattern that's found in infinitely many places along the line.

So if we pick an irrational gradient (the most likely result of picking one at random) we can say we've created a quasi-periodic tiling of a 1D space! One good irrational but nonrandom gradient to pick is the golden mean (or, as it's known in that context, the golden slope) which gives a tiling with interesting properties.

Now imagine we do the same sort of thing, except instead of a line across a 2D lattice, we use a plane which divides a 3D lattice, and we collect the set of points that are inside the space filled by placing a unit cube at every point on the plane. We then use projections of these points onto the plane as the vertices of our tiles. Here's one familiar and very regular tiling that may result:

        `:|#'       `:|#'       `:|#'       `:|#'       `:|
       ,##|:~.     ,##|:~.     ,##|:~.     ,##|:~.     ,##|
    .~####|::::~.~####|::::~.~####|::::~.~####|::::~.~####|
    |#####|:::::|#####|:::::|#####|:::::|#####|:::::|#####|
    |#####|:::::|#####|:::::|#####|:::::|#####|:::::|#####|
    |###~' `~:::|###~' `~:::|###~' `~:::|###~' `~:::|###~' 
    |#'       `:|#'       `:|#'       `:|#'       `:|#'    
    |:`.     ,##|:~.     ,##|:~.     ,##|`~.     ,##|:~.   
    |::::~.~####|::::~.~####|:::`~.~####|:::`~.~####|::::~.
    |:::::|#####|:::::|#####|:::::|#####|:::::|#####|:::::|
    |:::::|#####|:::::|#####|:::::|#####|:::::|#####|:::::|
     `~:::|###~' `~:::|###~' `~:::|###~' `~:::|###~' `~:::|
        `:|#'       `:|#'       `:|#'       `:|#'       `:|
       ,##|:~.     ,##|:~.     ,##|:~.     ,##|:~.     ,##|
    .~####|::::~.~####|::::~.~####|::::~.~####|::::~.~####|
    |#####|:::::|#####|:::::|#####|:::::|#####|:::::|#####|
    |#####|:::::|#####|:::::|#####|:::::|#####|:::::|#####|
    |###~' `~:::|###~' `~:::|###~' `~:::|###~' `~:::|###~'
    |#'       `:|#'       `:|#'       `:|#'       `:|#' 
    |:`.     ,##|:~.     ,##|:~.     ,##|`~.     ,##|:~.
    |::::~.~####|::::~.~####|:::`~.~####|:::`~.~####|::::~.
    |:::::|#####|:::::|#####|:::::|#####|:::::|#####|:::::|
    |:::::|#####|:::::|#####|:::::|#####|:::::|#####|:::::|
     `~:::|###~' `~:::|###~' `~:::|###~' `~:::|###~' `~:::|
        `:|#'       `:|#'       `:|#'       `:|#'       `:|
       ,##|:~.     ,##|:~.     ,##|:~.     ,##|:~.     ,##|

In the 2D example, we project two kinds of lines - horizontal and vertical - onto our diagonal, and colour them differently. Here, we have three kinds of plane - the xy, xz and yz planes, and we give them each a different colour when we project them. This looks 3D, just because it is a projection of 3D shapes onto the 2D plane. You can see it as the projection, or as a 2D representation of the 3D equivalent of the "steps" in the 2D/1D example we started with. That's exactly what "projecting it" means!

If we tilt the plane generating this pattern a little in the right way, breaking the simple symmetry in the above pattern - the equivalent of taking the diagonal line away from 45 degrees to an irrational gradient - we can get an aperiodic tiling with slightly differently shaped tiles.

This is difficult to render in ascii, because the angles are awkward, but perhaps something like this (adjusted for ease of ascification. Imagine it rotated about 10 degrees clockwise for a little more accuracy..)

                           
       _.:#|":._    |    _.~' `~._    |    _.~' `~._    |
   _.:#####|::::":._|_.~'         `~._|_.~'         `~._|
  |########|::::::::|":._         _.:#|":._         _.:#|":._         _.~#|":._
  |########|::::::::|::::":._ _.:#####|::::":._ _.:#####|::::":._ _.:#####|::::"~._
  |########|::::::::|::::::::|########|::::::::|########|::::::::|########|::::::::|
  |#####:~' `~:;::::|::::::::|########|::::::::|########|::::::::|########|::::::::|
  |#;~'         `~::|::::::::|########|::::::::|########|::::::::|########|::::::::|
  |":._         _.:#|"~.;::::|######*#|"~.;::::|#####:~' `~::::::|#####:~' `~:;::::|
  |::::":._ _.:#####|::::"~:;|##*#####|::::"~:;|#:~'         `~::|#:~'         `~:;|
  |::::::::|########|:::::::"|########|::::::::|":._         _.:#|":._         _.:#|
  |::::::::|########|::::::::|########|::::::::|::::"~._ _.:#####|::::":._ _.:#####|
  |::::::::|########|::::::::|########|::::::::|::::::::|########|::::::::|########|
   `~:;::::|#####:~' `~::::::|#####:~' `~::::::|::::::::|########|::::::::|########|
       `~:;|#:~'         `~::|#:~'         `~::|::::::::|########|::::::::|########|_
       _.:#|":._         _.:#|":._         _.:#|"~::::::|######*#|"~:;::::|######*#|":._
   _.:#####|::::":._ _.:#####|::::":._ _.:#####|::::"~:;|##*#####|::::"~:;|##*#####|::::":._
  |########|::::::::|########|::::::::|########|::::::::|########|::::::::|########|::::::::|
  |########|::::::::|########|::::::::|########|::::::::|########|::::::::|########|::::::::|
  |########|::::::::|########|::::::::|########|::::::::|########|::::::::|########|::::::::|
  |#####:~' `~:;::::|#####:~' `~:;::::|#####:~' `~:;::::|#####:~' `~:;::::|#####:~' `~:;::::|
  |#:~'         `~:;|#:~'         `~:;|#:~'         `~:;|#:~'         `~:;|#:~'         `~:;|
                     `~._         _.~' `~._         _.~' `~._         _.~' `~._         _.~'
                         `~._ _.~'         `~._ _.~'         `~._ _.~'         `~._ _.~'
                             |                 |                 |                 |
 
 

Notice how the tiling is now composed of two basic shapes, rather than the single shape of the regular tiling above it (the shaded areas have the same shape (or should do) but the white bits are more squashed). The same sort of thing is happening as when our 1D "tile" lines were of two different lengths, depending on the angle of the diagonal line. Similarly, if we choose the right aligment for the plane we project onto, our pattern will never repeat.

Now, in 5D ... No, beyond my ascii skills, I'm afraid, but that's one way to arrive at a Penrose tiling. The Penrose tilings were proved by N.G. de Bruijn in 1981 to be a particular class of such projections from a 5D hypercubic lattice onto a plane passing through it.

This is all the more remarkable, since Penrose arrived at his tilings in a very different way, by considering sets of shapes, and rules for placing them which would aperiodically cover a plane, algorithmically - from the point of view of a jigsaw puzzler, without a thought of projection in his head!

---

Read more, and generate tilings of your own, using the quasitiler program, to be found at:
http://www.geom.umn.edu/apps/quasitiler/

An impressive rendering of a penrose tiling, showing the 5-cube generating it, can be found (for now) at:
http://www.innerx.net/personal/tsmith/pwtile240.html

You can find much more information on Penrose and other tilings at the Geometry Junkyard:
http://www.ics.uci.edu/~eppstein/junkyard/penrose.

Information from:
Lecture notes on dynamic tilings at:
http://www.math.okstate.edu/mathdept/dynamics/lecnotes/node29.html
Lattice projections and tilings, at:
http://penelope.mast.queensu.ca/~andrew/qc/

That de Bruijn reference:
N. G. de Bruijn. Algebraic theory of Penrose's non-periodic tilings of the plane, i,ii. Nederl. Akad. Wetensch. Proc. Ser. A, 84:38-52, 53-66, 1981.