Anisotropic triangulations via discrete Riemannian Voronoi diagrams - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2017

Anisotropic triangulations via discrete Riemannian Voronoi diagrams

Anisotropic triangulations via discrete Riemannian Voronoi diagrams

(1) , (2) , (1)
1
2
Jean-Daniel Boissonnat
  • Function : Author
  • PersonId : 935453
Mael Rouxel-Labbé
  • Function : Author
  • PersonId : 996554
Mathijs Wintraecken
  • Function : Author
  • PersonId : 1020357

Abstract

The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\mathbb{R}^2$ and on surfaces embedded in $\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\cal P$ in a domain $\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\cal P$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.
Fichier principal
Vignette du fichier
RR-9056.pdf (3.71 Mo) Télécharger le fichier
Vignette du fichier
Sperner_construction_3D_2.pdf (27.21 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01507273 , version 1 (12-04-2017)

Identifiers

  • HAL Id : hal-01507273 , version 1

Cite

Jean-Daniel Boissonnat, Mael Rouxel-Labbé, Mathijs Wintraecken. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. [Research Report] RR-9056, Inria Sophia Antipolis. 2017. ⟨hal-01507273⟩
164 View
95 Download

Share

Gmail Facebook Twitter LinkedIn More