I'm always a bit more interested in what exciting problems I'm introduced to at a conference than the proof techniques used in the solution (probably partially because the best talks often don't get into the details). So here's my report back from SODA, in the form of exciting problem descriptions.
Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures by Mark de Berg, Herman Haverkort, and Constantinos Tsirogiannis - This problem was described as the "farmer's problem," the problem of determining what fields upslope might contaminate yours by draining with the flow of the water.
Shortest Non-Crossing Walks in the Plane by Jeff Erickson and Amir Nayyeri - This problem is as the title describes. The authors also consider the version in which there are polygonal obstacles. It was a nice problem and made me wonder if a variation has been solved... For public transportation networks it might be interesting to consider short walks that cross as many times as possible (or some balance of short paths and many crossings). This could probably be a variation of a facility location problem. Obviously, the polygonal obstacles would also translate in the form of neighborhoods that hate public transit and block construction attempts (or, more generously, in the form of existing buildings). Anyone know if a problem of this sort has been considered?
And here's one where I really did just like the solution...
Fast, Precise and Dynamic Distance Queries by Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, and Liam Roditty - This paper relies on a series of other nice ones about dynamic spanners and hierarchies. The first in that immediate group is Deformable Spanners and Applications by Gao, Guilbas, and Nguyen, which set up a tree hierarchy based on local distances between points in which points in the same level of the hierarchy and within some distance of each other are considered neighbors for the purpose of creating a spanner. These authors make the nice observation that the distance between points in the hierarchy whose parents are neighbors are a good approximation for the distance between their descendants. The full algorithm and proof are, of course, much more involved. (For a better description, complete with beautiful pictures, see the slides linked from Lee-Ad's homepage.)
Finally, the award for the best previous work slide goes to Maarten Loffler for his talk on the paper Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent by Maarten Loffler and Wolfgang Mulzer. While I haven't been able to find the incredible slides online, the previous work flow chart can be seen on page 2 of the paper. If I drew cartoons, I'd be able to do a nice parody tribute to this. Instead, all I have is this phd comics strip about references.
Induced Clebsch subgraphs
4 hours ago