CS 791 Assignment 3

Due date: Monday, 15 March.

You can submit this assignment by emailing me a PDF or a link to a web page, or by handing it to me on paper. You can write it up by hand as long as it's tidy.

If you're auditing the course, the implementation question is optional.

Question 1: Monohedral polygons

Show that for every k ≥ 3 there exists a monohodral tiling by a polygon with k sides. (Hint: this doesn't require a formal proof; it's easier to describe families of tilings that cover all possible values of k. I did it with a family for even k and a family for odd k.)

Question 2: Pentagons

Consider a set of prototiles consisting of a regular pentagon together with a rhomb with interior angles of 36 and 144 degrees and the same edge length as the pentagon. Using these shapes, construct the following tilings: (Each tiling must use both prototiles.)

Question 3: Isohedral tilings

Identify the isohedral types of the following tilings, according to the list given at the back of my book. Mark the tiling vertices of one tile and add (possibly directed) labels consistent with the incidence symbol for that tiling type. Disregard all colourings and markings that artificially distinguish tiles from one another.





Question 4: One shape, many isohedral types

Find a polygon that is the prototile of four different isohedral tilings, all of different types. That is, draw four isohedral tilings of different types, using the same polygonal prototile each time.

Question 5: 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.

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:

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. Some ideas for extensions are given on a separate page.

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:

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

Bonus: Vertex species

Write a program that enumerates all the legal vertex species (that is, all integers ni that satisfy the equation (n1-2)π/n1 + ... + (nk-2)π/nk)) = 2π), as discussed in the lecture on Archimedean tilings. You do not need to produce the legal types (i.e., all inequivalent orderings of the species), just the species themselves. You should print out each species, one per line, for a total of 17 lines.

Write the program in any language you want, and submit the source code, including a brief comment explaining the approach taken. I will be unimpressed by a program consisting of 17 print statements, or indeed a program that uses any a priori knowledge of the solution to the problem (for example, the fact that no ni can ever be larger than 42 or the fact that there are 17 species). Your program must derive the complete enumeration from first principles. The hard part is to avoid getting stuck in any kind of infinite loop (... 4.4.105, 4.4.106, 4.4.107, 4.4.108, ...).

If it helps, the solution doesn't have to be big or complicated. Mine took 22 lines of Python and runs in about 1/20 of a second. Python was useful because of the availability of a fractions library, making it easy to create and manipulate fractions as easily as ordinary numbers. Dr. Scheme might be useful for the same reason.

Craig S. Kaplan Last updated: