This guest post on CCCG 2010 is by CR reviewer Joseph O'Rourke, Professor and Chair of the Computer Science Department at Smith College.
The superbly organized 22nd annual Canadian Conference on Computational Geometry (CCCG 2010) was held August 9-11, 2010, at the University of Manitoba in Winnipeg, Canada. As usual, the talks were informal, with participant questions interrupting the (often student) speakers. And following a long tradition, there was intense activity surrounding open problems posed at the conference. All sessions were parallel, so I missed half of them. And, in any case, no summary of the wide variety is possible. Instead, I will focus on four personal favorites.
Coauthors of the famous Komei Fukuda (H. Miyata and S. Moriyama) reported on an impressive effort to complete enumeration of small oriented matroids. To cite one result, they established that there are exactly 47,923 5-dimensional polytopes with 9 vertices. The database of polytopes they have established should prove very useful for exploring conjectures, for example, concerning f-vectors of d-polytopes. Their calculations required two months on 64 machines, each with 64 cores!
There were three distinguished invited speakers—David Avis, David Eppstein, and David Kirkpatrick—but I will concentrate on the middle David. He showed that there is a generalization of “Schnyder woods” to regular labelings of graphs deriving from three distinct geometric classes: grid triangulations, rectangular subdivisions, and orthogonal polyhedra. In each case, it is possible to obtain if-and-only-if characterizations that capture the class by coloring and orienting the edges of the graph. This leaves the high-level open problem of discovering what unifying principle explains the close relation among these three different labelings.
A more focused open problem was raised in a paper presented by Filip Morić on behalf of his coauthors R. Fulek, B. Keszegh, and I. Uljarević. Let there be n red and n blue points in general position in the plane. They established that there is a simple polygon that separates red from blue that is composed of between n and 3⌈n/2⌉ edges. The open problem is to close the gap. Filip conjectured that their upper bound may be closer to the truth.
An unusual five-person presentation by a father and son (Martin and Erik Demaine) and a mother and her two sons (Anna Lubiw and Jonah and Arlo Shallit) explored zipper unfoldings of convex polyhedra. At one point in the presentation, Arlo emerged from a zippered box! They showed that all the Platonic and Archimedean solids have Hamiltonian paths along their edges, which, when cut, unfold the surfaces without overlap. They raised the intriguing question of whether every convex polyhedron has a Hamiltonian path, not necessarily along edges, which similarly unfolds the surface without overlap.
More than a third of the open problems presented at the 2009 conference were either completely or partially solved by the 2010 conference, and we can hope for a similar success rate with this year’s suite of problems.
Above photo from http://www.cs.umanitoba.ca/~cccg2010/
Comments