My travels (and the lack of decent internet connectivity in Crete) caused me to be remiss in blogging about some future theory events. First, the list of papers to be presented at SODA 2009, in New York City January 4–6 next year, is here. A very welcome innovation this year is the inclusion of abstracts with the titles.

I've already mentioned my accepted paper with Elena Mumford on self-overlapping curves. I also have another one in the list, with Mike Goodrich and Mike's student Darren Strash, “Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings.” The problem concerns the construction of the arrangement of line segments: this can be solved in optimal \( O(n\log n + k) \) time for \( n \) segments with \( k \) crossings in the general case, but we were looking for faster algorithms when more about the input is known. Specifically, we assume that the input is a connected graph of line segments for which one already knows the cyclic order of segments around each common endpoint; an important special case of this is dealing with self-crossing polygons. It was already known how to find all crossings in linear time when \( k \) is a little bit larger than \( n \); we show the same thing when \( k \) is a little bit smaller than \( n \). The case where both numbers are the same order of magnitude remains open. We should have a preprint version ready in a few days.

Finally, the call for papers for SoCG 2009, to be held in Aarhus, Denmark, June 8–10, is out. Titles and abstracts are due by November 24, with the actual submission deadline December 1.