On Monday, a bunch of us had hiked out to the Bell Rock, a rather large bell-shaped rock near the hotel. On Wednesday (I was too cowardly to brave the elements on Tuesday), we decided to climb as far up the rock as we could go. Lest you think that I am some kind of rock climbing savant, I will assure you that no such thing is true. The rocks were rough enough and the trails well marked enough that we could get pretty high up without needing technical apparatus of any kind.
Here, in all its beauty, is Bell Rock:
From this angle, it's hard to explain how high we got, but it was high enough :). It started raining as we descended. The rocks proceeded to get very slick, but in every other way the rain was highly welcome. The rest of the morning was pleasantly cool as a result; so much so that it was hard to stay indoors and attend the first session.
Even though it was day 3 of the conference, which usually means my brain is fried and I am longing to return home, I really wanted to attend the first session. You see, this session was one of many on the burgeoning area of computational topology, a topic that now has a significant presence within computational geometry.
In a sense, there is no surprise that computational topology has become an important area. One of the main application areas of geometry is the understanding of shape, whether it be the triangulated meshes that constitute shapes in an animation, or the intricate surfaces induced by electrostatic forces at the surface of a protein molecule.
Topology provides much of the underlying mathematics of shape. Not all of it: metric properties of the shape are obviously important. But a good deal of it. A classic example of this is the following question:
given points sampled from a shape, under what conditions can I reconstruct a shape that is geometrically and topologically similar to the original shape ?Many results over the years have attempted to answer this question via "sampling criteria" of the form, "if you sample points so that they satisfy some condition SC, then there's an algorithm that will correctly reconstruct the shape within some error bounds". The goal is to get as relaxed conditions SC as possible, given that we often don't have control over the sampling process.
Much work at this year's SoCG was on new sampling criteria and new ways of representing the medial axis (an important structure that acts as a kind of "skeleton" of a shape). In other words, the mathematics and the algorithmics of reconstructing shapes.
Another thread of work is on a notion called 'persistence'. Persistence is a little tricky to define intuitively (and I strongly recommend Afra Zomorodian's excellent monograph), but the basic idea is that you first create a sequence of evolving structures for a shape. One example of this could be the level sets of a terrain as you increase the "level". Then, you look for features that are "long-lasting", or "persistent" within this sequence. Such features are likely to be more permanent parts of the shape, and can be used to identify key parts of the shape. Much work has now gone into computing persistence, doing it in a stable fashion, and trying to generalize it in various settings.
In general, persistence is a way of identifying important elements of a shape, and can often be a "subroutine" in higher level topological analysis of shape.
A third thread that's somewhat distinct from the above, but deals squarely with "algorithmic topology" is exemplified by work on computing paths on shapes of different topological characteristics. Applications of this work are less immediate, but one can imagine using such algorithms to deal with the manifolds generated via surface reconstruction etc. I'm sure Jeff Erickson has more to say about this.
To work in this area, you need a very good grasp of topology (combinatorial, algebraic), some Morse theory, and of course good algorithmic and geometric intuition. The first two topics are not usually covered in a graduate degree in algorithms, and that makes this field a bit harder to get into, but its ranks are growing.
Computational topology is definitely a new and challenging direction in geometry. I wouldn't be surprised if it ended up having its own conference sooner or later: I hope not though. The cross-fertilization between topology and more traditional computational geometry is one of the more interesting trends in the field right now.
No comments:
Post a Comment