CS 791 Assignment 2
Due date: February 22nd.
In this assignment, you will complete a few mathematical exercises,
and then proceed on to an implementation question based on Celtic knots.
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
Each of the images below depicts a
fragment of a frieze or wallpaper pattern, in which the manner
of continuation should be clear. For each image,
do the following:
- 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.
Question 2: Symmetry theory
- 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
we can find the location
of T(p) for any point p in the plane.
- Consider two vectors
T1 = (1,0) and
T2 = (x,y),
with y ≠ 0. These two vectors define a lattice
of points, namely the set
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
- 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
- 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.
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.
- 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:
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.
- 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,
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
- 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 (a "sidle" pattern) 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