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 is optional.

Question 1: Incidence geometry

In Hilbert's formulation of Euclidean geometry, the following axioms constrain the behaviour of the undefined relation of incidence:
  1. Prove that there exist at least three lines that don't all meet in a single point.
  2. Prove that every point lies on at least two lines.
  3. Prove that the parallel postulate is independent of the axioms of incidence.
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.

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 "polygons-in-contact" approach. For more information on this technique, see my 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:

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:

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: 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.
Craig S. Kaplan Last updated: