More from CCCG

As I suspected in my previous post from the Canadian Conference on Computational Geometry, Tuesday went by in a bit of a blur after my own talk on regular labelings (the slides for which are now online here). So though I enjoyed several of the talks I went to I don't think I am ready to write at length about any of them.

I skipped the business meeting, but I heard later that it was unusually contentious this year. One issue that attracted a surprising amount of attention: should papers be allowed to appear both at EuroCG and at CCCG? Both conferences have only short (four page) papers, both publish a collection of their papers online and/or as a printed handout to attendees, both accept most but not all of their submissions (I think the acceptance rate for CCCG this year was around 70%), but somehow EuroCG gets to declare that its publications are not a real proceedings, allowing EuroCG papers to be sent to other selective conferences, while publication at CCCG prevents the same paper from being presented elsewhere. The net effect is that good papers that might be sent to SODA or SoCG (especially in years when SoCG is not in Europe) may also show up at EuroCG, while CCCG consists more of papers that are too small to make the cut at the more selective conferences. But I have to confess that I don't understand what this "not a real proceedings" thing means when the EuroCG looks like the CCCG proceedings in all ways except for its name.

Wednesday morning presented me with a tough choice of two parallel sessions both of which I wanted to go to, including two talks on straight skeletons unfortunately scheduled opposite each other. I ended up going to the more theoretical of the two, an O(n log n) algorithm for straight skeletons of monotone polygons. There was some question at the talk about whether one of their main lemmas (showing that certain of the events that happen over the course of the algorithm all involve features from both sides of the polygon) was correct, but I think it may be. The same session also had a nice talk by Bill Steiger involving applications of a continuous variant of Tukey depth contours to the statistical properties of convex hulls of random point sets (Steiger is one of the last holdouts using overhead transparencies instead of computer projectors), a very entertaining talk on polyhedron unfolding by Marty Demaine, Anna Lubiw, and their three children, and an intriguing attempt by Ryuhei Uehara to apply complexity-theoretic concepts to the analysis of the set of folded states of a 1xn rectangular polyomino the edges of which are labeled with mountain and valley folds. Uehara views the number of layers of paper inside any fold as being analogous to space complexity, and asks for folded states that minimize this quantity.

The third David (Kirkpatrick)'s invited talk Wednesday was on some interesting questions involving distances in arrangements of circles. One can define the distance between two cells of the arrangement in three different ways: the number of circles that contain one cell and do not contain the other (let's call this "containment distance"), the minimum number of times one has to cross a circle on a path from one cell to the other ("thickness"), and the minimum number of circles one has to cross on a path from one cell to the other ("resilience"). Containment distance and thickness are easy to compute, but resilience is both more significant (it measures the robustness of a set of sensors that are supposed to detect moving objects crossing some region of the plane) and more difficult to compute. To make one of many possible connections to Avis' talk, when every two cells have thickness equal to their containment distance, the dual graph of the arrangement can be isometrically embedded into a hypercube, and in this case the thickness also equals the resilience. The work Kirkpatrick spoke about was based on a paper by Kumar et al, which showed that for unit disks in a rectangle, the thickness and resilience are equal for paths between two uncovered points on the top and bottom of the rectangle. More, in this case, the thickness is the same as the number of "barriers", disjoint sets of disks that form chains connecting the left and right sides of the rectangle. For less restricted pairs of uncovered points in the plane, this nice equality is no longer true, but as Kirkpatrick described, it is still possible to use thickness as a constant factor approximation to resilience.

There were probably as many good talks that I saw but haven't posted about as those I have, and I'm sure at least as many that I didn't have to see. It was a very enjoyable conference, definitely enough to make me want to find an excuse to come back for future offerings.

Comments: