Skip to Main content Skip to Navigation

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
Abstract : Anisotropic meshes are desirable for various applications, such as the numerical solving of partial differential equations and graphics. In this report, 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. We give conditions that guarantee that our discrete Riemannian Voronoi diagram is combinatorially equivalent to the exact Riemannian Voronoi diagram. This allows us to build upon recent theoretical results on Riemannian Delaunay triangulations, and guarantee that the dual of our discrete Riemannian Voronoi diagram is an embedded triangulation using both approximate geodesics and straight edges. Our implementation employs recent developments in the numerical computation of geodesic distances. We observe that, in practice, our discrete Voronoi Diagram is correct in a far wider range of settings than our theoretical bounds imply. Both the theoretical guarantees on the approximation of the Voronoi diagram and the implementation are new and provides a step towards the practical application of Riemannian Delaunay triangulations.
Complete list of metadata

Cited literature [56 references]  Display  Hide  Download
Contributor : Mael Rouxel-Labbe <>
Submitted on : Sunday, October 8, 2017 - 11:20:02 PM
Last modification on : Wednesday, October 10, 2018 - 10:09:06 AM
Long-term archiving on: : Tuesday, January 9, 2018 - 12:20:16 PM


Files produced by the author(s)


  • HAL Id : hal-01612924, version 1



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⟩



Record views


Files downloads