Delaunay Stability  via Perturbations

Jean-Daniel Boissonnat; Ramsay Dyer; Arijit Ghosh

doi:10.1142/S021819591450006X

Journal Articles International Journal of Computational Geometry and Applications Year : 2014

Delaunay Stability via Perturbations

(1) , (2) , (3)

1
2
3

Jean-Daniel Boissonnat

Function : Author
PersonId : 935453

Geometric computing

Ramsay Dyer

Function : Author
PersonId : 962563

Bernoulli Institute for Mathematics and Computer Science and Artificial Intelligence

Arijit Ghosh

Function : Author

Algorithms and Complexity

Abstract

We present an algorithm that takes as input a finite point set in Rm , 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.

Keywords

Delaunay triangulation stability perturbation

Domains

Computer Science [cs] Computational Geometry [cs.CG]

Fichier principal

flat_pert.pdf (397.95 Ko)

pert_ball_shell.jpg (47.14 Ko)

pert_ball_shell.png (95.09 Ko)

Origin : Files produced by the author(s)

Format : Figure, Image
Origin : Files produced by the author(s)

Jean-Daniel Boissonnat : Connect in order to contact the contributor

https://hal.inria.fr/hal-01097086

Submitted on : Thursday, December 18, 2014-5:35:05 PM

Last modification on : Thursday, January 20, 2022-5:26:36 PM

Long-term archiving on: Monday, March 23, 2015-5:28:00 PM

Dates and versions

hal-01097086 , version 1 (18-12-2014)

Identifiers

HAL Id : hal-01097086 , version 1
DOI : 10.1142/S021819591450006X

Cite

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay Stability via Perturbations. International Journal of Computational Geometry and Applications, 2014, 24, pp.125 - 152. ⟨10.1142/S021819591450006X⟩. ⟨hal-01097086⟩

Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

Collections

INRIA INRIA2

207 View

125 Download