I’m at Carleton University in Ottawa, Canada, where the 29th Canadian Conference on Computational Geometry has just ended. CCCG long ago outgrew its initial we’ll-accept-anything reputation (recent acceptance rates for contributed submissions are more like 66%) and there were a lot of interesting talks, fewer than half of which I could see because of the double session scheduling. I already posted about my own talk; here are a few other idiosyncratically-selected highlights:

  • Joseph O’Rourke proved (with Anna Lubiw) that, in a non-obtuse triangulation of a convex region in the plane, every vertex can reach every other vertex by a path whose edge angles stay within a 90° range (arXiv:1707.00219). Joe is using this to attack the polyhedron unfolding problem: based on this he shows that, for polyhedra with acute triangulations (acute enough that they project to nonobtuse on a plane), the nearly-upward-facing triangles can be unfolded into a polyhedral net, so the whole polyhedron can be unfolded into a constant number of nets.

  • Another of the earliest talks in the conference was the one originally scheduled last, by Therese Biedl on drawing trees with straight-line edges of fixed slopes. If you allow edges that are vertical or in either of the two diagonal directions, any tree can be drawn, both upward (parents above children) and order-preserving (left child to the left of the right), in a very narrow column, only of width proportional to the square of the Strahler number of the tree. However, if we allow horizontal but not vertical edges, complete binary trees must have nearly-square-root width, because their height can be at most \(O(\log n)\) times their width and otherwise the area would be too small for the number of vertices. It is open whether every binary tree can be drawn with sublinear width.

  • Thursday morning’s invited talk was by Erin Chambers, with a survey “Burning the Medial Axis” on skeletonization. The medial axis can be defined by the “grassfire transformation” in which one sets fire to the boundary shape, lets it burn at constant speed away from the boundary, and keeps track of the points reached by the fire from more than one direction. When the given shape is simply connected in the plane, it is a tree. Similarly, she suggests to set fire to this tree at its leaves, with the fire going out when it reaches a point adjacent to two or more unburned branches, and keeping track of how long the fire takes to reach each point. The result is a natural and well-behaved measure of the significance of each branch of the tree, and its maximum is a nice central point within the given shape. Unlike many of the things you would want to do with medial axes, this all generalizes well to higher dimensions.

  • Despite the application-specific title of “Range Assignment of Base-Stations Maximizing Coverage Area without Interference” (arXiv:1705.09346, by Acharyya, De, Nandy, and Roy), it’s actually on a topic of great interest to me. Unfortunately I learned this too late to see the talk. Last year at CCCG I spoke about choosing circles with fixed centers to maximize the sum of radii. What they study is a more-natural but also more difficult variation, maximizing the sum of areas. As they show, this problem is \(\mathsf{NP}\)-hard. The algorithm from my paper last year approximates it to within half of the optimal area, and the new paper also provides a polynomial-time approximation scheme for it.

  • Saeed Mehrabi spoke in the parallel session to the coverage area talk about a very similar problem, placing non-overlapping rectangles with fixed corner positions within a larger bounding box to maximize the total area (with Biedl, Biniaz, and Maheshwari). If the fixed corners are all on the bounding box boundary, the solution involves at most four rectangles, and omits only a small rectangle within the bounding box, allowing it to be found in linear time if the boundary ordering is known.

  • The best student talk award went to Patrick Schnider for a talk I again missed. His work, with Luis Barba, has the colorful title “Sharing a Pizza”. It extends the ham sandwich theorem by showing that any four planar regions (or mass distributions) can be simultaneously bisected by two lines. (It doesn’t work to just use two ham sandwich cuts on two pairs of the regions; the two lines partition the plane into two double wedges, each of which must have exactly half of each region.)

  • Stefan Langerman presented the Ferran Hurtado Memorial Lecture this morning. It was mainly about polyhedra (and related surfaces) that can be unfolded into shapes that tile the plane, and he made it memorable and entertaining in part by handing out props (paper, tape, and scissors) for the audience to use in constructing these polyhedra and then unfolding them.

All papers are in the full proceedings and are linked individually from the conference program.