Flips in higher order Delaunay triangulations

Abstract: 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 of 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.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456