CS798 Assignment 3
Due date: Monday, 13 March.
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, the implementation question
Question 1: Incidence geometry
In Hilbert's formulation of Euclidean geometry, the following
axioms constrain the behaviour of the undefined relation of incidence:
- I1: For every two distinct points, there is a unique line
incident with both of them.
- I2: Every line is incident with at least two distinct points.
- I3: There exist at least three points with the property that
no line is incident with all of them.
These are all "quickies" -- they follow from the axioms in a couple
of steps. In fact, you don't even need I2 to prove any of them.
- Prove that there exist at least three lines that don't all
meet in a single point.
- Prove that every point lies on at least two lines.
- Prove that the parallel postulate is independent of the axioms
Question 2: Hyperbolic models
Let four points, A, B, C and D
be given in the Poincaré disk model of the hyperbolic plane.
Give a simple algorithm for computing the intersection of the two
line segments AB and CD.
Question 3: Islamic star patterns
Write a program that draws Islamic star patterns using the
For more information
on this technique, see
paper from GI 2005.
Given a tiling and a contact angle as input, and
produce a postscript file containing 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 alright to hard-code the tilings
you want to use into the program.
- 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:
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
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
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
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? 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.
Bonus: Polyhedral Sculpture
Produce a sculpture of a polyhedron. Points will be awarded based
on the originality and difficulty of the method of construction,
and the aesthetic appeal of the chosen polyhedron. Some recommendations:
Submit a photograph and description of your sculpture. If possible,
bring it to class.
- Choose a polyhedron with lots of symmetries (i.e., cuboctohedral
or icosidodecahedral symmetry).
- Choose one that's not convex. Very good choices would be
some of the fancier uniform polyhedra, stellations of the
icosahedron, compounds, or projections of 4D polytopes. If
you're feeling very ambitious,
you can copy Tom Lechner and build a
room-sized wooden small inverted retrosnub icosicosidodecahedron.
I would be suitably impressed.
- If the weather cooperates, sculpt your polyhedron out of snow
(this was my original idea for the bonus question; convex polyhedra
would be advisable in this case). If that's
not possible, consider also looking up Rona Gurkewitz's books
on modular origami polyhedra. See also the lovely and delicate
paper polyhedra by Ulrich
Mikloweit. Tensegrity is cool too.
- You actually have to build it. No kits like zometool or