# Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

Vincent Despré, Dorian Perrot, Marc Pouget

<figure><img src="image_1.png" /></figure>

## To cite this version:

Vincent Despré, Dorian Perrot, Marc Pouget. Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces. 2026. hal-05505880

HAL Id: hal-05505880

https://hal.science/hal-05505880v1

Preprint submitted on 11 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

Vincent Despré ☐

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Dorian Perrot ☐

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Marc Pouget ☐

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

1

## Abstract

2

3

4

5

6

7

8

9

10

The well known Bowyer-Watson algorithm constructs the Delaunay triangulation of a point set in the plane incrementally. The restoration of the Delaunay property in the conflict zone of an inserted point is non-ambiguous since this zone is a topological disk. This property no longer holds on a surface with non-trivial topology. We propose an extension of the Bowyer-Watson algorithm to hyperbolic surfaces. Our algorithm uses a thin/thick decomposition of the hyperbolic surface. It first computes an initial point set together with its Delaunay triangulation via an epsilon-net sampling of the surface. The insertion procedure in the thick part of the surface is as in the original algorithm in the plane. The insertion in the thin part differs to overcome the possibly non-trivial topology of the conflict zone.

**2012 ACM Subject Classification** Theory of computation → Computational geometry; Mathematics of computing → Geometric topology

**Keywords and phrases** Hyperbolic surface, Delaunay triangulation, Algorithm, Topology

11

## 1 Introduction

12

13

14

15

16

17

18

19

20

21

A *hyperbolic surface* is a surface endowed with a Riemannian metric of constant negative curvature. These surfaces play a fundamental role in the study of Riemannian geometry: every Riemann surface of genus at least two is conformally equivalent (i.e., biholomorphic) to a unique hyperbolic surface [5, Section 1.7]. In light of this universal property, it is unsurprising that hyperbolic surfaces have occupied a central place in geometric research for more than a century. In the computer science community, hyperbolic geometry first appeared as a tool for proving combinatorial or Euclidean results. A landmark contribution of this type is the work of Sleator, Tarjan, and Thurston on the diameter of the flip graph of triangulated polygons [20]. A broader perspective on this line of work was later provided by Eppstein in his survey [15].

22

23

24

25

26

27

28

29

30

31

32

There are also algorithmic studies focused on hyperbolic surfaces themselves, notably for Delaunay triangulations on such surfaces. Our work aims at designing an efficient Delaunay algorithm for a large number of points. As explained in Ebbens et al. [13], the preferred method in this case is the Bowyer algorithm. In particular, it is used in the CGAL project for Delaunay triangulations in the Euclidean case but also on the sphere [19] and quotients of flat spaces [17, 6, 7]. Recall that the Bowyer algorithm inserts the points one by one and maintains a Delaunay triangulation. When inserting a point *p* into the current Delaunay triangulation, it first computes the *conflict zone* of *p*, that is, the set of triangles whose circumdisks contain *p*, and then rebuilds a Delaunay triangulation by creating a star around *p*. A crucial requirement for the correctness of the algorithm is that the conflict zone of *p* forms a topological disk.

33

34

In the hyperbolic setting, the Bowyer algorithm was first generalized to the hyperbolic plane [2], and later to some specific hyperbolic surfaces like the Bolza surface [16, 13]. On

<figure><img src="image_3.png" /></figure>

© Vincent Despré, Dorian Perrot and Marc Pouget;
licensed under Creative Commons License CC-BY 4.0

<figure><img src="image_4.png" /></figure>

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
XX:2 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

a surface, the conflict zone may no longer be a topological disk. To overcome this issue,
following an idea of [3], the above mentioned works compute a set of dummy points $\mathcal{F}$ as
a preprocessing step, ensuring that the conflict zone of any additional point will indeed be
disk-like. They proved that it suffices to choose $\mathcal{F}$ dense enough with respect to the systole
of $S$, that is the length of a smallest non-contractible closed geodesic. However, determining
the systole or the dummy points for an arbitrary hyperbolic surface and computing the
input Delaunay triangulation is non-trivial. In particular, it requires a distinct algorithm to
compute Delaunay triangulations in the preprocessing step.

The notion of $\varepsilon$-nets has recently been used to compute dummy points. Let us recall its definition. Let $(X, d)$ be a metric space and $\varepsilon > 0$. As defined in [8], a set $A$ included in $X$ is an $\varepsilon$-covering if the closed balls of radius $\varepsilon$ centered at each $a \in A$ cover $X$, i.e. $X = \bigcup_{a \in A} \overline{B}(a, \varepsilon)$. The set $A$ is an $\varepsilon$-packing if the open balls of radius $\varepsilon/2$ centered at each $a$ in $A$ are pairwise disjoint, i.e. $\forall a \neq b \in A, B(a, \varepsilon/2) \cap B(b, \varepsilon/2) = \emptyset$. The set $A$ is an $\varepsilon$-net if it is both an $\varepsilon$-covering and an $\varepsilon$-packing. The computation of $\varepsilon$-nets on hyperbolic surfaces [11, 10] is achieved via Delaunay triangulations using the flip algorithm [12] which is a different strategy that the Bowyer algorithm. However, a naive application of this method produces a set of dummy points whose size is unbounded in general. This unbounded number of points is explained by the structure of collars of hyperbolic surfaces as recalled in Theorem 1. Specifically, if $S$ has a small closed geodesic curve, it must contain an embedded thin cylinder surrounding this curve. The width of this cylinder tends to infinity as the length of the curve approaches 0, requiring a linear number of points to cover the cylinder relative to its width. However, the collar theorem also states that these problematic regions are contained within at most $3g - 3$ disjoint collars. Manuel's Phd thesis [18] introduces the notion of a pseudo $\varepsilon$-net, which is designed to cover only the $\varepsilon$-thick part of $S$, which is the complement of the $\varepsilon$-collars, see Definition 2. This approach yields a bounded number of points, less than $16(g - 1)/\varepsilon^2$, which is independent of the systole.

We first prove that using a variant of a pseudo $\varepsilon$-net as a set of dummy points allows us to use the classical Bowyer algorithm in the thick part. We then propose an alternative algorithm for the insertion of points in the thin cylinders. Also, the parameter $\varepsilon$ should be as large as possible to minimize the number of dummy points. Finally, we prove that the Bowyer algorithm can be extended to any hyperbolic surface using a variant of a pseudo $\varepsilon_0$-net as set of dummy points for the value $\varepsilon_0 := \ln(2)/8$.

Section 2 presents the basics of hyperbolic geometry and the classical Bowyer algorithm.
Section 3 details the construction of the dummy points used to initialize the main algorithm,
which is then described and analyzed in Section 5. Sections 4 and Appendix A provide the
key arguments needed to prove the correctness and the termination of the insertion step, in
the $4\varepsilon_0$-thin part and the $4\varepsilon_0$-thick part of the surface, respectively.

2 Background and notation

## 2.1 Hyperbolic surfaces

We work with the Poincare disk model of the hyperbolic plane $\mathbb{H}^2$ with the hyperbolic
distance $d_h$. It is represented as the unit disk of the complex plane $\mathbb{C}$ where the boundary
(i.e. the unit circle) represents points at infinity. The geodesic lines are either diameters of
the unit disk, or circular arcs that meet the boundary circle orthogonally. The curve whose
points have the same orthogonal distance from a given geodesic line $\Delta$ is called a *hypercycle*.
The line $\Delta$ is called the *axis of the hypercycle* and the distance from the hypercycle to $\Delta$ is
called the *radius of the hypercycle*. In the Poincare disk model a hypercycle is a circular arc
that meets the boundary circle at the same points as its axis. Finally, hyperbolic circles are Euclidean circles but their hyperbolic and Euclidean centers differ.

A closed hyperbolic surface $S$ can be defined as the quotient of the hyperbolic plane $\mathbb{H}^2$ by a discrete group of orientation-preserving isometries $\Gamma$. The universal cover of $S$ is the hyperbolic plane $\mathbb{H}^2$, objects of $\mathbb{H}^2$ will be noted with a tilde $\tilde{\sim}$ while those of $S$ will be noted without. We note $\rho : \mathbb{H}^2 \to S = \mathbb{H}^2/\Gamma$ this projection. In particular, for an element $x$ on $S$, $\tilde{x}$ denotes a lift of $x$ and is any element of $\rho^{-1}(x)$ which is exactly $\Gamma \cdot \tilde{x}$. A copy of $\tilde{x}$ denotes another lift of $x$, i.e. another element of $\rho^{-1}(x)$. A fundamental domain for $S$ is a connected subset of $\mathbb{H}^2$ containing exactly one lift of every point of $S$, except on its boundary. In our algorithms, the surface $S = \mathbb{H}^2/\Gamma$ is represented by a polygonal fundamental domain $\Omega_0$ together with its side-pairings generating $\Gamma$. Without loss of generality [9], we assume that $\Omega_0$ is the Dirichlet domain of a lift $\tilde{b}$. Recall that a Dirichlet domain of a point $\tilde{b}$ is the cell of $\tilde{b}$ in the Voronoi diagram of all the lifts of $b$ in $\mathbb{H}^2$. Note that by duality the Delaunay triangulation of the point $b$ on the surface is implicitly given.

For more details about hyperbolic surfaces, we refer the reader to the books [1, 5].

## 2.2 Thin and thick parts

For $\varepsilon > 0$, a hyperbolic surface $S$ can be decomposed into its $\varepsilon$-thin and $\varepsilon$-thick parts [14]. The injectivity radius $r_p(S)$ of $S$ at $p$ is the supremum of all $r > 0$ such that $B(p, r)$, the open ball of center $p$ and radius $r$, for the metric on $S$, is isometric to a disk in $\mathbb{H}^2$. In particular, $B(p, r)$ is a topologically embedded disk on $S$ for all $r \le r_p(S)$. The $\varepsilon$-thin part of $S$, denoted $S_\varepsilon^t$, is the set of points which have an injectivity radius smaller or equal to $\varepsilon/2$, i.e. $S_\varepsilon^t = \{p \in S \mid r_p(S) \le \varepsilon/2\}$, and the $\varepsilon$-thick part, $S_\varepsilon^T$, is its complement on $S$. The systole $\sigma$ of a surface is the length of a shortest non-contractible curve, which is also denoted by $\sigma$. The length of a curve $\gamma$ on $S$ is denoted $l(\gamma)$.

**Theorem 1** ([5, Theorem 4.1.1 & 4.1.6]). Let $\gamma_1, \dots, \gamma_m$ be simple closed geodesics on $S$ of lengths smaller than $2 \arcsin h(1)$. Then the following statements hold.

(i) The curves $\gamma_1, \dots, \gamma_m$ are disjoint.

(ii) If $g$ is the genus of $S$ then $m \le 3g - 3$.

(iii) The collars $\mathcal{C}(\gamma_i) := \{p \in S \mid d_h(p, \gamma_i) \le w(\gamma_i)\}$ of widths $w(\gamma_i) := \arcsin h\left(\frac{1}{\sinh(\frac{1}{2}l(\gamma_i))}\right)$ are pairwise disjoint for $i = 1, \dots, m$.

(iv) If $p$ is in the collar $\mathcal{C}(\gamma_i)$ at distance $d$ from $\gamma_i$ then $\sinh(r_p(S)) = \sinh(\frac{1}{2}l(\gamma_i)) \cdot \cosh(d)$.

**Definition 2** ($\varepsilon$-collar). Let $0 < \varepsilon \le 2 \arcsin h(1)$ and $\gamma$ be a simple closed geodesic of length at most $\varepsilon$ on a hyperbolic surface $S$. The $\varepsilon$-collar of $\gamma$ is $\mathcal{C}(\gamma, \varepsilon) = \{x \in \mathcal{C}(\gamma) : r_x(S) \le \varepsilon/2\}$.

## 2.3 Triangulation and Delaunay triangulation

A triangulation $\tilde{T}$ of the hyperbolic plane $\mathbb{H}^2$ is a partition of a convex subset of $\mathbb{H}^2$ (that may be $\mathbb{H}^2$ itself) into non-intersecting triangles. The edges of $\tilde{T}$ are hyperbolic segments. A triangulation $\tilde{T}$ is said to be *Delaunay* if for each triangle $\tilde{t}$ of $\tilde{T}$ the open disk circumscribing $\tilde{t}$ contains no vertex of $\tilde{T}$ in $\mathbb{H}^2$. Let $\tilde{E}$ be a set of points in $\mathbb{H}^2$ without accumulation point, then there always exists a Delaunay triangulation whose vertices are the points in $\tilde{E}$ denoted $DT(\tilde{E})$. In the generic case, i.e. if there are no four cocyclic points in $\tilde{E}$, then there is a unique Delaunay triangulation. Note that it is not possible to assume genericity since pseudo $\varepsilon$-nets contain cocyclic points in the thin parts [18, Section III.5]. Consider a point $\tilde{p} \in \mathbb{H}^2$ that does not belong to $\tilde{E}$. A triangle $\tilde{t}$ of $DT(\tilde{E})$ is in conflict with $\tilde{p}$ if it lies in the closed
XX:4 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

<figure><img src="image_5.png" /><figcaption>■ **Figure 1** Insertion step of the Bowyer-Watson algorithm: The conflict zone of $p$ is the orange region star-shaped at $p$.</figcaption></figure>

circumdisk of $\tilde{t}$, we consider closed circumdisks to handle non-generic cases. The conflict zone of $\tilde{p}$ is the set of triangles in conflict with $\tilde{p}$ (Figure 1). Let $E$ be a finite set of points in $S$. A Delaunay triangulation of $E$ on $S$, denoted $DT(E)$, is the image by the projection map $\rho: \mathbb{H}^2 \to S$ of a Delaunay triangulation on $\mathbb{H}^2$ of the infinite point set $\rho^{-1}(E)$. Similarly, a triangle in conflict with a point $p \in S$ and the conflict zone of $p$ are respectively the images by $\rho$ of a triangle in conflict with $\tilde{p}$ and the conflict zone of $\tilde{p}$, for any lift $\tilde{p}$ of $p$.

2.4 Bowyer-Watson algorithm

The Bowyer-Watson algorithm [4, 21] is an incremental algorithm that computes a Delaunay triangulation of a set of points in the Euclidean space, thus in particular in the plane. The incremental step starts with a Delaunay triangulation $DT$. To add a new point $p$ in $DT$, the algorithm computes the conflict zone of $p$, deletes all edges in the interior of this zone and creates new triangles by connecting $p$ to the vertices on the boundary of the conflict zone (Figure 1). The key point of this approach is Theorem 4 stating that the conflict zone is star-shaped at the inserted point. For completeness, we give a proof of this fact valid both in the Euclidean and hyperbolic settings using the properties that, in the Poincaré disk model, circles are Euclidean circles and the intersection of a disk and a geodesic line is a geodesic segment (possibly empty).

**Lemma 3.** Let $D$ be the circumdisk of a triangle $v_1v_2v_3$ and $p$ a point in $D$. Then, there exists a disk $D'$ contained in $D$ and containing $p$ and $v_1$.

**Proof.** Let $d$ be the diameter of $D$ passing through $v_1$. As $p$ is contained in $D$, the angle between $[v_1, p]$ and $d$ is smaller than $\pi/2$. Hence, the perpendicular bisector of $[v_1, p]$ intersects $d$ at a point $c$ as shown in the Figure 2. Let $C$ be the circle with center $c$ and passing through $v_1$. This circle also passes through $p$ and is internally tangent to the boundary of the disk $D$ at $v_1$. Thus, the disk $D'$ bounded by $C$ is appropriate. ◀

**Theorem 4.** The conflict zone of $p$ is star-shaped at $p$.
<figure><img src="image_6.png" /><figcaption>■ **Figure 2** The circumscribed disk $D$ of the triangle $v_1v_2v_3$ contains the disk $D'$ of center $c$, internally tangent to $\partial D$ at $v_1$, and with $p$ on its boundary.</figcaption></figure>

**Proof.** Let $t$ be a triangle in conflict with $p$ and $x$ be a point in $t$. Suppose, for the sake of contradiction, that there exists a point $y$ in the segment $[p, x]$ that does not belong to the conflict zone of $p$. Then, there exists a triangle $\triangle$ containing $y$ that is not in conflict with $p$. As $x$ is outside of $\triangle$, there is a side $e$ of $\triangle$ which intersects the segment $[y, x]$. In addition, the endpoints of $e$ are outside of the circumdisk of $t$ (see Figure 3). Then $e$ separates the circumdisk of $t$ in two regions, one containing $p$ and $y$, and the other containing $x$ and $t$. Then, by convexity of the disk, the segments from $p$ to the vertices of $t$ intersect $e$. By Lemma 3, these segments are contained in empty disks and are thus Delaunay edges of the triangulation with the point $p$ added. This is in contradiction with the fact that they intersect $e$ that is also a Delaunay edge. ◀

<figure><img src="image_7.png" /><figcaption>■ **Figure 3** Illustration for the proof of Theorem 4.</figcaption></figure>
3 Dummy points and thin/thick decomposition

3.1 Hyperbolic surface triangulation data structure

Recall that the surface $S$ is given by a fundamental domain $\Omega_0$ in the form of a Dirichlet domain of a point $b$ so that the group $\Gamma$ of the surface is generated by the side-pairings of this domain. Our algorithms use the triangulation data structure of [12] where each point $p$ of the surface has a unique lift $\tilde{p}^0$ in $\Omega_0$. A vertex $v$ has a constant-time access to $\tilde{v}^0$ and one of its incident triangles. A triangle $t$ has a constant-time access to its three vertices $v_0, v_1, v_2$, its three adjacent triangles, and three isometries $\gamma_{0,t}, \gamma_{1,t}, \gamma_{2,t}$ in $\Gamma$ defined as follows. In general $t$ does not have a lift included in $\Omega_0$ but it always has a lift $\tilde{t}^0$ with its vertex $\tilde{v}_{0,t}$ in $\Omega_0$ (see Figure 4). Then $\gamma_{0,t}, \gamma_{1,t}$ and $\gamma_{2,t}$ are the isometries such that $\gamma_{i,t}^{-1} \cdot \tilde{v}_{i,t} = \tilde{v}_{i,t}^0$ for $i = 0, 1, 2$. Note that by definition $\gamma_{0,t} = \text{id}$, and that $\gamma_{0,t}^{-1} \cdot \tilde{t}^0, \gamma_{1,t}^{-1} \cdot \tilde{t}^0$ and $\gamma_{2,t}^{-1} \cdot \tilde{t}^0$ are all the lifts of $t$ having at least one vertex in $\Omega_0$. In our data structure, two adjacent triangles $t$ and $t'$ on the surface could be represented by two triangles $\tilde{t}^0$ and $\tilde{t}'^0$ which are not adjacent in $\mathbb{H}^2$. However, there is an isometry $\gamma$ in $\Gamma$ such that $\tilde{t}^0$ and $\gamma \cdot \tilde{t}'^0$ are adjacent.

To encode an $\varepsilon$-thin/thick decomposition, we add labels to vertices. A vertex that is in an $\varepsilon$-thin collar $\mathcal{C}(\gamma, \varepsilon)$ is labeled [thin, $\Delta$, $T$] where $T$ is the hyperbolic translation in $\Gamma$ associated to the closed geodesic $\gamma$ and $\Delta$ is its axis intersecting $\Omega_0$. A vertex that is in the $\varepsilon$-thick part is labeled [Thick].

<figure><img src="image_8.png" /><figcaption>■ **Figure 4** Triangulation data structure. Hyperbolic triangles are schematically represented with straight lines. The triangle $t_1$ has two lifts, shown in blue, inside the fundamental domain $\Omega_0$, each with two vertices corresponding to the same point on the surface. The triangle $t_2$ has three lifts, shown in purple, each with a single vertex inside $\Omega_0$.</figcaption></figure>
## 3.2 Naive dummy points algorithm

To ensure that all conflict zones are topological balls, [13, Prop. 3] introduces the validity condition for a set of points $Q$ on a surface $S$: $\delta(Q) < \sigma/2$, where $\delta(Q)$ is the greatest diameter of a disk in $\mathbb{H}^2$ that does not contain any point of $\rho^{-1}(Q)$ and $\sigma$ is the systole of $S$. The validity condition prevents the graph of edges of the Delaunay triangulation of $\rho^{-1}(Q)$ to have 1- or 2-cycles. This implies that the conflict zone of a point $p$ with respect to a Delaunay triangulation on $S$ containing such a point set $Q$ is a topological disk so that the Bowyer algorithm applies.

On the other hand, there is an algorithm to compute $\varepsilon$-nets on a hyperbolic surfaces $S$ that incrementally adds circumcenters of all Delaunay triangles of radius larger than $\varepsilon$ [11]. Given an $\varepsilon$-net $Q$ for $\varepsilon < \sigma/4$, the largest empty disks in the Delaunay triangulation of $\rho^{-1}(Q)$ are Delaunay circumdisks and thus $\delta(Q) \le 2\varepsilon < \sigma/2$. This set $Q$ satisfies the validity condition and can then be chosen for a set of dummy points so that inserting additional points in a Delaunay triangulation on $S$ containing $Q$ is possible with the classical Bowyer algorithm.

In addition, [18, Lemma III.15] states that given an $\varepsilon$-net with $\varepsilon < \arcsinh 1$, if $\sigma \le \varepsilon$ then there is a loop edge in the Delaunay triangulation. This suggests the following algorithm to compute a dummy points set. First, as in the $\varepsilon$-net algorithm, add circumcenters of the largest Delaunay circumdisks to compute a point set $Q_0$ such that there is no loop edge in its Delaunay triangulation on $S$. [18, Lemma III.15] yields $\sigma > \varepsilon' := \delta(Q_0)/2$ and refining again $Q_0$ to an $\varepsilon'/4$-net gives a dummy points set.

The main drawback of this method is that the number of dummy points is in $\Theta(1/\sigma^2)$ [18, Section III.2], it is thus arbitrarily large for surfaces with arbitrarily small systoles.

## 3.3 Dummy points via a thin/thick decomposition

To obtain a dummy points set whose size does not depend on the systole, the idea is to decompose the surface and compute dummy points only for the thick part. We reuse and adapt [18, Algorithm III.10] computing a pseudo $\varepsilon$-net, which is an $\varepsilon$-net of the $\varepsilon$-thick part of a surface. The rationale for computing a $\varepsilon_0$-covering of the $4\varepsilon_0$-thick part, and not only of the $\varepsilon_0$-thick part, is to ensure that dummy points are dense enough to constrain the conflict zone of a point in the $4\varepsilon_0$-thin to be contained in a collar (Section 4) and allow us to use the classical Bowyer algorithm in the $4\varepsilon_0$-thick part (Section A). Since $\varepsilon_0$ is a constant, the number of dummy points output by Algorithm 1 only depends linearly on the genus of the surface. The value $\varepsilon_0 = \ln(2)/8$ comes from the original pseudo $\varepsilon$-net Algorithm [18, Algorithm III.10]. The requirement that the point $b$ should not be in the $4\varepsilon_0$-thin part also comes from this algorithm, but it is easily obtained as explained in [18, Section III.5.2]. An output of the algorithm is illustrated on Figure 5.
XX:8 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

222

**Algorithm 1** Dummy points via a thin/thick decomposition

223 **Input:** A Delaunay triangulation $DT(b)$ on a single vertex $b$ of a hyperbolic surface $S$, $b \notin 4\varepsilon_0$-thin part with $\varepsilon_0 = \ln(2)/8$.

224 **Output:** The Delaunay triangulation $DT(\mathcal{F})$ such that $b \in \mathcal{F} \subset S$ and
■ $\mathcal{F}$ is an $\varepsilon_0$-covering of $S_{4\varepsilon_0}^T$.

■ $\mathcal{F} \cap S_{4\varepsilon_0}^T$ is an $\varepsilon_0$-packing of $S_{4\varepsilon_0}^T$.

■ Points of $\mathcal{F}$ are labeled with respect to the $4\varepsilon_0$-thin/thick decomposition.

225 (a) Compute $\mathcal{F}_0$ a pseudo $4\varepsilon_0$-net of $S$ [18, Algorithm III.10].

226 Label all vertices of $\mathcal{F}_0$ as [Thick] but the points on the boundaries of $4\varepsilon_0$-collars that are labeled [thin, $\Delta$, $T$] with the data of their collars [18, Lemma III.12].

227 (b) Refine $\mathcal{F}_0$ to $\mathcal{F} \subset S$ by inserting the circumcenter $c$ of each Delaunay triangle whose circumradius is larger or equal to $\varepsilon_0$ and has at least one vertex in $S_{4\varepsilon_0}^T$.

228 If all vertices of the triangle are labeled [Thick] then label $c$ by [Thick];

229 Else at least one vertex is labeled [thin, $\Delta$, $T$],

230 if $d_h(\tilde{c}^0, T(\tilde{c}^0)) \le 4\varepsilon_0$ then label $c$ by [thin, $\Delta$, $T$], and else by [Thick].

231

232

233

<figure><img src="image_9.png" /></figure>

**Figure 5** A hyperbolic surface of genus 3 with two collars colored in green and blue. The systoles of collars are denoted $\sigma_{\epsilon_1}$ and $\sigma_{\epsilon_2}$. The $4\epsilon_0$-thin part is in green with the dummy points $b_1^1, b_2^1, b_1^2$ and $b_2^2$ on its boundary.

234

4 Conflict zone

235

236

237

238

239

240

241

We now investigate the conflict zone of a point $p$ in a given Delaunay triangulation $DT$ of a point set $\mathcal{P}$, where $\mathcal{P}$ includes a set of dummy points computed by Algorithm 1. In order to adapt the Bowyer algorithm in a meaningful way, we first show that the resulting conflict zones possess sufficient structure to permit a direct reconstruction of the Delaunay triangulation of $\mathcal{P} \cup \{p\}$.

If $p$ is in the $4\varepsilon_0$-thick part of $S$, we will use the following theorem, whose proof is in Appendix A.

242

243

**Theorem 5.** Let $\tilde{D}$ be an empty disk in $\tilde{DT}$. The sets $\tilde{D}_i \cap \rho^{-1}(S_{4\varepsilon_0}^T)$, where $\tilde{D}_i$ is a copy of $\tilde{D}$, are pairwise disjoint.

244

245

246

In particular, Theorem 5 implies that every empty disk $\tilde{D}$ is such that $\rho(\tilde{D}) \cap S_{4\varepsilon_0}^T$ is a topological ball on $S$. We show, in Section 5.2, that this implies that the classical Bowyer method works for the insertion of $p$ in $DT$.
Suppose now that $p$ lies in the $4\epsilon_0$-thin part of $S$. In this situation, a conflict zone, even when contained within a single collar, may form a cylinder or an even more intricate shape inside that collar. Consequently, it may admit infinitely many possible triangulations, making a dedicated procedure necessary to reconstruct a valid Delaunay triangulation. To address this difficulty, we introduce a *restricted conflict zone* in $\mathbb{H}^2$ for a chosen lift of $p$. This restricted zone contains only a bounded number of lifts of any given point of $S$ and is proved to be star-shaped. These properties are the key ingredients that make our generalization possible.

Our first result is that the conflict zone of $p$ is entirely contained within its collar $\mathcal{C}$, see Figure 6. The proofs of Proposition 6 and Corollary 7 are in Appendix B.

**Proposition 6.** Consider a collar $\mathcal{C}$ such that $\sigma_{\mathcal{C}}$ is no longer than $2 \arcsin h(1)$. Let $d_1$ be the distance between the boundary of $\mathcal{C}$ and $\sigma_{\mathcal{C}}$, and $d_2$ the distance between the $4\epsilon$-thick part and $\sigma_{\mathcal{C}}$. If $\epsilon$ is smaller than $\frac{1}{4} \ln(3)$ then $d_1 - d_2 > 2\epsilon$.

<figure><img src="image_10.png" /><figcaption>Figure 6 Illustration of Proposition 6 and Corollary 7. The blue part is the collar $\mathcal{C}$, the green part is the $4\epsilon$-thin part, and the orange part is the conflict zone of the point $p$ within the $4\epsilon$-thin part.</figcaption></figure>

**Corollary 7.** Let $\epsilon \in (0, \frac{1}{4} \ln(3))$ and $p$ be a point in the $4\epsilon$-thin part of a collar $\mathcal{C}$. Then, the conflict zone of $p$ is included in $\mathcal{C}$.

In the following, we usually work in the universal cover of $S$ and in particular with the lifts of collars. We therefore detail the structure of $\rho^{-1}(\mathcal{C})$ for a given collar $\mathcal{C}$ of systole $\sigma_{\mathcal{C}}$ and set some notation. The set of lifts of $\sigma_{\mathcal{C}}$ consists of a family of geodesic lines in $\mathbb{H}^2$. Let $\Delta$ be one such line that is the axis of a primitive translation $T$ in the isometry group of the surface. For $\epsilon > 0$, we define the $\epsilon$-banana with axis $\Delta$ as the lift of the $\epsilon$-collar containing $\Delta$. Equivalently, it is the region bounded by the two hypercycles at distance $\mathrm{arccosh}(\frac{\sinh(\epsilon/2)}{\sinh(\sigma_{\mathcal{C}}/2)})$ from $\Delta$. In the Poincaré disk model, this region visually resembles a banana, which motivates the terminology. By extension, we also refer to the lift of the entire collar as a *banana*. We can now reformulate Corollary 7 in the universal cover.

**Corollary 8.** Let $\Delta$ be a geodesic line such that $\rho(\Delta)$ is the systole of a collar $\mathcal{C}$. Let $\epsilon \in (0, \frac{1}{4} \ln(3))$ and $\tilde{p}$ be a point in the $4\epsilon$-banana of axis $\Delta$. Then, the conflict zone of $\tilde{p}$ is included in the banana of axis $\Delta$.
XX:10 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

To a lift $\tilde{x}$ of a point of a collar $\mathcal{C}$, we associate a banana $\mathcal{B}$, that comes with a geodesic axis $\Delta$ and a translation $T$. We denote by $\mathcal{H}_{\tilde{x}} \subset \mathcal{B}$ the hypercycle of axis $\Delta$ that contains $\tilde{x}$. We introduce the orthogonal projection onto $\Delta$, denoted $\pi : \mathbb{H}^2 \to \Delta$. The map $\pi$ commutes with both $T$ and $T^{-1}$. Indeed, for any point $\tilde{y} \in \mathbb{H}^2$, the geodesic segment joining $\tilde{y}$ to $\pi(\tilde{y})$ is orthogonal to $\Delta$. Since $T$ is an isometry preserving $\Delta$ (as its axis), it maps this orthogonal segment to the segment joining $T(\tilde{y})$ to $T \circ \pi(\tilde{y})$, which is therefore also orthogonal to $\Delta$. On the other hand, the segment joining $T(\tilde{y})$ to $\pi \circ T(\tilde{y})$ is, by definition, orthogonal to $\Delta$. Thus the points $T \circ \pi(\tilde{y})$ and $\pi \circ T(\tilde{y})$ lie on $\Delta$ and belong to the same orthogonal geodesic through $T(\tilde{y})$. Hence they coincide and we conclude that $T \circ \pi = \pi \circ T$.

Our second result is that the conflict zone of a point $\tilde{x}$ in a $4\epsilon_0$-banana is contained within a region bounded by the two geodesic lines orthogonal to the axis of the banana and passing through $T(\tilde{x})$ and $T^{-1}(\tilde{x})$ respectively. We use the following classical lemma that we prove for completeness in Appendix B and illustrate in figure 7.

**Lemma 9.** Let $\tilde{D}$ be a closed disk and $\tilde{x}, \tilde{y}$ two distinct points in $\tilde{D}$ then all hypercycle-arcs or horocycle-arcs from $\tilde{x}$ to $\tilde{y}$ are contained in $\tilde{D}$.

<figure><img src="image_11.png" /><figcaption>Figure 7 The blue disk $\tilde{D}$ in the Poincare disk contains the arc from $\tilde{x}$ to $\tilde{y}$ of the hypercycle $\mathcal{H}_{\tilde{x}, \tilde{y}}$, and the arc from $\tilde{x}$ to $\tilde{y}$ of the green horocycle.</figcaption></figure>

**Theorem 10.** Let $T$ be a translation associated to a banana $\mathcal{B}$ and let $\tilde{x}$ and $\tilde{y}$ be two points in $\mathcal{B}$ projecting on distinct points of $S$. If the segment $[\tilde{x}, \tilde{y}]$ is an edge of a Delaunay triangulation then $\tilde{y}$ lies between the geodesic lines $(T(\tilde{x}), \pi(T(\tilde{x})))$ and $(T^{-1}(\tilde{x}), \pi(T^{-1}(\tilde{x})))$.

**Proof.** Assume, by contradiction, that $\pi(T(\tilde{x}))$ lies in the open segment $(\pi(\tilde{x}), \pi(\tilde{y}))$ (the case where $\pi(T^{-1}(\tilde{x}))$ is in this segment is similar). We shall prove that every circle admitting $[\tilde{x}, \tilde{y}]$ as a chord is nonempty. We first consider the circumdisk $\tilde{C}_0$ of the triangle $\tilde{x}T(\tilde{x})\tilde{y}$. It is possible that the circumdisk of a given triangle is not well defined. Geometrically, this case corresponds to a circumdisk that reaches infinity. In this case, the triangle cannot be in
any Delaunay triangulation since its circumdisk contains infinitely many points (See [12] for more details).

<figure><img src="image_12.png" /><figcaption>■ **Figure 8** The red geodesic line $\Delta$ is the axis of the translation $T$ and the green line $\Upsilon$ is the bisector of $[\tilde{x}, T(\tilde{x})]$. The hypercycles of axis $\Delta$ passing through $\tilde{x}$ and $\tilde{y}$ are denoted $\mathcal{H}_{\tilde{x}}$ and $\mathcal{H}_{\tilde{y}}$ respectively. The green circle $\tilde{C}_0$, centered at $\tilde{c}$, is the circumcircle of $\tilde{x}, T(\tilde{x})$ and $\tilde{y}$.</figcaption></figure>

We now consider the case where $\tilde{C}_0$ exists in $\mathbb{H}^2$, see Figure 8. Since $T$ is the translation of a collar $\mathcal{C}$, the sequence $(\pi \circ T^m(\tilde{y}))_{m \in \mathbb{Z}}$ is a $\sigma_{\mathcal{C}}$-net of the axis $\Delta$ (with the induced metric). Moreover, as $d_h(\pi(\tilde{x}), \pi \circ T(\tilde{x})) = \sigma_{\mathcal{C}}$, there exists one integer $k_0$ such that $\pi \circ T^{k_0}(\tilde{y}) \in [\pi(\tilde{x}), \pi \circ T(\tilde{x}))$. Let $\Upsilon$ be the perpendicular bisector of the segment $[\tilde{x}, T(\tilde{x}))$. In particular, the objects $\Delta, \mathcal{H}_{\tilde{x}}, \mathcal{H}_{\tilde{y}}$ and $\tilde{C}_0$ are invariant under reflection across the axis $\Upsilon$, this reflection maps $\tilde{y}$ to $\tilde{y}'$, the second intersection point between $\tilde{C}_0$ and $\mathcal{H}_{\tilde{y}}$, and we have $[\pi(\tilde{x}), \pi \circ T(\tilde{x})] \subseteq [\pi(\tilde{y}'), \pi(\tilde{y})]$. By Lemma 9, we deduce that the hypercycle-arc of $\mathcal{H}_{\tilde{y}}$ from $\tilde{y}'$ to $\tilde{y}$ is contained in the disk bounded by $\tilde{C}_0$. Since $\pi \circ T^{k_0}(\tilde{y})$ belongs to $[\pi(\tilde{x}), \pi \circ T(\tilde{x}))$, which in turn is contained in $[\pi(\tilde{y}'), \pi(\tilde{y})]$, it follows that $T^{k_0}(\tilde{y})$ lies on this hypercycle-arc and thus it belongs to the disk bounded by $\tilde{C}_0$.

The segment $[\tilde{x}, \tilde{y}]$ cuts the disk bounded by $\tilde{C}_0$ into two parts $P_0$ and $P_1$, the first containing $T(\tilde{x})$ on its boundary and the other containing either $T^{k_0}(\tilde{y})$ or infinitely many points. Then, if a circle $\tilde{C}$ admitting $[\tilde{x}, \tilde{y}]$ as a chord is different from $\tilde{C}_0$, it bounds a disk $\tilde{D}$ (or an infinite region) that strictly contains either $P_0$ or $P_1$. If $\tilde{D}$ contains $P_0$ then it contains $T(\tilde{x})$ and if it contains $P_1$, it contains either $T^{k_0}(\tilde{y})$ or infinitely many points. Then, in all cases $\tilde{D}$ is nonempty and $[\tilde{x}, \tilde{y}]$ cannot be a Delaunay edge. ◀

Theorem 10 shows that a lift $\tilde{x}$ of a point $x$ in a collar $\mathcal{C}$ can only be connected to the “nearest” lifts (within the banana) of another point $y$ in the same collar. An edge of a Delaunay triangulation connecting $x$ and $y$ is thus one of the two (or three if the orthogonal
XX:12 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

326

327

projection of $x$ onto $\sigma_c$ coincides with that of $y$) shortest geodesics connecting these two points, see Figure 9.

<figure><img src="image_13.png" /></figure>

328

329

330

■ **Figure 9** Possible Delaunay edges in a collar. The green segment is the shortest geodesic between the two points. Left: the second shortest geodesic, shown in pink, is unique. Right: There are two second shortest geodesics.

<figure><img src="image_14.png" /></figure>

331

332

333

334

■ **Figure 10** A banana (resp. 4ε-banana) of axis $\Delta$ and its boundary in black (resp. in blue). The hypercycle passing through $\tilde{x}$ is denoted $\mathcal{H}_{\tilde{x}}$. The orange (resp. purple) triangles are copies of a triangle in conflict with $\tilde{x}$. The restricted conflict zone of $\tilde{x}$ is the set of triangles in conflict with $\tilde{x}$ with at least one vertex included in the green region.

**Corollary 11.** Let $\tilde{x}$ be a point in a banana and $\tilde{t}$ be a triangle in conflict with $\tilde{x}$, then there is a copy of $\tilde{t}$ in conflict with $\tilde{x}$ having a vertex in the region between the geodesics lines $(T(\tilde{x}), \pi(T(\tilde{x})))$ and $(T^{-1}(\tilde{x}), \pi(T^{-1}(\tilde{x})))$.

335

336

337

**Proof.** Let $X := \{T^k(\tilde{x}) \in \mathbb{H}^2 \mid k \in \mathbb{Z}$ and $T^k(\tilde{x})$ is in conflict with $\tilde{t}\}$, since $\tilde{t}$ is in conflict with $\tilde{x}$ and the circumdisk of $\tilde{t}$ is compact, it follows that $X$ is a finite, non-empty set. Let $\tilde{v}$ be a vertex of $\tilde{t}$, applying Lemma 3, there exists $\tilde{x}_0 \in X$ such that the segment $[\tilde{x}_0, \tilde{v}]$ is included in an empty disk. Then this segment belongs to the Delaunay triangulation. Let $n_0 \in \mathbb{Z}$ be an integer such that $T^{n_0}(\tilde{x}_0) = \tilde{x}$, in particular $T^{n_0}(\tilde{t})$ is in conflict with $T^{n_0}(\tilde{x}_0) = \tilde{x}$.

338

339

340

341

342
and $T^{n_0}([\tilde{x}_0, \tilde{v}]) = [\tilde{x}, T^{n_0}(\tilde{v})]$ is an edge of the Delaunay triangulation. By Theorem 10, we deduce that $T^{n_0}(\tilde{v})$ is in the region between the geodesics lines $(T(\tilde{x}), \pi(T(\tilde{x})))$ and $(T^{-1}(\tilde{x}), \pi(T^{-1}(\tilde{x})))$, completing the proof. ◀

The previous corollary motivates the definition of the *restricted conflict zone of* $\tilde{x}$ as the region that contains all triangles of the conflict zone of $\tilde{x}$ that have at least one vertex is in the region bounded by lines $(T(\tilde{x}), \pi(T(\tilde{x})))$ and $(T^{-1}(\tilde{x}), \pi(T^{-1}(\tilde{x})))$, see Figure 10.

**Theorem 12.** *The restricted conflict zone of $\tilde{x}$ is star-shaped at $\tilde{x}$ in $\mathbb{H}^2$.*

**Proof.** By contradiction, assume that there exists a point $\tilde{y}$ in the restricted conflict zone of $\tilde{x}$ such that the segment $\tilde{s} = [\tilde{x}, \tilde{y}]$ is not entirely contained in the restricted conflict zone of $\tilde{x}$, see Figure 11. The segment $\tilde{s}$ crosses a sequence of triangles $\tilde{t}_0, \tilde{t}_1, \dots, \tilde{t}_k$, ordered from $\tilde{x}$ to $\tilde{y}$ along $\tilde{s}$, all contained in the (full) conflict zone of $\tilde{x}$ by Theorem 4. Thus, there exists an index $i$ such that $\tilde{t}_i$ is not contained in the region bounded by the lines $T^+ := (T(\tilde{x}), \pi(T(\tilde{x})))$ and $T^- := (T^{-1}(\tilde{x}), \pi(T^{-1}(\tilde{x})))$. We choose $i$ maximal with this property. By symmetry, without loss of generality, we assume that $\tilde{t}_i$ is separated from $\tilde{x}$ by the line $T^+$ and we call $\mathcal{R}$ the half space bounded by $T^+$ and containing $\tilde{x}$. Note that $i < k$, since the triangle containing $\tilde{y}$ lies in the restricted conflict zone. The triangles $\tilde{t}_i$ and $\tilde{t}_{i+1}$ share an edge crossed by $\tilde{s}$, and this edge lies outside $\mathcal{R}$. Therefore, $\tilde{t}_{i+1}$ has one vertex $\tilde{v}_0$ inside $\mathcal{R}$ and two vertices $\tilde{v}_1$ and $\tilde{v}_2$ outside $\mathcal{R}$. Let $\tilde{C}$ denote the circumcircle of $\tilde{t}_{i+1}$. Since $\tilde{t}_{i+1}$ lies in the conflict zone of $\tilde{x}$, the point $\tilde{x}$ lies in the interior of $\tilde{C}$. The line supporting $\tilde{s}$ cuts $\tilde{C}$ at two points, $\tilde{x}'$ and $\tilde{x}''$ appearing on $\tilde{s}$ in the order $\tilde{x}', \tilde{x}, \tilde{x}''$. In the circular order around $\tilde{C}$, the points appear in the order $\tilde{v}_0, \tilde{v}_1, \tilde{x}', \tilde{v}_2$ since $\tilde{s}$ enters the triangle $\tilde{t}_{i+1}$ through its edge $(\tilde{v}_1, \tilde{v}_2)$. This leads to a contradiction since $\tilde{v}_0$ and $\tilde{x}'$ are in $\mathcal{R}$ and $\tilde{v}_1$ and $\tilde{v}_2$ are not, but the line $T^+$ cannot separate the four points this way. ◀

<figure><img src="image_15.png" /><figcaption>**Figure 11** Illustration of the proof of Theorem 12.</figcaption></figure>

**Corollary 13.** *The restricted conflict zone of $\tilde{p}$ is a topological ball in $\mathbb{H}^2$.*

# 5 Hyperbolic Bowyer-Watson algorithm

## 5.1 Algorithm

We detail Algorithm 2 below, and Appendix C illustrates the two different insertion steps. In the first step, Algorithm 1 computes the set $\mathcal{F}$ of dummy points together with its
XX:14 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

<caption>**Algorithm 2** Bowyer-Watson hyperbolic surface Delaunay triangulation</caption>

371 **Input:** A Delaunay triangulation $DT(b)$ on a single vertex $b$ of a hyperbolic surface $S$, $b \notin 4\epsilon_0$-thin part with $\epsilon_0 = \ln(2)/8$ and a finite point set $\mathcal{P}$ on $S$.

372 **Output:** A Delaunay triangulation on $S$ of $\mathcal{P}$ and the dummy points $\mathcal{F}$.

373 $DT(\mathcal{F}) = \text{Algorithm 1}(DT(b))$

374 **for** $p \in \mathcal{P}$ **do**

375 &nbsp;&nbsp;&nbsp;&nbsp;**(a)** Find a Delaunay triangle $\delta$ containing $p$.

376 &nbsp;&nbsp;&nbsp;&nbsp;**(b)** If all vertices of the $\delta$ are labeled [Thick] then label $p$ by [Thick];
377 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Else at least one vertex is labeled [thin, $\Delta$, $T$],
378 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $d_h(\tilde{p}^0, T(\tilde{p}^0)) \le 4\epsilon_0$ then label $p$ by [thin, $\Delta$, $T$], and else by [Thick].

379 &nbsp;&nbsp;&nbsp;&nbsp;**if** $p$ is labeled [Thick] **then**

380 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**(c)** Compute the conflict zone of $\tilde{p}^0$.

381 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**(d)** Insert $p$ and update the Delaunay triangulation with the classical strategy of the Bowyer-Watson algorithm.

382 &nbsp;&nbsp;&nbsp;&nbsp;**else** $p$ is labeled [thin, $\Delta$, $T$]

383 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**(e)** Compute the restricted conflict zone of $\tilde{p}^0$.

384 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**(f)** Insert $p$ and update the Delaunay triangulation handling possible conflicts involving $T(\tilde{p}^0)$ and $T^{-1}(\tilde{p}^0)$.

385 **end**

Delaunay triangulation. In addition, vertices are labeled with respect to the $4\epsilon_0$-thin/thick decomposition.

**Step (a):** A Delaunay triangle $\delta$ containing $p$ is found by checking if $\tilde{p}^0$ belongs to one of the, at most three, lifts of each triangle using the orientation predicate.

**Step (c):** The computation of the conflict zone $C_p$ of $\tilde{p}^0$ works similarly as in the classical Bowyer algorithm using a DFS from $\delta$. The only difference is that the triangulation is locally lifted around $\tilde{p}^0$ in $\mathbb{H}^2$. We store the edges on the boundary of $C_p$ in a list $L_p$. We add in a queue, $Q$, the lifts of the three triangles adjacent to $\delta$ with their common edge to the lift of $\delta$ that contains $\tilde{p}^0$. For each triangle-edge pair $(\tilde{t}^0, \tilde{s})$ in $Q$, let $\gamma_t$ be the isometry that glues $\tilde{t}^0$ along $\tilde{s}$. If $\gamma_t(\tilde{t}^0)$ is not in conflict with $\tilde{p}^0$, record the edge $\tilde{s}$ in $L_p$; otherwise $\gamma_t(\tilde{t}^0)$ is in conflict with $\tilde{p}^0$, then add $\tilde{t}^0$ in $C_p$, and push the couples of the form $(\tilde{t}'^0, \gamma_t(\tilde{s}'))$ to the queue $Q$ where $t'$ is an adjacent unprocessed triangle of $t$ and $\tilde{s}'$ is the lift of the edge of $t$ in common with $t'$ that belong to $\gamma_t(\tilde{t}^0)$.

**Step (d):** Remove all triangles in $C_p$. Then, for each edge $\tilde{s}$ in $L_p$, add in the triangulation the triangle $t$ such that its lift $\tilde{t}^0$ includes $\tilde{s}$ as one edge and $\tilde{p}^0$ as the opposite vertex.

**Step (e):** First, compute $T(\tilde{p}^0)$, $T^{-1}(\tilde{p}^0)$ and the lines $T^+$, $T^-$ orthogonal to $\Delta$ passing through $T(\tilde{p}^0)$ and $T^{-1}(\tilde{p}^0)$ respectively. The computation of the conflict zone in the thin part works as previously but is restricted by the lines $T^+$ and $T^-$. Only triangles with at least one of its vertices in the *restricted zone*, that is between the lines $T^+$ and $T^-$, are considered and an edge is added to the list $L_p$ only if at least one of its endpoint is in the *restricted zone*.

**Step (f):** Remove all triangles in the restricted conflict zone of $\tilde{p}^0$. Consider each edge $\tilde{s} := [\tilde{v}_s, \tilde{v}'_s]$ in $L_p$. If exactly one of $\tilde{v}_s$ or $\tilde{v}'_s$ is in the restricted zone, without loss of generality we assume it is $\tilde{v}_s$, then add the triangle $\tilde{p}^0\tilde{v}_sT(\tilde{p}^0)$ to the triangulation if $T^+$ intersects the segment $[\tilde{v}_s, \tilde{v}'_s]$, otherwise add the triangle $\tilde{p}^0\tilde{v}T^{-1}(\tilde{p}^0)$. Else, $\tilde{v}_s$ and $\tilde{v}'_s$ are in the restricted zone, check conflicts between the triangle $\tilde{t}$ formed by $\tilde{s}$ and $\tilde{p}^0$ and the points $T(\tilde{p}^0)$ and $T^{-1}(\tilde{p}^0)$. If there is no conflict, this triangle is Delaunay and added
in the triangulation. If $T(\tilde{p}^0)$ is in conflict with $\tilde{t}$, determine the new Delaunay triangles by evaluating the incircle predicate with the four points $\tilde{p}^0, T(\tilde{p}^0), \tilde{v}_1, \tilde{v}_2$, see Figure 12. Add triangles that contain $\tilde{p}^0$ in the triangulation. The case where the triangle contains $T^{-1}(\tilde{p}^0)$ is similar.

## 5.2 Correctness and Termination

The parameter $\varepsilon_0$ is small enough to use Algorithm 1 and all results in Section 4 and A. The termination is clear and for the correctness it is sufficient to prove that, at each insertion of a point $p$, we compute the Delaunay triangulation of the current point set.

If $p$ is in the $4\varepsilon_0$-thick part, the correctness follows from the correctness of the classical Bowyer algorithms in $\mathbb{H}^2$ (Section 2.4) and Theorem 5. Indeed, we have to prove that the created triangles belong to the Delaunay triangulation with $p$ added. Recall that a new triangle is formed by an edge on the boundary of the conflict zone and $\tilde{p}^0$. The only thing that would prevent such a triangle from being Delaunay is when its circumdisk contains another copy of $\tilde{p}^0$ and this cannot occur thanks to Theorem 5.

Otherwise, $p$ is in the $4\varepsilon$-thin part and the conflict zone of a lift $\tilde{p}^0$ may contain other lifts of $p$. By Corollary 13, the restricted conflict zone $C_p$ is still a topological ball in $\mathbb{H}^2$ thus the DFS algorithm visits all triangles in the restricted conflict zone. By Corollary 11, every triangle in the conflict zone of $\tilde{p}^0$ has a copy in conflict with $\tilde{p}^0$ in $C_p$. Thus, removing all triangles in $C_p$ is the same as removing all triangles in the conflict zone of $\tilde{p}^0$.

By Theorem 10, every new Delaunay edge from $\tilde{p}^0$ has its other endpoint between the lines $T^+$ and $T^-$, thus it is enough to consider triangles in conflict that have at least one vertex in the restricted zone, that is between $T^+$ and $T^-$. In addition, each new Delaunay triangle with vertex $p$ has a lift with vertex $\tilde{p}^0$ in $\mathbb{H}^2$. We cannot connect $\tilde{p}^0$ to every vertex in the restricted zone of a triangle in $C_p$ because we could create triangles in conflict with $T(\tilde{p}^0)$ or $T^{-1}(\tilde{p}^0)$. Let $\tilde{s} = [\tilde{v}_1, \tilde{v}_2]$ be an edge on the boundary of $C_p$.

**Case 1:** $\tilde{s}$ is in the restricted zone. We check conflicts between the triangle $\tilde{t}$ formed by $\tilde{s}$ and $\tilde{p}^0$ and the points $T(\tilde{p}^0)$ and $T^{-1}(\tilde{p}^0)$.

If there is no conflict, this triangle does not contain any other copy of $\tilde{p}^0$ and is thus Delaunay. If $T(\tilde{p}^0)$ is in conflict with $\tilde{t}$, its circumdisk contains $T(\tilde{p}^0)$ and the segments $[T(\tilde{p}^0), \tilde{p}^0]$, $[T(\tilde{p}^0), \tilde{v}_1]$ and $[T(\tilde{p}^0), \tilde{v}_2]$ belong to the triangulation by Lemma 3. The new Delaunay triangles are determined by the evaluation of the incircle predicate with the four points $\tilde{p}^0, T(\tilde{p}^0), \tilde{v}_1, \tilde{v}_2$, see Figure 12.

The case where the triangle contains $T^{-1}(\tilde{p}^0)$ is analogous, with $T^+$ replaced by $T^-$.

**Case 2:** $\tilde{s}$ intersects $T^+$ or $T^-$. Without loss of generality, we may assume that $\tilde{s}$ intersects $T^+$ and that $\tilde{v}_1$ is between $T^+$ and $T^-$. Let us show that the triangle $\tilde{p}^0T(\tilde{p}^0)\tilde{v}_1$ is in the Delaunay triangulation.

The circumdisk of the triangle $\tilde{p}^0\tilde{v}_1\tilde{v}_2$ may only contain some copies of $\tilde{p}^0$. Furthermore, this circumdisk cannot be empty otherwise the edge $[\tilde{p}^0, \tilde{v}_2]$ would belong to the Delaunay triangulation which is in contradiction with Theorem 10. By hypothesis, $\tilde{v}_2$ is not on the same side of $T^+$ as $\tilde{p}^0$, then by Lemma 9, the circumdisk of $\tilde{p}^0\tilde{v}_1\tilde{v}_2$ necessarily contains $T(\tilde{p}^0)$. It follows that the circumdisk of triangle $\tilde{p}^0T(\tilde{p}^0)\tilde{v}_1$ may only contain some copies of $\tilde{p}^0$. However, by the above and Theorem 10, the vertex $\tilde{v}_1$ can only be connected to $\tilde{p}^0$ and $T(\tilde{p}^0)$, then the circumdisk of $\tilde{p}^0T(\tilde{p}^0)\tilde{v}_1$ is necessarily empty otherwise $\tilde{v}_1$ would be connected to another copy of $\tilde{p}^0$ which is impossible. Finally, the triangle $\tilde{p}^0T(\tilde{p}^0)\tilde{v}_1$ belongs to the Delaunay triangulation.
<figure><img src="image_16.png" /><figcaption>■ **Figure 12** All possible cases, up to swapping $\tilde{v}_1$ and $\tilde{v}_2$, when the circumdisk of the triangle $\tilde{p}^0\tilde{v}_1\tilde{v}_2$ is nonempty.</figcaption></figure>

## 5.3 Complexity

We consider the following elementary operations in $\mathbb{H}^2$ that have constant complexity in the real RAM model:

- Computing distances in $\mathbb{H}^2$.

- Applying an isometry to a triangle or a point.

- Evaluating the orientation predicate, that is deciding if a point lies on the right or left side of an oriented geodesic line.

- Evaluating the incircle predicate, that is given three points deciding whether a fourth one is inside or outside the circumdisk of the three points.

- Orthogonally projecting a point onto a given line.

The complexity of Algorithm 1 only depends on the genus of the surface [18, Thm. III.14], which we assume constant. The number of points in the dummy points set $\mathcal{F}$ is thus a constant. We note $n$ the cardinal of $\mathcal{P}$. At the insertion of the $i$-th point, the number of triangles in the Delaunay triangulation is denoted $F_i = O(n)$.

- Step (a): Testing whether a lift of a triangle contains a point is done by at most three orientation predicates. Every triangle has at most three lifts, thus this step is in $O(F_i)$.

- Step (b): Labels on points are accessed in constant time, so this step is in $O(1)$.

- Step (c): Testing $O(F_i)$ incircle predicates is in $O(F_i)$.

- Step (d): The number of new triangles is in $O(F_i)$ so this step is in $O(F_i)$.

- Step (e): It is in $O(F_i)$ because computing the lines $T^+$ and $T^-$ is an elementary operation, and the algorithm processes each triangle a constant number of times.

- Step (f): It is in $O(F_i)$ because for each edge in the list $L_p$, the algorithm computes at most four incircle predicates and computes the side of $T^+$ and $T^-$ its endpoints lie, and these are $O(1)$ operations.

To conclude, each insertion takes $O(F_i) = O(n)$ time. Summing over all $i$, the algorithm takes $O(n^2)$ time.

## References

1. Alan F. Beardon. *The Geometry of Discrete Groups*, volume 91 of *Graduate Texts in Mathematics*. Springer, New York, NY, 1983. doi:10.1007/978-1-4612-1146-4

2. Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic delaunay complexes and voronoi diagrams made practical. In *Proceedings of the twenty-ninth Annual Symposium on Computational Geometry*, pages 67–76, 2013.
494

3 Mikhail Bogdanov and Monique Teillaud. Delaunay triangulations and cycles on closed hyperbolic surfaces. (RR-8434), December 2013. URL: https://inria.hal.science/hal-00921157.

495

496

4 A. Bowyer. Computing dirichlet tessellations. *The Computer Journal*, 24(2):162–166, 01 1981.
doi:10.1093/comjnl/24.2.162.

497

498

5 Peter Buser. *Geometry and Spectra of Compact Riemann Surfaces*. Springer, Boston, 1992.
doi:10.1007/978-0-8176-4992-0.

499

500

6 Manuel Caroli, Aymeric Pellé, Mael Rouxel-Labbé, and Monique Teillaud. 3D periodic triangulations. In *CGAL User and Reference Manual*. CGAL Editorial Board, 6.1 edition, 2025. URL: https://doc.cgal.org/6.1/Manual/packages.html#PkgPeriodic3Triangulation3.

501

502

503

7 Manuel Caroli and Monique Teillaud. Computing 3D Periodic Triangulations. In *Lecture Notes in Computer Science*, volume 5757 of *Lecture Notes in Computer Science*, pages 59–70, Copenhagen, Denmark, September 2009. Springer. URL: https://inria.hal.science/hal-02954152, doi:10.1007/978-3-642-04128-0\_6.

504

505

506

507

8 Kenneth L. Clarkson. Building triangulations using epsilon-nets. In *STOC '06*, page 326–335, New York, NY, USA, 2006. URL: https://kenclarkson.org/enet_tris/p.pdf, doi:10.1145/1132516.1132564.

508

509

510

9 Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud. Computing a dirichlet domain for a hyperbolic surface. *Journal of Computational Geometry*, 15(2):40–56, Feb. 2025. URL: https://jocg.org/index.php/jocg/article/view/5169, doi:10.20382/jocg.v15i2a2.

511

512

513

514

10 Vincent Despré, Camille Lanuel, Marc Pouget, and Monique Teillaud. e-net algorithm implementation on hyperbolic surfaces. In *Proceedings 33th European Symposium on Algorithms*, 2025.

515

516

517

11 Vincent Despré, Camille Lanuel, and Monique Teillaud. Computing an epsilon-net of a closed hyperbolic surface. In *EuroCG'24 - 40th European Workshop on Computational Geometry*, March 2024. URL: https://hal.science/hal-04509616.

518

519

520

12 Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping geometric triangulations on hyperbolic surfaces. *LIPICS, Volume 164*, SoCG 2020, 164:35:1–35:16, 2020. doi:10.4230/LIPICS.SOCG.2020.35.

521

522

523

13 Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, and Gert Vegter. Delaunay triangulations of generalized Bolza surfaces. *Journal of Computational Geometry*, 13(1):125–177, April 2022. URL: https://inria.hal.science/hal-03664678, doi:10.20382/jocg.v13i1a5.

524

525

526

14 Matthijs Ebbens, Hugo Parlier, and Gert Vegter. Minimal Delaunay Triangulations of Hyperbolic Surfaces. *Discrete & Computational Geometry*, 69(2):568–592, 2023. URL: https://link.springer.com/10.1007/s00454-022-00373-0, doi:10.1007/s00454-022-00373-0.

527

528

529

15 David Eppstein. Hyperbolic geometry, Möbius transformations, and geometric optimization. In *MSRI Introductory Workshop on Discrete and Computational Geometry*, 2003.

530

531

16 Iordan Iordanov and Monique Teillaud. Implementing Delaunay Triangulations of the Bolza Surface. *LIPICS, Volume 77*, SoCG 2017, 77:44:1–44:15, 2017. doi:10.4230/LIPICS.SOCG.2017.44.

532

533

534

17 Nico Kruithof. 2D periodic triangulations. In *CGAL User and Reference Manual*. CGAL Editorial Board, 6.1 edition, 2025. URL: https://doc.cgal.org/6.1/Manual/packages.html#PkgPeriodic2Triangulation2.

535

536

537

18 Camille Lanuel. *Computing an ε-net of a hyperbolic surface*. Theses, Université de Lorraine, November 2025. URL: https://hal.science/tel-05385908.

538

539

19 Mael Rouxel-Labbé, Monique Teillaud, and Claudia Werner. 2D triangulations on the sphere. In *CGAL User and Reference Manual*. CGAL Editorial Board, 6.1 edition, 2025. URL: https://doc.cgal.org/6.1/Manual/packages.html#PkgTriangulationOnSphere2.

540

541

542

20 Daniel Dominic Sleator, Robert Endre Tarjan, and William P Thurston. Rotation distance, triangulations, and hyperbolic geometry. In *Proceedings of the eighteenth annual ACM symposium on Theory of computing*, pages 122–135, 1986.

543

544
A Conflict zone in the $4\epsilon_0$-thick part

547

548

549

550

551

552

In this section, we study the case where the point $p$ to be inserted is in the $4\epsilon_0$-thick part. Recall that the current Delaunay triangulation $DT$ includes a set of dummy points $\mathcal{F}$ as computed by Algorithm 1. We prove that the set of conflicting triangles of a lift $\tilde{p}$ of $p$ contains only this lift and that there is no Delaunay loop edge in the $4\epsilon_0$-thick part. Let us recall the following result.

**Lemma 14** ([5, th 4.1.5]). Let $p$ be a point of $S$ and $r_p(S)$ its injectivity radius. We have $2r_p(S) = l(\mu_p)$ where $\mu_p$ is the shortest geodesic loop at $p$.

553

554

We study different cases depending on the location of the conflicting disk center.

555

**Lemma 15.** Let $\tilde{D}$ be an empty disk with center $\tilde{c}$ in conflict with $\tilde{p}$. If $\tilde{c}$ belongs to $\rho^{-1}(S_{4\epsilon_0}^T)$ then all copies of $\tilde{D}$ are pairwise disjoint.

556

557

**Proof.** As the set $\mathcal{F}$ is an $\epsilon_0$-covering of $S_{4\epsilon_0}^T$, $\tilde{D}$ has a radius smaller than $\epsilon_0$. Therefore, $\tilde{D}$ is included in the open disk $B(p, 2\epsilon_0)$. However, by Lemma 14 we have $r_p(S) > 2\epsilon_0$ because $p$ belongs to $S_{4\epsilon_0}^T$ and then $\tilde{D}$ is included in $B(p, r_p(S))$. The result follows because all lifts of $B(p, r_p(S))$ are pairwise disjoint. ◀

558

559

560

561

In the case where the center of an empty disk, which is in conflict with a point $p$, is in $S_{4\epsilon_0}^T$, the situation becomes more technical. In fact, two lifts of a conflicting disk may intersect each other, but we will show that the intersection is included in $S_{4\epsilon_0}^T$.

562

563

564

<figure><img src="image_17.png" /><figcaption>Figure 13 The $4\epsilon_0$-banana of axis $\Delta$ is displayed in yellow. Lifts of a point $b_i$ lying on its boundary are shown in green, $b_i$ is one of them. In blue: lifts of a disk centered at a point $c$ lifting to $\tilde{c}$ inside the $4\epsilon_0$-banana.</figcaption></figure>

565

566

567

There are two different cases illustrated in the Figure 13. Either the center of the disk is close to the boundary of the $4\epsilon_0$-banana, or the center is far from it, see Lemma 19 for the precise definitions. In the first case (left-hand side of Figure 13), no two lifts of the disk can intersect outside the $4\epsilon_0$-banana, otherwise there would exist a ball of radius $\epsilon_0$ included in the disk, implying that the disk contains a point of the triangulation. In the second case

568

569

570

571

572
XX:20 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

(right-hand side of Figure 13), if two lifts of the disk intersect outside the $4\epsilon_0$-banana, then the disk would contain a hypercycle arc of the boundary greater than $4\epsilon_0$. On the other hand, the dummy points set constructed by Algorithm 1 contains one point on each of the boundaries of every $4\epsilon_0$-collars [18, Algorithm III.10]. This implies that the disk contains at least one dummy point. We start with several technical results.

► Lemma 16. We have the equality in $\mathbb{R}$:

$$ \forall (a, b) \in \mathbb{R} \times \mathbb{R}^*, \quad \frac{1}{\cosh(a)^2} - \left( \frac{\tanh(a)}{\sinh(b)} \right)^2 = 1 - \left( \frac{\tanh(a)}{\tanh(b)} \right)^2. $$

Proof. The equality $\cosh^2 - \sinh^2 = 1$ is used twice. Let $(a, b) \in \mathbb{R} \times \mathbb{R}^*$, then

$$ \begin{aligned} \frac{1}{\cosh(a)^2} - \left( \frac{\tanh(a)}{\sinh(b)} \right)^2 &= \frac{\cosh(a)^2 - \sinh(a)^2}{\cosh(a)^2} - \left( \frac{\tanh(a)}{\sinh(b)} \right)^2 \\ &= 1 - \tanh(a)^2 \left( 1 + \frac{1}{\sinh(b)^2} \right) \\ &= 1 - \tanh(a)^2 \left( 1 + \frac{\cosh(b)^2 - \sinh(b)^2}{\sinh(b)^2} \right) \\ &= 1 - \left( \frac{\tanh(a)}{\tanh(b)} \right)^2. \end{aligned} $$

► Lemma 17. Let $\tilde{b}_i$ be a point lying on the boundary of a $4\epsilon_0$-banana of axis $\Delta$. Let $T$ be the translation associated to the banana, we have

$$ d_h([\tilde{b}_i, T(\tilde{b}_i)], \Delta) = \arccosh \left( \frac{\tanh(2\epsilon_0)}{\tanh(\sigma/2)} \right). $$

Proof. Define $d := d_h([\tilde{b}_i, T(\tilde{b}_i)], \Delta)$, let $\tilde{m}$ be the midpoint of the geodesic segment $[\tilde{b}_i, T(\tilde{b}_i)]$ and $w$ be the radius of $\mathcal{H}_{\tilde{b}_i}^-$ the hypercycle of axis $\Delta$ passing through $\tilde{b}_i$ and $T(\tilde{b}_i)$.

First, we show that the geodesic line orthogonal to both $\Delta$ and the line $(\tilde{b}_i, T(\tilde{b}_i))$ goes through $\tilde{m}$, which proves that $d = d_h(\tilde{m}, \pi(\tilde{m}))$. Then we use trigonometric formulas to compute the distance $d$, see Figure 14.

Let $\Upsilon$ be the line orthogonal to both $\Delta$ and the line $(\tilde{b}_i, T(\tilde{b}_i))$. As $\Upsilon$ is orthogonal to $\Delta$, then $\Upsilon$ is also orthogonal to $\mathcal{H}_{\tilde{b}_i}^-$. In particular, $\Delta$, $\mathcal{H}_{\tilde{b}_i}^-$ and $(\tilde{b}_i, T(\tilde{b}_i))$ are invariant under reflection across the axis $\Upsilon$. Then, this reflection maps $\tilde{b}_i$ to $T(\tilde{b}_i)$. We deduce that $\Upsilon \cap (\tilde{b}_i, T(\tilde{b}_i))$ is exactly the midpoint $\tilde{m}$ of the segment $[\tilde{b}_i, T(\tilde{b}_i)]$. To compute $d$, we remark that triangles $\tilde{b}_i, \tilde{m}, \pi(\tilde{m})$ and $\tilde{b}_i, \pi(\tilde{b}_i), \pi(\tilde{m})$ are right triangles in $\tilde{m}$ and $\pi(\tilde{b}_i)$ respectively. By the hyperbolic Pythagorean Theorem, we deduce that

$$ \cosh(\sigma/2) \cosh(w) = \cosh(2\epsilon_0) \cosh(d). $$

Moreover, Theorem 1 yields $\cosh(w) = \frac{\sinh(2\epsilon_0)}{\sinh(\sigma/2)}$ and it follows that $\frac{\tanh(2\epsilon_0)}{\tanh(\sigma/2)} = \cosh(d)$. ◀

► Lemma 18. Define $d := d_h([\tilde{b}_i, T(\tilde{b}_i)], \Delta)$ and let $w$ be the radius of the hypercycle $\mathcal{H}_{\tilde{b}_i}^-$ of axis $\Delta$ passing through $\tilde{b}_i$ and $T(\tilde{b}_i)$. We have $w - d < \epsilon_0$.
<figure><img src="image_18.png" /><figcaption>Figure 14 Illustration of the proof of Lemma 17.</figcaption></figure>

**Proof.** By Theorem 1 and Lemma 17, we know that

$$w = \operatorname{arccosh}\left(\frac{\sinh(2\varepsilon_0)}{\sinh(\sigma/2)}\right), \quad d = \operatorname{arccosh}\left(\frac{\tanh(2\varepsilon_0)}{\tanh(\sigma/2)}\right).$$

Use the fact that $\operatorname{arccosh}(x) = \ln(x + \sqrt{x^2 - 1}) = \ln(x) + \ln(1 + \sqrt{1 - \frac{1}{x^2}})$ for $x > 1$, then

$$w - d = \ln\left(\frac{\sinh(2\varepsilon_0)}{\sinh(\sigma/2)}\right) + \ln\left(1 + \sqrt{1 - \left(\frac{\sinh(\sigma/2)}{\sinh(2\varepsilon_0)}\right)^2}\right) - \ln\left(\frac{\tanh(2\varepsilon_0)}{\tanh(\sigma/2)}\right) \\ - \ln\left(1 + \sqrt{1 - \left(\frac{\tanh(\sigma/2)}{\tanh(2\varepsilon_0)}\right)^2}\right).$$

However,

$$- \ln \left( \frac{\tanh(2\varepsilon_0)}{\tanh(\sigma/2)} \right) = - \ln \left( \frac{\sinh(2\varepsilon_0)}{\sinh(\sigma/2)} \right) + \ln(\cosh(2\varepsilon_0)) - \ln(\cosh(\sigma/2)).$$
Then,

$$
\begin{align*}
w - d &= \ln(\cosh(2\epsilon_0)) + \ln \left( 1 + \sqrt{1 - \left( \frac{\sinh(\sigma/2)}{\sinh(2\epsilon_0)} \right)^2} \right) - \ln(\cosh(\sigma/2)) \\
&\qquad - \ln \left( 1 + \sqrt{1 - \left( \frac{\tanh(\sigma/2)}{\tanh(2\epsilon_0)} \right)^2} \right) \\
&= \ln(\cosh(2\epsilon_0)) + \ln \left( \frac{1}{\cosh(\sigma/2)} + \sqrt{ \frac{1}{\cosh(\sigma/2)^2} - \left( \frac{\tanh(\sigma/2)}{\sinh(2\epsilon_0)} \right)^2 } \right) \\
&\qquad - \ln \left( 1 + \sqrt{1 - \left( \frac{\tanh(\sigma/2)}{\tanh(2\epsilon_0)} \right)^2} \right) \\
&= \ln(\cosh(2\epsilon_0)) + \ln \left( \frac{1}{\cosh(\sigma/2)} + \sqrt{ 1 - \left( \frac{\tanh(\sigma/2)}{\tanh(2\epsilon_0)} \right)^2 } \right) \\
&\qquad - \ln \left( 1 + \sqrt{1 - \left( \frac{\tanh(\sigma/2)}{\tanh(2\epsilon_0)} \right)^2} \right),
\end{align*}
$$

where we used Lemma 16 to go from the second to the third line. Thus, we have $w - d \le \ln(\cosh(2\epsilon_0)) < \epsilon_0$. □

► Lemma 19. Let $\tilde{D}$ be an empty disk with center $\tilde{c}$ in a $4\epsilon_0$-banana. For every distinct integers $k,l$, one has $T^k(\tilde{D}) \cap T^l(\tilde{D}) \cap \rho^{-1}(S_{4\epsilon_0}^T) = \emptyset$.

**Proof.** For a point $\tilde{x}$ in the $4\epsilon_0$-banana bounded by two hypercycles $\mathcal{H}_1$ and $\mathcal{H}_2$, we introduce the notion *close to* and *far from* $\mathcal{H}_i$ for $i = 1, 2$. On the hypercycle $\mathcal{H}_i$, there are lifts $(T^k(\tilde{b}_i))_{k \in \mathbb{Z}}$ spaced $4\epsilon_0$ apart since the dummy points set contains a point on each boundary of $4\epsilon_0$-collars. In particular, the geodesic segments $[T^k(\tilde{b}_i), T^{k+1}(\tilde{b}_i)]$ coincides with $\mathcal{H}_i$ at the points $T^k(\tilde{b}_i)$ and $T^{k+1}(\tilde{b}_i)$. Hence, each segment defines a region bounded by the $\mathcal{H}_i$-arc from $T^k(\tilde{b}_i)$ to $T^{k+1}(\tilde{b}_i)$ and the geodesic segment $[T^k(\tilde{b}_i), T^{k+1}(\tilde{b}_i)]$. If $\tilde{x}$ belongs to one of these regions we will say that $\tilde{x}$ is close to $\mathcal{H}_i$ and else that it is far from $\mathcal{H}_i$. For example, in Figure 13, the point $\tilde{c}$ is close to $\tilde{\mathcal{H}}_{\tilde{b}_i}$ on the left, and $\tilde{c}$ is far from $\tilde{\mathcal{H}}_{\tilde{b}_i}$ on the right.

We argue by contradiction. Suppose there are two distinct integers $k$ and $l$ such that $A_{k,l} := T^k(\tilde{D}) \cap T^l(\tilde{D}) \cap \rho^{-1}(S_{4\epsilon_0}^T)$ is nonempty. As $T$ is an isometry, we can suppose that $k=0$. Let $\tilde{z} \in A_{0,l}$, then, both $\tilde{z}$ and $T^{-l}(\tilde{z})$ are in $\tilde{D}$, and, as the translation distance is larger than $4\epsilon_0$ for all points outside of the $4\epsilon_0$-banana, we deduce that $d_h(\tilde{z}, T^{-l}(\tilde{z})) > 4\epsilon_0$. It follows that $\tilde{D}$ has a chord longer than $4\epsilon_0$, then the radius of $\tilde{D}$ is larger than $2\epsilon_0$. We distinguish two cases.

• If $\tilde{c}$ is close to $\tilde{\mathcal{H}}_{\tilde{b}_i}$, then by Lemma 18, we have $d_h(\tilde{c}, \tilde{\mathcal{H}}_{\tilde{b}_i}) < \epsilon_0$. It follows that $\tilde{D}$ contains a disk of radius $\epsilon_0$ and whose center lies on $\tilde{\mathcal{H}}_{\tilde{b}_i}$. As the set $\mathcal{F}$ is an $\epsilon_0$-covering of $S_{4\epsilon_0}^T$, it follows that the disk $\tilde{D}$ is nonempty, which is impossible.

• If $\tilde{c}$ is far from $\tilde{\mathcal{H}}_{\tilde{b}_i}$, let $\tilde{h}_1$ and $\tilde{h}_2$ be the intersection points between $\partial\tilde{D}$ and $\tilde{\mathcal{H}}_{\tilde{b}_i}$. As $\tilde{c}$ is far from $\tilde{\mathcal{H}}_{\tilde{b}_i}$, the chord from $\tilde{h}_1$ to $\tilde{h}_2$ separates $\tilde{z}$ and $T^{-l}(\tilde{z})$ from $\tilde{c}$ and, thus, $d_h(\tilde{h}_1, \tilde{h}_2) > d_h(\tilde{z}, T(\tilde{z})) > 4\epsilon_0$. Then, the $\tilde{\mathcal{H}}_{\tilde{b}_i}$-arc from $\tilde{h}_1$ to $\tilde{h}_2$ contains a point of $(T^k(\tilde{b}_i))_{k \in \mathbb{Z}}$ since it is a $4\epsilon$-net of $\tilde{\mathcal{H}}_{\tilde{b}_i}$. Moreover, the $\tilde{\mathcal{H}}_{\tilde{b}_i}$-arc from $\tilde{h}_1$ to $\tilde{h}_2$ is included in $\tilde{D}$. It follows that the disk $\tilde{D}$ is nonempty, which is impossible. □
To prove Theorem 5, we use the following known fact about bananas that we prove for completeness.

**Lemma 20.** The bananas of a set of simple closed geodesics shorter than $2\arcsin h(1)$ are pairwise disjoint.

**Proof.** Let $\mathcal{B}_1$ and $\mathcal{B}_2$ be two different bananas of axis $\Delta_1$ and $\Delta_2$ respectively. If $\mathcal{B}_1$ and $\mathcal{B}_2$ are lifts of different collars, then, by Theorem 1, we deduce that they are disjoint. Otherwise $\mathcal{B}_1$ and $\mathcal{B}_2$ are lifts of a same collar. Denote $w$ its width, $\sigma$ its systole, and suppose that $\mathcal{B}_1$ and $\mathcal{B}_2$ intersect each other. Then there exists a segment of length strictly smaller than $2w$ from $\Delta_1$ to $\Delta_2$ included in $\mathcal{B}_1 \cup \mathcal{B}_2$. Therefore, there is, on the surface, a path from $\sigma$ to $\sigma$ that is not homotopic to $\sigma$ or $\sigma^{-1}$ and of length strictly smaller than $2w$. This is impossible by Theorem 1.

◀

**Proof of Theorem 5.** Let $\tilde{c}$ be the center of $\tilde{D}$. If $\tilde{c}$ belongs to $\rho^{-1}(S_{4\varepsilon_0}^T)$, the result follows by Lemma 15. Otherwise, $\tilde{c}$ belongs to $\rho^{-1}(S_{4\varepsilon_0}^t)$. Let us prove that $\tilde{D}$ is included in the banana containing its center. In fact, if $\tilde{D}$ intersects the boundary of this banana, then it would have a radius larger than $2\varepsilon_0$ by Proposition 6. Therefore, there would exist a disk of radius $\varepsilon_0$ included in $\tilde{D} \cap S_{4\varepsilon_0}^T$ and then $\tilde{D}$ would be nonempty. That proves that $\tilde{D}$ is included in a banana and by Lemma 20, we deduce that two copies of $\tilde{D}$ in different bananas are disjoint. Finally, in the same banana, by Lemma 19, we know that the lifts of $\tilde{D}$, restricted to the thick part, are pairwise disjoint which completes the proof.

◀

## B Proofs of Section 4

**Proof of Proposition 6.** We have $4\varepsilon < \ln(3) < 2\arcsin h(1)$ so that $4\varepsilon$-collar is included in the collar and $d_1$ and $d_2$ are given by Theorem 1. Then,

$$d_1 - d_2 = \arcsin h \left( \frac{1}{\sinh\left(\frac{\sigma\varepsilon}{2}\right)} \right) - \arccosh \left( \frac{\sinh(2\varepsilon)}{\sinh\left(\frac{\sigma\varepsilon}{2}\right)} \right).$$

Use the fact that $\arccosh(x) = \ln(x + \sqrt{x^2 - 1}) = \ln(x) + \ln(1 + \sqrt{1 - \frac{1}{x^2}})$ for $x > 1$ and $\arcsin h(x) = \ln(x + \sqrt{x^2 + 1}) = \ln(x) + \ln(1 + \sqrt{1 + \frac{1}{x^2}})$ for a real $x$, then

$$\begin{aligned} d_1 - d_2 &= \ln \left( \frac{1}{\sinh\left(\frac{\sigma\varepsilon}{2}\right)} \right) + \ln \left( 1 + \sqrt{1 + \sinh\left(\frac{\sigma\varepsilon}{2}\right)^2} \right) - \ln \left( \frac{\sinh(2\varepsilon)}{\sinh\left(\frac{\sigma\varepsilon}{2}\right)} \right) \\ &\qquad - \ln \left( 1 + \sqrt{1 - \frac{\sinh\left(\frac{\sigma\varepsilon}{2}\right)^2}{\sinh(2\varepsilon)^2}} \right) \\ &= -\ln(\sinh(2\varepsilon)) + \ln \left( 1 + \sqrt{1 + \sinh\left(\frac{\sigma\varepsilon}{2}\right)^2} \right) - \ln \left( 1 + \sqrt{1 - \frac{\sinh\left(\frac{\sigma\varepsilon}{2}\right)^2}{\sinh(2\varepsilon)^2}} \right). \end{aligned}$$

Thus, we have $d_1 - d_2 \ge \ln(\frac{1}{\sinh(2\varepsilon)})$ with equality if and only if $\sigma\varepsilon = 0$. But the systole of a compact surface is always positive then $d_1 - d_2 > \ln(\frac{1}{\sinh(2\varepsilon)})$.

To conclude, it is sufficient to prove that $\ln(\frac{1}{\sinh(2\varepsilon)}) \ge 2\varepsilon$. It is equivalent to $1 \ge \sinh(2\varepsilon) \exp(2\varepsilon)$ which is equivalent to $\frac{1}{4} \ln(3) \ge \varepsilon$.

◀
XX:24 Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

**Prof of Corollary 7.** Let $\tilde{p}$ be a lift of $p$ and $\tilde{t}$ be a triangle in conflict with $\tilde{p}$. By definition, the circumscribed disk $\tilde{D}$ of $\tilde{t}$ contains $\tilde{p}$. Suppose that $\rho(\tilde{D})$ is not included in $\mathscr{C}$ then $\rho(\tilde{D})$ has a point in $S \setminus \mathscr{C}$ and in the $4\epsilon$-thin part. Proposition 6 implies that the diameter of $\tilde{D}$ is larger than $2\epsilon$. Hence, we can find a disk $\tilde{D}'$ of diameter $\epsilon$ included in $\tilde{D}$ and whose projection $\rho(\tilde{D}')$ is included in the $4\epsilon$-thick part and in $\mathscr{C}$. However, the set of vertices of the Delaunay triangulation is also an $\epsilon$-covering of the $4\epsilon$-thick part, then $\rho(\tilde{D}')$ is nonempty thus $\tilde{D}'$ is nonempty and therefore $\tilde{D}$ is nonempty. ▲

**Proof of Lemma 9.** Let $\mathscr{H}_{x,y}^{\sim}$ be a hypercycle or a horocycle passing through $\tilde{x}$ and $\tilde{y}$. In the Poincare disk, $\mathscr{H}_{x,y}^{\sim}$ is a part of a line or a circle that intersects the boundary of the Poincare disk in two points $l_0$ and $l_1$, which may coincide if $\mathscr{H}_{x,y}^{\sim}$ is a horocycle (see Figure 7). Then, $\mathscr{H}_{x,y}^{\sim}$ intersects $\partial\tilde{D}$ at two distinct points $\tilde{x}_D$ and $\tilde{y}_D$ from $\tilde{x}$ to $l_0$ and from $\tilde{y}$ to $l_1$ respectively. $\mathscr{H}_{x,y}^{\sim}$ is divided into three disjointed parts, one of which is included in $\tilde{D}$: a part from $l_0$ to $\tilde{x}_D$, a second from $\tilde{x}_D$ to $\tilde{y}_D$ containing $\tilde{x}$ and $\tilde{y}$, and a third from $\tilde{y}_D$ to $l_1$. Necessarily the first and third parts are outside of $\tilde{D}$ and then the second is included in it. This concludes because the $\mathscr{H}_{x,y}^{\sim}$-arc from $\tilde{x}$ to $\tilde{y}$ is included in it. ▲

C Illustration of the algorithm

C.1 Insertion in the thick part

The following is a description of the insertion of a point $p$ in the $4\epsilon_0$-thick part, it is illustrated in the Figure 15. We denote by $\tilde{s}_{i,j}$ the edge of the triangle $\tilde{t}_i$ in common with the triangle $\tilde{t}_j$. Note that $\tilde{s}_{i,j}$ and $\tilde{s}_{j,i}$ may be different in our data structure (the first one belongs to $\tilde{t}_i$ and the second to $\tilde{t}_j$) but there exists an isometry in $\Gamma$ that maps $\tilde{s}_{i,j}$ to $\tilde{s}_{j,i}$.

**Iteration 0:** Let $L_p$ be the list of boundary edges of the conflict zone of $\tilde{p}^0$ with their isometries. Let $C_p$ be the list of the triangles of the conflict zone of $\tilde{p}^0$ with their isometries. Let $Q$ be the queue that will contain pairs (triangle, edge) to be processed during the DFS. In the Figure 15, elements of $C_p$, $L_p$ and $Q$ are respectively displayed in orange, red and green.

**Data:** $C_p = []$, $L_p = []$ and $Q = []$.

**Iteration 1:** Find a triangle $\tilde{t}_0^0$ and an isometry $\gamma_0$ such that $\gamma_0(\tilde{t}_0^0)$ contains $\tilde{p}^0$. Add $\tilde{t}_0^0$ to $C_p$ and push $(\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))$, $(\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2}))$ and $(\tilde{t}_3^0, \gamma_0(\tilde{s}_{0,3}))$ to $Q$.

**Data:** $C_p = [\tilde{t}_0^0]$, $L_p = []$ and $Q = [(\tilde{t}_3^0, \gamma_0(\tilde{s}_{0,3})), (\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 2:** Pop the element $(\tilde{t}_3^0, \gamma_0(\tilde{s}_{0,3}))$ of $Q$ and denote by $\gamma_3$ the isometry that glues $\tilde{t}_3^0$ with $\gamma_0(\tilde{t}_0^0)$ along $\gamma_0(\tilde{s}_{0,3})$. The circumdisk of $\gamma_3(\tilde{t}_3^0)$ contains $\tilde{p}^0$, then add $\tilde{t}_3^0$ in $C_p$ and push $(\tilde{t}_4^0, \gamma_3(\tilde{s}_{3,4}))$ and $(\tilde{t}_5^0, \gamma_3(\tilde{s}_{3,5}))$ in $Q$.

**Data:** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0]$, $L_p = []$ and $Q = [(\tilde{t}_5^0, \gamma_3(\tilde{s}_{3,5})), (\tilde{t}_4^0, \gamma_3(\tilde{s}_{3,4})), (\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 3:** Pop the element $(\tilde{t}_5^0, \gamma_3(\tilde{s}_{3,5}))$ of $Q$ and denote by $\gamma_5$ the isometry that glues $\tilde{t}_5^0$ with $\gamma_3(\tilde{t}_3^0)$ along $\gamma_3(\tilde{s}_{3,5})$. The circumdisk of $\gamma_5(\tilde{t}_5^0)$ does not contains $\tilde{p}^0$, then add $\gamma_3(\tilde{s}_{3,5})$ in $L_p$.

**Data:** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5})]$ and $Q = [(\tilde{t}_4^0, \gamma_3(\tilde{s}_{3,4})), (\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 4:** Pop the element $(\tilde{t}_4^0, \gamma_3(\tilde{s}_{3,4}))$ of $Q$ and denote by $\gamma_4$ the isometry that glues $\tilde{t}_4^0$ with $\gamma_3(\tilde{t}_3^0)$ along $\gamma_3(\tilde{s}_{3,4})$. The circumdisk of $\gamma_4(\tilde{t}_4^0)$ does not contains $\tilde{p}^0$, then add $\gamma_3(\tilde{s}_{3,4})$.
$\gamma_4(\tilde{s}_{3,4})$ in $L_p$.

719

**Data :** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5}), \gamma_3(\tilde{s}_{3,4})]$ and $Q = [(	ilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

720

**Iteration 5 :** Pop the element $(\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2}))$ of $Q$ and denote by $\gamma_2$ the isometry that glues $\tilde{t}_2^0$ with $\gamma_0(\tilde{t}_0^0)$ along $\gamma_0(\tilde{s}_{0,2})$. The circumdisk of $\gamma_2(\tilde{t}_2^0)$ contains $\tilde{p}^0$, then add $\tilde{t}_2^0$ in $C_p$ and push $(\tilde{t}_6^0, \gamma_2(\tilde{s}_{2,6}))$ and $(\tilde{t}_7^0, \gamma_2(\tilde{s}_{2,7}))$ in $Q$.

721

722

723

**Data :** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0, \tilde{t}_2^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5}), \gamma_3(\tilde{s}_{3,4})]$ and

724

725

$Q = [(	ilde{t}_7^0, \gamma_2(\tilde{s}_{2,7})), (\tilde{t}_6^0, \gamma_2(\tilde{s}_{2,6})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 6 :** Pop the element $(\tilde{t}_7^0, \gamma_2(\tilde{s}_{2,7}))$ of $Q$ and denote by $\gamma_7$ the isometry that glues $\tilde{t}_7^0$ with $\gamma_2(\tilde{t}_2^0)$ along $\gamma_2(\tilde{s}_{2,7})$. The circumdisk of $\gamma_7(\tilde{t}_7^0)$ does not contains $\tilde{p}^0$, then add $\gamma_2(\tilde{s}_{2,7})$ in $L_p$.

726

727

728

**Data :** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0, \tilde{t}_2^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5}), \gamma_3(\tilde{s}_{3,4}), \gamma_2(\tilde{s}_{2,7})]$ and

729

730

$Q = [(	ilde{t}_6^0, \gamma_2(\tilde{s}_{2,6})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 7 :** Pop the element $(\tilde{t}_6^0, \gamma_2(\tilde{s}_{2,6}))$ of $Q$ and denote by $\gamma_6$ the isometry that glues $\tilde{t}_6^0$ with $\gamma_2(\tilde{t}_2^0)$ along $\gamma_2(\tilde{s}_{2,6})$. The circumdisk of $\gamma_6(\tilde{t}_6^0)$ contains $\tilde{p}^0$, then add $\tilde{t}_6^0$ in $C_p$ and push $(\tilde{t}_8^0, \gamma_6(\tilde{s}_{6,8}))$ and $(\tilde{t}_9^0, \gamma_6(\tilde{s}_{6,9}))$ in $Q$.

731

732

733

**Data :** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0, \tilde{t}_2^0, \tilde{t}_6^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5}), \gamma_3(\tilde{s}_{3,4}), \gamma_2(\tilde{s}_{2,7})]$ and

734

735

$Q = [(	ilde{t}_9^0, \gamma_6(\tilde{s}_{6,9})), (\tilde{t}_8^0, \gamma_6(\tilde{s}_{6,8})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 8 :** Pop the element $(\tilde{t}_9^0, \gamma_6(\tilde{s}_{6,9}))$ of $Q$ and denote by $\gamma_9$ the isometry that glues $\tilde{t}_9^0$ with $\gamma_6(\tilde{t}_6^0)$ along $\gamma_6(\tilde{s}_{6,9})$. The circumdisk of $\gamma_9(\tilde{t}_9^0)$ does not contains $\tilde{p}^0$, then add $\gamma_6(\tilde{s}_{6,9})$ in $L_p$.

736

737

738

**Data :** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0, \tilde{t}_2^0, \tilde{t}_6^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5}), \gamma_3(\tilde{s}_{3,4}), \gamma_2(\tilde{s}_{2,7}), \gamma_6(\tilde{s}_{6,9})]$ and

739

740

$Q = [(	ilde{t}_8^0, \gamma_6(\tilde{s}_{6,8})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 9 :** Pop the element $(\tilde{t}_8^0, \gamma_6(\tilde{s}_{6,8}))$ of $Q$ and denote by $\gamma_8$ the isometry that glues $\tilde{t}_8^0$ with $\gamma_6(\tilde{t}_6^0)$ along $\gamma_6(\tilde{s}_{6,8})$. The circumdisk of $\gamma_8(\tilde{t}_8^0)$ does not contains $\tilde{p}^0$, then add $\gamma_6(\tilde{s}_{6,8})$ in $L_p$.

741

742

743

**Data :** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0, \tilde{t}_2^0, \tilde{t}_6^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5}), \gamma_3(\tilde{s}_{3,4}), \gamma_2(\tilde{s}_{2,7}), \gamma_6(\tilde{s}_{6,9}), \gamma_6(\tilde{s}_{6,8})]$ and

744

745

$Q = [(	ilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 10 :** Pop the element $(\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))$ of $Q$ and denote by $\gamma_1$ the isometry that glues $\tilde{t}_1^0$ with $\gamma_0(\tilde{t}_0^0)$ along $\gamma_0(\tilde{s}_{0,1})$. The circumdisk of $\gamma_1(\tilde{t}_1^0)$ does not contains $\tilde{p}^0$, then add $\gamma_0(\tilde{s}_{0,1})$ in $L_p$.

746

747

748

**Data :** $C_p = [\tilde{t}_0^0, \tilde{t}_3^0, \tilde{t}_2^0, \tilde{t}_6^0]$, $L_p = [\gamma_3(\tilde{s}_{3,5}), \gamma_3(\tilde{s}_{3,4}), \gamma_2(\tilde{s}_{2,7}), \gamma_6(\tilde{s}_{6,9}), \gamma_6(\tilde{s}_{6,8}), \gamma_0(\tilde{s}_{0,1})]$

749

750

and $Q = []$.

**Iteration 11 :** Remove the triangles in $C_p$ from the data structure.

751

**Iteration 12 :** Add the triangles with edges in $L_p$ and vertex $\tilde{p}^0$ to the data structure.

752

## C.2 Insertion in the thin part

754

The following is a description of the insertion in the $4\epsilon_0$-thin part, it is illustrated in the Figure 16. As above, we use the notation $\tilde{s}_{i,j}$ for the common edge to the triangles $\tilde{t}_i$ and $\tilde{t}_j$.

755

756

As opposed to the $4\epsilon_0$-thick part, there may be 1-cycle in the triangulation. Then, there may be a triangle $\tilde{t}_i$ whose two adjacent triangles are copies of the same triangle $\tilde{t}_j$. If it the case, we denote by $\tilde{s}_{i,j}$ and $\tilde{s}_{j,i}$ the edges of $\tilde{t}_i$ in common with the two copies of $\tilde{t}_j$.

757

758

759
**Iteration 0**: $C_p$ is the list of triangles in the restricted conflict zone of $\tilde{p}^0$, and $L_p$ the list of its boundary edges. Let $Q$ be the queue that will contain the pairs (triangle, edge) to be processed during the DFS. In the Figure 15, elements of $C_p$, $L_p$ and $Q$ are respectively displayed in orange, red and green.

**Data**: $C_p = []$, $L_p = []$ and $Q = []$.

**Iteration 1**: Find a triangle $\tilde{t}_0^0$ and an isometry $\gamma_0$ such that $\gamma_0(\tilde{t}_0^0)$ contains $\tilde{p}^0$. Add $\tilde{t}_0^0$ to $C_p$ and push $(\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1})), (\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2}))$ and $(\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2}))$ to $Q$.

**Data**: $C_p = [\tilde{t}_0^0]$, $L_p = []$ and $Q = [(\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 2**: Pop the element $(\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2}))$ of $Q$ and denote by $\gamma_3$ the isometry that glues $\tilde{t}_2^0$ with $\gamma_0(\tilde{t}_0^0)$ along $\gamma_0(\tilde{s}_{0,2})$. The circumdisk of $\gamma_3(\tilde{t}_2^0)$ contains $\tilde{p}^0$ and has its three vertices between $T^+$ and $T^-$, then add $\tilde{t}_2^0$ in $C_p$ and push $(\tilde{t}_3^0, \gamma_3(\tilde{s}_{2,3}))$ and $(\tilde{t}_0^0, \gamma_3(\tilde{s}_{2,0}))$ in $Q$.

**Data**: $C_p = [\tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = []$ and

$Q = [(\tilde{t}_0^0, \gamma_3(\tilde{s}_{2,0})), (\tilde{t}_3^0, \gamma_3(\tilde{s}_{2,3})), (\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 3**: Pop the element $(\tilde{t}_0^0, \gamma_3(\tilde{s}_{2,0}))$ of $Q$ and denote by $\gamma_1$ the isometry that glues $\tilde{t}_0^0$ with $\gamma_3(\tilde{t}_2^0)$ along $\gamma_3(\tilde{s}_{2,0})$. The circumdisk of $\gamma_1(\tilde{t}_0^0)$ does not contain $\tilde{p}^0$ and the edge $\gamma_3(\tilde{s}_{2,0})$ has a vertex between $T^+$ and $T^-$, then add $\gamma_3(\tilde{s}_{2,0})$ in $L_p$.

**Data**: $C_p = [\tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_3(\tilde{s}_{2,0})]$ and $Q = [(\tilde{t}_3^0, \gamma_3(\tilde{s}_{2,3})), (\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 4**: Pop the element $(\tilde{t}_3^0, \gamma_3(\tilde{s}_{2,3}))$ of $Q$ and denote by $\gamma_6$ the isometry that glues $\tilde{t}_3^0$ with $\gamma_3(\tilde{t}_2^0)$ along $\gamma_3(\tilde{s}_{2,3})$. The circumdisk of $\gamma_6(\tilde{t}_3^0)$ does not contain $\tilde{p}^0$ and the edge $\gamma_3(\tilde{s}_{2,3})$ has a vertex between $T^+$ and $T^-$, then add $\gamma_3(\tilde{s}_{2,3})$ in $L_p$.

**Data**: $C_p = [\tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_3(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,0})]$ and $Q = [(\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 5**: Pop the element $(\tilde{t}_2^0, \gamma_0(\tilde{s}_{0,2}))$ of $Q$ and denote by $\gamma_4$ the isometry that glues $\tilde{t}_2^0$ with $\gamma_0(\tilde{t}_0^0)$ along $\gamma_0(\tilde{s}_{0,2})$. The circumdisk of $\gamma_4(\tilde{t}_2^0)$ contains $\tilde{p}^0$ and this triangle has two vertices between $T^+$ and $T^-$, then add $\tilde{t}_2^0$ in $C_p$ and push $(\tilde{t}_0^0, \gamma_4(\tilde{s}_{2,0}))$ and $(\tilde{t}_3^0, \gamma_4(\tilde{s}_{2,3}))$ in $Q$.

**Data**: $C_p = [\tilde{t}_2^0, \tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_3(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,0})]$ and

$Q = [(\tilde{t}_3^0, \gamma_4(\tilde{s}_{2,3})), (\tilde{t}_0^0, \gamma_4(\tilde{s}_{2,0})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 6**: Pop the element $(\tilde{t}_3^0, \gamma_4(\tilde{s}_{2,3}))$ of $Q$ and denote by $\gamma_7$ the isometry that glues $\tilde{t}_3^0$ with $\gamma_4(\tilde{t}_2^0)$ along $\gamma_4(\tilde{s}_{2,3})$. The circumdisk of $\gamma_7(\tilde{t}_3^0)$ does not contain $\tilde{p}^0$ and the edge $\gamma_4(\tilde{s}_{2,3})$ has a vertex between $T^+$ and $T^-$, then add $\gamma_4(\tilde{s}_{2,3})$ in $L_p$.

**Data**: $C_p = [\tilde{t}_2^0, \tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_4(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,0})]$ and

$Q = [(\tilde{t}_0^0, \gamma_4(\tilde{s}_{2,0})), (\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 7**: Pop the element $(\tilde{t}_0^0, \gamma_4(\tilde{s}_{2,0}))$ of $Q$ and denote by $\gamma_2$ the isometry that glues $\tilde{t}_0^0$ with $\gamma_4(\tilde{t}_2^0)$ along $\gamma_4(\tilde{s}_{2,0})$. The circumdisk of $\gamma_2(\tilde{t}_0^0)$ does not contain $\tilde{p}^0$, then add $\gamma_4(\tilde{s}_{2,0})$ in $L_p$.

**Data**: $C_p = [\tilde{t}_2^0, \tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_4(\tilde{s}_{2,0}), \gamma_4(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,0})]$ and $Q = [(\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))]$.

**Iteration 8**: Pop the element $(\tilde{t}_1^0, \gamma_0(\tilde{s}_{0,1}))$ of $Q$ and denote by $\gamma_5$ the isometry that glues $\tilde{t}_1^0$ with $\gamma_0(\tilde{t}_0^0)$ along $\gamma_0(\tilde{s}_{0,1})$. The circumdisk of $\gamma_5(\tilde{t}_1^0)$ contains $\tilde{p}^0$ and has its three vertices between $T^+$ and $T^-$, then add $\tilde{t}_1^0$ in $C_p$ and push $(\tilde{t}_4^0, \gamma_5(\tilde{s}_{1,4}))$ and $(\tilde{t}_4^0, \gamma_5(\tilde{s}_{1,4}))$ in $Q$.

**Data**: $C_p = [\tilde{t}_1^0, \tilde{t}_2^0, \tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_4(\tilde{s}_{2,0}), \gamma_4(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,0})]$ and

$Q = [(\tilde{t}_4^0, \gamma_5(\tilde{s}_{1,4})), (\tilde{t}_4^0, \gamma_5(\tilde{s}_{1,4}))]$.
**Iteration 9 :** Pop the element $(\tilde{t}_4^0, \gamma_5(\tilde{s}_{1,4}))$ of $\mathcal{Q}$ and denote by $\gamma_8$ the isometry that glues $\tilde{t}_4^0$ with $\gamma_5(\tilde{t}_1^0)$ along $\gamma_5(\tilde{s}_{1,4})$. The circumdisk of $\gamma_8(\tilde{t}_4^0)$ does not contain $\tilde{p}^0$ and the edge $\gamma_5(\tilde{s}_{1,4})$ has a vertex between $T^+$ and $T^-$, then add $\gamma_5(\tilde{s}_{1,4})$ in $L_p$.

803

804

805

**Data :** $C_p = [\tilde{t}_1^0, \tilde{t}_2^0, \tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_5(\tilde{s}_{1,4}), \gamma_4(\tilde{s}_{2,0}), \gamma_4(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,0})]$ and $Q = [(\tilde{t}_4^0, \gamma_5(\tilde{s}_{1,4}))]$.

806

807

**Iteration 10 :** Pop the element $(\tilde{t}_4^0, \gamma_5(\tilde{s}_{1,4}))$ of $\mathcal{Q}$ and denote by $\gamma_9$ the isometry that glues $\tilde{t}_4^0$ with $\gamma_5(\tilde{t}_1^0)$ along $\gamma_5(\tilde{s}_{1,4})$. The circumdisk of $\gamma_9(\tilde{t}_4^0)$ does not contain $\tilde{p}^0$ and the edge $\gamma_5(\tilde{s}_{1,4})$ has a vertex between $T^+$ and $T^-$, then add $\gamma_5(\tilde{s}_{1,4})$ in $L_p$.

808

809

810

**Data :** $C_p = [\tilde{t}_1^0, \tilde{t}_2^0, \tilde{t}_2^0, \tilde{t}_0^0]$, $L_p = [\gamma_5(\tilde{s}_{1,4}), \gamma_5(\tilde{s}_{1,4}), \gamma_4(\tilde{s}_{2,0}), \gamma_4(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,3}), \gamma_3(\tilde{s}_{2,0})]$ and $Q = []$.

811

812

**Iteration 11 :** Remove the triangles in $C_p$ from the data structure.

813

**Iteration 12 :** Add the triangles with edges in $L_p$ and vertex $\tilde{p}^0$ to the data structure, handling possible conflicts involving $T(\tilde{p}^0)$ and $T^{-1}(\tilde{p}^0)$.

814

815
<figure><img src="image_19.png" /><figcaption>Figure 15 Insertion in the $4\epsilon_0$-thick part.</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>Figure 16 Iteration in the $4\epsilon_0$-thin part.</figcaption></figure>