It’s the last day of classes for the winter quarter here at UCI, and a good time for some spring cleaning of old bookmarked links. Probably also a good time for a reminder that Google+ is shutting down in two weeks so if, like me, you still have links to it then you don’t have long to replace them with archived copies before it gets significantly more difficult.

• ## Planar graphs needing many lines

As I said in my previous post my two SoCG papers both involved trying and failing to prove something else, and writing down what I could prove instead. For the one that appears today, “Cubic planar graphs that cannot be drawn on few lines” (arXiv:1903.05256), that something else was Open Problem 16.14 of my book, which can be rephrased as: does there exist a family of planar graphs that cannot be drawn planarly with all vertices on a constant number of convex curves?

• ## Counting polygon triangulations is hard

In some sense both of my accepted papers at SoCG are about a situation where I really wanted to prove something else, wasn’t able to, and wrote up what I could prove instead. The one whose preprint appears today, “Counting polygon triangulations is hard” (arXiv:1903.04737), proves that it’s $\#\mathsf{P}$-complete to count the triangulations of a polygon with holes.

This seems like a good time to throw in a word of appreciation for archive.org and their wayback machine for making it so easy to make permanent links to online resources that might otherwise go away, such as other people’s Google+ posts. Just search for the link on archive.org and, if it’s not archived already, it will give you a convenient link to immediately archive it. There’s one of those hiding in the links below, and more among the older links on my blog.

• ## Mutual nearest neighbors versus closest pairs

In the 1990s I published a series of papers on data structures for closest pairs. As long as you already know how to maintain dynamic sets of objects of some type, and answer nearest-neighbor queries among them, you can also keep track of the closest pair, and this can be used as a subroutine in many other computational geometry algorithms. But it turns out that many of those algorithms can now be simplified and sped up by using mutual nearest neighbors (pairs of objects that are each other’s nearest neighbors) instead of closest pairs.

Beware the Ides of February.

• ## Big convex polyhedra in grids

I recently wrote here about big convex polygons in grids, a problem for which we know very precise answers. This naturally raises the question: what about higher dimensions? How many vertices can be part of a convex polyhedron in an $n\times n\times n$ grid, or more generally a convex polytope in a $d$-dimensional grid of side length $n$? Here we do still know some pretty good answers, at least up to constant factors in spaces of constant dimension.