A paper uploaded to the arXiv this evening by Anna Lubiw and Vinayak Pathak just caught my attention. I think the title speaks for itself (always a good thing for a title to do): Flip Distance Between Two Triangulations of a Point-Set is NP-complete. The proof doesn't look very hard, once you see it: a standard gadget-based reduction to a variation of the problem for polygons with holes, together with another reduction from polygons to point sets that consists of protecting the polygon edges with layers of triangles that would be too expensive to flip through.

Although it's a big step forward, the paper still doesn't resolve the question of how hard it is to compute flip distance between triangulations of a convex polygon. This remains as a big open problem, one of a small number of natural problems neither known to be polynomial time nor known to be NP-hard.