Colloquium Mathematics - Matthijs Ebbens MSc University Groningen

Title: "Delaunay triangulations of hyperbolic surfaces"

Abstract:

Triangulations are among the most important and well-studied objects in computational geometry. Approximating a surface by a triangulation allows the use of computer algorithms to analyze the geometry of the surface or perform simulations. A Delaunay triangulation, a particular kind of triangulation often used in applications, is characterized by the property that the circumscribed disk of every triangle does not contain any vertices of the triangulation in its interior.

In this talk we will look at Delaunay triangulations of hyperbolic surfaces. Hyperbolic surfaces are two-dimensional Riemannian manifolds with constant negative Gaussian curvature.

We start by describing the properties of a specific class of hyperbolic surfaces that allow a well-known algorithm for computing Delaunay triangulations to be generalized to these surfaces. In particular, we compute the systole of these surfaces, i.e., the length of the shortest non-contractible closed curve, as it is an important parameter in the algorithm. Moreover, we look at the minimal number of vertices of Delaunay triangulations of a hyperbolic surface, in terms of the genus of the surface. We show that every hyperbolic surface of genus g has a Delaunay triangulation with at most 151g vertices. We also construct a class of hyperbolic surfaces for which the order of this bound is optimal. This class is given as a collection of subsets of Teichmüller spaces, i.e., the sets of hyperbolic surfaces of a fixed genus. Furthermore, to give a general lower bound, we show that the Omega(sqrt(g)) lower bound for the number of vertices of a simplicial triangulation of a topological surface of genus g is tight for hyperbolic surfaces as well.