CS798 Assignment 2

Due date: February 20th.

You can submit this assignment by emailing me a PDF 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: Regular polygons and stars

Here is Exercise 5 in Section 2.1 of Tilings and Patterns:
Show that if a tiling by regular polygons contains an octagon, then it must be the tiling (4.8²).

Actually, the statement is false as written. Give a simple counterexample. Now prove the statement under the added assumption that every side of every tile has same length.
The general problem of tiling the plane with tiles all of which have five-fold symmetry is still open. Let's dispense with two of the easier-to-describe cases.
1. Prove that it is impossible to tile the plane with regular pentagons.
2. Sketch a proof of why it is impossible to tile the plane with regular pentagons and regular |5/2| pentacles.

Question 2: Isohedral tilings

Determine the isohedral type of each of the following tilings, according to the table given by Grünbaum and Shephard. Mark the tiling vertices of one tile and add (possibly directed) labels consistent with the incidence symbol given in the table. As always, disregard colours and other markings that artificially distinguish tiles from one another.

(a) (PDF)
(b) (PDF)

(c)
(d)
A pentomino is a topological disk formed by taking five contiguous squares from the regular tiling 4⁴. It is well known that the twelve different pentominos can each tile the plane isohedrally. Nine of the twelve pentominoes can tile by translations alone. For the remaining three, two distinct aspects (orientations) are required. Find the three two-aspect pentominoes, draw tilings that use them, and determine the isohedral types of those tilings.

Question 3: Tiling playground

Write an interactive program to manipulate the shapes of marked Isohedral tilings with topology type [4⁴]. You may assume that in all cases, the tiling vertices are fixed in a square configuration (so you don't need to worry about tiling vertex parameterizations). Of the 36 isohedral types with this topology, you only need to handle the 28 for which the tile shape is not constrained to be a square.

Features

At a minimum, your program should support the following features:

Choose an isohedral type. You can support this via the command line or via an interactive selector. When a new type is chosen, you should revert to a default square tile.
Drag points on the tile's boundary. You can click and drag on edit points along the boundary to change the edge shapes. If you click where there's no edit point, a new one is created. When the user modifies the tile shape, all symmetric copies of that edit are applied as well.
Delete points on the tile's boundary. There should be some way to delete edit points. In my program, you can control-click on points to delete them. Tiling vertices cannot be deleted!
Display the current tiling. A separate window shows a tiled region using the current tile shape. You don't need to worry about colouring. You don't need to rotate or translate the tiling in the window, but you should be able to scale the view and see more or fewer tiles. You don't need to use a very fancy method for filling the window with tiles, but the region you fill should roughly correspond to the window (i.e., don't draw too many off-screen tiles or leave big gaps on-screen). When the user modifies the tile shape, this window should also update automatically.
In theory, the tiling viewer can be combined with the tile editor into a single interface that lets you click anywhere on any tile boundary.
Export the tiled region as a postscript file.

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:

Describe your implementation. What set of languages, tools, and libraries did you use? What is the interface? 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).

Bonus: Tiling scavenger hunt

Find and document as many interesting tilings as you can that can be found within Waterloo city limits. These tilings can't be temporary (posters or chalk drawings). They have to be permanently installed as fixed architecture (brickwork, paving, ceramic tile, murals, wood inlay, driveways, etc). You are permitted to construct a new permanent building, or renovate an old one, with your choice of tilings if you want to go the extra mile. The tiling should have structure: a random jumble of paving stones isn't very interesting. For each tiling, take a photograph and indicate where the tiling can be found. Explain the structure of the tiling (give its isohedral type, for example). Ideally, they should all be found on public property, or at least visible from public property. Everybody should be able to find squares, hexagons, and bricks. Start with those. Here are some others I'd love to see...

Other Laves tilings
Other Archimedean tilings (4.8² and variations are popular)
Tilings by squares or triangles in multiple sizes
Aperiodic tilings (the windows of the Physics building at the University of Washington are etched with Penrose tiles)
Anything with pentagons

Craig S. Kaplan

Last updated:

(a) (PDF)	(b) (PDF)
(c)	(d)