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
- How many symmetries does a square have (that is, how many
elements are there in its symmetry group)?
- 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
- Sketch a proof of why no unmarked quadrilateral can have symmetry
Question 2: Identifying symmetry groups
Each of the images below depicts a finite pattern in its entirety,
or a fragment of a frieze or wallpaper pattern. For each image,
do the following:
- 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.
Question 3: Celtic knots
- 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
- File format
- Let us agree on the following simple file format for
specifying a knotwork:
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
- 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
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.
- 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
- 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
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
- 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
- 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:
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
- 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,
- 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
If you fold a strip of paper into a zig-zag accordion, cut a shape
out of it, and unfold the strip, you obtain a frieze pattern of
symmetry group pm11 made out of repeated copies of the shape.
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