Flips in Higher Order Delaunay Triangulations
| Autor: | Elena Arseneva, Prosenjit Bose, Rodrigo I. Silveira, Pilar Cano |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications |
| Rok vydání: | 2020 |
| Předmět: |
Grafs
Teoria de Delaunay triangulation Diagonal 0211 other engineering and technologies Order (ring theory) Triangulation (social science) 0102 computer and information sciences 02 engineering and technology Convex position Computer Science::Computational Geometry 01 natural sciences Vertex (geometry) Graph theory Combinatorics 010201 computation theory & mathematics Mathematics::Category Theory Graph (abstract data type) Circumscribed circle 05 Combinatorics::05C Graph theory [Classificació AMS] Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC] 021101 geological & geomatics engineering Mathematics |
| Zdroj: | LATIN 2020: Theoretical Informatics ISBN: 9783030617912 LATIN UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| DOI: | 10.1007/978-3-030-61792-9_18 |
| Popis: | The final authenticated version is available online at https://doi.org/10.1007/978-3-030-61792-9_18 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 at most 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. E.A. was supported by RFBR, project number 20-01-00488. P.B. was partially supported by NSERC. P.C. was supported by CONACYT, MX. R.S. was supported by MINECO through the Ramón y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|