Thursday, June 12, 2008

SoCG 2008: Invited Talks

A Discrete Laplace-Beltrami Operator

Alexander Bobenko gave the first invited talk at the conference. As with Mathieu Desbrun's talk from a few years ago, this talk was on the area of 'discrete differential geometry', particularly focusing on a discrete Laplace-Beltrami operator, and how to compute Delaunay triangulations on polyhedral surfaces.

The general principle behind efforts in discrete differential geometry is quite apropos for a CS audience. Rather than doing a 'numerical discretization' of differential geometry to enable computations, the idea is to discretize the entire theory, so that the continuous theory emerges as the limit of the discrete theory.

This goes against the flow of much of what we often see in discrete computer science, where the idea is to relax to an underlying continuous domain in order to learn things about discrete structures. It also makes a lot of sense, because if successful, it gives a 'native' version of differential geometry that's naturally robust without having to worry about the level of discretization etc.

The slides are quite readable on their own, and I'd recommend that anyone who's interested take a look. In summary the idea is this. Given a function on a manifold, you can write down an energy operator (called the Dirichlet energy) such that the gradient of this energy is the Laplace-Beltrami operator on the manifold.

If you do this for piecewise linear functions defined on a simplicial surface in 3-space, then you get an expression for the Laplacian: however, this expression is not intrinsic (it depends on the embedding of the surface in 3-space). In the world of differential geometry, being intrinsic is the whole point, so this is not a happy state of affairs.

It turns out that if you use a triangulation of the surface constructed by using an 'intrinsic Delaunay triangulation' (more on that in a second), and then define an interpolation for a function on the vertices in the usual manner, then the resulting energy function is minimal, and the Laplacian you get *is* intrinsic. An intrinsic Delaunay triangulation is constructed much like you'd construct a regular Delaunay triangulation, with the caveat being that you might have to use geodesics on the surface as "edges" of the triangles, and some triangles might end up being degenerate (so it's not a "normal" triangulation).

But in any case, doing this allows you to work with a well-defined Laplace operator on a discrete structure, and the second part of the talk showed how you can construct discrete minimal surfaces using such an operator.

Geometry is Everywhere (part XLVII)

Ken Clarkson gave the second invited talk, which was a romp through the world of metric spaces and the various notions of dimensions used to describe them. Ken doesn't yet have talk slides online, but somewhere in the union of this, this and this is much of the talk material. The main premise was to weave together different notions of dimension for a metric space, and how they can be used to do geometry in the abstract. If I'm not giving more details, it's because the talk covered so much ground that it's hard to know where even to start. It was wildly entertaining though, and there was a general clamor afterwards for Ken to write a book on this topic (which I hope he does).

And the "47" ? A cryptic shoutout to Pomona College alumni: if you're one, you probably understand the reference.