${\boldsymbol{s}}_{0}$. The distance between ${\boldsymbol{p}}^{\prime}_{1}$
and ${\boldsymbol{v}}_{2g+1}$ is $\ell-x$, where the length $\ell$ of the
sides satisfies $\cosh(\tfrac{1}{2}\ell)=\cot(\tfrac{\pi}{4g})$. Let
$\alpha_{2}$ be the angle between ${\boldsymbol{\gamma}}_{2}$ and
${\boldsymbol{s}}_{2g}$.

Figure 22: Construction in the proof of Part 4 of Lemma 11.

By the hyperbolic sine rule,

$\dfrac{\sinh(\operatorname{length}({\boldsymbol{\gamma}}_{1}))}{\sin(\tfrac{\pi}{2g})}=\dfrac{\sinh(x)}{\sin(\alpha_{1})},$

so

$\sinh(\operatorname{length}({\boldsymbol{\gamma}}_{1}))\geq\sinh(x)\sin(\tfrac{\pi}{2g}).$

In a similar way, we obtain

$\sinh(\operatorname{length}({\boldsymbol{\gamma}}_{2}))\geq\sinh(\ell-x)\sin(\tfrac{\pi}{2g}).$

We minimize

$f(x):=\operatorname{arcsinh}(\sinh(x)\sin(\tfrac{\pi}{2g}))+\operatorname{arcsinh}(\sinh(\ell-x)\sin(\tfrac{\pi}{2g}))$

subject to $0<x<\ell$, as this provides a lower bound for
$\operatorname{length}({\boldsymbol{\gamma}}_{1}\cup{\boldsymbol{\gamma}}_{2})$.
Because

$\dfrac{d^{2}}{dx^{2}}\;\operatorname{arcsinh}(\sinh(x)\sin(\tfrac{\pi}{2g}))=\dfrac{\sin(\tfrac{\pi}{2g})\cos^{2}(\tfrac{\pi}{2g})\sinh(x)}{(\sin^{2}(\tfrac{\pi}{2g})\sinh^{2}(x)+1)^{3/2}}>0$

for all $x>0$, the function
$x\mapsto\operatorname{arcsinh}(\sinh(x)\sin(\tfrac{\pi}{2g}))$ is strictly
convex. It follows that $f$ is also strictly convex, so it has a unique global
minimum. The derivative of $f$ is given by

$f^{\prime}(x)=\dfrac{\sin(\tfrac{\pi}{2g})\cosh(x)}{(\sin^{2}(\tfrac{\pi}{2g})\sinh^{2}(x)+1)^{1/2}}-\dfrac{\sin(\tfrac{\pi}{2g})\cosh(\ell-x)}{(\sin^{2}(\tfrac{\pi}{2g})\sinh^{2}(\ell-x)+1)^{1/2}}.$

It is clear that $f^{\prime}(\tfrac{1}{2}\ell)=0$, so $x=\tfrac{1}{2}\ell$ is
the unique minimizer with minimum value
$f(\tfrac{1}{2}\ell)=2\operatorname{arcsinh}(\sinh(\tfrac{1}{2}\ell)\sin(\tfrac{\pi}{2g}))$.
By the discussion above, this implies that

$\sinh(\tfrac{1}{2}\operatorname{length}({\boldsymbol{\gamma}}_{1}\cup{\boldsymbol{\gamma}}_{2}))\geq\sinh(\tfrac{1}{2}\ell)\sin(\tfrac{\pi}{2g}).$

Then

$\displaystyle\cosh(\operatorname{length}({\boldsymbol{\gamma}}_{1}\cup{\boldsymbol{\gamma}}_{2}))$
$\displaystyle=2\sinh^{2}(\tfrac{1}{2}\operatorname{length}({\boldsymbol{\gamma}}_{1}\cup{\boldsymbol{\gamma}}_{2}))+1,$
$\displaystyle\geq 2\sinh^{2}(\tfrac{1}{2}\ell)\sin^{2}(\tfrac{\pi}{2g})+1,$
$\displaystyle=2(\cot^{2}(\tfrac{\pi}{4g})-1)\sin^{2}(\tfrac{\pi}{2g})+1,$
$\displaystyle=(1+2\cos(\tfrac{\pi}{2g}))^{2},$

from which we conclude that
$\operatorname{length}({\boldsymbol{\gamma}}_{1}\cup{\boldsymbol{\gamma}}_{2})>\tfrac{1}{2}\varsigma_{g}$.

  5. 5.

Now, using the notation from Part 4, assume that
${\boldsymbol{\gamma}}={\boldsymbol{\gamma}}_{1}\cup{\boldsymbol{\gamma}}_{2}$.
By the argument in Part 4, the length of ${\boldsymbol{\gamma}}$ is minimal
when ${\boldsymbol{p}}_{1}$ is the midpoint of ${\boldsymbol{s}}_{1}$ and
${\boldsymbol{p}}^{\prime}_{1}$ is the midpoint of ${\boldsymbol{s}}_{2g+1}$,
given any location of the starting point of ${\boldsymbol{\gamma}}_{1}$ and
the endpoint of ${\boldsymbol{\gamma}}_{2}$. By symmetry of the argument, it
follows that $\operatorname{length}({\boldsymbol{\gamma}})$ is minimal when
the starting point of ${\boldsymbol{\gamma}}_{1}$ is the midpoint of
${\boldsymbol{s}}_{0}$ and the endpoint of ${\boldsymbol{\gamma}}_{2}$ is the
midpoint of ${\boldsymbol{s}}_{2g}$. It can be seen that the resulting curve
is the curve constructed in the proof of Lemma 9, the length of which is
$\varsigma_{g}$. This finishes the proof.

##  Appendix C Proofs omitted in Section 5

First, we give the proof of Proposition 13, which states that for any finite
set of points $\mathcal{Q}_{g}$ containing $\mathcal{W}_{g}$, each face in
$\operatorname{DT}_{\mathbb{D}}\mathopen{}\left(\pi_{g}^{-1}(\mathcal{Q}_{g})\right)\mathclose{}$
with at least one vertex in $\widetilde{D}_{g}$ is contained in
$D_{\mathcal{N}_{g}}$.

The proof will use the following lemma.

######  Lemma 21.

Let $C_{{\boldsymbol{q}}}$ be a Euclidean disk centered at $O$ and passing
through a point ${{\boldsymbol{q}}}$ (Figure 23). Let $H_{1}$ and $H_{2}$
denote the two open half-planes bounded by the Euclidean line through $O$ and
${{\boldsymbol{q}}}$. Let $H_{0}$ be a half-plane that contains
${{\boldsymbol{q}}}$, bounded by another Euclidean line passing through $O$
but not through ${{\boldsymbol{q}}}$. Let $R_{j}=\mathopen{}\left(H_{0}\bigcap
H_{j}\right)\mathclose{}\setminus C_{{\boldsymbol{q}}},j=1,2$, and let
${\boldsymbol{p}}_{j}\in R_{j},i=1,2$. The disk
$C({\boldsymbol{p}}_{1},{\boldsymbol{p}}_{2})$ through
$O,{\boldsymbol{p}}_{1},$ and ${\boldsymbol{p}}_{2}$ contains
${{\boldsymbol{q}}}$.

Figure 23: Illustrations for the proof of Lemma 21.

###### Proof.

It is easy to verify that there exist pairs of points
$({\boldsymbol{p}}_{1},{\boldsymbol{p}}_{2})\in R_{1}\times R_{2}$ for which
the point ${{\boldsymbol{q}}}$ lies inside the disk
$C({\boldsymbol{p}}_{1},{\boldsymbol{p}}_{2})$. For instance, consider a line
perpendicular to the line through $O$ and ${{\boldsymbol{q}}}$ so that
${{\boldsymbol{q}}}$ is closer to $O$ than to their intersection point, as
shown in Figure 23 \- Left. If ${\boldsymbol{p}}_{1}$ lies on this
perpendicular line and ${\boldsymbol{p}}_{2}$ is the reflection of
${\boldsymbol{p}}_{1}$ in the line through $O$ and ${{\boldsymbol{q}}}$, then
the disk $C({\boldsymbol{p}}_{1},{\boldsymbol{p}}_{2})$ contains
${{\boldsymbol{q}}}$. Since this disk varies continuously when
$({\boldsymbol{p}}_{1},{\boldsymbol{p}}_{2})$ ranges over $R_{1}\times R_{2}$,
it is sufficient to prove that there are no pairs
$({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})\in R_{1}\times R_{2}$ for
which ${{\boldsymbol{q}}}$ lies on the boundary of
$C({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})$.

Suppose, for a contradiction, that there exists a pair
$({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})\in R_{1}\times R_{2}$ for
which $C({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})$ is a disk with
${{\boldsymbol{q}}}$ and $O$ on its boundary. Consider the disk
$C_{{\boldsymbol{q}}}$ centered at $O$ and passing through
${{\boldsymbol{q}}}$. Let $F$ be the intersection of the disk with diameter
$\mathopen{}\left[O,{{\boldsymbol{q}}}\right]\mathclose{}$ with the half-plane
$H_{1}$, as shown in Figure 23 \- Right. For any point ${\boldsymbol{p}}\in
H_{2}\setminus C_{{\boldsymbol{q}}}$, the circle $C_{{\boldsymbol{p}}}$
through $O,{{\boldsymbol{q}}},$ and ${\boldsymbol{p}}$ has a non-empty
intersection with $H_{1}$, which is completely included in $F$, so in
particular $C({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})$ intersects
$H_{1}$ inside the disk with diameter
$\mathopen{}\left[O,{{\boldsymbol{q}}}\right]\mathclose{}$. By a symmetric
observation, $C({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})$ also
intersects $H_{2}$ inside the same disk. Therefore,
$C({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})$ is the disk with
diameter $\mathopen{}\left[O,{{\boldsymbol{q}}}\right]\mathclose{}$. This
implies that both ${\boldsymbol{p}}_{1}$ and ${\boldsymbol{p}}_{2}$ lie in the
disk $C_{{\boldsymbol{q}}}$, which is a contradiction. Therefore, there exists
no pair $({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})\in R_{1}\times
R_{2}$ for which $C({\boldsymbol{p}}_{1}^{*},{\boldsymbol{p}}_{2}^{*})$ has
${{\boldsymbol{q}}}$ on its boundary. This finishes the proof. ∎

Note that Lemma 21 can be directly used in the Poincaré disk because
hyperbolic circles are represented as Euclidean circles, and hyperbolic
geodesics through the origin $O$ are supported by Euclidean lines.

We can now proceed with the proof of Proposition 13.

###### Proof.

Figure 24:  Illustration for the proof of Proposition 13 for $g=2$.

We show that each edge in
$\operatorname{DT}_{\mathbb{D}}\mathopen{}\left(\pi_{g}^{-1}(\mathcal{Q}_{g})\right)\mathclose{}$
with one endpoint in $\widetilde{D}_{g}$ has its other endpoint inside
$D_{\mathcal{N}_{g}}$.

Let ${\boldsymbol{e}}$ be a segment with an endpoint in $\widetilde{D}_{g}$
and an endpoint outside $D_{\mathcal{N}_{g}}$. We will prove that every disk
passing through the endpoints of ${\boldsymbol{e}}$ contains a point in
$\mathcal{W}_{g}$. There are two cases to consider: ${\boldsymbol{e}}$ either
crosses only one image of $\widetilde{D}_{g}$ under an element of
$\mathcal{N}_{g}\setminus\\{\mathbbm{1}\\}$, or it crosses several of its
images. We examine each case separately.

#### Case A: The edge ${\boldsymbol{e}}$ crosses only one image of
$\widetilde{D}_{g}$ before leaving $D_{\mathcal{N}_{g}}$.

This case is illustrated in Figure 24 \- Left. Let
$f(\widetilde{D}_{g}),f\in\mathcal{N}_{g}\setminus\\{\mathbbm{1}\\}$ be the
Dirichlet region that ${\boldsymbol{e}}$ crosses. The image
${\boldsymbol{e}}^{\prime}=f^{-1}({\boldsymbol{e}})$ of ${\boldsymbol{e}}$
then crosses $\widetilde{D}_{g}$, intersecting two of its non-adjacent sides
${\boldsymbol{s}}_{j}$ and ${\boldsymbol{s}}_{k}$ in the points
${\boldsymbol{p}}_{j}$ and ${\boldsymbol{p}}_{k}$, respectively. We can assume
without loss of generality that the hyperbolic segment
$[{\boldsymbol{p}}_{j},{\boldsymbol{p}}_{k}]$ does not contain the origin,
since in that case any disk through ${\boldsymbol{p}}_{j}$ and
${\boldsymbol{p}}_{k}$ clearly contains the origin. Then, there exists a line
${\boldsymbol{l}}_{O}$ through $O$ such that ${\boldsymbol{p}}_{j}$ and
${\boldsymbol{p}}_{k}$ are contained in the same half-space. Let
${\boldsymbol{m}}_{\ell}$ be the midpoint of a side between
${\boldsymbol{s}}_{j}$ and ${\boldsymbol{s}}_{k}$ in the same half-space as
${\boldsymbol{p}}_{j}$ and${\boldsymbol{p}}_{k}$. Consider the disk centered
at $O$ that passes through ${\boldsymbol{m}}_{\ell}$ (and, of course, through
all the other midpoints ${\boldsymbol{m}}_{k}$ as well), and consider also the
line through $O$ and ${\boldsymbol{m}}_{\ell}$. By Lemma 21, the disk
$C({\boldsymbol{p}}_{j},{\boldsymbol{p}}_{k})$ passing through
$O,{\boldsymbol{p}}_{j},$ and ${\boldsymbol{p}}_{k}$ contains
${\boldsymbol{m}}_{\ell}$. Since $O$ and ${\boldsymbol{m}}_{\ell}$ are on both
sides of the segment
$\mathopen{}\left[{\boldsymbol{p}}_{j},{\boldsymbol{p}}_{k}\right]\mathclose{}$,
any disk through ${\boldsymbol{p}}_{j}$ and ${\boldsymbol{p}}_{k}$ contains
either ${\boldsymbol{m}}_{\ell}$ or $O$, therefore there is no empty disk that
passes through ${\boldsymbol{p}}_{j}$ and ${\boldsymbol{p}}_{k}$. Assume now
that there is an empty disk that passes through the endpoints of
${\boldsymbol{e}}^{\prime}$. This empty disk can then be shrunk continuously
so that it passes through ${\boldsymbol{p}}_{j}$ and ${\boldsymbol{p}}_{k}$.
The shrunk version of the disk must be also empty, which is a contradiction.
Therefore, there is no empty disk passing through the endpoints of
${\boldsymbol{e}}^{\prime}$, which implies that ${\boldsymbol{e}}^{\prime}$
(and, by consequence, ${\boldsymbol{e}}$) cannot be an edge in
$\operatorname{DT}_{\mathbb{D}}\mathopen{}\left(\pi_{g}^{-1}(\mathcal{Q}_{g})\right)\mathclose{}$.

#### Case B: The edge ${\boldsymbol{e}}$ crosses several images of
$\widetilde{D}_{g}$ before leaving $D_{\mathcal{N}_{g}}$.

This case is illustrated in Figure 24 \- Right. There exist multiple images of
${\boldsymbol{e}}$ in
$\operatorname{DT}_{\mathbb{D}}\mathopen{}\left(\pi_{g}^{-1}(\mathcal{Q})\right)\mathclose{}$
that intersect $\widetilde{D}_{g}$, in fact as many as the number of Dirichlet
regions it intersects. Each one of these images intersects two adjacent sides
of $\widetilde{D}_{g}$. Let ${\boldsymbol{e}}^{\prime}$ be an image of
${\boldsymbol{e}}$ that intersects two adjacent sides ${\boldsymbol{s}}_{j}$
and ${\boldsymbol{s}}_{j+1}$ of $\widetilde{D}_{g}$ so that the hyperbolic
line supporting ${\boldsymbol{e}}^{\prime}$ separates $O$ and the midpoint
${\boldsymbol{m}}_{j+1}$. Note that such an image of ${\boldsymbol{e}}$ exists
always: ${\boldsymbol{e}}$ either separates $O$ and the midpoint
${\boldsymbol{m}}_{j+1}$, or it separates an image of $O$ under some
translation $f$ of $\Gamma_{g}$ and ${\boldsymbol{m}}_{j+1}$; in the second
case, $f^{-1}({\boldsymbol{e}})$ separates $O$ and the midpoint
$f^{-1}({\boldsymbol{m}}_{j+1})$. The edge ${\boldsymbol{e}}^{\prime}$
intersects also the side ${\boldsymbol{s}}_{k}$ adjacent to
${\boldsymbol{s}}_{j+1}$ in the Dirichlet region that shares the side
${\boldsymbol{s}}_{j+1}$ with $\widetilde{D}_{g}$ (see Figure 24 \- Right).
Let ${\boldsymbol{p}}_{j}$ and ${\boldsymbol{p}}_{k}$ be the intersection
points of ${\boldsymbol{e}}^{\prime}$ with ${\boldsymbol{s}}_{j}$ and
${\boldsymbol{s}}_{k}$, respectively. Consider the circle centered at the
origin that passes through ${\boldsymbol{m}}_{j+1}$. Consider also the line
through $O$ and ${\boldsymbol{m}}_{j+1}$ and the line ${\boldsymbol{l}}_{0}$
through $O$ perpendicular to it. By Lemma 21, the disk
$C({\boldsymbol{p}}_{j},{\boldsymbol{p}}_{k})$ passing through
$O,{\boldsymbol{p}}_{j},$ and ${\boldsymbol{p}}_{k}$ contains
${\boldsymbol{m}}_{j+1}$. Since $O$ and ${\boldsymbol{m}}_{j+1}$ are on both
sides of the segment
$\mathopen{}\left[{\boldsymbol{p}}_{j},{\boldsymbol{p}}_{k}\right]\mathclose{}$,
any disk through ${\boldsymbol{p}}_{j}$ and ${\boldsymbol{p}}_{k}$ contains
either ${\boldsymbol{m}}_{j+1}$ or $O$, therefore there is no empty disk that
passes through ${\boldsymbol{p}}_{j}$ and ${\boldsymbol{p}}_{k}$. By the same
reasoning as in Case A, there is no empty disk passing through the endpoints
of ${\boldsymbol{e}}^{\prime}$ either, which implies that
${\boldsymbol{e}}^{\prime}$ (and, by consequence, ${\boldsymbol{e}}$) cannot
be an edge in
$\operatorname{DT}_{\mathbb{D}}\mathopen{}\left(\pi_{g}^{-1}(\mathcal{Q}_{g})\right)\mathclose{}$.

In conclusion, no edge of
$\operatorname{DT}_{\mathbb{D}}\mathopen{}\left(\pi_{g}^{-1}(\mathcal{Q}_{g})\right)\mathclose{}$
can have an endpoint in $\widetilde{D}_{g}$ and an endpoint outside
$D_{\mathcal{N}_{g}}$, therefore all faces with at least one vertex in
$\widetilde{D}_{g}$ are included in $D_{\mathcal{N}_{g}}$. ∎

Second, we compute the distance between any pair of Weierstrass points, as
mentioned in the proof of Theorem 14.

######  Lemma 22.

The distance between any pair of distinct Weierstrass points of
$\mathbb{M}_{g}$ is at least
$\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.

###### Proof.

Recall that the Weierstrass points of $\mathbb{M}_{g}$ are represented by the
origin, the vertices and the midpoints of the sides of $D_{g}$. The distance
between midpoints of non-consecutive sides is clearly larger than the distance
between midpoints of consecutive sides. Hence, by symmetry, it is sufficient
to consider the region in Figure 25.

Figure 25: Computing the distances between Weierstrass points of
$\mathbb{M}_{g}$.

Let ${\boldsymbol{m}}_{k}$ be the midpoint of side ${\boldsymbol{s}}_{k}$ and
let ${\boldsymbol{p}}_{k}^{*}$ be the midpoint of ${\boldsymbol{m}}_{k-1}$ and
${\boldsymbol{m}}_{k}$. First, in the right-angled triangle
$[O,{\boldsymbol{m}}_{0},{\boldsymbol{v}}_{0}]$ we know that [6, Theorem
7.11.3]

$\displaystyle\cosh(d(O,{\boldsymbol{m}}_{0}))=\cosh(d({\boldsymbol{m}}_{0},{\boldsymbol{v}}_{0}))$
$\displaystyle=\dfrac{\cos(\tfrac{\pi}{4g})}{\sin(\tfrac{\pi}{4g})}=\cot(\tfrac{\pi}{4g}),$
$\displaystyle\cosh(d(O,{\boldsymbol{v}}_{0}))$
$\displaystyle=\cot^{2}(\tfrac{\pi}{4g}).$

Second, because
$d(O,{\boldsymbol{m}}_{0})=d({\boldsymbol{m}}_{0},{\boldsymbol{v}}_{1})$,
$[O,{\boldsymbol{m}}_{0},{\boldsymbol{p}}_{1}^{*}]$ and
$[{\boldsymbol{v}}_{1},{\boldsymbol{m}}_{0},{\boldsymbol{p}}_{1}^{*}]$ are
congruent triangles. In particular,
$\angle(O{\boldsymbol{m}}_{0}{\boldsymbol{p}}_{1}^{*})=\angle({\boldsymbol{v}}_{1}{\boldsymbol{m}}_{0}{\boldsymbol{p}}_{1}^{*})=\tfrac{\pi}{4}$.
It follows that

$\cosh(\tfrac{1}{2}d({\boldsymbol{m}}_{0},{\boldsymbol{m}}_{1}))=\cosh(d({\boldsymbol{m}}_{0},{\boldsymbol{p}}_{1}^{*}))=\dfrac{\cos(\tfrac{\pi}{4g})}{\sin(\tfrac{\pi}{4})}=\sqrt{2}\cos(\tfrac{\pi}{4g}).$
(16)

The above formulas yield expressions for
$d(O,{\boldsymbol{m}}_{0}),d(O,{\boldsymbol{v}}_{0})$ and
$d({\boldsymbol{m}}_{0},{\boldsymbol{m}}_{1})$ and comparing these to the
expression for
$\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$ (see
Theorem 2) yields the result. ∎

##  Appendix D Structured algorithm

Like the symmetric algorithm, this algorithm respects the $4g$-fold symmetry
of the Dirichlet region of $\mathbb{M}_{g}$. Before we give the algorithm in
pseudocode, we first explain the idea and the notation. See Figure 26 for an
illustration of the dummy points within one slice of the $4g$-gon.

Figure 26: Dummy points within one slice of the $4g$-gon.

  1. 1.

As in the other algorithms, initially $\mathcal{Q}_{g}$ consists of the
Weierstrass points of $\mathbb{M}_{g}$: the origin, the vertex and the
midpoints of the sides. As usual, the origin and the vertices of $D_{g}$ are
denoted by $O$ and ${\boldsymbol{v}}_{k}$ respectively. The midpoint of side
${\boldsymbol{s}}_{k}$ is denoted by ${\boldsymbol{p}}^{0}_{k}$. Because the
sides are paired to obtain $\mathbb{M}_{g}$, we only consider
$k=0,\ldots,2g-1$ to avoid that several points are actually the same on the
surface. Just as the side ${\boldsymbol{s}}_{k}$ is obtained from
${\boldsymbol{s}}_{0}$ by rotating it around the origin by angle
$\tfrac{k\pi}{2g}$, so ${\boldsymbol{p}}^{0}_{k}$ is obtained from
${\boldsymbol{p}}^{0}_{0}$ by rotating it in the same way. Hence, we use the
lower index as ‘rotation’ index in the definition of the other points as well.

  2. 2.

Secondly, the projections $\pi_{g}({\boldsymbol{p}}^{*}_{k})$ of the midpoints
${\boldsymbol{p}}^{*}_{k}$ of the geodesic segment in $\mathbb{H}^{2}$
connecting consecutive pairs
$({\boldsymbol{p}}^{0}_{k},{\boldsymbol{p}}^{0}_{k+1})$ of midpoints are added
to $\mathcal{Q}_{g}$. These points are unique in the sense that they will be
the only points in $\mathcal{Q}_{g}$ that have their pre-image in
$\widetilde{D}_{g}$ not on some line segment $[O,{\boldsymbol{p}}^{0}_{k}]$.
This is the reason why they have a star as superscript.

  3. 3.

Thirdly, points ${\boldsymbol{p}}^{j}_{0}$ are consecutively added on
$[O,{\boldsymbol{p}}^{j-1}_{0}]$ in such a way that the distance between
consecutive points ${\boldsymbol{p}}^{j-1}_{0}$ and ${\boldsymbol{p}}^{j}_{0}$
is given by
$d({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j-1}_{0})=\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$,
until
$d({\boldsymbol{p}}^{j}_{0},O)\leq\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
By rotating the points in the same way as before we obtain the points
${\boldsymbol{p}}^{j}_{k}$. The projections
$\pi_{g}({\boldsymbol{p}}^{j}_{k})$ are added to $\mathcal{Q}_{g}$. Here, the
upper index denotes the ‘iteration’ index. Notice that the midpoints of the
sides were denoted ${\boldsymbol{p}}^{0}_{k}$ to initialize this process.
Since
$d(O,{\boldsymbol{p}}^{0}_{0})=\operatorname{arccosh}(\cot(\tfrac{\pi}{4g}))$,
this step consists of

$m=\left\lceil\dfrac{\operatorname{arccosh}(\cot(\tfrac{\pi}{4g}))}{\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}}\right\rceil-1$

iterations.

  4. 4.

Finally, observe that the triangles
$[O,{\boldsymbol{p}}^{0}_{k},{\boldsymbol{p}}^{0}_{k+1}]$ and
$[{\boldsymbol{v}},{\boldsymbol{p}}^{0}_{k},{\boldsymbol{p}}^{0}_{k+1}]$ are
congruent under reflection in
$[{\boldsymbol{p}}^{0}_{k},{\boldsymbol{p}}^{0}_{k+1}]$. To establish the same
congruence in $\mathcal{Q}_{g}$, we want to apply this reflection to all
points in $[O,{\boldsymbol{p}}^{0}_{k},{\boldsymbol{p}}^{0}_{k+1}]$ that are
currently in $\pi_{g}^{-1}(\mathcal{Q}_{g})\cap D_{g}$. However, if we do so
directly, we obtain several pairs of points projecting to the same point on
$\mathbb{M}_{g}$. To avoid this, we reflect the points
${\boldsymbol{p}}^{j}_{k}$ in one half of the fundamental polygon across the
line through ${\boldsymbol{p}}^{0}_{k}$ and ${\boldsymbol{p}}^{0}_{k+1}$ and
the points ${\boldsymbol{p}}^{j}_{k}$ in the other half of the fundamental
polygon across the line through ${\boldsymbol{p}}^{0}_{k-1}$ and
${\boldsymbol{p}}^{0}_{k}$. In each case, the image of the
${\boldsymbol{p}}^{j}_{k}$ after reflection is denoted by
${\boldsymbol{q}}^{j}_{k}$ and its projection
$\pi_{g}({\boldsymbol{q}}^{j}_{k})$ is added to $\mathcal{Q}_{g}$.

One of the major advantages of this algorithm is that the combinatorics of the
resulting Delaunay triangulation can be explicitly described. Below we
describe these combinatorics. The proof that this is the Delaunay
triangulation of the dummy point set will be given in Lemma 25. Again, see
Figure 26 for an illustration of the dummy points and the triangulation
$\mathcal{T}$ within one slice of the $4g$-gon.

######  Definition 23.

Define the infinite triangulation $\mathcal{T}$ of
$\pi_{g}^{-1}(\mathcal{Q}_{g})$ as follows:

  * •

As vertices take $\pi_{g}^{-1}(\mathcal{Q}_{g})$.

  * •

The edges completely contained in the hyperbolic triangle
$[O,{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{0}_{1}]$ are given by the
following list.

$({\boldsymbol{p}}^{j}_{k},{\boldsymbol{p}}^{j+1}_{k})$ | $j=0,\ldots,m-1,$ | $k=0,1,$
---|---|---
$({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j+1}_{1})$ | $j=1,\ldots,m-1,$ |
$({\boldsymbol{p}}^{m}_{k},O)$ |  | $k=0,1,$
$({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1})$ | $j=1,\ldots,m,$ |
$({\boldsymbol{p}}^{j}_{k},{\boldsymbol{p}}^{*}_{0})$ | $j=0,1,$ | $k=0,1.$

The other edges can be obtained as the images of the edges in the list above
under the following maps:

    * –

rotation around the origin by angle $\tfrac{k\pi}{2g}$,

    * –

reflection in the line through
${\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{0}_{1}$,

    * –

reflection in the line through
${\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{0}_{1}$, followed by rotation
around the origin by angle $\tfrac{k\pi}{2g}$,

    * –

any one of the above maps, followed by an element of $\Gamma_{g}$.

Algorithm 3 shows the algorithm in pseudocode. We refer to this algorithm as
the structured algorithm.

Input : hyperbolic surface $\mathbb{M}_{g}$

Output : finite point set $\mathcal{Q}_{g}\subset\mathbb{M}_{g}$ such that
$\delta({\mathcal{Q}_{g}})<\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$

1 Initialize: let $\mathcal{Q}_{g}$ be the set $\mathcal{W}_{g}$ of
Weierstrass points of $\mathbb{M}_{g}$.

2 Label the vertex by $v$ and the origin by $O$.

3 For all $k=0,\ldots,4g-1$, label the midpoint of side ${\boldsymbol{s}}_{k}$
by ${\boldsymbol{p}}^{0}_{k}$.

4 For all $k=0,\ldots,4g-1$, label the midpoint of ${\boldsymbol{p}}^{0}_{k}$
and ${\boldsymbol{p}}^{0}_{k+1}$ by ${\boldsymbol{p}}^{*}_{k}$ and add
$\pi_{g}({\boldsymbol{p}}_{k}^{*})$ to $\mathcal{Q}_{g}$.

5 $m\leftarrow\lceil
4\operatorname{arccosh}(\cot(\tfrac{\pi}{4g}))/\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}\rceil-1$.

6 for  _$i=1,\ldots,m$_ do

7 Let ${\boldsymbol{p}}^{j}_{0}$ be the point on
$[{\boldsymbol{p}}^{j-1}_{0},O]$ with
$d({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j-1}_{0})=\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$
and add $\pi_{g}({\boldsymbol{p}}^{j}_{0})$ to $\mathcal{Q}_{g}$.

8 for  _$k=1,\ldots,2g-1$_ do

9 Let ${\boldsymbol{p}}^{j}_{k}$ be ${\boldsymbol{p}}^{j}_{0}$ rotated
clockwise around the origin by angle $\tfrac{k\pi}{2g}$.

10 Let ${\boldsymbol{q}}^{j}_{k}$ be the reflection of
${\boldsymbol{p}}^{j}_{k}$ in the line through
${\boldsymbol{p}}^{0}_{k},{\boldsymbol{p}}^{0}_{k+1}$.

11 Add $\pi_{g}({\boldsymbol{p}}^{j}_{k})$ and
$\pi_{g}({\boldsymbol{q}}^{j}_{k})$ to $\mathcal{Q}_{g}$.

12 end for

13 for  _$k=2g,\ldots,4g-1$_ do

14 Let ${\boldsymbol{p}}^{j}_{k}$ be ${\boldsymbol{p}}^{j}_{0}$ rotated
clockwise around the origin by angle $\tfrac{k\pi}{2g}$.

15 Let ${\boldsymbol{q}}^{j}_{k}$ be the reflection of
${\boldsymbol{p}}^{j}_{k}$ in the line through
${\boldsymbol{p}}^{0}_{k-1},{\boldsymbol{p}}^{0}_{k}$.

16 Add $\pi_{g}({\boldsymbol{p}}^{j}_{k})$ and
$\pi_{g}({\boldsymbol{q}}^{j}_{k})$ to $\mathcal{Q}_{g}$.

17 end for

18

19 end for

Algorithm 3 Structured algorithm

The main difference between the structured algorithm and the other two
algorithms is that there is no while loop in the structured algorithm, only
for loops. As a result, the cardinality of the resulting dummy point set is
known precisely (see Theorem 26). On the other hand, for the cardinality of
the dummy point sets for the refinement or symmetric algorithm we can only
give an estimate and the exact number of points depends on the implementation.

The following two lemmas show that the circumdiameters of triangles
$\mathcal{T}$ are smaller than
$\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$
and that $\mathcal{T}$ is a Delaunay triangulation. As the proofs are rather
technical, the reader may want to skip them at a first reading.

######  Lemma 24.

The circumdiameters of triangles in $\mathcal{T}$ are smaller than
$\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.

###### Proof.

See again Figure 26. By symmetry it is sufficient to consider the
circumscribed disks of the triangles

$[{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}],[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}],[{\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O],[{\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1}],$

for $1\leq j\leq m-1$. For easy reference, the used lengths and angles satisfy
the following relations. Here we denote
$\operatorname{length}([{\boldsymbol{p}},{\boldsymbol{q}}])$ by abuse of
notation by $[{\boldsymbol{p}},{\boldsymbol{q}}]$.

$\displaystyle[{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{*}_{0}]$
$\displaystyle=[{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0}]=\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{},$
(17)
$\displaystyle\cosh(\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})$
$\displaystyle=1+2\cos(\tfrac{\pi}{2g}),$ (18)
$\displaystyle\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})$
$\displaystyle=\tfrac{\pi}{4},$ (19)
$\displaystyle\sinh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])$
$\displaystyle=\sinh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\sin(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})),$
(20)
$\displaystyle\sin\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})$
$\displaystyle=\dfrac{\sinh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\sin\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})}{\sinh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$
(21)
$\displaystyle\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{1}_{1})$
$\displaystyle=\pi-2\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0}).$
(22)

Equations (17) and (18) follow from the construction in the proof of Lemma 9
and from Theorem 2, respectively. Equation (19) holds because
$\angle(O{\boldsymbol{p}}_{0}^{0}{\boldsymbol{v}}_{1})=\tfrac{\pi}{2}$ and the
triangles $[O,{\boldsymbol{p}}_{0}^{0},{\boldsymbol{p}}_{1}^{0}]$ and
$[{\boldsymbol{v}}_{1},{\boldsymbol{p}}_{0}^{0},{\boldsymbol{p}}_{1}^{0}]$ are
congruent. Equation (20) follows from the application of [6, Theorem
7.11.2(ii)] to the triangle with vertices
${\boldsymbol{p}}_{0}^{1},{\boldsymbol{p}}_{0}^{0}$ and the midpoint of
${\boldsymbol{p}}_{0}^{1}$ and ${\boldsymbol{p}}_{0}^{*}$: this is a right-
angled triangle, because
$[{\boldsymbol{p}}_{0}^{1},{\boldsymbol{p}}_{0}^{0},{\boldsymbol{p}}_{0}^{*}]$
is isosceles. Equation (21) is the sine rule [6, Chapter 7.12] in triangle
$[{\boldsymbol{p}}_{0}^{1},{\boldsymbol{p}}_{0}^{0},{\boldsymbol{p}}_{0}^{*}]$.
Finally, Equation (22) holds by symmetry.

The circumradius $R$ of an isosceles triangle with legs of length $b$ and
vertex angle $\alpha$ (see Figure 27 satisfies

$\tanh(R)=\dfrac{\tanh(\tfrac{1}{2}c)}{\cos(\tfrac{1}{2}\alpha)},$ (23)

which can be derived by applying [6, Theorem 7.1..2(iii)] to the interior
triangle with edges of length $R$ and $\tfrac{1}{2}b$.

Figure 27: Deriving a formula for the circumradius of an isosceles triangle.

First, consider the circumradius
$R({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
of
$[{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}]$.
By the above observation,

$\displaystyle\tanh(R({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}))$
$\displaystyle=\dfrac{\tanh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})}{\cos(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))},$
$\displaystyle=\sqrt{4-2\sqrt{2}}\tanh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}).$

We want to prove that
$R({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})<\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$,
or, equivalently, that

$\tanh(R({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}))<\tanh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}).$

Because
$\tanh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})$
is strictly increasing as function of $g$, we know that

$\sqrt{4-2\sqrt{2}}\tanh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})<\sqrt{4-2\sqrt{2}}\lim_{g\rightarrow\infty}\tanh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\approx
0.448.$

For the same reason,

$\tanh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\geq\tanh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\big{|}_{g=2}\approx
0.643.$

It follows that
$\tanh(R({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}))<\tanh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})$
holds. This proves that the circumdiameter of
$[{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}]$
is smaller than
$\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
Second, consider the circumradius
$R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
of
$[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}]$.
By a similar computation as above, we see that

$\displaystyle\tanh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}))$
$\displaystyle=\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\cos(\tfrac{1}{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{1}_{1}))},$
$\displaystyle\overset{\eqref{eq:topangle}}{=}\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\sin\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})}.$

By using

$\displaystyle\sin\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})$
$\displaystyle\overset{\eqref{eq:interiorangle}}{=}\dfrac{\sinh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\sin\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})}{\sinh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$
$\displaystyle=\dfrac{\sinh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\cdot
2\sin(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))\cos(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))}{\sinh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$
$\displaystyle\overset{\eqref{eq:firstdiagonal}}{=}\dfrac{\sinh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])\cdot
2\cos(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))}{2\sinh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])\cosh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$
$\displaystyle=\dfrac{\cos(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))}{\cosh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$

we can rewrite this as

$\displaystyle\tanh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}))$
$\displaystyle=\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])\cosh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\cos(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))},$
$\displaystyle=\dfrac{\sinh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\cos(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))},$
$\displaystyle\overset{\eqref{eq:firstdiagonal}}{=}\sinh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\tan(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})),$
$\displaystyle=(\sqrt{2}-1)\sinh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}).$

By the same reasoning as before,

$\tanh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}))<(\sqrt{2}-1)\lim_{g\rightarrow\infty}\sinh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\approx
0.414,$

which shows that
$\tanh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}))<\tanh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})$.
This proves that the circumdiameter of
$[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}]$
is smaller than
$\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
Third, consider the circumradius
$R({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$ of
$[{\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O]$. We know that
$[O,{\boldsymbol{p}}^{m}_{0}]=x\leq\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
By a similar computation as above, we see that

$\displaystyle\tanh(R({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O))$
$\displaystyle=\dfrac{\tanh(\tfrac{1}{2}x)}{\cos(\tfrac{\pi}{4g})},$
$\displaystyle\leq\dfrac{\tanh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})}{\cos(\tfrac{\pi}{8})},$
$\displaystyle=\tanh(R({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})),$
$\displaystyle<\tanh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}),$

from which we conclude that
$R({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)<\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
This proves that the circumdiameter of
$[{\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O]$ is smaller than
$\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
Finally, let $1\leq j\leq m-1$ and consider the circumradius
$R({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
of
$[{\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1}]$.
In fact, the points
${\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{0},{\boldsymbol{p}}^{j+1}_{1}$
are concircular due to symmetry, so the center of the circumscribed circle of
$[{\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1}]$
lies on the line segment $[O,{\boldsymbol{p}}^{*}_{0}]$. It follows that the
circumradius of this disk decreases when the distance of
${\boldsymbol{p}}^{j}_{0}$ to $[O,{\boldsymbol{p}}^{*}_{0}]$ decreases, or
equivalently, when the distance $[O,{\boldsymbol{p}}^{j}_{0}]$ decreases.
Hence, for all $1\leq j\leq m-1$,
$R({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})<R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$.
Therefore, it is sufficient to show that
$R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})<\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
In this case, we cannot use equation (23), since
$[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}]$
is not an isosceles triangle. There exists a more general expression for the
circumradius of an arbitrary (not necessarily isosceles) triangle, but this
will lead to unnecessarily long expressions. Instead, consider the
circumcenter ${\boldsymbol{c}}$ of
$[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}]$.
See also Figure 28 for a more detailed view of the relevant triangles.

Figure 28: Close-up of situation at
$[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}]$

By the discussion above, we know that
${\boldsymbol{c}}\in[O,{\boldsymbol{p}}^{*}_{0}]$. Let
${\boldsymbol{c}}^{\prime}$ be the orthogonal projection of ${\boldsymbol{c}}$
onto $[O,{\boldsymbol{p}}^{0}_{1}]$. Since
$[{\boldsymbol{c}},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}]$ is
isosceles, we know that

$[O,{\boldsymbol{c}}^{\prime}]=[O,{\boldsymbol{p}}^{2}_{1}]+\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}=[O,{\boldsymbol{p}}^{0}_{1}]-\tfrac{3}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}=\operatorname{arccosh}(\cot(\tfrac{\pi}{4g}))-\tfrac{3}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{},$

from which it can be seen that $[O,{\boldsymbol{c}}^{\prime}]$ is strictly
increasing as function of $g$. Furthermore, [6, Theorem 7.11.2(i)]

$\tanh([{\boldsymbol{c}},{\boldsymbol{c}}^{\prime}])=\sinh([O,{\boldsymbol{c}}^{\prime}])\tan(\tfrac{\pi}{4g}),$

which after substitution of our expression for $[O,{\boldsymbol{c}}^{\prime}]$
can be rewritten as

$\tanh([{\boldsymbol{c}},{\boldsymbol{c}}^{\prime}])=\sqrt{1-\tan^{2}(\tfrac{\pi}{4g})}\cosh(\tfrac{3}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})-\sinh(\tfrac{3}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}).$

By the Pythagorean law in
$[{\boldsymbol{c}},{\boldsymbol{c}}^{\prime},{\boldsymbol{p}}^{2}_{1}]$ we
know

$\cosh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}))=\cosh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\cosh([{\boldsymbol{c}},{\boldsymbol{c}}^{\prime}]).$

Using this expression of
$R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$,
it can be seen that
$R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$
is strictly increasing as function of $g$. Therefore,

$\cosh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}))<\lim_{g\rightarrow\infty}\cosh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}))\approx
1.140,$

which can be obtained by computing the corresponding limits of
$\cosh(\tfrac{1}{8}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})$
and $\cosh([{\boldsymbol{c}},{\boldsymbol{c}}^{\prime}])$. It follows that
$\tanh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}))<0.480$,
so
$\tanh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}))<\tanh(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})$.
This proves that the circumdiameter of
$[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1}]$
is smaller than
$\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
Since the circumdiameters of all four triangles are smaller than
$\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$
and since by symmetry every triangle is congruent to one of these four, this
concludes the proof. ∎

######  Lemma 25.

The triangulation $\mathcal{T}$ is a Delaunay triangulation of
$\pi_{g}^{-1}(\mathcal{Q}_{g})$.

###### Proof.

We show that the circumdisks of triangles in $\mathcal{T}$ do not have
vertices of $\mathcal{T}$ in their interior. Denote the circumscribed circle
and _open_ circumscribed disk of a triangle
$[{\boldsymbol{p}},{\boldsymbol{q}},{\boldsymbol{r}}]$ by
$C({\boldsymbol{p}},{\boldsymbol{q}},{\boldsymbol{r}})$ and
$D({\boldsymbol{p}},{\boldsymbol{q}},{\boldsymbol{r}})$ respectively, and
similarly when more than three points are concircular. Observe in particular
that $C({\boldsymbol{p}},{\boldsymbol{q}},{\boldsymbol{r}})\cap
D({\boldsymbol{p}},{\boldsymbol{q}},{\boldsymbol{r}})=\emptyset$. Denote the
hyperbolic line through points ${\boldsymbol{p}},{\boldsymbol{q}}$ by
$L({\boldsymbol{p}},{\boldsymbol{q}})$ and the open and closed line segments
connecting ${\boldsymbol{p}},{\boldsymbol{q}}$ by
$({\boldsymbol{p}},{\boldsymbol{q}}),[{\boldsymbol{p}},{\boldsymbol{q}}]$
respectively. By symmetry it is sufficient to consider only
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}),D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}),D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O),D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$,
for $1\leq j\leq m-1$. For convenience, we treat the cases for each circumdisk
in a fixed order, namely

  1. 1.

$O,{\boldsymbol{v}}$

  2. 2.

${\boldsymbol{p}}^{*}_{k},k=0,\ldots,4g-1$,

  3. 3.

${\boldsymbol{p}}^{j}_{k},k=0,\ldots,4g-1,j=0,\ldots,m$,

  4. 4.

${\boldsymbol{q}}^{j}_{k},k=0,\ldots,4g-1,j=1,\ldots,m$.

First, consider
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$.

  1. 1.

Clearly, $O$ and ${\boldsymbol{v}}$ are too far away from
${\boldsymbol{p}}^{*}_{0}$ to be inside
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$.

  2. 2.

Since ${\boldsymbol{p}}^{*}_{0}\in
C({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$,
we know that ${\boldsymbol{p}}^{*}_{0}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$.
Since the center of
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
lies inside
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
on the bisector of angle
$\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})$
we see that ${\boldsymbol{p}}^{*}_{4g-1}$ is farther away from this center
than ${\boldsymbol{p}}^{*}_{0}$. Since ${\boldsymbol{p}}^{*}_{0}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$,
it follows that ${\boldsymbol{p}}^{*}_{4g-1}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
as well. Since
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})\cap
C({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})$ is contained
in the shortest open chord of
$C({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})$ between
${\boldsymbol{p}}^{*}_{0}$ and ${\boldsymbol{p}}^{*}_{4g-1}$, we see that
${\boldsymbol{p}}^{*}_{k}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
for $k=0,\ldots,4g-1$.

  3. 3.

Since the center of
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
is in the interior of
$[{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}]\subset[O,{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{*}_{0}]$,
we know that ${\boldsymbol{p}}^{j}_{0}$ is closer to the center of
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
than ${\boldsymbol{p}}^{j}_{k}$ for $j=0,\ldots,m$ and $k\neq 0$. Because
$L(O,{\boldsymbol{p}}^{0}_{0})\cap
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})=({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0})$,
we know that ${\boldsymbol{p}}^{j}_{0}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
for all $j=0,\ldots,m$. Therefore, ${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
for $j=0,\ldots,m$ and $k=0,\ldots,4g-1$.

  4. 4.

By a reasoning similar to above, ${\boldsymbol{p}}^{j}_{k}$ is closer to the
center of
$D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
than ${\boldsymbol{q}}^{j}_{k}$. Since by the previous step
${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
for $j=1,\ldots,m$ and $k=0,\ldots,4g-1$, it follows that
${\boldsymbol{q}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0})$
for $j=1,\ldots,m$ and $k=0,\ldots,4g-1$ as well.

Second, consider
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$.

  1. 1.

Clearly, $O$ and ${\boldsymbol{v}}$ are too far away from
${\boldsymbol{p}}^{*}_{0}$ to be inside
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$.

  2. 2.

The circle
$C({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
is tangent to
$C({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})$, because both
circles have their center on $[O,{\boldsymbol{p}}_{0}^{*}]$ and pass through
${\boldsymbol{p}}_{0}^{*}$. Since the radius of
$C({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
is smaller than the radius of
$C({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})$, this means
that
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})\subseteq
D({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})$. Therefore,
${\boldsymbol{p}}^{*}_{k}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
for all $k=0,\ldots,4g-1$.

  3. 3.

First, to prove that ${\boldsymbol{p}}^{j}_{0}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
for all $j=0,\ldots,m$, we now show that
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})\cap(O,{\boldsymbol{p}}^{1}_{0})=\emptyset$.
First observe that the line $L(O,{\boldsymbol{p}}^{0}_{0})$ intersects
$C({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
in one or two points. If the intersection consists of one point, then it has
to be ${\boldsymbol{p}}^{1}_{0}$ and we are done. If the intersection consists
of two points, then it is sufficient to show that ${\boldsymbol{p}}^{1}_{0}$
is the closest of these two to $O$. Let ${\boldsymbol{p}}^{M}_{0}$ denote the
midpoint of ${\boldsymbol{p}}^{1}_{0}$ and ${\boldsymbol{p}}^{1}_{1}$. It is
sufficient to show that
$[{\boldsymbol{p}}^{*}_{0},{\boldsymbol{p}}^{M}_{0}]\geq
R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$,
since then the center of
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
is contained in
$[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0}]$.
It is known that [6, Theorem 7.11.2(iii)]

$\tanh([{\boldsymbol{p}}^{*}_{0},{\boldsymbol{p}}^{M}_{0}])=\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])\cos\tfrac{1}{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{1}_{1})=\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])\sin\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0}),$

where the second equality follows from Equation (22) in the proof of Lemma 24.
Therefore, $[{\boldsymbol{p}}^{*}_{0},{\boldsymbol{p}}^{M}_{0}]\geq
R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
is equivalent with the following sequence of inequalities:

$\displaystyle\tanh([{\boldsymbol{p}}^{*}_{0},{\boldsymbol{p}}^{M}_{0}])$
$\displaystyle\geq\tanh(R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})),$
$\displaystyle\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])\sin\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})$
$\displaystyle\geq\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\sin\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})},$
$\displaystyle\sin^{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})$
$\displaystyle\geq\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}.$

Since

$\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}=\tfrac{1}{2}\tanh^{2}(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])+\tfrac{1}{2},$

and since $[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}]$ is strictly
increasing by (20) in the proof of Lemma 24, we find that

$\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}\leq\lim_{g\rightarrow\infty}\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}\approx
0.542.$

Furthermore, since

$\displaystyle\sin^{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})$
$\displaystyle\overset{\eqref{eq:interiorangle}}{=}\dfrac{\sinh^{2}(\tfrac{1}{4}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{})\sin^{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})}{\sinh^{2}([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$
$\displaystyle\overset{\eqref{eq:firstdiagonal}}{=}\dfrac{\sinh^{2}(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])\sin^{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})}{\sin^{2}(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))\sinh^{2}([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$
$\displaystyle=\dfrac{\cos^{2}(\tfrac{1}{2}\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0}))}{\cosh^{2}(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])},$

and since $\angle(O{\boldsymbol{p}}^{0}_{0}{\boldsymbol{p}}^{*}_{0})$ is
constant and $[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}]$ strictly
increasing, we see that
$\sin^{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})$
is strictly decreasing, so

$\sin^{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})\geq\lim_{g\rightarrow\infty}\sin^{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})\approx
0.744.$

From this we can conclude that

$\sin^{2}\angle({\boldsymbol{p}}^{1}_{0}{\boldsymbol{p}}^{*}_{0}{\boldsymbol{p}}^{0}_{0})\geq\dfrac{\tanh(\tfrac{1}{2}[{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}{\tanh([{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{*}_{0}])}$

holds, which by the chain of equivalent inequalities means that
$[{\boldsymbol{p}}^{*}_{0},{\boldsymbol{p}}^{M}_{0}]\geq
R({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$.
It follows that if $L(O,{\boldsymbol{p}}^{0}_{0})\cap
C({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
consists of two points, then ${\boldsymbol{p}}^{1}_{0}$ is the closest of
these two. This implies that
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})\cap(O,{\boldsymbol{p}}^{1}_{0})=\emptyset$.
We conclude that ${\boldsymbol{p}}^{j}_{0}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
for all $j=0,\ldots,m$. By symmetry, we see that
${\boldsymbol{p}}^{j}_{1}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
for all $j=0,\ldots,m$.
Second, by the reasoning above we see that
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
is contained in the union of the triangle
$[O,{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{0}_{1}]$ and the (open) annulus

$D({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})\setminus(D({\boldsymbol{p}}^{1}_{0},\ldots,{\boldsymbol{p}}^{1}_{4g-1})\cup
C({\boldsymbol{p}}^{1}_{0},\ldots,{\boldsymbol{p}}^{1}_{4g-1}))$

centered at $O$, with boundary passing through ${\boldsymbol{p}}^{*}_{0}$ on
one side and through ${\boldsymbol{p}}^{1}_{0}$ on the other side. Combining
this with ${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
for $j=0,\ldots,m$ and $k=0,1$, we can immediately conclude that
${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
for $j=0,\ldots,m$ and $k=0,\ldots,4g-1$.

  4. 4.

As we have seen before,
$C({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
is tangent to
$C({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})$, which means
that
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
is contained in the interior of the $4g$-gon
$[{\boldsymbol{p}}^{0}_{0},\ldots,{\boldsymbol{p}}^{0}_{k},\ldots,{\boldsymbol{p}}^{0}_{4g-1}]$.
Therefore, ${\boldsymbol{q}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{*}_{0})$
for $j=1,\ldots,m$ and $k=0,\ldots,4g-1$.

Third, consider $D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$.

  1. 1.

Since $O\in C({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$, we know
that $O\not\in D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$.
Clearly, ${\boldsymbol{v}}$ is too far away from $O$ to be inside
$D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$.

  2. 2.

Clearly, the points ${\boldsymbol{p}}^{*}_{k}$ for $k=0,\ldots,4g-1$ are too
far away from $O$ to be inside
$D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$.

  3. 3.

Since $D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$ is contained in
the union of the disk
$D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},\ldots,{\boldsymbol{p}}^{m}_{4g-1})$
and the (closed) triangle
$[O,{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{0}_{1}]$, we immediately see
that ${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$ for all $j=0,\ldots,m$
and $k\neq 0,1$. Since $L(O,{\boldsymbol{p}}^{m}_{0})\cap
D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)=(O,{\boldsymbol{p}}^{m}_{0})$,
it follows that ${\boldsymbol{p}}^{j}_{0}\not\in
D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$ for $j=0,\ldots,m$.
Similarly, ${\boldsymbol{p}}^{j}_{1}\not\in
D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$ for $j=0,\ldots,m$.
Therefore, ${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$ for all $j=0,\ldots,m$
and $k=0,\ldots,4g-1$.

  4. 4.

Clearly, the points ${\boldsymbol{q}}^{j}_{k}$ for $j=1,\ldots,m$ and
$k=0,\ldots,4g-1$ are too far away from $O$ to be inside
$D({\boldsymbol{p}}^{m}_{0},{\boldsymbol{p}}^{m}_{1},O)$.

Finally, let $1\leq j\leq n-1$ and consider
$D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$.

  1. 1.

Clearly, ${\boldsymbol{v}}$ is too far away from the center of
$D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
to be inside
$D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$.
Moreover, $O\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$,
since $L(O,{\boldsymbol{p}}^{0}_{1})\cap
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})=({\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$.

  2. 2.

Of the set of disks
$\\{D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1}),j=1,\ldots,m-1\\}$,
the one that is closest to ${\boldsymbol{p}}^{*}_{0}$ is
$D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$,
i.e., if ${\boldsymbol{p}}^{*}_{0}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$,
then ${\boldsymbol{p}}^{*}_{0}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=1,\ldots,m-1$. Observe that
$C({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$
and
$C({\boldsymbol{p}}^{*}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1})$
intersect in the points ${\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1}$.
Since the center of
$C({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$
is closer to $O$ than the center of
$C({\boldsymbol{p}}^{*}_{0},{\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1})$,
we can conclude that ${\boldsymbol{p}}^{*}_{0}\not\in
D({\boldsymbol{p}}^{1}_{0},{\boldsymbol{p}}^{1}_{1},{\boldsymbol{p}}^{2}_{1})$.
Therefore, ${\boldsymbol{p}}^{*}_{0}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=1,\ldots,m-1$. It follows that
$D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})\subseteq
D({\boldsymbol{p}}^{*}_{0},\ldots,{\boldsymbol{p}}^{*}_{4g-1})$ for
$j=1,\ldots,m-1$, which implies that ${\boldsymbol{p}}^{*}_{k}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=1,\ldots,m-1$ and $k=0,\ldots,4g-1$.

  3. 3.

Since
${\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{0},{\boldsymbol{p}}^{j+1}_{1}$
are concircular, we see that
$D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
is contained in the union of the (closed) triangle
$[O,{\boldsymbol{p}}^{0}_{0},{\boldsymbol{p}}^{0}_{1}]$ and the (open) annulus

$D({\boldsymbol{p}}^{j}_{0},\ldots,{\boldsymbol{p}}^{j}_{4g-1})\setminus(D({\boldsymbol{p}}^{j+1}_{0},\ldots,{\boldsymbol{p}}^{j+1}_{4g-1})\cup
C({\boldsymbol{p}}^{j+1}_{0},\ldots,{\boldsymbol{p}}^{j+1}_{4g-1}))$

centered at $O$, with boundary passing through ${\boldsymbol{p}}^{j}_{0}$ on
one side and through ${\boldsymbol{p}}^{j+1}_{0}$ on the other side.
Therefore, ${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=0,\ldots,m$ and $k\neq 0,1$. Furthermore, since
$L(O,{\boldsymbol{p}}^{0}_{0})\cap
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})=({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j+1}_{0})$,
we see that ${\boldsymbol{p}}^{j}_{0}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=0,\ldots,m$. Similarly, ${\boldsymbol{p}}^{j}_{1}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=0,\ldots,m$. We conclude that ${\boldsymbol{p}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=0,\ldots,m$ and $k=0,\ldots,4g-1$.

  4. 4.

Clearly,
$D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
is contained in the $4g$-gon
$[{\boldsymbol{p}}^{0}_{0},\ldots,{\boldsymbol{p}}^{0}_{k},\ldots,{\boldsymbol{p}}^{0}_{4g-1}]$,
which means that ${\boldsymbol{q}}^{j}_{k}\not\in
D({\boldsymbol{p}}^{j}_{0},{\boldsymbol{p}}^{j}_{1},{\boldsymbol{p}}^{j+1}_{1})$
for $j=1,\ldots,m$ and $k=0,\ldots,4g-1$.

Since each triangle of the infinite triangulation $\mathcal{T}$ is congruent
to one of the triangles above and since the circumdisk of each of the above
triangles is empty, it follows that $\mathcal{T}$ is a Delaunay triangulation.
∎

From these two lemmas the main statement of this subsection follows directly.

######  Theorem 26.

The structured algorithm terminates. The resulting dummy point
$\mathcal{Q}_{g}$ set satisfies
$\delta({\mathcal{Q}_{g}})<\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$
and its cardinality $|\mathcal{Q}_{g}|$ is equal to

$6g+2+8g(\lceil
4\operatorname{arccosh}(\cot(\tfrac{\pi}{4g}))/\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}\rceil-1).$

A Delaunay triangulation
$\operatorname{DT}_{\mathbb{D}}\mathopen{}\left(\pi_{g}^{-1}(\mathcal{Q}_{g})\right)\mathclose{}$
is given by $\mathcal{T}$.

###### Proof.

Termination of the algorithm is trivial. By Lemma 24, the resulting dummy
point set satisfies
$\delta({\mathcal{Q}_{g}})<\tfrac{1}{2}\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}$.
The cardinality of $\mathcal{Q}_{g}$ can be computed as follows. In line 1,
$\mathcal{Q}_{g}$ contains the $2g+2$ Weierstrass points of $\mathbb{M}_{g}$.
In line 4 we add $4g$ points to $\mathcal{Q}_{g}$. There are

$m=\lceil
4\operatorname{arccosh}(\cot(\tfrac{\pi}{4g}))/\operatorname{sys}\mathopen{}\left(\mathbb{M}_{g}\right)\mathclose{}\rceil-1$

iterations of the for loop in line 6, each adding $8g$ points
$\mathcal{Q}_{g}$. The cardinality of $\mathcal{Q}_{g}$ is obtained by adding
these expressions. By Lemma 25, $\mathcal{T}$ is a Delaunay triangulation.
This finishes the proof. ∎

## References

  * [1] William Abikoff.  The Uniformization Theorem.  The American Mathematical Monthly, 88(8):574–592, 1981.  doi:10.2307/2320507.
  * [2] H. Akrout.  Un processus effectif de détermination des systoles pour les surfaces hyperboliques.  Geometriae Dedicata, 121(1):1–8, 2006.  doi:10.1007/s10711-006-9076-x.
  * [3] M. A. Armstrong.  Basic Topology.  Undergraduate Texts in Mathematics. Springer New York, 2013.
  * [4] R. Aurich, E. B. Bogomolny, and F. Steiner.  Periodic orbits on the regular hyperbolic octagon.  Physica D: Nonlinear Phenomena, 48(1):91–101, 1991.  doi:10.1016/0167-2789(91)90053-C.
  * [5] R. Aurich and F. Steiner.  On the periodic orbits of a strongly chaotic system.  Physica D: Nonlinear Phenomena, 32(3):451–460, 1988.  doi:10.1016/0167-2789(88)90068-1.
  * [6] Alan F. Beardon.  The geometry of discrete groups.  Springer-Verlag New York, 1 edition, 1983.  doi:10.1007/978-1-4612-1146-4.
  * [7] Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud.  Hyperbolic Delaunay complexes and Voronoi diagrams made practical.  Journal of Computational Geometry, 5:56–85, 2014.  doi:10.20382/jocg.v5i1a4.
  * [8] Mikhail Bogdanov, Monique Teillaud, and Gert Vegter.  Delaunay triangulations on orientable surfaces of low genus.  In Proceedings of the Thirty-second International Symposium on Computational Geometry, pages 20:1–20:15, 2016.  doi:10.4230/LIPIcs.SoCG.2016.20.
  * [9] Oskar Bolza.  On Binary Sextics with Linear Transformations into Themselves.  American Journal of Mathematics, 10:47–70, 1887.  doi:10.2307/2369402.
  * [10] A. Bowyer.  Computing Dirichlet tessellations.  The Computer Journal, 24(2):162–166, 1981.  doi:10.1093/comjnl/24.2.162.
  * [11] P. Buser.  Geometry and Spectra of Compact Riemann Surfaces.  Progress in Mathematics Series. Birkhäuser, 1992.
  * [12] P. Buser and P. Sarnak.  On the period matrix of a Riemann surface of large genus (with an Appendix by J.H. Conway and N.J.A. Sloane).  Inventiones mathematicae, 117:27–56, 1994.  doi:10.1007/BF01232233.
  * [13] Manuel Caroli and Monique Teillaud.  3D periodic triangulations.  In CGAL User and Reference Manual. CGAL Editorial Board, 3.5 edition, 2009.  URL: http://doc.cgal.org/latest/Manual/packages.html#PkgPeriodic3Triangulation3Summary.
  * [14] Manuel Caroli and Monique Teillaud.  Delaunay triangulations of closed Euclidean d-orbifolds.  Discrete & Computational Geometry, 55(4):827–853, 2016.  URL: https://hal.inria.fr/hal-01294409, doi:10.1007/s00454-016-9782-6.
  * [15] P. Chossat, G. Faye, and O. Faugeras.  Bifurcation of hyperbolic planforms.  Journal of Nonlinear Science, 21:465–498, 2011.  doi:10.1007/s00332-010-9089-3.
  * [16] M. Dehn.  Transformation der Kurven auf zweiseitigen Flächen.  Mathematische Annalen, 72(3):413–421, 1912.  doi:10.1007/BF01456725.
  * [17] Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud.  Flipping geometric triangulations on hyperbolic surfaces.  In Proceedings 36th International Symposium on Computational Geometry, pages 35:1–35:16, 2020.  doi:10.4230/LIPIcs.SoCG.2020.35.
  * [18] Olivier Devillers, Sylvain Pion, and Monique Teillaud.  Walking in a triangulation.  International Journal of Foundations of Computer Science, 13:181–199, 2002.  URL: https://hal.inria.fr/inria-00102194, doi:10.1142/S0129054102001047.
  * [19] Olivier Devillers and Monique Teillaud.  Perturbations for Delaunay and weighted Delaunay 3D Triangulations.  Computational Geometry: Theory and Applications, 44:160–168, 2011\.  URL: http://hal.inria.fr/inria-00560388/, doi:10.1016/j.comgeo.2010.09.010.
  * [20] Vincent Despré, Benedikt Kolbe, and Monique Teillaud.  Half-minimizers and Delaunay triangulations on closed hyperbolic surfaces.  Technical report, INRIA, 2020.  URL: https://hal.inria.fr/hal-03045921.
  * [21] Matthijs Ebbens.  Delaunay triangulations on hyperbolic surfaces.  Master’s thesis, University of Groningen, 2017.  URL: http://fse.studenttheses.ub.rug.nl/id/eprint/15727.
  * [22] Matthijs Ebbens, Hugo Parlier, and Gert Vegter.  Minimal Delaunay triangulations of hyperbolic surfaces, 2020.  arXiv:2011.09847.
  * [23] Hershel M Farkas and Irwin Kra.  Riemann surfaces.  In Riemann surfaces, pages 9–31. Springer, 1992.
  * [24] Martin Greendlinger.  Dehn’s algorithm for the word problem.  Communications on Pure and Applied Mathematics, 13(1):67–83, 1960\.  doi:10.1002/cpa.3160130108.
  * [25] Iordan Iordanov.  Delaunay triangulations of a family of symmetric hyperbolic surfaces in practice.  PhD thesis, Université de Lorraine, 2019.  URL: https://tel.archives-ouvertes.fr/tel-02072155.
  * [26] Iordan Iordanov and Monique Teillaud.  Implementing Delaunay triangulations of the Bolza surface.  In Proceedings of the Thirty-third International Symposium on Computational Geometry, pages 44:1–44:15, 2017.  doi:10.4230/LIPIcs.SoCG.2017.44.
  * [27] Iordan Iordanov and Monique Teillaud.  2D periodic hyperbolic triangulations.  In CGAL User and Reference Manual. CGAL Editorial Board, 4.14 edition, 2019.  URL: https://doc.cgal.org/latest/Manual/packages.html#PkgPeriodic4HyperbolicTriangulation2.
  * [28] Clément Jamin, Sylvain Pion, and Monique Teillaud.  3D triangulations.  In CGAL User and Reference Manual. CGAL Editorial Board.  URL: https://doc.cgal.org/latest/Manual/packages.html#PkgTriangulation3.
  * [29] Mikhail G. Katz, Mary Schaps, and Uzi Vishne.  Logarithmic growth of systole of arithmetic riemann surfaces along congruence subgroups.  J. Differential Geom., 76(3):399–422, 07 2007.  URL: http://projecteuclid.org/euclid.jdg/1180135693.
  * [30] Charles L. Lawson.  Software for $C^{1}$ surface interpolation.  In Symposium on Mathematical Software, 1977.  NASA Technical Report JPL-PUBL-77-30.  URL: https://ntrs.nasa.gov/citations/19770025881.
  * [31] T Long Calvin.  Elementary introduction to number theory.  Lexington: DC Heath and Company, LCCN, 77171950, 1972.
  * [32] J. R. Munkres.  Elements of Algebraic Topology.  Advanced book classics. Perseus Books, 1984.
  * [33] Marjatta Näätänen.  Regular n-gons and Fuchsian groups.  Annales Academiae Scientiarum Fennicae, Series A I Mathematica, 7:291–300, 1982.  doi:10.5186/aasfm.1982.0724.
  * [34] Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud.  Generalizing CGAL periodic Delaunay triangulations.  In Proceedings 28th European Symposium on Algorithms, pages 75:1–75:17, 2020.  (Best Paper Award - Track B: Engineering and Applications).  doi:10.4230/LIPIcs.ESA.2020.75.
  * [35] J. Ratcliffe.  Foundations of Hyperbolic Manifolds.  Number vol. 10 in Graduate Texts in Mathematics. Springer, 2006.
  * [36] Jim Ruppert.  A Delaunay refinement algorithm for quality 2-dimensional mesh generation.  Journal of algorithms, 18(3):548–585, 1995.  doi:10.1006/jagm.1995.1021.
  * [37] Paul Schmutz Schaller.  Teichmüller Space and Fundamental Domains of Fuchsian Groups.  L’Enseignement Mathématique, 45:169–187, 1999.
  * [38] D. F. Watson.  Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes.  The Computer Journal, 24(2):167–172, 1981.  doi:10.1093/comjnl/24.2.167.
  * [39] C. K. Yap and T. Dubé.  The exact computation paradigm.  In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, volume 4 of Lecture Notes Series on Computing, pages 452–492. World Scientific, Singapore, 2nd edition, 1995.  doi:10.1142/9789812831699_0011.
  * [40] Chee Yap _et al._ The CORE library project.  URL: http://cs.nyu.edu/exact/core_pages/intro.html.


# Automated Time-frequency Domain Audio Crossfades using Graph Cuts

###### Abstract

The problem of transitioning smoothly from one audio clip to another arises in
many music consumption scenarios; especially as music consumption has moved
from professionally curated and live-streamed radios to personal playback
devices and services. Classically, transitioning from one song to another has
been reliant on either pre-mixed transitions on recorded digital or physical
media, hardware or software crossfading on the playback device, or
professional transitions by a host or disk jockey (DJ). While options for
software crossfading are ubiquitous on music streaming platforms and media
players alike, these transitions pale in quality when compared to those
manually applied by an audio engineer or DJ who can harmonically and
rhythmically align tracks—and importantly—manually apply equalizer (EQ)
filters during transitions. The application of EQ filters specifically allow
for different transitions in different audio spectrums. For example, the bass
register of one track can be made to replace the bass register of another
track before transitioning the higher frequencies. Typically the task of
deciding how and where to apply transitions in the frequency domain has been
completed manually using a limited number of EQ filters.

There is much research on creating, sorting, and extending playlists so as to
have tracks naturally flow into each other, as well as on determining optimal
times to transition between similar tracks [1, 8, 3, 4, 6]. Both of these
research areas play a key role in synthesising a human DJ. To our knowledge,
however, all of these approaches still rely on classical methods of
transitioning tracks using amplitude in the time domain (crossfading).

Through the application of an existing visual texture extension algorithm
borrowed from computer vision, we present the first steps toward a new method
of automatically transitioning from one audio clip to another by discretizing
the frequency spectrum into bins and then finding transition times for each
bin. [5].

We begin by phrasing the problem of transitioning from one song to another as
a graph optimization problem: the graph represents the two songs in the
transition range, and a cut happens when we transition from one song to the
other at a particular time point. To obtain these representations we first
apply a short term fourier transform (STFT) to each song, and then convert the
resulting complex time-frequency mapped amplitude values into real decibel
values. In order to align the tracks we apply rudimentary tempo matching and
beat alignment using the libROSA Python library, and overlap the tracks by a
number of beats [7]. We call the resulting STFT transformed data of the first
and second song’s overlapped segments matrix $A$ and matrix $B$ respectfully,
as seen in Figure 3. Next, we define a simple loss function:

$w^{k,l}_{i,j}(A,B)=||A_{i,j}-B_{i,j}||+||A_{k,l}-B_{k,l}||$ (1)

We apply the loss function to each adjacent time-frequency bin and use the
resulting values to assign weights to edges in an undirected graph with
dimensions equal to $A$ and $B$. Finally, the resulting graphs left-most nodes
are anchored to a source node, and the right-most nodes are anchored to a sink
node. Figure 3 shows a representation of the completed flow graph. In order to
obtain a min-cut, we apply the Boykov-Kolmogorov algorithm [2]. The indices of
this min-cut are the seam where each frequency bin transitions.

In order to apply the found transition to the audio tracks, we concatenate the
complex time-frequency song representations found earlier along the seam, and
apply an inverse STFT to obtain the final audio transition seen in Figure 1.

The work here presents an initial foray into automatically transitioning
between songs in the time-frequency domain. The loss function described in 1
does not well characterize the inherent qualities found in music, but there is
good reason to believe such a cost function can be found through further
development. On harmonically similar tracks with similar tempi, the current
implementation produces acoustically pleasing results.

Figure 2: Overlapping song segment spectrogram’s used to compute graph weights
using eq. 1. Each segment represents 64 beats.

Figure 3: Flow graph model showing adjacent weight calculations. The orange
and green nodes are fixed to the first and second songs respectfully. Nodes
represent time-frequency bins.

Figure 1: This spectrogram shows overlapped segments of two music tracks after
being combined and reconstructed along a per-frequency seam (bright yellow).
The tracks were beat and tempo matched, then overlapped by 64 beats.

## References

  * [1] Rachel M Bittner, Minwei Gu, Gandalf Hernandez, Eric J Humphrey, Tristan Jehan, P. Hunter McCurry, and Nicola Montecchio.  Automatic Playlist Sequencing and Transitions.  Proceedings of the 18th International Society for Music Information Retrieval Conference (ISMIR), pages 442–448, 2017.
  * [2] Yuri Boykov and Vladimir Kolmogorov.  An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision 1 Introduction.  Technical Report 9, 2004.
  * [3] Roman B. Gebhardt, Matthew E.P. Davies, and Bernhard U. Seeber.  Psychoacoustic approaches for harmonic music mixing.  Applied Sciences, 6(5), 2016.
  * [4] Tatsunori Hirai, Hironori Doi, and Shigeo Morishima.  MusicMixer: Computer-Aided DJ system based on an automatic song mixing.  In ACM International Conference Proceeding Series, volume 16-19-Nove. Association for Computing Machinery, nov 2015.
  * [5] Vivek Kwatra, Arno Schödl, Irfan Essa, Greg Turk, and Aaron Bobick.  Graphcut textures: Image and video synthesis using graph cuts.  In ACM SIGGRAPH 2003 Papers, SIGGRAPH ’03, pages 277–286, 2003\.
  * [6] Heng Yi Lin, Yin Tzu Lin, Ming Chun Tien, and Ja Ling Wu.  Music paste: Concatenating music clips based on chroma and rhythm features.  In Proceedings of the 10th International Society for Music Information Retrieval Conference, ISMIR 2009, pages 213–218, 2009.
  * [7] Brian McFee, Colin Raffel, Dawen Liang, Daniel Ellis, Matt McVicar, Eric Battenberg, and Oriol Nieto.  librosa: Audio and Music Signal Analysis in Python.  In Proceedings of the 14th Python in Science Conference, pages 18–24, 2015.
  * [8] Jaume Parera.  Dj codo nudo: a novel method for seamless transition between songs for electronic music.  Master’s thesis, Universitat Pompeu Fabra, Barcelona, 2016.