CS 791 Assignment 2

Due date: February 22nd.

Summary

If you're auditing the course, Question 3(a) (the implementation question) is optional. But you must still complete 3(b).

Question 1: Identifying symmetry groups

• Identify the symmetry group by giving the usual international crystallographic symbol (or the orbifold signature, if you prefer). If you feel you need to suppress small variations in the image to account for imperfections in the execution, state what you're choosing to ignore.
• Indicate a single fundamental region. Ideally, trace a region on top of the image using drawing or painting software. In the worst case, you can provide me with a paper hardcopy of the patterns with the fundamental regions indicated.

(a)

(b)

(c) (ignore the diagonal construction line)	(d)
(e)	(f)

(g)

Question 2: Symmetry theory

1. Let T be an isometry (that is, a function of the plane for which the distance between T(p) and T(q) is the same as the distance between p and q for all pairs of points p and q in the plane). Prove that T is completely determined by its action on one triangle. In other words, let ABC be a (non-isosceles) triangle. Prove that if we know the locations of T(A), T(B), and T(C), then we can find the location of T(p) for any point p in the plane.
2. Consider two vectors T₁ = (1,0) and T₂ = (x,y), with y ≠ 0. These two vectors define a lattice of points, namely the set {aT₁ + bT₂} where a and b range over all integers.

   Of the 17 wallpaper groups, find those that can be the symmetry group of a lattice generated in this way. For each possibility, name the group and give one possible pair (x,y) for which the resulting lattice will produce a pattern belonging to that group.

Question 3: Celtic knots

1. Write a program to draw Celtic knots using the method described in Peter Cromwell's article "Celtic knotwork: mathematical art" (Mathematical Intelligencer 15(1) (1993), pages 36–47; the link should work from an on-campus computer). Your program must accept an input file giving the size of the grid and the locations of break markers, and produce as output a vector image of the corresponding knotwork (in postscript, SVG, PDF, etc). You will also need to extend your program in a novel way (see below).
   
   

   File format

   Let us agree on the following simple file format for specifying a knotwork:

   • The first line contains an integer width, an integer height, and the number of break markers. Each cell in this grid represents one quarter of a square in Cromwell's primal grid.
   • Each subsequent line describes a single break marker. The line has three parts: two integers giving the X and Y coordinates of the start of the break marker (zero-based and relative to the top left of the grid), and a letter S or E indicating whether the break marker should extend to the south or east. The X and Y coordinates must sum to an even number. Each break marker will extend across two of these "sub-cells".

   Here's a quick example. The first twelve break markers are used to define the border. The first image is a visualization of the resulting framework, and the image on the right is a possible rendering of the corresponding knotwork.

   6 6 15 0 0 E 2 0 E 4 0 E 0 0 S 0 2 S 0 4 S 6 0 S 6 2 S 6 4 S 0 6 E 2 6 E 4 6 E 1 1 S 1 3 E 4 4 E

   You are free to extend this format in any way you want, or even adopt an entirely different format, as long as you provide a way to read the old format into your program. Ideally, you should create an interactive interface for editing the break markers (see the list of extensions). You can assume the input is well-formed. The goal here is to get you as quickly as possible into the interesting part of the assignment.

   
   

   Output

   There are many possible styles for drawing Celtic knots. You can choose a simple default style for all output. Your default must at least give some indication of interlacing, and must use real curves (they can't be purely polygonal).

   
   

   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.

   
   

   Notes

   Some implementation notes to get you started:

   • You don't have to draw whole ribbons directly. If you experiment a bit, you'll notice that you can assemble a knotwork using little tiles, one for each grid cell. Furthermore, the number of different possible tile motifs is very small (not including rotations and reflections).
   • One tricky part in assigning motifs to cells is getting the interlacing to work. With a bit more experimentation, you'll find that the over-under relationship at the crossings can be determined in advance from the grid position.

   
   

   Programming language

   You are free to use any Turing-complete language. Google is not a valid programming language. That is, you can find many web pages describing how to draw Celtic knots. Some include implementations. Some even include source code. You're welcome to browse the web in search of inspiration and algorithms, but please don't look at any other source code during the assignment. If in doubt about external sources of information, talk to me first.

   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 you created an interactive user interface, include screen shots.
   • 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 samples produced by your program. At least one sample must clearly demonstrate the effect of your extension, if possible.
   Your write-up can either be a PDF document or a web page. Your submission should not contain more than about three or four pages of text, though you're welcome to make it longer by including lots of pictures. Some time before the deadline, email me either a URL for your web-based write-up or a PDF.

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

2. Cromwell's paper mentions ten one- and two-colour frieze groups that arise naturally as symmetry groups of Celtic frieze patterns. Pick five of those groups and for each one produce an illustration of a Celtic frieze with those symmetries. The illustration should be different from the one in the paper. Label it with the symbol for the group.

   You do not have to respect the frieze symmetry at the edges of your illustration -- the knotwork can fold back on itself. Just make sure to include enough repeats that the implied frieze symmetry is evident.

   Obviously, the intention is for you to produce these drawings using your program from the previous question. But you're welcome to use any other medium you choose. Thus, you can draw them by hand if your program doesn't work or works only partially (or if the muse strikes).

Bonus: Paper frieze dolls

Figure out how to do the same thing for as many of the other frieze groups as you can. You should be able to take an appropriately-folded strip, cut out a single asymmetric shape, and unfold the result into a design with the appropriate frieze symmetry. Submit the strips, cut and still folded (in an envelope) with the relevant symmetry group written on each. If your folding and cutting required any special or unusual steps, include a short explanation.