A Bound for Delaunay Flip Algorithms on Flat Tori
Dubois, Loïc · HAL (Le Centre pour la Communication Scientifique Directe) · 2022
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.