SODA roundup

Now that I'm back from SODA, I guess it's appropriate for me to post a recap of some of the more memorable parts of it for me.

I don't really want to talk in detail about elevator scheduling algorithms, crowded stretch limos with mirrored ceilings and mysteriously absent return rides, ants on the 14th floor, shorting crooked cabdrivers, rose-flavored gelato and Peruvian musicians, forgotten laptop power adapters, new sunglasses, and drawbridge stunt helicopter explosions. So you'll have to use your imagination for those parts.

As usual, it was good to see so many old friends and meet some new ones as well. I'm not sure why but I had less of the feeling that I sometimes do at SODA, of being lost in a sea of people none of whom I know. Since I'm blogging, I'll just single out some bloggers here — besides Jeff and Suresh, of course, and Scott "Shtetl-Optimized" Aaronson at the STOC PC meeting, it was a pleasant discovery to find that [Lowerbounds, Upperbounds] is not just a CMU talk announcement and LaTeX tip board, but also a person by the name of Maverick. We had an interesting discussion involving, if I remember correctly, DSLR photography, the view from Phil's penthouse, lost cell phones, and the gender of the Winnie the Pooh characters (apparently Piglet is female in the Chinese movie dubs). I also spoke with a mystery blogger who, in order to remain incognito, is avoiding such obvious subjects as algorithms, Borges, and his recent trip to Antarctica, in favor of posts on hair color. A good strategy, I guess, since searches for that subject hide his blog among those of thousands of teen girls. (ETA: Found by Suresh.)

There were too many good papers for me to pick out any one as a favorite, but there were a couple of subject areas where I particularly enjoyed the small number of papers in the area and wished there were more (I guess this means I should try harder to write some myself...). First, two papers that I saw dealt with computational topology: representing surfaces (or higher dimensional manifolds, but these ones were about surfaces) as abstract complexes of cells, and solving algorithmic problems for these complexes. Jeff Erickson had a nice paper with Éric Colin de Verdière on continuously deforming a curve on such a surface to the shortest possible topologically equivalent curve. The proof involved cutting the surfaces along crossing geodesics into octagons, passing to the universal cover (the {8,4} tiling of the hyperbolic plane), and showing that one could limit the search to a linear number of octagons in this tiling. Sergio Cabello's paper on planar shortest paths (using techniques related to separator based sparsification) seems on the face of it to be purely a graph algorithms paper, but it's really on a very similar problem to that of Erickson and Colin de Verdière: finding the shortest possible nonseparating cycle on a topological surface. The connection between this topological problem and planar graph shortest paths comes from a previous paper by Cabello and Bogdan Mohar.

The second area I wanted to highlight is that of data structures for low dimensional geometry. There were two very interesting papers in this area that both involved the geometry of three-dimensional convex hulls. A convex hull and associated point location data structure can be used in a straightforward way to answer certain range queries: is there any data point in a query halfspace of \( \mathbb{R}^3 \)? Kaplan and Sharir had a nice convex-hull based data structure for a similar but more informative query: what is the approximate number of data points in a halfspace? The method involves a trick of Edith Cohen: if you assign a collection of objects random keys in the interval \( [0,1] \), and search for the minimum key in a range, then ranges with more data points in them are likely to have smaller minimum keys, so by repeating this minimum key search with different random assignments you can estimate the range size. But this random minimum key problem is basically the same as point location in some intermediate state of a randomized incremental convex hull construction algorithm, so a point location structure used for that algorithm lets one handle the queries efficiently. Also in this area, Timothy Chan showed for the first time that one could maintain a dynamic 3d point set with queries that seek extreme vertices of the convex hull in polylogarithmic time per update or query, improving an \( O(n^{\epsilon}) \) bound by Agarwal and Matousek in 1992. Chan's data structure improves the times for a big collection of other dynamic geometry problems including the post office problem, diameter, width, bichromatic closest pairs, minimum enclosing disks, and minimum spanning trees. The technique is still a little complicated, though, involving machinery such as shallow cuttings, and the polylogs have high exponents, so there's plenty of room for improvement.

Comments: