Discretized Riemannian Delaunay triangulations

Maël Rouxel-Labbé 1 M Wintraecken 2 J.-D Boissonnat 2
1 GeometryFactory
MULTICORE
2 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Anisotropic meshes are desirable for various applications, such as the numerical solving of partial differential equations and graphics. In this paper, we introduce an algorithm to compute discrete approximations of Riemannian Voronoi diagrams on 2-manifolds. This is not straightforward because geodesics, shortest paths between points, and therefore distances cannot in general be computed exactly. Our implementation employs recent developments in the numerical computation of geodesic distances and is accelerated through the use of an underlying anisotropic graph structure. We give conditions that guarantee that our discrete Riemannian Voronoi diagram is combinatorially equivalent to the Riemannian Voronoi diagram and that its dual is an embedded triangulation, using both approximate geodesics and straight edges. Both the theoretical guarantees on the approximation of the Voronoi diagram and the implementation are new and provide a step towards the practical application of Riemannian Delaunay triangulations.
Liste complète des métadonnées

Littérature citée [41 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-01367525
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : vendredi 16 septembre 2016 - 12:24:20
Dernière modification le : samedi 18 février 2017 - 01:14:44
Document(s) archivé(s) le : samedi 17 décembre 2016 - 14:33:50

Fichiers

IMR2016_hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01367525, version 1

Collections

Citation

Maël Rouxel-Labbé, M Wintraecken, J.-D Boissonnat. Discretized Riemannian Delaunay triangulations. Proceedings 25th International Meshing Roundtable (IMR25), Sep 2016, Washington DC, United States. Elsevier, 2016, 〈http://imr.sandia.gov/25imr/index.html〉. 〈hal-01367525〉

Partager

Métriques

Consultations de la notice

162

Téléchargements de fichiers

162