Let $S$ be a closed hyperbolic surface (i.e. a compact Riemann surface of genus $\geq 2$) and let $P=\{p_1,\ldots,p_m\}$ be a non-empty finite subset of $m$ points in $S$. Let $\pi:\mathbb H\rightarrow S$ be the uniformization map and let $\Gamma\simeq \pi_1(S)$ be the subgroup of ${\rm Aut}(\mathbb H)$ such that $\mathbb H/\Gamma\simeq S$.

A)-- Since $P'=\pi^{-1}(P)$ is closed and discrete in $\mathbb H$, one can apply the "empty sphere (here circle) method of Delaunay" to $P'$ (cf. the second section of [L] for instance). Since the contruction is $\Gamma$-invariant, it can be pushed-down to $S$ in order to obtain the so-called "Delaunay tessellation of $S$ relatively to $P$", denoted by $\mathcal D_P$. Its 2-cells are cyclic hyperbolic polygons, etc.

One can also associated to $P$ another tessellation, the so-called "Voronoi tessellation" $\mathcal V_P$, the 2-cells of which are the sets $$V_{p_i}=\{ s\in S \, \lvert \, d(s,p_i)\leq d(s,p_j)\; \forall j=1,\ldots,m\; \}\; , \qquad i=1,\ldots,m$$ (of course, here $d(\cdot,\cdot)$ stands for the metric associated to the hyperbolic structure of $S$)

PRELIMINARY QUESTION A: how are related $\mathcal V_P$ and $\mathcal D_P$?

(as for the euclidean case, this is certainly well-known. A precise reference would be considered as a good answer).


B)-- On the other hand, $S^*=S\setminus P$ can be viewed naturaly as a complete hyperbolic surface with cusps. If $\pi^*:\mathbb H\rightarrow \mathbb H/\Gamma^*\simeq S^*$ stands for the uniformization map, then using the hyperboloïd model of $\mathbb H$ in Minkowski 3-space, Penner (see [P] and also [EP]) constructs, for each choice of horocycles centered at the $p_i$'s, a canonical tessellation of $S$ by ideal hyperbolic polygons, denoted by $\mathcal D_P^*$.

One can also consider a kind of Voronoi tesselation $\mathcal V_P^*$ of $S^*$ as follows: for $i=1,\ldots,m$, let $H_i$ be the horocycle choosen at $p_i$ to perform Penner's construction. Then the 2-cells of $\mathcal V_P^*$ are the sets $$ V_{p_i}^*=\{ s\in S^* \, \lvert \, d^*(s,H_i)\leq d^*(s,H_{j})\; \forall j=1,\ldots,m\, \}\; , \qquad i=1,\ldots,m $$

(of course, here $d^*(\cdot,\cdot)$ stands for the metric associated to the complete hyperbolic structure of $S^*$)

PRELIMINARY QUESTION B: how are related $\mathcal V^*_P$ and $\mathcal D^*_P$?

(here again, a precise reference would be considered as a good answer).

C)-- The main thing I'm interested in is the following:

MAIN QUESTION: how are related the tessellations $\mathcal D_P$ and $\mathcal D^*_P$ (as well as $\mathcal V_P$ and $\mathcal V^*_P$)?

By construction, $\mathcal D_P$ is canonical whereas $\mathcal D^*_P$ depends on the choice of horocycles $H_1,\ldots,H_m$ at the punctures. But by taking all the $H_i$'s with the same length, Penner's construction gives a canonical tessellation $\mathcal D_P^*$. Is it the same than $\mathcal D_P$?



[L] G. Leibon, Characterizing the Delaunay decompositions of compact hyperbolic surfaces. Geom. Topol. 6 (2002), 361–391.

[P] R. C. Penner, ``Decorated Teichmuller space of punctured surfaces". Comm. Math. Phy. 113 (1987), p. 299.

[EP] Epstein, R. C. Penner, ``* Euclidean decompositions of non-compact hyperbolic manifolds*". J. Differential Geom. 27 (1988), p. 67.


Thanks for any help!

  • $\begingroup$ Re "Penner constructs": this is usually referred to as the "Epstein-Penner construction". $\endgroup$
    – Igor Rivin
    Jul 5, 2013 at 13:11
  • $\begingroup$ As far I understand, the construction is due to Penner in the case 2-dimensional case. The "Epstein-Penner construction" concerns the arbitrary dimensional case, that I'm not considering at all in my post. Maybe that it was not really relevent to mention [EP] here... $\endgroup$
    – Lucien
    Jul 5, 2013 at 14:58

2 Answers 2


Two references ("...made easy" & "...made practical") to partially address your preliminary question A:

Frank Nielsen and Richard Nock. "Hyperbolic Voronoi diagrams made easy." Computational Science and Its Applications (ICCSA), IEEE, 2010. (arXiv link)

and this recent paper (from just this summer):

Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. "Hyperbolic Delaunay complexes and Voronoi diagrams made practical." Proc. 29th Symposium on Computational Geometry. ACM, 2013. (ACM link)


A closely related question is the following: given a polyhedron in $\mathbb{R}^3,$ how does its combinatorial structure relate to the Delaunay tesselation of the intrinsic metric with respect to the cone points (this is closer related than you might think, by way of the Klein model; if the vertices are at the sphere at infinity, the polyhedron is actually a complete hyperbolic surface of genus 0, every such surface arises in this way). If you could answer this question this would give an efficient version of Alexandrov's isometric embedding theorem, but no such version yet exists, and no good understanding of the relationship between the various triangulations exists either, alas.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.