Representing Infinite Periodic Hyperbolic Delaunay Triangulations Using Finitely Many Dirichlet Domains

Vincent Despré (1) , Benedikt Kolbe (1, 2) , Monique Teillaud (1)

1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
2 HCM - Hausdorff Center for Mathematics

The Delaunay triangulation of a set of points P on a hyperbolic surface is the projection of the Delaunay triangulation of the set $\widetilde{P}$ of lifted points in the hyperbolic plane. Since $\widetilde{P}$ is infinite, the algorithms to compute Delaunay triangulations in the plane do not generalize naturally. Using a Dirichlet domain, we exhibit a finite set of points that captures the full triangulation. We prove that an edge of a Delaunay triangulation has a combinatorial length (a notion we define in the paper) smaller than $12g-6$ with respect to a Dirichlet domain. To achieve this, we introduce new tools, of intrinsic interest, that capture the properties of length-minimizing curves in the context of closed curves. We then use these to derive structural results on Delaunay triangulations and exhibit certain distance minimizing properties of both the edges of a Delaunay triangulation and of a Dirichlet domain. The bounds produced in this paper depend only on the topology of the surface. They provide mathematical foundations for hyperbolic analogs of the algorithms to compute periodic Delaunay triangulations in Euclidean space.

Mots clés: Delaunay triangulations; Hyperbolic surfaces; Fuchsian group; Moduli space; Dirichlet domain

Domaines: Géométrie algorithmique [cs.CG]; Topologie géométrique [math.GT]

Vincent Despré, Benedikt Kolbe, Monique Teillaud. Representing Infinite Periodic Hyperbolic Delaunay Triangulations Using Finitely Many Dirichlet Domains. Discrete and Computational Geometry, 2024, ⟨10.1007/s00454-024-00653-x⟩. ⟨hal-04577851⟩