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

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch

References and Relationships

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

Contributors, Places and Time

• Creator: Dubois, Loïc

Further information

• DOI: 10.57717/cgt.v2i2.27
• URN: urn:nbn:de:101:1-2023120223272803862581
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 15.08.2025, 7:33 AM CEST