Assignments

Written/Coding Assignments

Roughly every two weeks you will implement some kind of numerical algorithm for manipulating geometry.  An important part of this exercise will be deriving essential algorithmic details, starting from the smooth geometric point of view that we will discuss in class.  Each assignment is split roughly between derivations/proofs, and coding exercises in Python.  However, you will not have to write this code “from scratch”—for each assignment we will provide a code skeleton and ask you to implement critical routines that have been removed.  Since this class tends to be a fairly diverse mix, we suggest that folks with a strong coding background seek out those with a strong math background and vice versa.  However, your final work must be your own!

Click here for a list of all assignments.

Reading

Periodically we will ask you to read from the course notes or from a relevant research paper.  To encourage you to think more deeply about this material, we will ask you to send us an email for each reading consisting of

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / incomplete / not addressed.

Writing this summary will also help you prepare for our in-class discussion.  Summaries should be sent to both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu.  To receive credit, you must send your summary by 10:00 AM (UTC-05:00) on the day of lecture, including the string DDGSpring2016 in the subject line.

Click here for a list of all readings.

Final Project

For the final project, you will pick a geometric object that piques your interest (say, the Hopf fibration or a symplectic manifold) and explore it in depth.  The project will consist of three main parts:

  1. A writeup (~10 pages) defining the object and discussing where/how it is used in computational algorithms, and exploring where there might be remaining challenges/questions/potentially interesting applications.
  2. A short (~10 minutes) in-class presentation outlining what you discovered in your writeup.
  3. A final coding project where you implement some cool/fun/interesting/beautiful algorithm related to your object.  Here you may either implement an existing algorithm or—if you are truly bold—cook up your own.

Your topic must be selected and sent to us no later than 5pm on Monday, March 14th 2016, and will be approved by us shortly thereafter.  Since you will be stuck with this object for the rest of the semester, you should take some time to pick a good one.  We are glad to provide suggestions.

You are welcome to work in pairs (but not larger groups), as long as (i) both teammates contribute substantially to the final project, and (ii) the scope of the project is significantly larger than it would be for a single individual. For instance, the writeup should be more thorough, the presentation should be a bit longer/more in-depth, and the final implementation project should be about twice as ambitious. We will help you calibrate the size and scope of the project when you submit your proposals. If you choose to work with a partner, it should be clearly indicated in your proposal and in your final submission. Finally, you should try to take advantage of the diverse experience of our class (e.g., pairing with someone from math if you’re in CS, or someone from engineering if you’re in math). This is not a hard requirement, but it is strongly encouraged.

A few pointers that will help you get started:

  • An excellent place to start is Wikipedia’s list of differential geometry topics. Many of these ideas may still be hard to understand based on what we’ve studied in class, but spend some time searching around for something that resonates with you / some topic that seems within your grasp. The goal of the assignment is to then connect one of these objects with existing algorithms and discretizations.
  • Here’s a fairly good list of DDG-related papers from a similar course at Caltech, which may help you dig up geometric objects/ideas that we haven’t had a chance to discuss in class. Note, however, that your goal in this project is a bit different than what’s represented on this page: you should not focus your project around a single paper, i.e., do not simply regurgitate one of the papers on this list. Instead, your project should be primarily focused around some geometric object; papers and algorithms should be used only to understand the place of this object within computation.
  • Discrete Geometric Mechanics and Variational Integrators – this talk by Ari Stern gives a very nice high-level overview of how symplectic geometry helps with numerical integration of mechanical systems. As in Ari’s talk, you should be sure to discussion practical tradeoffs and existing algorithms where your geometric object is used. For our class, you should also include a few more of the elementary definitions needed to understand your geometric object (in the spirit of our course lecture slides). Remember that the goal is to both state the formal definition and give geometric intuition. I.e., why is this the definition; what real-world geometric behavior motivated this particular list of properties or axioms?
  • A Survey of Efficient Structures for Geometry Processing – although this writeup does not address a topic in discrete differential geometry, it does represent the style and format of writeup we will expect you to write. I.e., it contains some basic definitions (and perhaps theorems), as well as a survey of existing literature. We will be grading you in part on the quality of the writing and presentation (rather than just the content), so take this assignment as an opportunity to hone your writing ability and technical communication skills. At 23 pages and 53 citations, this writeup is a bit on the long side of what we will expect, but you should aim to summarize the most important results and applications (generally found in academic papers) of the object you are studying.