Monday, June 14, 2010

SoCG, Day 1



I'm here in beautiful, cold, Salt Lake City (or really, in Snowbird, a ski resort in the mountains above the city) for the Symposium on Computational Geometry. So far, it looks like it's going to be a great conference.

I don't know if the first session was purposefully packed with excellent talks, or maybe it just happened to be a session I was interested in, but not only were the results interesting, the talks were good too. Some highlights:

Optimal Partitions Trees and Tight Lower Bounds for Halfspace Range Searching:

Timothy Chan presented a new data structure for range searching with essentially the same bounds as a previous structure by Matousek (aside from preprocessing costs), but which has the important properties of being simpler (implementations possible!) and being based on a multilevel partition tree approach, which is useful for many applications. In fact, this upper bound was shown to be matched later in the session by a lower bound requiring this partition tree approach. David Mount presented that joint paper with Sunil Arya and Jian Xia. (Another connection between the two talks was the levity provided by Dave's attempt to open a Mountain Dew bottle in the middle of Chan's talk - a bottle I suspect was purchased at the bottom of the mountain and then driven up 2000 feet, thus providing for an explosive change in pressure...)

Consistent Digital Line Segments:

This talk provided, for me, an introduction to a really beautiful problem I had never thought in depth about before. The problem is essentially about defining methods for drawing digital lines (lines that are drawn with pixel paths) that are consistent with underlying geometric axioms - ideally axioms that define the important pieces of the intuition about lines that we have taken from Euclidean geometry, for example, two lines should intersect in only one place. It's a nice problem (and solution) that seems to go to the literal heart of computational geometry.

The Geometry of Flocking:

Chazelle presented a continuation of his work on natural algorithms, with a focus on bird flocking. I've written about this line of work a bit already, and don't have much more to say, but I'm looking forward to hearing another talk by him later in the conference.

Discrete Geometric Structures for Architecture:

The invited talk today was by Helmut Pottmann of the Geometric Modeling and Industrial Geometry group at Vienna University of Technology. I must admit, I was skeptical of a talk by a non-geometer, but it was excellent. It was about modern "natural" architecture (like the picture above that I stole from the group page), a style in which architects eschew the traditional lines and right angles of buildings in favor of a more curved appearance. He spoke about types of meshes that could work with these design concepts. I can't do the talk justice here, and I do hope that he puts the slides online.

Lunch today featured the student meet-up that was discussed after the 2008 SoCG, forgotten for awhile, and revived by Suresh in an email to me last week. In other words, it took very little organizational effort - Suresh made an announcement this morning that any interested students should meet outside the conference room at lunch time. Then we all went to a deli, got sandwiches, and took them to a room to eat. About 8-10 students showed up (though we lost some to the need to change rooms to sit down to eat) and it was nice to sit and chat. Thanks folks for showing up and thanks Suresh for making this happen! I hope it continues at future SoCGs - it's certainly worth the effort.

Finally, the business meeting was relatively uncontroversial. SoCG 2012 will be at UNC Chapel Hill (the only bid). If I remember correctly, attendance this year is somewhat down at 105 (compared to about 135 last year and 141 the year before in Maryland). Student attendance is correspondingly down to 28 from about 45. (So getting 8-10 students at the informal lunch is actually pretty good!) All numbers may be somewhat made up since I didn't write anything down. There was some encouragement from the current PC chair to continue the not-actually-a-rebuttal process next year, but no guarantees. Next year in Paris!

No comments: