Comparing two Delaunay tessellations on a hyperbolic surface 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!
 A: 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: 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.
