HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Sunday, October 8, 2017 - 11:20:02 PM
Last modification on : Friday, February 4, 2022 - 3:11:48 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