We study the flip graph of higher order Delaunay triangulations. A triangulation of a set S of n points in the plane is order-k Delaunay if for every triangle its circumcircle encloses at most k points of S. The flip graph of S has one vertex for each possible triangulation of S, and an edge connecting two vertices when the two corresponding triangulations can be transformed into each other by a flip (i.e., exchanging the diagonal of a convex quadrilateral by the other one). The flip graph is an essential structure in the study of triangulations, but until now it had been barely studied for order-k Delaunay triangulations. In this work we show that, even though the order-k flip graph might be disconnected for k ≥ 3, any order-k triangulation can be transformed into some other order-k triangulation by at most k-1 flips, such that the intermediate triangulations are order-(2k-2), in the following settings: (1) for any k ≥ 0 when S is in convex position, and (2) for any k ≤ 5 and any point set $S$. Our results imply that the flip distance between two order-k triangulations is O(kn), as well as an efficient enumeration algorithm.

This is a joint work with Elena Arseneva, Prosenjit Bose and Rodrigo I. Silveira.