Minimal Delaunay Triangulations of Hyperbolic Surfaces

Motivated by recent work on Delaunay triangulations of hyperbolic surfaces, we consider the minimal number of vertices of such triangulations. First, we show that every hyperbolic surface of genus g has a simplicial Delaunay triangulation with O(g) vertices, where edges are given by distance paths. Then, we construct a class of hyperbolic surfaces for which the order of this bound is optimal. Finally, to give a general lower bound, we show that the Ω(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.