Wang Tiles and Aperiodic Tiling

Wang originally conjectured that no aperiodic tilings could exist. Wang was interested in the decidability of the Tiling Problem; it is said to be decidable if there exists an algorithm which will yield a solution for any given set of prototiles in  a finite number of steps or trials. The following is a simplified version of his approach (Grünbaum and Shephard 1987, page 602).

If a set of prototiles admits a tiling then one of these possibilities must hold:

(a) the set admits only periodic tilings, for example just one regular hexagon.

(b) the set admits periodic and non-periodic tilings, for example a square.

(c) the set admits only non-periodic tilings, in other words is an aperiodic set.

Wang showed that the Tiling Problem is decidable if one only considers sets which satisfy (a) and (b). In 1961 he went on to conjecture that possibility (c) could not occur, at the time an entirely plausible assertion.

The discovery of an aperiodic set spoilt Wang’s argument and it is now known that the Tiling Problem is undecidable.

The first aperiodic set was found by Wang’s student Berger (1966) and consisted of 20,426 tiles. This was first reduced by Berger to 104 tiles, then by Knuth to 96.

Other aperiodic tilings have since been used to produce smaller sets of aperiodic Wang tiles, from 32 to 24 and 16 as shown below.

According to Grünbaum and Shephard (Grünbaum and Shephard 1987, page 596).

“The reduction in the number of Wang tiles in an aperiodic set from over 20,000 to 16 has been a notable achievement. Perhaps the minimum possible number has now been reached. If, however, further reductions are possible then it seems certain that new ideas and methods will be required.”

Kari suggested such a method and produced a set of 14 tiles over 6 colours (Kari 1996). This was reduced by Culik to 13 tiles over 5 colours (Culik 1998) and this appears to be the smallest known set, although together they have attempted to show that one tile can be removed from the set.

However for Architectural and Computer Graphics applications the smallest set is not necessarily the most desirable.

Penrose P2 to Wang Tiling (32 Tiles)

A set of 32 Wang tiles can be generated from an aperiodic Penrose P2 tiling. The following procedure was suggested by Penrose and refined by Robinson. It starts with a Penrose P2 tiling such as that below, although Grünbaum and Shephard suggest the procedure could be simplified by using a Penrose P3 Rhomb tiling.

1. Grid the Penrose Tiling

Cut up the Penrose P2 tiling by keeping as close to the horizontal and vertical as possible. In fact each patch is made up of Robinson’s A-tiles (kites, darts, half-kites and half-darts).

2. Catalogue the Cut-Up Shapes

Catalogue the cut-up shapes using the dot and arrow matching rule for Penrose P2 Tiling (each type of dot must match and arrows be in same direction).

3. Assign Colours to Edges of Cut-Up Shapes

Using the following colours

Assign colours to vertical and horizontal edges respecting and the encoding by dots and arrows as follows:-

4. Assign A Wang Tile to Each Cut-Up Shape

Assign Wang tiles to each of the cut-up shapes including their rotations and reflections using the encoded edge colours. The rotations and reflections are required because Wang tiles do not permit rotation or reflection.

5. Assign Appropriate Wang Tiles

Replace the gridded P2 Tiling with the corresponding Wang tiles:-

This is the Wang tile equivalent of the original Penrose P2 tiling shown at the the start of this section, using 32 tiles over 16 colours.

Ammann A2 to Wang Tiling (24 Tiles)

Ammann A2 tiles can have unit length sides, so the prototiles can be made up of collections of 3 squares and 5 squares.

Because Wang tiles cannot be rotated or mirrored each of the possible orientations of the A2 prototypes needs to have its own unique set of Wang tiles.

1. Create a Set of 24 Wang Tiles Using 24 Colours

The 24 colours on the left are used to generate the 24 unique Wang tiles on the right.

2. Map the 24 Wang Tiles onto 8 Prototiles

The Wang tiles are then mapped onto the 4 possible orientations of  Ammann A2 prototiles (8 tiles in all as listed in the diagram below).

As indicated by the orientation of the coloured triangles in the colour list above, the first row of colours is used on the top and bottom edges of the Wang and A2 prototiles; these both have to match other tiles edge to edge. Similarly the second row of colours is used on the left and right hand edges of both sets of tiles.

The third and fourth rows are used for the top and bottom edges of the Wang tiles that become the internal edges of the A2 prototiles.

Rows five and six  are used for the left and right hand internal edges of the A2 prototiles.

The functional arrangement of the colours above differs from Grünbaum and Shephard, but the numbers above and below them are those that they used.

3. Allow Duplication Between 3 and 5 Square Prototiles

The red numbered Wang tiles in the prototile catalogue represent the tiles that are used in both the 5 and 3 square A2 prototiles and allowing these duplications allows the number of Wang tiles to be reduced to 24.

Ammann A2 to Wang Tiling (16 Tiles)

A sets of 16 Wang tiles can be generated from the Golden Section version of the same aperiodic Ammann A2 tiling marked with 2 sets of parallel Ammann bars. These form overlapping red and cyan grids.

1. Catalogue the Tiles formed by the Cyan Grid

Using the cyan grid to provide the edges of a new set of tiles and the red grid to create the markings that provide the matching conditions, catalogue the different tile types (outlined in blue and numbered below).

According to Grünbaum and Shephard this results in the following 16 tiles (although tile 6 does not appear to be present above)

2. Map the Catalogued Tiles to Wang Tiles

Map the 16 catalogued tiles above to the 16 Wang tiles below using 6 colours.

A further set of tiles can be generated that correspond to composed or decomposed versions of the tiles above.

3. Apply the Wang Tiles to the Original Tiling

A Wang tiling can then be generated that corresponds to the original Golden Section Ammann A2 tiling  using 16 tiles over 6 colours and with the composed tiling indicated by thickened lines.

/Users/grahamshawcross/Documents/blog_drafts/Wang Tiles and Aper

Smaller Sets

More recently smaller sets of Wang tiles have been found using an entirely different method due to Kari, (Kari 1996). This uses Mealy machines that multiply Beatty sequences of real numbers by rational constants. Using this method Kari produced a tile set of 14 tiles over 6 colours. Using a slightly modified version of Kari’s method Culik, Culik 1996, produced a set of 13 tiles over 5 colours.

The authors propose the following 13 over 5 colour Wang tile set.

Bibliography

Grünbaum B., Shephard G. C. (1987)
Tilings and Patterns
W.H. Freeman and Company
New York
 
Kari J., 1996
A small aperiodic set of Wang Tiles
Discrete Mathematics 1996 Volume 160 Issue 1-3 Pages 259-264
 
Culik K., 1996
An Aperiodic Set of 13 Wang Tiles
Discrete Mathematics Volume 160 Issue 1-3 Pages 245-251

About Graham Shawcross

Architect PhD student at Edinburgh University Interested in order, rhythm and pattern in Architectural Design
This entry was posted in Aperiodic Tiling, Architecture, Geometry, Tiling and tagged , , . Bookmark the permalink.

12 Responses to Wang Tiles and Aperiodic Tiling

  1. armahzar says:

    Good article. However you must update your article to include the smallest set of 11 Wang tiles https://arxiv.org/abs/1506.06492

    Like

  2. Mario Apps says:

    This blog was… how do I say it? Relevant!! Finally I’ve
    found something which helped me. Thank you!

    Like

  3. Monsters move as they sing, meaning your island is sooner or
    later complete of gorgeous creatures all singing and
    moving in one particular large harmony.

    Like

  4. I think the whole idea of using Wang tiles, or other aperiodic tiles, is to have a feeling of tight local order and loose overall randomness. In musical terms I am not sure which parts the colours and tiles take.

    In the post different combinations are illustrated:

    32 tiles in 16 colours (from Penrose P2), 24 tiles in 24 colours (Ammann A2), 16 tiles in 6 colours (Golden Section A2), 14 in 6 (Kari) and 13 in 5 Culic. Whilst mathematically the aim seems to be the minimum number of tiles and colours, visually, and I suspect musically, the larger number of tiles seem to be more satisfying.

    See

    A completely different take is given here

    Like

  5. If you rotate things through 45 degrees, each Wang tile has two triangles above the horizontal and 2 below. These can be thought of as two layers of musical ideas, running in counterpoint – the primary one at the top, the secondary one underneath. Each colour could represent a different musical idea.

    The counterpoint would need to be invertible. But it would not be necessary for all the different ideas (colours) to work with each other simultaneously.

    The music would be performed by playing the music associated with the Wang tile, plus (as a subordinate, maybe quieter) the two touching tiles above and below the Wang tile. The performer then moves from tile to tile, with the music changing seamlessly as it does so

    Imagine a person playing a computer game – the person’s location within the game could be used to trigger the associated Wang tiles music, giving a feeling of cohesion without any obvious periodic looping.

    Like

  6. Hello, after reading this amazing piece of writing i am also happy to share my knowledge here with
    mates.

    Like

  7. Emile says:

    I have read so many psts regarding the blogger lovers but
    this article is actually a pleasant paragraph, keep itt up.

    Like

  8. I have read so many articles or reviews concerning the blogger lovers but this paragraph is actually a
    good article, keep it up.

    Like

  9. Michael McGrady says:

    Do you know how to turn a first-order logic well-formed formula without functions and equality into a Kahr-Wang-Moore formula with the Wang tiles? I would like to know where to learn how to do this. Thank you. My email is michael.mcgrady@gmail.com

    Like

  10. Pingback: Wang Tiles and Aperiodic Tiling | ESALA

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s