2013/10/31 by Jean-Daniel Boissonnat, JEAN-DANIEL BOISSONNAT, Ramsay Dyer +3 · 26 citations
Computer Science · #Bowyer–Watson algorithm #Chew's second algorithm #Computational Geometry and Mesh Generation #Constrained Delaunay triangulation #Delaunay triangulation #Minimum-weight triangulation #Perturbation (astronomy) #Pitteway triangulation #Polynomial and algebraic computation #Stability (learning theory) #Topological and Geometric Data Analysis #cs.CG
paper · pdf · doi:10.1142/s021819591450006x
published in International Journal of Computational Geometry & Applications 24(02), 125-152 (World Scientific)
openalex publication_date 2014/06/01 · arxiv created 2015/05/06 · arxiv updated 2015/05/08 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
We present an algorithm that takes as input a finite point set in ℝ m , and performs a perturbation that guarantees that the Delaunay triangulation of the resulting perturbed point set has quantifiable stability with respect to the metric and the point positions. There is also a guarantee on the quality of the simplices: they cannot be too at. The algorithm provides an alternative tool to the weighting or refinement methods to re-move poorly shaped simplices in Delaunay triangulations of arbitrary dimension, but in addition it provides a guarantee of stability for the resulting triangulation.