DELAUNAY STABILITY VIA PERTURBATIONS
JEAN-DANIEL BOISSONNAT, RAMSAY DYER, ARIJIT GHOSH · International Journal of Computational Geometry & Applications · 2014
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.