Welcome to 15-458 / 15-858B! (Spring 2016)

Welcome to the website for 15-458/858B.  Here you’ll find course notes, lecture slides, and homework (see links on the right).

If you are a student in the class, register now by clicking here!

We strongly prefer that you register using your CMU email, but in any case you must not register with an address at hotmail.com, live.com, gmail.com, yahoo.com, aol.com, earthlink.net, as email from these domains will be filtered out by the host.

A few things to note:

  • You will be subscribed to receive email notification about new posts, comments, etc.
  • You can ask questions by leaving a comment on a post.  If you’re apprehensive about asking questions in public, feel free to register under a pseudonym.
  • Otherwise, please associate a picture to your profile by registering your email address at Gravatar.com—doing so will help us better recognize you in class!
  • You can include mathematical notation in your questions using standard $\LaTeX$ syntax.  For instance, when enclosed in a pair of dollar signs, an expression like dollar\int_M K dA = 2\pi\chidollar gets typeset as $\int_M K dA = 2\pi\chi$.
If you encounter any problems while trying to use the website, please contact the TA at nsharp@cs.cmu.edu.

Assignment 0

Part of your course grade is determined by participation, which can include both in-class participation as well as discussion here on the course webpage.  Therefore, your first assignment is to:

  1. create an account, and
  2. leave a comment on this post containing your favorite mathematical formula (see below).
To make things interesting, your comment should include a description of your favorite mathematical formula typeset in $\LaTeX$.  If you don’t know how to use $\LaTeX$ this is a great opportunity to learn — a very basic introduction can be found here.  (And if you don’t have a favorite mathematical formula, this is a great time to pick one!)

Assignment 1

A1 Assignment 1 has been released, and can be obtained by clicking on the image or on this link.  It will be due on January 21st at 11:00pm.  Solutions can be submitted either electronically (cc’ing both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu), or physically either in class or outside 215 Smith Hall.  (Note that Smith Hall is typically locked in the evening, so if you want to submit physically you should plan to do so a bit earlier!)  Solutions will be graded not only on correctness, but also on legibility and quality of exposition—part of our goal this term is to help you become better mathematical communicators; solving problems in a vacuum helps nobody.  We will take points off for terrible handwriting—for those of you who suffer from this affliction, we strongly suggest you use $\LaTeX$.  Please make sure to put both your name and your Andrew ID on your submission.

The coding portion of this assignment is forthcoming—basically you will just need to get the code skeleton up and running on your machine, and we will be glad to assist you (potentially in a recitation session).

If you don’t know where to get started with some of these proofs, just ask!  We are glad to provide further hints, suggestions, and guidance either here on the website, via email, or in person.  Office hours are still TBD, but let us know if you’d like to arrange an individual meeting.  Also, don’t be afraid to chat with your classmates—you will learn much more together than you will in isolation.

Good luck!

Assignment 1 (Codebase)

As Keenan mentioned in class, the second component of getting started is downloading the codebase and getting a sample program to run. The codebase for this course is available at https://github.com/nmwsharp/DDGSpring2016.

The README displayed on that page contains some instructions for getting started and running a test program, as well as some other information. If you are an experienced programmer, feel free to ignore the instructions and do as you wish, there’s nothing especially unusual going on here (just get the test program working!).

To verify your success, please email me (nsharp@cs.cmu.edu) a screenshot of the window displaying the bunny by Jan 21. Don’t forget to include “DDGSpring2016” in the subject line.

There will surely be some hiccups getting started with this code, don’t hesitate to contact me with issues either via email or blog comments. I will also be holding an optional help session next Tuesday (Jan 19) around 5:00 so we can get things sorted out. If you aren’t available at that time and you would like to meet, let me know.

Reading 1 – The Simplicial Complex

ddg_simplices

For your first reading assignment, your goal will be understand of the idea of a simplicial complex—or one of its many generalizations, if you’re already familiar with this idea (see below).  Simplicial complexes are the basis of many of the algorithms we’ll study in this class—and for a vast array of algorithms used in mesh processing, scientific computing, and Hollywood.  They are also one common way to discretize topological spaces, which are the starting point for our study of geometry in the smooth setting.

We will discuss this concept further in class, so don’t worry if you’re utterly confused!  Also, please feel free to discuss and ask questions here, by posting in the comments.

Listed below are some suggested readings (from “beginner” to “expert”).  For this first reading assignment, you are also free to search for references that you find easier or more interesting:

  • Simplicial Complex (up through & including “Closure, Star, and Link”) – Perhaps it seems lazy to send a link to the Wikipedia (which is the first result on Google), but then again, I wrote much of this page many years ago—and made the figures.  It would be a useful exercise to contrast with  Abstract Simplicial Complex.
  • Simplicial Complexes and Simplicial Complexes – two brief introductions, both by Herbert Edelsbrunner.
  • Cell Complexes – more advanced (and nicely illustrated) introduction by Jeff Erickson.
  • Algebraic Topology (pp. 102–104) – very nice (and free!) book by Allen Hatcher, who here discusses $\Delta$-complexes, a close cousin of simplicial complexes.  Those of you who want to go really deep might also take a look at pp. 5–10 on cell (CW) complexes, as well as an additional supplement on simplicial CW structures.

Finally:

  • A Survey of Efficient Structures for Digital Geometry Processing, Section 2.2 – I include this reference not because it is particularly good introduction to simplicial complexes—in fact, there are some errors!—but because it gives a rough sense of the kind of document you will write for your final project (albeit a bit different in focus).

Submission: Please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, January 19; please include the string DDGSpring2016 in your subject line, so that we can be sure we catch your submission.  Your email for readings should always include:

  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.

For this particular reading, your summary should include a clear, concise definition for a simplicial complex, i.e., one that could be used to quickly communicate the idea to one of your peers without ambiguity.  For those of you already familiar with simplicial complexes, try to summarize the taxonomy of different complex types (simplicial complex, oriented simplicial complex, $\Delta$-complex, CW-complex, simplicial set, …).

Reading 2 – Topology

TopologyExamples

“Point set topology is a disease from which the human race will soon recover.”

—Henri Poincaré, father of modern topology

The goal of your second reading assignment is to make sure you understand at least the basic definition of each object we discussed in the last lecture, namely:

Topological Space
Metric / Metric Topology
Equivalence Relation / Quotient Topology

You may of course use whatever literature you like, since these definitions are all fairly standard. You should also read the Wikipedia page on topology, which gives a nice overview of its history and applications.

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, January 21st including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  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.

To test your own understanding, your email summary should answer the following two questions:

  1. Treating the black dots as points, and the blue blobs as subsets, which of the collections A–F is a topological space? Note that a blob with no points in it is the empty set.
  2. Two points \(x\) and \(y\) are “separated by neighborhoods” if there is a set \(U\) containing \(x\) and a set \(V\) containing \(y\) such that \(U \cap V = \emptyset\). Suppose we define an equivalence relation \(x \sim y\) where \(x\) is equivalent to \(y\) if and only if \(x\) and \(y\) cannot be separated. Again referencing the picture above, what then is quotient topology \(E/\!\sim\)? (Hint: this topology has a special name!)

Reading 3 – Topological Data Analysis

tda

Up until now, we’ve focused mainly on low-level concepts and definitions—for our next reading, we’ll take a high-level look at some very cool, contemporary algorithmic tools that leverage simplicial topology to make sense of large data sets in high dimensions. These tools fall under the broad heading of topological data analysis (TDA). One particular tool that’s received a lot of buzz in recent years (both within computer science as well as in applications in material science, imaging, biology, etc.) is persistent homology. The following video provides an excellent introduction, and should be mostly understandable based on what you’ve already learned in class:

Introduction to Persistent Homology (video)

Your reading assignment between now and February 2nd is to find one paper or survey on persistent homology that piques your interest (could be theory, could be applications) and summarize it to whatever degree you feel capable. Don’t worry if a lot of the terminology still seems alien—an important skill in reading academic papers is being able to extract the key idea without decoding every little detail and definition. If you find this subject interesting, you might consider doing your course project on TDA. More broadly, the emerging field of computational topology spans a broad range of beautiful and fascinating topics that could make good course projects.

Here are some pointers to get you started with persistent homology:

You might also try to give a rough summary of the different types of complexes that show up in topological data analysis (e.g., Vietoris-Rips, Čech, Witness, …).

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, February 2nd including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

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

Assignment 2

Assignment 2 is now available! You can view the document here. This assignment will be due at 11:00 pm on Feb 4th. The submission guidelines are identical to the previous assignment. Electronic submissions are preferred (cc’ing both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu), but if you wish to submit a physical document, do so in class or at 215 Smith Hall. Smith Hall locks to the public at 5:00 pm, so plan accordingly.

The document linked above has several questions inline, numbered as Exercises 12-17. You DO NOT need to complete problems 13 and 16; they involve material we have not yet covered. Also, there are some sections of text that might not recognize yet, such as a discussion of the Laplace-Beltrami operator and some use of exterior calculus. Don’t worry about these for now — they are not necessary to solve the problems, and we will be covering them in class in the upcoming weeks.

At the end of the document there is a coding assignment asking you to implement several of the quantities defined in the preceding text. A corresponding code skeleton is now present in the course repository, which you should download and modify. Note that the core library has also been updated, so you will need to re-download (or git pull, if you’re using git) the entire repository. The skeleton in Assignment2.py contains empty methods in which you will implement your solution, all of your modifications must be between the lines which say BEGIN YOUR CODE and END YOUR CODE. To submit the coding portion, email us your modified copy of the file Assignment2.py along with your written submission. There are some additional questions at the conclusion of the coding section, include your responses in the written submission.

To keep things simple, we will only be considering meshes without boundary for this assignment. There is a collection of such meshes in the Assignment2/Boundaryless_Meshes/ directory on which to test your code.

To investigate your code, run it as we did with the test assignment. Pressing ‘h’ will print (to your terminal) a list of commands supported by the program. Clicking on the mesh will print useful information about faces/edges/vertices.

Finally, on Tuesday (1/26) in class, I will be leading a workshop with a quick introduction to computing with meshes and a guide to using the course library. It is highly recommended that you attend! Please refrain from asking me any questions about the codebase until after that workshop.

Slides – Topological Structure and Meshes

The slides from our lectures on meshes and topology have been uploaded (click the image below to download).  Might be good to review if you’re unfamiliar with these ideas/definitions.  Note that some of this material (last few slides) has not yet been covered in class—we will talk about it in the next lecture.  As always, please feel free to leave questions/comments/corrections.

DDG_CMUSpring2016_TopologyAndMeshes

Reading 4 – A Quick and Dirty Introduction to Differential Geometry

A1 Your reading assignment for Thursday is to read Chapter 2 of our course notes on Discrete Differential Geometry, “A Quick and Dirty Introduction to Differential Geometry.” This chapter provides a different perspective from the topological picture we’ve been studying in class: rather than slowly building everything “from the ground up” (sets, topology, smooth structure…) it skips immediately to the juicy stuff: curved surfaces with real geometry sitting in space. We’ll fill in everything “in between” in the next few lectures.

To test your own understanding, try computing (in explicit coordinates) the metric induced by the immersion
\[
f(u,v) := \frac{1}{u^2+v^2+1}(2u,2v,u^2+v^2-1),\qquad\qquad
\]
which maps the plane \(\mathbb{R}^2\) to the unit sphere in \(\mathbb{R}^3\). Do you notice anything special about this metric?

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 4th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

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

Reading 5 – The Laplacian

The Laplace-Beltrami operator plays a fundamental role in geometry and physics; it is also a key object in digital geometry processing, take the role (in some sense) of the fast Fourier transform from traditional signal processing. Your next reading assignment will be to gain a better understanding of the Laplacian, both from a formal as well as intuitive geometric viewpoint. (If you haven’t seen vector calculus in a while, this may also be a good moment to brush up on things like the divergence, gradient, and curl.)

Some potential starting points:

  • Laplace operator – the obligatory Wikipedia link
  • Laplace-Beltrami – a generalized version of the Laplacian used in geometry; a discrete version of this operator is what we will effectively use to develop a number of algorithms throughout the remainder of the term.
  • Laplace-Beltrami: The Swiss Army Knife of Geometry Processing – some slides that give a nice visual overview of the Laplacian, its relationship with geometry, its discretization, and its applications in digital geometry processing.
  • Chapter 6 – The Laplacian – from our course notes; you will see a version of this chapter again very soon, since it forms the basis for your next assignment.
  • A discrete Laplace-Beltrami operator for simplicial surfaces – for folks who want to dig a bit deeper, this paper goes into some of the deeper questions about how to define a Laplace operator on a discrete surface, while capturing important features of the smooth operator.
  • Discrete Laplace operators: No free lunch – another “go deeper” paper; this one shows that (under certain assumptions) it’s actually impossible to preserve all the properties you might like to have.

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, February 9th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

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

Assignment 3

Assignment 3 is now available! You can view the document here. This assignment will be due at 11:00 pm on Feb 23rd. The submission guidelines are identical to the previous assignment. Electronic submissions are preferred (cc’ing both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu), but if you wish to submit a physical document, do so in class or at 215 Smith Hall. Smith Hall locks to the public at 5:00 pm, so plan accordingly.

The document linked above has several questions inline, numbered as Exercises 18-26. You DO NOT need to complete exercises 20 and 26, and you might not understand Section 6.3 — these all depend on exterior calculus, which we will be covering soon.

Once again, there is a coding component at the conclusion of the document, where you will be asked to implement some of the ideas described in the preceding text. A corresponding code skeleton is now present in the course repository, which you should download and modify. Note that the core library has also been updated, so you will need to re-download (or git pull, if you’re using git) the entire repository. The skeleton in Assignment3.py contains empty methods in which you will implement your solution, all of your modifications must be between the lines which say BEGIN YOUR CODE and END YOUR CODE. Some of the function names referenced in the text might not perfectly align with the codebase; don’t worry about this, just fill out the skeleton code. To submit the coding portion, email us your modified copy of the file Assignment3.py along with your written submission.

Again, we will only be considering triangular meshes without boundary for this assignment. There is a collection of such meshes in the Assignment3/Boundaryless_Meshes/ directory on which to test your code. Also, the codebase wiki has some information on matrix computation in Python which you might find useful.

Be warned, this coding portion is a bit more involved than the previous assignment, I suggest you start early so you have time to ask questions as needed.

Reading 6 – Generalized Winding Numbers

winding

For the next reading assignment, you should take a (brief!) look at the paper

Jacobson et al, “Robust Inside-Outside Segmentation using Generalized Winding Numbers.”

This paper provides a nice example of how simple geometric observations can lead to very practical algorithms for mesh processing.  The goal of this reading is not to understand every detail of the algorithm, but rather to get a sense of

  1. What is the practical problem the authors are trying to solve?
  2. What is a winding number?
  3. How did the authors generalize this notion of winding number, and how does it help them solve the practical problem?

As always, Wikipedia is your friend.

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 11th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

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

Reading 7 – Optimal Transport

An emerging tool for processing visual or geometric data (among many other things) is optimal transport / earth mover’s distance / Wasserstein distance.  For this reading, try to give an (extremely!) high-level description of the problem of optimal transport, and identify at least one interesting/cool/useful place where part of this theory has been applied.  In addition to the links above, some good starting points for applications in image and geometry processing include

As usual, you can probably Google for “optimal transport” plus any application and find something interesting.  The goal here is not to get an in-depth understanding of the subject, but rather just get a feel for the kind of problems people are solving with optimal transport.

More technical, in-depth introductions can be found in Ambrosio & Gigli, “A User’s Guide to Optimal Transport” and Villani, “Optimal Transport, Old and New.”

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 18th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

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

Reading 8 — Exterior Calculus Part I

A1

Time to get busy with exterior calculus. Very roughly speaking, exterior calculus is a “souped up” version of vector calculus that will let us do lots of interesting calculations on surfaces, both mathematically and computationally. This material is critical to the assignments we’ll do during the rest of the course; it is well-worth your time to understand it well! Your reading assignment for Thursday (not Tuesday) is to read the first half of Chapter 3 from our course notes, namely Sections 3.1–3.3 (pp. 23-35). We have also given you four mini-exercises below, which you should submit answers to either by email, or in-class if you prefer to do them on paper. These shouldn’t take more than a few minutes, and are mostly to confirm your own understanding; if you’re having trouble, please don’t hesitate to ask questions either here on the website or via email.

  1. Write the column vector \(u = [\ 1\ 2\ 3\ ]^T\) and the row vector \(\alpha = [\ 4\ 5\ 6\ ]\) using the notation described for vectors and 1-forms (respectively) in Section 3.1.
  2. Using the same values of \(u\) and \(\alpha\), what is \(\alpha(u)\)?
  3. Bonus question: suppose that for vectors \(u,v \in \mathbb{R}^n\), we define the metric as \(g(u,v) := 2\langle u, v \rangle\) where \(\langle \cdot, \cdot \rangle\) is the usual Euclidean inner product, i.e., our metric \(g\) is simply a conformal rescaling of the Euclidean metric by a factor 2. Based on the comment immediately preceding Section 3.1.1., what do you think the 1-form \(u^\flat\) and the vector \(\alpha^\sharp\) should be (using the same values for \(u\) and \(\alpha\) as in the previous question)? You can work out the answer using matrices if you like, but try writing the final answer in terms of the basis vectors and 1-forms (as in the previous question).
  4. Letting \(\alpha := 2 dx + 3 dy + 4 dz\) and \(\beta := 5 dx + 6 dy + 7 dz\), calculate \(\alpha \wedge \beta\). (This time, no matrices allowed!)
  5. Letting \(\alpha := 8 dx \wedge 9 dy\), write out \(d\alpha \wedge d\alpha\), showing explicitly why it’s equal to zero.

To give a couple concrete examples of what these calculations look like: if \(u := \tfrac{\partial}{\partial x} – 2 \tfrac{\partial}{\partial y}\), \(\alpha = dx – dy\), and \(\beta = 2 dx + dy\), then
\[
\alpha(u) = dx(u) – dy(u) = dx(\tfrac{\partial}{\partial x} – 2 \tfrac{\partial}{\partial y}) – dy(\tfrac{\partial}{\partial x} – 2 \tfrac{\partial}{\partial y}) = 1 – (-2) = 3,
\]
and
\[
\alpha \wedge \beta = (dx-dy) \wedge (2dx + dy) = 2 dx \wedge dx + dx \wedge dy – 2 dy \wedge dx – dy \wedge dy = 0 + dx \wedge dy + 2 dx \wedge dy – 0 = 3 dx \wedge dy.
\]

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 24th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

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

Reading 9 — Exterior Calculus, Part Deux

A1

Continuing with the last reading, your next reading will again be from our course notes, Sections 3.4–3.6. (If it’s been a while since you’ve looked at vector calculus, now may also be a good time to brush up on things like div, grad, and curl.) We’ve again included some simple calculations below, to test your own understanding of these ideas—as usual, please post in the comments if you have any trouble! This reading will be due before class next Tuesday. Note that it is important to do these warm-up exercises, because your next homework will be all about exterior calculus!

  1. Consider the scalar function \(\psi: \mathbb{R}^2 \to \mathbb{R}; (x,y) \mapsto \tfrac{1}{2}x^2 – 3y\), and compute the quantities \(d\psi\), \(\star d\psi\), \(d\star d\psi\), and finally \(\star d \star d \psi\). Express the results in terms of the basis 1-forms \(dx,dy\).
  2. Consider the scalar function \(\phi: \mathbb{R}^2 \to \mathbb{R}; (x,y) \mapsto e^{-(x^2+y^2)}\). Calculate the exterior derivative \(d\phi\), expressing the result in terms of the basis 1-forms \(dx,dy\).
  3. Using the same function \(\phi\) as above, evaluate the directional derivative \(\phi(X)\), where \(X := -(\tfrac{1}{4xe^{-(x^2+y^2)}}\tfrac{\partial}{\partial x} + \tfrac{1}{4ye^{-(x^2+y^2)}}\tfrac{\partial}{\partial y})\). Note that unlike the previous reading, here you are working with a “1-form field“, i.e., you are effectively taking a different inner product at each point. Alternatively, you can imagine that you’re computing a different directional derivative at each point, where the direction is given by \(X\).
  4. Integrate the 1-form \(\omega := \sin\theta\ d\theta\) over the unit circle.

To give a couple concrete examples of what these calculations look like: if \(f(x,y) := y/x – y^2\) and \(Z := \tfrac{\partial}{\partial x} – \tfrac{\partial}{\partial y}\), then
\[
df = \frac{\partial f}{\partial x} dx + \frac{\partial f}{\partial y} dy = -\frac{y}{x^2} dx + (\frac{1}{x}-2y) dy
\]
and
\[
df(Z) = -\frac{y}{x^2} \underbrace{dx(Z)}_{=1} + (\frac{1}{x}-2y) \underbrace{dy(Z)}_{=-1} = -\frac{y}{x^2} – \frac{1}{x}-2y = \frac{2x^2 y – x – y}{x^2}.
\]

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, March 1st including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

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

Assignment 4

For your next assignment, due on Friday, March 4th, you will simply complete the exercises you previously skipped over that required use of exterior calculus. These exercises can all be found in the class notes, and include:

  • Chapter 5, Exercise 13 (Hint: read very carefully the end of Section 3.2)
  • Chapter 5, Exercise 16
  • Chapter 6, Exercise 20
  • Chapter 6, Exercise 26

You should also carefully read Section 6.3 (which leads up to Exercise 26), which provides an alternative perspective on the Laplacian to the finite element approach you derived in your last homework, and will be very useful to understand for upcoming assignments.  For the exercises in Chapter 5, it may also be helpful to review your reading of Chapter 2 (on the geometry of surfaces), re-thinking these concepts in terms of differential forms.  (For example, the Weingarten map \(dN\) and differential \(df\) of the immersion can both be viewed as vector-valued 1-forms.)  These exercises are a bit more challenging than the “warm up” exercises from your readings, so please post comments if you have any trouble.

Final Project Proposal

We have updated the assignments page with additional information about your final project, as well as some pointers to get you started. Note that your initial project proposal is due on Monday, March 14th by 5pm. Please send us an email containing a short (1-2 paragraph) description of your proposed project including:

  • the geometric object you plan to study,
  • a few preliminary citations/pointers to papers, books, etc., that describe this object and its place in computation, and
  • a tentative goal for what you hope to achieve in the final “implementation” part (i.e., the code and/or proof/derivation you hope to write).

The first two parts of the project (writeup and in-class presentation) should help you refine your final project goal; it is perfectly fine if you don’t have all the details worked out at this point. Also: if you’re having trouble coming up with a project idea, or don’t understand the scope of the project, please still send us a preliminary proposal—we are more than happy to help you brainstorm during office hours. The goal here is to do something small, but interesting. To quote Nobel laureate Richard Feynman,

“The worthwhile problems are the ones you can really solve or help solve, the ones you can really contribute something to. A problem is grand in science if it lies before us unsolved and we see some way for us to make some headway into it. I would advise you to take even simpler, or as you say, humbler, problems until you find some you can really solve easily, no matter how trivial. You will get the pleasure of success, and of helping your fellow man, even if it is only to answer a question in the mind of a colleague less able than you. You must not take away from yourself these pleasures because you have some erroneous idea of what is worthwhile.

I have worked on innumerable problems that you would call humble, but which I enjoyed and felt very good about because I sometimes could partially succeed. … No problem is too small or too trivial if we can really do something about it.

Assignment 5

Assignment 5 is now available! There is no standalone document for this assignment, just a code skeleton in the class repository and section 8.1 of the class notes. You do not need to submit the exercises in the text, only the programming component. This assignment will be due at 11:00 pm on March 28th. The submission guidelines are identical to the previous assignments. Electronic submissions are preferred (cc’ing both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu).

As with the previous assignments, a code skeleton is now present in the course repository, which you should download and modify. Note that the core library has also been updated, so you will need to re-download (or git pull, if you’re using git) the entire repository. The skeleton in Assignment5.py contains empty methods in which you will implement your solution, all of your modifications must be between the lines which say BEGIN YOUR CODE and END YOUR CODE. Some of the function names referenced in section 8.1 of the text might not perfectly align with the codebase; don’t worry about this, just fill out the skeleton code. To submit the coding portion, email us your modified copy of the file Assignment5.py.

Additionally, include in your email a paragraph or two commenting on the results of this assignment. If your implementation is successful, analyze the results and comment on why they make sense. If you do not have faith in your results, comment on what appears to be wrong and what may be the cause.

Reading 10 – Presentation Tips

President Barack Obama delivering his State of the Union address on January 28, 2014.

For your final “reading” assignment, you will take a look at some material on how to give effective presentations. Giving truly great presentations is an art, and a lifelong endeavor. Especially in technical fields there is often a temptation to believe that if your ideas are brilliant enough, then essentially nothing else matters. This sentiment could not be further from the truth: ideas that are not broadly communicated or understood cannot have an impact on the world. Moreover, the process of distilling difficult technical material into a clear and accessible explanation is in and of itself a creative act that can often lead to new insights.

Next week, each of you will give a 10 minute in-class presentation on your final project topic. Since 10 minutes is a very short amount of time, your presentation should make use of visual aids that help your classmates quickly gain some geometric intuition about your chosen topic—just as you have seen in the lecture slides throughout the semester. For this reason you are strongly encouraged to use slide presentation software like PowerPoint, Keynote (or any number of free alternatives), or Beamer, though if you are exceptionally good at drawing compelling figures by hand in real-time then you may also give a presentation on the whiteboard. Either way, note that the visual aspect of your presentation will constitute an important part of your evaluation. You do not, however, have to generate all of these figures yourself! For a class presentation, it is perfectly acceptable to use figures found on the web, and textbooks, or in other media, so long as you properly cite the source on each slide.

As a reminder, the structure of your in-class presentation should look similar to the organization of your writeup. In particular, it should be split up roughly as follows:

  1. (1 minute) An intuitive introduction to your geometric object–this should include some visual aids.
  2. (2 minutes) A formal definition of the object in the smooth setting, and a brief statement of the most relevant theorems or properties of this object.
  3. (3 minutes) A high level overview of efforts to discretize the object, perhaps commenting on places where the current literature falls short.
  4. (3 minutes) A high level overview of applications of the object in computational algorithms. This section motivates why this object is interesting from a practical point of view.
  5. (1 minute) A very brief statement of your goals for the final implementation part of the project. Here you are setting your own criteria for success, and will later be evaluated on your success in carrying out these goals (or cogently explaining why things didn’t work out as expected!)

(Although this might not seem like much time, real conference presentations are often not much longer than this and still manage to pack in quite a bit of meaningful information—consider this an exercise preparing you for the real deal.) If you have been attending lecture, then you should already have a pretty good sense of what a presentation like this looks like: it is basically the structure we’ve been following in class, and you will find many examples for various topics in the course slides.  For this “reading” assignment you should also take a look at the following resources:

  • Trivial Connections on Discrete Surfaces—this presentation doesn’t strictly follow the format outlined above, but it is an example of a real conference talk that addresses a problem in discrete differential geometry, i.e., it takes a well-established idea from the smooth setting and shows how that idea can be put to work for computation. It also uses visual aids to quickly get the most important ideas across. (Also, this is a fun algorithm that could be easily implemented using the knowledge you’ve gained in this class!)
  • Giving an Academic Talk—some great general advice from Jonathan Shewchuk.
  • Tips for Giving Clear Talks—some great advice from Kayvon Fatahalian; some of these points won’t apply directly to your presentation since for the most part you’ll be explaining a mathematical idea (and its discretization) rather than discussing research outcomes. But still definitely useful to flip through.
  • How to Write Mathematics Badly—an amusing discussion of mathematical presentation and writing from Jean-Pierre Serre.

Just as important as content and organization are mechanical aspects of giving a talk such as body language, pacing, vocal tone, elimination of verbal pauses, and so forth. Here I don’t have any particular recommendations for readings or videos, but there are plenty on the web. In the long term, the absolute best way to get better at giving presentations is to practice it on a regular basis! there are plenty of fun organizations they can help you get this kind of practice—for instance, at CMU there is the CMU Mock Trial; you might also try tracking down a local chapter of Toastmasters.

Your assignment for this reading  is not to write a summary of what you read or watched, as we have done with previous readings, but rather to simply leave a link to your favorite resource on giving presentations in the comments below. These links will also help your classmates as they prepare for their presentations next week.   You should post a link no later than 6 PM on Monday, April 25.

[Also stay tuned for the schedule of speakers on Tuesday/Thursday of next week.]

Final Presentation Schedule

The schedule of final project presentations can be found below. Note that we’re on a pretty tight schedule (with just one minute to switch between presenters), so please make sure to have your talk ready to go before the end of the preceding presentation. If possible, you should coordinate with other students in your session to run your presentation off the same computer. The classroom should have a VGA and HDMI hookup; if you do not have a laptop that you can use to run your presentation, and you can’t sort something out with a classmate, please contact Nick about possible alternatives.

The schedule was carefully and thoughtfully constructed by calling the RandomSample[] method in Mathematica. If you absolutely cannot present on this date, please let us know no later than Sunday evening so that we have time to negotiate a swap with one of the other students. (In this situation it is especially helpful if you can find a friend willing to make the swap!)

Tuesday, April 26

  • 12:00—Yu
  • 12:11—Kirov
  • 12:22—Liu
  • 12:33—Shearer
  • 12:44—Bern
  • 12:55—Li
  • 1:06—Brakensiek

Thursday, April 28

  • 12:00—Han
  • 12:11—Kaffine
  • 12:22—Daids
  • 12:33—Yuan
  • 12:44—Soliman
  • 12:55—Su

[If somehow you don’t see your name on this list, please let us know ASAP!]

Wrapping Up

A few notes about our final class:

  • The “final” will be this Friday, May 6 from 8:30–11:30am in GHC 4215.  Note that this room is different from our usual classroom.
  • You will each have no more than 10 minutes to show off your final project (or 20 minutes for teams of two).  You will not be graded on the presentation (as you were last week), but should clearly demonstrate what you did in your project—or explain what went wrong!
  • You should also email any project-related materials (code, proofs, etc.) to Nick and I before the beginning of class on Friday.  Basically we want to push you to be done before you enter the room, so that you can stay actively engaged in your classmates’ projects.

Also a couple notes about your final writeup:

  • Most of you have received feedback about your writeup and final presentation; if not, you should see it shortly.
  • Based on this feedback, you have an opportunity to receive additional credit (achieving up to 100% of the full grade for the writeup portion of the final project) by submitting a revised version no later than 11:00pm on Tuesday, May 10 2016.

(There is of course an obvious reason we didn’t tell you about the second bullet point ahead of time: had we told you, then it would be logical to compromise on the quality of the initial draft and try to make up the points later.  Revealing this information post-submission ensures that everyone takes the initial assignment seriously!)

Finally, we would like to make your projects available for students in future years (either publicly or privately)—more information to come.

Final Project Gallery

Below you will find a few selected final projects from our course. Students were asked to pick a topic from differential geometry and explore the different ways in which it can be explained and understood form a discrete, computational perspective. Some students devised new algorithms, while others proved new results in DDG. Overall, it’s been a very fun and stimulating semester! Thanks to everyone who participated.

[Students: if you do not see your project below, but still would like it posted here, please send us an email!]


Mean and Principal Curvature Estimation from Noisy Point Cloud Data of Manifolds in \(\mathbb{R}^n\)
Yousuf Soliman

NoisyCurvatureTeaser

[Writeup] [Presentation] [Final Project] [Code]

Description: Data is often provided as a finite set of points embedded in Euclidean space. In many applications, we have reason to believe that these data points are generated from a distribution with support over a manifold, rather than from a distribution with support over all of \(\mathbb{R}^n\). In this paper, I will consider the problem of recovering the local curvature of an underlying manifold based on noisy point samples. I will then present an extension of integral invariants to submanifolds with arbitrary codimension as a methodology for inferring the curvature of point cloud data at different scales. Curvature is a widely used invariant feature in pattern classification and computer vision algorithms. Furthermore, understanding the curvature of the data gives one a better understanding of the local manifold geometry, which can then be used to better construct a sufficiently fine triangulation of the underlying manifold.


On the Conformal Maps of Triangle Linkages
(Anonymous)

KagomeTeaser

[Writeup/Final Project] [Presentation]

Description: This project studies the nature of conformal maps, particularly in connection with discrete differential geometry. The discrete model we focus on is the triangular linkage geometry introduced by Konakovic et al. Abstractly, these linkages are equilateral triangles such that pairs of triangles meet at vertices and the triangles are connected in cycles of length six. In practice, such surfaces can be manufactured from flat “auxetic” (opening) materials with slits cut in them, providing many more degrees a freedom than ordinary developable (no-cut) surfaces. We present an overview of discretization of conformal geometry, both in the traditional Lagrangian element model as well as in the Crouzeix-Raviart element model. We describe how this theory connects to the geometry of triangular linkages, laying a foundation of discrete differential geometry for these structures. Furthermore, we propose a working definition of discrete conformal maps on triangular linkages, and prove some implications.


Heat Kernel Signature
Ye Han

HeatKernelTeaser

[Writeup] [Presentation] [Final Project] [Code]

Description: I implement the computation of HKS by following the pipeline described by Sun et al, and apply it on several geometric models. The details involve computing the HKS of different feature vertices at different time step, comparing HKS of the same geometric models under isometric transformation, and comparing the HKS of different geometric models at the same scale. Examples showcase the multi scale property of HKS, where the chosen points are similar under local scale while the difference only appears at large time step.


Introduction to Spin Transformation and its Application on Shape Descriptor
Derek Liu

SpinTransformationTeaser

[Writeup] [Presentation] [Final Project]

Description: The topic of mapping shapes to different feature spaces is called shape descriptor design. The most common approach utilizes surface properties, such as curvature and geodesic distance, to construct shape descriptors. Another popular approach uses shape operators, such as Laplace-Beltrami operator to describe shape as a linear combination of basis functions. However, most descriptors were built heuristically and their performance is strongly task dependent. Which properties best represent a 3D shape? Bonnet proposed that mean curvature and metric should suffice to determine the surface generically. These two geometric objects are building blocks of conformal transformation and spin transformation in differential geometry. This article therefore aims to introduce spin transformations and their application as shape descriptors.