carrier image

Discretized Riemannian Delaunay triangulations

Rouxel-Labbé, Mael, Mathijs Wintraecken, Jean-Daniel Boissonnat

Proceedings, 25th International Meshing Roundtable, Elsevier, Science Direct, September 26-30 2016

INTERNATIONAL
MESHING
ROUNTABLE

25th International Meshing Roundtable
Washington DC, U.S.A.
September 26-30, 2016

Mael Rouxel-Labbé, GeometryFactory / INRIA, FR, mael.rouxel-labbe@inria.fr
Mathijs Wintraecken, INRIA, NL, mathijs.wintraecken@inria.fr
Jean-Daniel Boissonnat, INRIA, FR, jean-daniel.boissonnat@inria.fr

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 exact 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.

Download Full Paper (PDF)


Contact author(s) or publisher for availability and copyright information on above referenced article