A bound for Delaunay flip algorithms on flat tori - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

A bound for Delaunay flip algorithms on flat tori

Résumé

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_Γ • n^2 • Λ(T) where Λ(T) is the maximum length of an edge of T , n is the number of vertices of T , and C_Γ > 0 depends only on the flat torus. The bound improves on the preexisting upper bound 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.
Fichier principal
Vignette du fichier
CCCG2022_paper_16.pdf (677.94 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03666488 , version 1 (12-05-2022)
hal-03666488 , version 2 (05-07-2022)
hal-03666488 , version 3 (08-09-2022)

Identifiants

  • HAL Id : hal-03666488 , version 3

Citer

Loïc Dubois. A bound for Delaunay flip algorithms on flat tori. CCCG 2022 - 34th Canadian Conference on Computational Geometry, Aug 2022, Toronto, Canada. ⟨hal-03666488v3⟩
181 Consultations
104 Téléchargements

Partager

Gmail Facebook X LinkedIn More