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$?

--

REFERENCES:

[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!

Epstein-Penner construction". – Igor Rivin Jul 5 '13 at 13:11