Discretized Riemannian Delaunay Triangulations

Mael Rouxel-Labbé 1, 2 Mathijs Wintraecken 1 Jean-Daniel Boissonnat 1
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Résumé : Les maillages anisotropes sont désirables pour de nombreuses applications, telles que la résolution numérique d'équations aux dérivées partielles ou la visualisation. Dans ce rapport, nous présentons un algorithme qui permet de calculer une approximation discrète d'un diagramme de Voronoi Riemannien sur une 2-variété. Il s'agit d'une tache complexe car ce diagramme est basé sur la notion de courbe géodésique, qui ne peut en général pas être calculée de manière exacte. Nous donnons dans ce rapport des conditions qui garantissent que notre diagramme de Voronoi Riemannien discret est combinatoirement équivalent au diagramme de Voronoi Riemannien exact. Ceci nous permet ensuite d'utiliser des résultats récents sur les triangulations de Delaunay Riemanniennes pour garantir le fait que le dual de notre diagramme de Voronoi Riemannien discret est une triangulation plongée, à la fois en utilisant des arêtes géodésiques et des arêtes droites. Notre implémentation est basée sur de récentes avancées dans le calcul numérique des distances géodésiques. Nous observons en pratique que notre diagramme de Voronoi Riemannien discret est correct dans des conditions beaucoup moins contraignantes que ce que notre théorie implique. Les garanties théoriques et l'approximation du diagramme de Voronoi sont nouvelles et sont une étape de plus vers une utilisation pratique des triangulations de Delaunay Riemanniennes.
Type de document :
Rapport
[Research Report] RR-9103, INRIA Sophia Antipolis - Méditerranée. 2017, pp.51
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01612924
Contributeur : Mael Rouxel-Labbe <>
Soumis le : dimanche 8 octobre 2017 - 23:20:02
Dernière modification le : samedi 27 janvier 2018 - 01:31:37
Document(s) archivé(s) le : mardi 9 janvier 2018 - 12:20:16

Fichier

RR-9103.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01612924, version 1

Citation

Mael Rouxel-Labbé, Mathijs Wintraecken, Jean-Daniel Boissonnat. Discretized Riemannian Delaunay Triangulations. [Research Report] RR-9103, INRIA Sophia Antipolis - Méditerranée. 2017, pp.51. 〈hal-01612924〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

45