BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Pilar Cano (Université Libre de Bruxelles) DTSTART:20210304T150000Z DTEND:20210304T160000Z DTSTAMP:20260422T065509Z UID:CJCS/8 DESCRIPTION:Title: Fli ps in higher order Delaunay triangulations\nby Pilar Cano (Université Libre de Bruxelles) as part of Copenhagen-Jerusalem Combinatorics Seminar \n\n\nAbstract\nWe study the flip graph of higher order Delaunay triangula tions. A triangulation of a set S of n points in the plane is order-k Dela unay 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 triangula tions 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 orde r-k triangulation by at most k − 1 flips\, such that the intermediate tr iangulations are of order 2k − 2\, in the following settings: (1) for an y k ≥ 0 when S is in convex position\, and (2) for any k ≤ 5 and any p oint set S. Our results imply that the flip distance between two order-k t riangulations is O(kn)\, as well as an efficient enumeration algorithm.\n LOCATION:https://researchseminars.org/talk/CJCS/8/ END:VEVENT END:VCALENDAR