The goal of this paper is to exhibit and analyze an algorithm that takes a given closed orientable hyperbolic surface and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While grounded in topological considerations, the algorithm makes key use of the geometry of the surface. We introduce data structures that reflect this interplay between geometry and topology and show that the algorithm finishes in polynomial time, in terms of the initial perimeter and the genus of the surface.

Abstract 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 $$\Omega (\sqrt{g})$$ Ω ( 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.

This paper investigate the problem of deciding whether or not determinants of binary circulant matrices (i.e. matrices with entries in either {0,1} or {-1,1} ) can reach Hadamard's bound. It finds necessary and sufficient conditions for the existence of such matrices. A direct consequence of this study relates to the existence of Barker sequences.