0
$\begingroup$

I am starting to learn about the laplacian operator $\Delta = \nabla \cdot \nabla\phi(p)$

Which can be described as the divergence of the gradient of a scalar function $\phi$. This is equivalent to the sum of the second order partial derivatives of the function.

However, it seems its graph equivalent is just the sum of the differences of adjacent vertices. Am I reading that right? In my head that should be equivalent to the first order partial derivatives, not the second order ones.

(I didn't know whether to ask here or in math, I decided here is more relevant because this is in the context of geometry processing)

$\endgroup$
2
$\begingroup$

You can see why the sum of differences is giving a second derivative if you look at the derivative of a one-dimensional function $f$. The derivative of $f$ at $x_0$ is $$ \frac{df}{dx}(x_0) \approx \frac{f(x_0 + dx) - f(x_0)}{dx} $$ The second derivative is then \begin{eqnarray*} \frac{d^2f}{dx^2}(x_0) &\approx& \frac{df/dx(x_0) - df/dx(x_0-dx)}{dx} \\ &\approx& \frac{\left(f(x_0+dx) - f(x_0)\right) - \left(f(x_0) - f(x_0-dx)\right)}{dx^2} \\ &=& \frac{\left(f(x_0+dx) - f(x_0)\right) + \left(f(x_0-dx) - f(x_0)\right)}{dx^2}, \end{eqnarray*} i.e. the sum of the local differences, scaled by a distance factor $dx^2$. In a graph Laplacian, you don't have any distances, just graph connections, so it's just the sum of the local differences.

When working on meshes, though, we typically want to take the geometry of the mesh into account. There are many ways to do this, but the most popular seems to be the cotangent Laplacian, where the local difference for each edge is weighted by the sum of the cotangents of the angles opposite that edge.

| improve this answer | |
$\endgroup$
  • $\begingroup$ You've written out a finite difference Taylor expansion approximation that is valid on a regular grid. And while it gives some intuition, it doesn't answer the question imo. $\endgroup$ – lightxbulb Aug 13 at 12:09
  • 1
    $\begingroup$ I figured that an intuition as to how a sum of differences represents the second derivative was the required level here. The answers to this recent MathOverflow question go far more in depth as to what a graph Laplacian is and what it represents. $\endgroup$ – gilgamec Aug 14 at 8:15
  • $\begingroup$ This is a great answer. Thanks for linking it for completeness. $\endgroup$ – lightxbulb Aug 14 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.