We study the flip graph of higher order De­lau­nay tri­an­gu­la­tions. A tri­an­gu­la­tion of a set S of n points in the plane is order-k De­lau­nay if for every tri­an­gle its cir­cum­cir­cle en­closes at most k points of S. The flip graph of S has one ver­tex for each pos­si­ble tri­an­gu­la­tion of S, and an edge con­nect­ing two ver­tices when the two cor­re­spond­ing tri­an­gu­la­tions can be trans­formed into each other by a flip (i.e., ex­chang­ing the di­ag­o­nal of a con­vex quadri­lat­eral by the other one). The flip graph is an es­sen­tial struc­ture in the study of tri­an­gu­la­tions, but until now it had been barely stud­ied for order-k De­lau­nay tri­an­gu­la­tions. In this work we show that, even though the order-k flip graph might be dis­con­nected for k ≥ 3, any order-k tri­an­gu­la­tion can be trans­formed into some other order-k tri­an­gu­la­tion by at most k-1 flips, such that the in­ter­me­di­ate tri­an­gu­la­tions are order-(2k-2), in the fol­low­ing set­tings: (1) for any k ≥ 0 when S is in con­vex po­si­tion, and (2) for any k ≤ 5 and any point set $S$. Our re­sults imply that the flip dis­tance be­tween two order-k tri­an­gu­la­tions is O(kn), as well as an ef­fi­cient enu­mer­a­tion al­go­rithm.

This is a joint work with Elena Ar­seneva, Pros­en­jit Bose and Ro­drigo I. Sil­veira.