CS798 Assignment 1

Due date: January 30th.

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, Question 3(a) (the implementation question) is optional. But you must still complete 3(b).

Question 1: Symmetric quadrilaterals

1. How many symmetries does a square have (that is, how many elements are there in its symmetry group)?
2. Consider all possible subsets of the symmetries of the square. For some of those subsets (including the set itself), there exist unmarked quadrilaterals possessing those symmetries and no others. Identify those subsets by drawing a representative quadrilateral for each. Arrange your drawings into a directed graph so that there is a path from quadrilateral A to quadrilateral B if A's symmetries are a superset of B's.
   
   Note: we don't simply want to classify quadrilaterals up to group isomorphism. Lines of reflection through a quadrilateral's vertices should be considered different from reflections through edge centres, even though the resulting symmetry groups might be isomorphic.
3. Sketch a proof of why no unmarked quadrilateral can have symmetry group C₄.

Question 2: Identifying symmetry groups

• Identify the symmetry group by giving the usual international symbol. 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. The easiest way to do so is to trace one on top of the image itself. If you're feeling more ambitious, you can crop one out of the source image digitally.

(a)	(b)
(c)
(d)
(e)	(f)

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