SoCG 2008: Day 1

A good first day for the conference: we were inside mostly, so the murderous heat didn't affect us in any real way. The conference is hosted in the business school, which is really nice and plush, like all business schools are. Of course, you have to get used to seeing scrolling stock tickers.

The most entertaining talk by far was Jeff Erickson's talk on the homotopic Frechet distance. This is a variant of the Frechet distance where you have obstacles in the space the leash is moving in, and the leash has to move continuously around obstacles (in other words, two adjacent leash positions should be homotopic). They have a polynomial time algorithm in which the main nontrivial step is showing that the set of homotopy classes of paths that can yield optimal paths is bounded.

The Frechet distance is called a man-dog distance because you can think of it as the shortest leash length needed when a man walks on one curve and a dog walks on the other. During the talk, Jeff used Marty and Erik Demaine to demonstrate the algorithm, carefully omitting to specify who was man and who was dog. For obstacles, he used two graduate students on the paper: the deeper significance of "grad student = obstacle" I will leave for the reader to ponder.

In the category of "Talk that clearly was something interesting, if only I was smart enough to understand it", was Manor Mendel's talk on p-convexity. The deeper message was very intriguing: namely, that obstructions to embedding trees with small distortion in normed spaces take the form of a kind of strong convexity of the norm.

Many other talks were quite interesting: Timothy Chan's dynamic core sets talk, Tasos Sidiripoulos's talk on "circular embeddings", a way of generalizing the well known Treemap visualization tool so that the regions are no longer necessarily long and skinny, and Ken Clarkson's talk on Johnson-Lindenstrauss projections for manifold distances.

It was a good day.

p.s Twitting was an interesting experience. I'm not sure what to make of it. It provides more instant gratification to the (few) people following along, and it didn't distract me too much during the talks (I can't say what it did to my neighbours, but I didn't get any dirty looks, so...)

It's definitely different from blogging, which is more long form (yes, it's 2008: a blog post is now officially "long form"). I'll do some more of it tomorrow, and see how it goes.