Skip to Main content Skip to Navigation

Delaunay stability via perturbations

Jean-Daniel Boissonnat 1 Ramsay Dyer 1, * Arijit Ghosh 2
* Corresponding author
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We present an algorithm that takes as input a finite point set in Euclidean space, 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 flat. The algorithm provides an alternative tool to the weighting or refinement methods to remove poorly shaped simplices in Delaunay triangulations of arbitrary dimension, but in addition it provides a guarantee of stability for the resulting triangulation.
Document type :
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Ramsay Dyer Connect in order to contact the contributor
Submitted on : Monday, October 28, 2013 - 10:47:23 PM
Last modification on : Thursday, January 20, 2022 - 4:12:41 PM
Long-term archiving on: : Friday, April 7, 2017 - 5:40:45 PM


Files produced by the author(s)


  • HAL Id : hal-00806107, version 2
  • ARXIV : 1310.7696



Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay stability via perturbations. [Research Report] RR-8275, INRIA. 2013, pp.26. ⟨hal-00806107v2⟩



Les métriques sont temporairement indisponibles