# Assignment 3 (Written): The Laplacian

These exercises will lead you through two different derivations for the cotan-Laplace operator. As we’ll discuss in class, this operator is basically the “Swiss army knife” of discrete differential geometry and digital geometry processing, opening the door to a huge number of interesting algorithms and applications. Note that this time the exercises all come from the course notes—you will need to read the accompanying notes in order to familiarize yourself with the necessary material (though actually we’ve covered much of this stuff in class already!)

## 17 thoughts on “Assignment 3 (Written): The Laplacian”

1. Leslie says:

Could the slides of previous lectures be released? I think it will be really helpful for us to understand the surface and solve the homework. Thanks!

1. Keenan says:

I’ve already uploaded all the complete sets of lecture sides, but these should provide a lot of useful info about the Laplacian:

Swiss Army Laplacian

2. yangxio says:

Just want to bring up a point in the notes (“paper.pdf”) Chapter 6 between Exercise 20 and 21, unless it is intentional for homework: the convention for the sign of the Laplacian $\Delta$ bounces back and forth between positivity and negativity, and it is not consistent. Same issue appears in the discussion of Galerkin method (or finite element method) before Exercise 22.

1. Keenan says:

It’s not intentional; thank you for pointing it out.

3. aishwaryapawar says:

In the notes it is mentioned that Poisson problems are solved on compact surfaces without boundary. It is not clear as to why we deal with surfaces without boundary while computing laplacian.

1. Keenan says:

Because life is *so* much easier if you don’t have to deal with boundary conditions! 🙂

We may talk about boundary conditions a bit in class, but for your first time through (with this or any problem) it is generally a good idea to see if you can get things working without boundary first, then add boundary conditions (which can be confusing and error-prone).

4. yangxio says:

Section 6.3 of the course notes, in particular Exercise 26 in the notes (Exercise 9 of written Assignment 3), does not seem true to me, unless the sum of $\cot\alpha_{ij}+\cot\beta_{ij} \ge 0$, or equivalently the mesh is Delaunay. The point here is that two approaches do not give us the same formula for the Laplacian always. I understand that in practice one should use a Delaunay mesh whenever possible (at least for solving Poisson equation), but what if such mesh is impractical to generate (say dimension is greater than two or there are simply overwhelming data to deal with)? Does one cross fingers and go ahead with the cotangent formula (as deduced in finite elements) or take the absolute value (as deduced in discrete exterior calculus)? Let’s restrict the purpose to solve PDEs here so that we don’t run into the situation of different inequivalent discretizations for different applications.

1. Keenan says:

Good catch. A better way to talk about the discrete Hodge star might be to consider the ratio of oriented volumes, in which case one can indeed get a negative dual/primal length ratio. (Of course this discussion takes a bit more work…). To be clear: discrete exterior calculus also uses the cotan formula as the standard choice of diagonal Hodge star; it does not take the absolute value.

Much more importantly: negative cotans are not, in general, a problem!

One way to understand why is that the discrete Laplacian is simply the restriction of the smooth Laplacian to the space of piecewise linear functions. As a result, it will always be positive semidefinite, even if individual cotans are negative. (Think: a matrix with negative entries can still be positive-(semi)definite).

The main thing that *might* be lost is something called the maximum principle. There is a very nice discussion of this fact in the paper Discrete Laplace Operator: No Free Lunch. We will talk about this a bit in class as well.

5. apoorva says:

I think the notation in Exercise 24 is ambiguous. When we take the inner product of $\nabla\phi$ with itself, do we treat is as a vector or as a function (i.e. are we just saying what the inner product should be at each point or are we integrating it)? From the expected result, I’m guessing it’s the latter (i.e. we integrate its inner product with itself over the triangle), but the notation is not clear.

1. anobani says:

as far i understand, you can reason on it as dot product. in the previous question we proofed that $\bigtriangledown \phi = \dfrac{e^{\perp}}{2A}$, thus as dot product you can think about it as the dot product between the 2 perpendicular edges $e^{\perp}$ divided by the total area factor as a scalar. i hope this helps

2. Josh says:

Yes, the inner product is an integral over the whole triangle. This was clarified in Thursday’s lecture.

6. anobani says:

in question 25, $\langle \bigtriangledown \phi_i, \bigtriangledown \phi_j \rangle = – \dfrac{1}{2} cot \theta$.

should it be (negative) ? when i am solving it it, i can’t reason on the negative sign, i am having a positive value, unless there is something i am missing. thought to ask just to double check .

1. Josh says:

I think the sign convention in the notes is correct. You might need to use the fact that $\cot \alpha = -\cot (\pi – \alpha)$.

7. jimola says:

Exercise 18 asks us to informally argue why the only functions in the kernel of the Laplacian are the constant functions. However, using the definition of the Laplacian as the sum of the second partial derivatives, shouldn’t any linear function have zero Laplacian? I must be missing something here…

1. Josh says:

The question assumes that the function is on a compact surface without boundary (e.g., the surface of a sphere). A linear function (except for a constant function) is not harmonic since we are using the Laplacian induced by the surface. Does that make sense?

8. intrepidowl says:

For the triangles in Exercise 24 and 25, does the area happen to be 1? The derivations I’ve been working through are hinging on this proposition, which I haven’t been able to prove.

Could someone provide a hint to the proof if this is true, or a hint in the opposite direction/a different direction to pursue if this is false?

1. Josh says:

I think your problem may be how you are interpreting the inner product. The inner product is an integral of the dot product over the whole triangle. (My guess right now is you are taking a point-wise dot product.)