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

Delaunay triangulations of spaces of constant negative curvature

Mikhail Bogdanov 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We study triangulations of spaces of constant negative curvature -1 from both theoretical and practical points of view. This is originally motivated by applications in various fields such as geometry processing and neuro mathematics. We first consider Delaunay complexes and Voronoi diagrams in the Poincaré ball, a conformal model of the hyperbolic space, in any dimension. We use the framework of the space of spheres to give a detailed description of algorithms. We also study algebraic and arithmetic issues, observing that only rational computations are needed. All proofs are based on geometric reasoning, they do not resort to any use of the analytic formula of the hyperbolic distance. We present a complete, exact, and efficient implementation of the Delaunay complex and Voronoi diagram in the 2D hyperbolic space. The implementation is developed for future integration into the CGAL library to make it available to a broad public. Then we study the problem of computing Delaunay triangulations of closed hyperbolic surfaces. We define a triangulation as a simplicial complex, so that the general incremental algorithm for Euclidean Delaunay triangulations can be adapted. The key idea of the approach is to show the existence of a finite-sheeted covering space for which the fibers always define a Delaunay triangulation. We prove a sufficient condition on the length of the shortest non-contractible loops of the covering space. For the specific case of the Bolza surface, we propose a method to actually construct such a covering space, by studying normal subgroups of the Fuchsian group defining the surface. Implementation aspects are considered.
Document type :
Complete list of metadata

Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Thursday, December 4, 2014 - 9:43:04 AM
Last modification on : Wednesday, February 2, 2022 - 3:53:05 PM
Long-term archiving on: : Monday, March 9, 2015 - 5:55:18 AM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2099-12-04

Please log in to resquest access to the document


  • HAL Id : tel-01090723, version 1



Mikhail Bogdanov. Delaunay triangulations of spaces of constant negative curvature. Computer Science [cs]. Univeristé Nice Sophia Antipolis, 2013. English. ⟨NNT : 2013NICE4139⟩. ⟨tel-01090723⟩



Record views