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

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.

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

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

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 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, …).