CS 791 Assignment 3
Due date: Monday, 15 March.
You can submit this assignment by emailing me a PDF or a link to a web
page, 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: Monohedral polygons
Show that for every k ≥ 3 there exists a monohodral
tiling by a polygon with k sides. (Hint: this doesn't
require a formal proof; it's easier to describe families of
tilings that cover all possible values of k. I did
it with a family for even k and a family for odd k.)
Question 2: Pentagons
Consider a set of prototiles consisting of a regular pentagon together
with a rhomb with interior angles of 36 and 144 degrees and the same
edge length as the pentagon. Using these shapes, construct the
following tilings:
- A periodic tiling.
- A tiling with d5 symmetry.
- A tiling with c5 symmetry.
(Each tiling must use both prototiles.)
Question 3: Isohedral tilings
Identify the isohedral types of the following tilings, according to
the list given at the back of my book. Mark the tiling vertices of
one tile and add (possibly directed) labels consistent with the
incidence symbol for that tiling type. Disregard
all colourings and markings that artificially distinguish tiles from
one another.
Question 4: One shape, many isohedral types
Find a polygon that is the prototile of four different
isohedral tilings, all of different types. That is, draw four
isohedral tilings of different types, using the same polygonal
prototile each time.
Question 5: Islamic star patterns
Write a program that draws Islamic star patterns using the
"polygons-in-contact" approach.
For more information
on this technique, see
my
paper from GI 2005.
Your program should accept the specification or name of a tiling
and a contact angle, and
produce a vector graphics file containing (a region of)
the corresponding star
pattern. Your program need not have an interactive user
interface, though having an interface is a great way to
explore the design space of star patterns. If you want
to be fully general you can read specifications for tilings
in from files, but it's acceptable to hard-code the tilings
you want to use into the program.
- Features
- At a minimum, your program should do the following:
- You should support at least the Archimedean
tilings 3.12.12, 4.6.12, 4.8.8, and 6.6.6, and the "rosette
dual" tilings 10RD and 8RD. Specifications for these tilings
(and others) are provided in two formats:
- archimedeans.tl,
hanbury.tl: a simple XML-based
format, if you're comfortable with XML parsers.
- archimedeans.txt,
hanbury.txt: an even simpler
text format that has all the information from the XML
file predigested into just the numbers. The first
file explains the format.
In any case, you can either parse the specifications
(in which case you'll get other tilings for free) or hard-code
the appropriate tilings into your program.
- You should have a rendering mode that starts with a two-coloured
fill of
the interiors of the polygons in the star pattern, and covers
that with a thickened drawing of the edges as ribbons. The
ribbons need to have an interior colour and a border colour.
You are not required to implement interlacing. The following
image gives an example. You can click on it for a PDF version.
- 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? If
appropriate, 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: Vertex species
Write a program that enumerates all the legal vertex species (that is,
all integers ni that satisfy the equation
(n1-2)π/n1 + ... +
(nk-2)π/nk)) = 2π),
as discussed in the lecture on Archimedean tilings. You do not need
to produce the legal types (i.e., all inequivalent orderings of
the species), just the species themselves. You should print out
each species, one per line, for a total of 17 lines.
Write the program in any language you want, and submit the source code,
including a brief comment explaining the approach taken. I will be
unimpressed by a program consisting of 17 print statements, or
indeed a program that uses any a priori knowledge of the solution to
the problem (for example, the fact that no ni can
ever be larger than 42 or the fact that there are 17 species). Your
program must derive the complete enumeration from first principles.
The hard part is to avoid getting stuck in any kind of infinite loop
(... 4.4.105, 4.4.106, 4.4.107, 4.4.108, ...).
If it helps, the solution doesn't have to be big or complicated.
Mine took 22 lines of Python and runs in about 1/20 of a second.
Python was useful because of the availability of a fractions
library, making it easy to create and manipulate fractions as easily
as ordinary numbers. Dr. Scheme might be useful for the same reason.
