Three talks at SOCG

I just came back from a lovely trip to Rio de Janeiro for SOCG. This year's meeting was quite a bit busier than usual, with three different presentations lasting in total almost three hours. In order of increasing importance:

• On Monday morning, I presented my paper "Efficiently hex-meshing things with topology" (slides). The paper answers the following question: When can a polyhedron with quadrilateral faces be partitioned into a complex of topological cubes, without refining the boundary? It is not hard to see that the number of quads must be even. For even surface meshes, I prove that the following equivalent conditions are necessary and sufficient:
  • No odd cycle in the surface graph is the boundary an immersed surface in the interior.
  • The dual of the surface graph is the boundary of an immersed surface in the interior.
  The paper says "null-homologous" instead of "the boundary of an immersed surface", but these two phrases are synonymous. This generalizes earlier results by Thurston and Mitchell for polyhedra with genus zero, where an even number of quads is sufficient, and by Eppstein for bipartite surface meshes, which always have an even number of facets. The proof is constructive.

• On Monday afternoon, in a fantastic workshop on mesh generation organized by Marcelo Siqueira, I gave a one-hour survey talk on theoretical hexahedral meshing (slides). The first chunk of the talk establishes some basic definitions, which are usually left unstated by both computational geometers and mesh generators. In particular, in actual hexahedral finite-element meshes, the word "hexahedron" does not mean a convex polyhedron with six planar facets, but the multilinear hull of eight labeled points; the facets of a "hex element" are ruled surface patches. There are lots of good practical heuristics for building hex meshes, but no fully automatic methods, or as I usually call them, algorithms. If we allow boundary refinement, hex meshing is actually easy — just triangulate and then refine each tet into four hexes — but only if we don't care about mesh quality. If we don't allow boundary refinement, even the existence of hex meshes is a more subtle open problem, leading to lots of interesting geometry and topology, but again, even where we have algorithms, we have nothing with useful quality guarantees. The big open problem is to define a general class of input domains, define a useful quality measure, and then describe an algorithm that provably generates a high-quality mesh for any domain in the class, as Bern, Eppstein, Ruppert, Shewchuk, and many others have done for triangular and tetrahedral meshing.

• Finally, on Tuesday evening, I ran my first SOCG business meeting as steering commitee chair. David Eppstein's official minutes and the complete meeting slides (mirror) are now available on www.computational-geometry.org, but here are some highlights:
  • There were 150 attendees, which is less than Paris in 2011 and Chapel Hill in 2012, but more than the six years before that. Thanks to incredibly low student registration fees, there were 66 registered students.

  • The Best Paper award went to Victor Alvarez and Raimund Seidel, for their excellent paper "A simple aggregative algorithm for counting triangulations of planar point sets and related problems".

  • The video and multimedia committee raised the awesomeness standard for submissions. They also distributed this year's videos much more widely, not only on the SOCG web page and in the Digital Library, but also on YouTube and at imaginary.org.

  • The SOCG 2014 PC chairs are Siu-Wing Cheng and Olivier Devillers.

  • Starting with Victor and Raimund this year, SOCG Best Paper Award winners will be invited to submit a full version of their paper to Journal of the ACM.

  • Starting next year, we expect to offer NSF travel support to SOCG for US students and postdocs.

  • There was strong support for the idea of co-locating SOCG with STOC in 2016, moderated by lots of pertinent logistical questions. I said "I don't know yet; we'll have to work that out" a lot.

  • SOCG 2015 will be held at TU Eindhoven, in the Netherlands. The other bidders, which all tied for second place in the first voting round, were Braunschweig, Germany; Brisbane, Australia; and Portland, Oregon.

  • There will be a third and final vote regarding the future relationship between SOCG and ACM, which will take place in October. I've set up a discussion blog, where I will describe issues related to the vote. I will also invite posts from other members of the SOCG community, ACM representatives, and organizers of other conferences. My goal is to ensure that all relevant stakeholders have a voice before voting begins.

  Whew!

  One important item was not announced at the business meeting. The Best Student Presentation award was shared by two students:

  • João Peixão, for his presentation of "Parameterized Complexity of Discrete Morse Theory"
  • Luis Barba, for his presentation of "Bichromatic Compatible Matchings"

  These two winners were announced Thursday morning, after all student speakers had presented their papers. The award is based on audience evaluations.