The 25th ACM Symposium on Computational Geometry just finished yesterday. Suresh has already reported on the pre-conference historical review of computational geometry, but I thought I'd mention a few highlights of the conference itself.

One strong theme this year concerned epsilon-nets and geometric set cover problems. An epsilon-net for a weighted set \( S \) of \( n \) points and a family \( F \) of shapes is a set \( N \) such that every shape in \( F \) that contains at least an epsilon fraction of the total weight of \( S \) has a nonempty intersection with \( N \). When F consists of shapes with constant description complexity, one can find epsilon-nets with cardinality 1/epsilon times some more slowly growing function of epsilon, and the growth rate of this function controls the quality of certain approximation algorithms for geometric set cover problems (or their dual hitting set problems) in which one finds a small point set that hits all shapes in \( F \) by choosing an epsilon-net, doubling the weights of the points that would hit some unhit set, and repeating until finding an epsilon-net that hits everything. Varadarajan described the relation between this more slowly growing function and the combinatorial complexity of unions of shapes in \( F \); similar results were obtained independently (at STOC 2009) by Aronov, Ezra, and Sharir, who had a paper at SoCG about speeding up the hitting set algorithms. Bukh, Matoušek and Nivasch had a paper on lower bounds on the size of weak epsilon-nets; normally a net must be a subset of the given points but in a weak epsilon-net this constraint is lifted. Mustafa and Ray showed that the epsilon-net approach to hitting sets is not always best: it can be replaced in some circumstances by local search algorithms that provide much more accurate approximations. Miller and Sheehy had a nice derandomization of some old work of mine on centerpoints, which are essentially single-point weak epsilon-nets. And Ken Clarkson spoke about generalized set cover problems in which some points need to be covered by multiple sets; he and his co-authors showed that many of the epsilon-net-based set cover approximations work in this more general setting.

Along with the invited talk on the computational geometry of origami by Robert Lang, there was an "origami session" that featured a proof by Katoh and Tanigawa of the "molecular conjecture" that frameworks of flat rigid panels with hinges (not unlike a piece of origami in the process of being folded) behave generically like more general rigid bodies with hinges, and a proof by Panina and Streinu that, if you cut a wedge from a piece of paper and fold it so that all the fold lines pass through the vertex of the wedge, then any configuration of the folded paper can be reached from any other configuration.

This year I supervised an undergraduate doing a project on watershed boundaries, so I was interested to see the work of van Kreveld and Silveira on river networks. Their problem is one of integrating two types of data, high resolution maps of river networks (showing only their \( x \) and \( y \) coordinates) and lower-resolution elevation maps. They describe methods for modifying the elevation map so that it makes sense with respect to the river that is supposed to flow over it: the water should flow where it actually does flow (that is, the river's elevation should consistently decrease) and it shouldn't flow where it doesn't (the banks of the river should maintain a higher elevation than the river itself).

Metric embedding is a subject that has been surprisingly absent from SoCG in the past — it's more popular at FOCS/STOC/SODA despite its geometric flavor — so it was good to see some of it this time. Borradaile, Lee, and Sidiropoulos described a randomized embedding from genus-\( g \) graphs to planar graphs in which the expected dilation of any distance is \( O(g^2) \), a big improvement over the previous exponential bound. On the other hand, the best lower bound for this problem is logarithmic in \( g \), so there may be another exponential improvement to be made. Chin, Guo, and Sun also described a hardness result for finding a smallest subset of the Manhattan plane containing the same shortest paths connecting a given set of points as the whole plane; this isn't the tight span (or orthogonal convex hull) because it doesn't require points outside the given set to be connected by paths.

There were lots of other interesting papers, so if I didn't mention yours you can safely assume that it's because I ran out of energy for writing this post rather than because I didn't like it.

Lars Arge did a great job of organizing, and especially in organizing the food. The reception buffet never ran out, the banquet featured a whole roast boar among an impressive spread of other foods, and the daily lunch spread was almost as impressive. I can't claim a very strong performance in the go-kart race excursion after the conference, but it was a lot of fun too.

All in all, a good conference.