Vertex Removal in Two Dimensional Delaunay Triangulation: Speed-up by Low Degrees Optimization
Résumé
The theoretical complexity of vertex removal in a Delaunay triangulation is often given in terms of the degree d of the removed point, with usual results O(d), O(d log d), or O(d²). In fact, the asymptotic complexity is of poor interest since d is usually quite small. In this paper we carefully design code for small degrees 3≤ d≤ 7, it improves the global behavior of the removal for random points by more than 45%.
Domaines
Géométrie algorithmique [cs.CG]
Fichier principal
paper.pdf (201.91 Ko)
Télécharger le fichier
vignette-inria-00560379.jpg (60.22 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...