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.

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 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!]

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

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.

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.