Discretized Riemannian Delaunay Triangulations

Overview & Synopsis

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.