Assignment 4


Assignment 4: Tilings and Islamic star patterns

Due date: Monday, July 13th, 2015


In this assignment, you will complete a couple of simple exercises related to tilings of the plane, and then proceed on to an implementation question based on Islamic star patterns.

Please try to submit everything in a single document, so that I can mark it all at once.

Question 1: Impossible vertex types

When deriving the 11 Archimedean tilings in class, we began with a list of 21 candidate vertex types (see Figure 3 of the paper Tilings by Regular Polygons by Grünbaum and Shephard for diagrams). We then eliminated ten types that could not be extended to tilings of the plane in which every vertex has that type. One simple heuristic eliminated some of those illegal types: if a vertex type is made up of three distinct integers, they must all be even. However, this heuristic does not cover everything.

For each of the vertex types,, and, prove that there cannot exist a tiling of the plane in which every vertex has that type. Don’t worry, these proofs are easy. Just try to build outward from a vertex, and prove that you’ll reach a point where you must fail. It’s probably easiest to communicate your proofs as sequences of diagrams.

Question 2: Constructing polygonal tilings

Using a single polygonal prototile, draw (patches of) three tilings of the plane:

  • One that is neither edge-to-edge nor corner-to-corner;
  • One that is corner-to-corner but not edge-to-edge; and
  • One that is edge-to-edge

Note that you must find a single shape that admits distinct tilings with the properties above. The shape need not be complicated, but finding it requires a bit of intuition. Submit drawings of the three tilings.

Question 3: Islamic star patterns

Write a program that draws Islamic star patterns using the “polygons-in-contact” approach. For more information on this technique, see my paper from GI 2005. (I also have a draft book chapter that I can share with you personally if you want a more detailed description and a few bug fixes; but that shouldn’t be strictly necessary for the scope of this assignment.)

Your program should accept the specification or name of a tiling and a contact angle, and produce a vector graphics file containing (a region of) the corresponding star pattern. Your program need not have an interactive user interface, though having an interface is a great way to explore the design space of star patterns. If you want to be fully general you can read specifications for tilings in from files, but it’s acceptable to hard-code the tilings you want to use into the program.


At a minimum, your program should do the following:

  • You should support at least the Archimedean tilings 3.12.12, 4.6.12, 4.8.8, and 6.6.6, and the “rosette dual” tilings 10RD and 8RD. Specifications for these tilings (and others) are provided in two formats:
    •, a simple XML-based format, if you’re comfortable with XML parsers.
    • archimedeans.txt, hanbury.txt: an even simpler text format that has all the information from the XML file predigested into just the numbers. The first file explains the format.

    In any case, you can either parse the specifications (in which case you’ll get other tilings for free) or hard-code the appropriate tilings into your program.

  • You should have a rendering mode that starts with a two-coloured fill of the interiors of the polygons in the star pattern, and covers that with a thickened drawing of the edges as ribbons. The ribbons need to have an interior colour and a border colour. You are not required to implement interlacing. The following image gives an example with ugly colours. You can click on it for a PDF version.

Non-trivial extension

You must implement at least one non-trivial extension to your program beyond what’s decribed here. This part of the assignment is open-ended.

Extension ideas
  • Add a second layer of inference to the interiors of large regular polygons, as described in Section 3 of my paper.
  • Implement the “rosette transform” to generate new tilings suitable for this construction technique. Adjust the contact positions by moving them away from edge centres as necessary.
  • Implement “two-point patterns”.
  • Implement other rendering styles, most obviously interlacing. Note that in this case, you can get away with making local decisions about the over-under relationships at crossings (that is, there’s a cheap way to figure out the interlacings without actually doing a depth-first search).
  • Implement a colouring technique that automatically attempts to colour regions in a manner consistent with the Zellij style of star pattern design.
  • Add a method for automatically decorating the ribbons and interiors of the star pattern with small elements such as floral motifs.
  • Figure out how to turn the straight bands of the star pattern into spline curves in an attractive way. See this page for inspiration.
  • Extend the technique to some non-periodic tilings, for example Kepler’s Aa tiling or tilings produced by placing regular polygons at the vertices of Quasitiler-type tilings. More information about these extensiosn can be found in my thesis.
  • Build star patterns from tilings produced using the overlay-dual technique. This approach presents the interesting possibility of building a pattern with a large, many-pointed central star.
  • Build star patterns containing stars with unusual numbers of points or in unusual combinations. See Jay Bonner’s page on star patterns for some ideas.
  • Extend the star patterns to non-Euclidean geometry, either on the surface of a sphere or in the hyperbolic plane. Alternatively, extend them to polyhedra.
  • Perform other geometric transforms on star patterns, such as circular inversion.
  • Execute your computer-generated star patterns in a novel medium, such as 3D printing, paper cutting, sculpture, etc. (You should aim to gain direct benefit from software here; don’t just print out your star pattern and paint a picture of it.)
  • Find artistic ways to dynamically alter your star pattern interactively. One approach would be to construct Islamic parquet deformations, as in my paper. Another might be to animate a star pattern in response to music. The collaboration A Hidden Order by artist Sama Mara and Lee Westwood might provide some inspiration.

This part of the assignment is not intended to be overwhelming; it’s just a way to get you thinking about what ideas might follow on from the basic implementation. Don’t feel you have to wear your fingers down to nubs trying to implement your extension. A proof-of-concept will suffice.


You must produce a short write-up describing your implementation. You can structure your submission as you wish, but should include at least the following:

  • Describe your implementation. What set of languages, tools, and libraries did you use? What is the interface? If appropriate, include a few select screen shots to show the various features of your system in operation.
  • Mention any bugs or limitations, and say what you would do to overcome them.
  • Describe your extension. Explain briefly how you modified the core implementation to accommodate the extension. Comment on how successful you feel it was.
  • Include some polished samples produced by your program. At least one sample must clearly demonstrate the effect of your extension, if possible.

I don’t plan to examine your source code, but I reserve the right to request it for marking purposes. I also reserve the right to request a demonstration (a demo might be the best way to show off some extensions).


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.