A Bound for Delaunay Flip Algorithms on Flat Tori

Abstract: We are interested in triangulations of flat tori. A Delaunay flip algorithm performs Delaunay flips on the edges of an input triangulation T until it reaches a Delaunay triangulation. We prove that no sequence of Delaunay flips is longer than CΓ·n2·Λ(T) where Λ(T) is the maximum length of an edge of T, n is the number of vertices of T, and CΓ depends only on the flat torus. The bound improves on the upper bound previously known in three ways: the dependency in the "quality" of the input triangulation is linear instead of quadratic, the bound is tight, and the "quality parameter" is simpler.  . https://www.cgt-journal.org/index.php/cgt/article/view/27

Angaben zum Objekt

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• Umfang: Online-Ressource
• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: A Bound for Delaunay Flip Algorithms on Flat Tori ; volume:2 ; number:2 ; year:2023 ; Computing in Geometry and Topology ; 2, Heft 2 (2023)

Beteiligte, Orts- und Zeitangaben

• Urheber: Dubois, Loïc

Weitere Informationen

• DOI: 10.57717/cgt.v2i2.27
• URN: urn:nbn:de:101:1-2023120223272803862581
• Rechteinformation: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Letzte Aktualisierung: 15.08.2025, 07:33 MESZ