On the hyperbolicity of Delaunay triangulations

1.   Introduction

The concept of Gromov hyperbolicity grasps the essence of negatively curved spaces like the classical hyperbolic space, Riemannian manifolds of negative sectional curvature, and of discrete spaces like the Cayley graphs of many finitely generated groups and trees ^[1,2,3]. Initially, Gromov spaces were applied to the study of automatic groups in computer science ^[4,5].

The hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it ^[6]. This conceptualization has multiple practical applications such as networks and algorithms ^[7], random graphs ^[8,9,10], or real networks ^[11,12]. For example, it has been shown in ^[13,14] that the internet topology and the topology of many complex networks embed with better accuracy into a hyperbolic space than into an Euclidean space of comparable dimension. Another important application of Gromov hyperbolic spaces is the study of the spread of viruses through on the internet ^[15,16] and secure transmission of information on the network ^[17].

By a tessellation graph we mean the $1$-skeleton (i.e., the set of $1$-cells) of a CW $2$-complex contained in the Euclidean plane $\mathbb{R}^2$ such that every point in $\mathbb{R}^2$ is contained in some face ($2$-cell) of the complex. The edges of a tessellation graph are straight segments and have its Euclidean length. Note that this class of graphs contains as particular cases many planar graphs.

Delaunay triangulations are an important kind of Euclidean graphs. It is important to note that Delaunay triangulations are the dual of Voronoi graphs (the $1$-skeleton of the Voronoi diagram) in the Euclidean plane ^[18,19,20]. Euclidean graphs have been used as a modeling tool; for example, in circuit layout ^[21]. They also arise indirectly in the solution to geometric problems such as motion planning ^[22]. Delaunay triangulations are good candidates for approximating graphs, since if $S$ has $N$ points, then the triangulation contains only a linear number of edges and can be computed from $S$ in $O(N \log N)$ time ^[23].

Delaunay triangulations tend to have desirable geometric properties, such as maximizing the minimum angle of the triangles, which leads to more regular and well-conditioned triangles. This quality is crucial in applications where accurate and robust geometric computations are required. Delaunay triangulations are widely used for generating triangular meshes. They provide a way to divide a complex domain into a set of non-overlapping triangles, which is useful in finite element analysis, computational physics, and computer-aided design (CAD) applications. Also, Delaunay triangulations can be employed for interpolating values or reconstructing surfaces from scattered data points. They provide a natural and optimal way to connect data points, allowing for the creation of smooth surfaces or accurate approximations based on the input data. Besides, Delaunay triangulations serve as a fundamental building block in many computational geometry algorithms. They are used as a data structure to efficiently solve problems such as nearest neighbor search, point location, convex hull computation, and geometric intersection problems.

Since the Euclidean plane is non-hyperbolic, it is natural to conjecture that "every tessellation of the Euclidean plane with convex tiles induces a non-hyperbolic graph". In ^[24] it was shown that the conjecture is false. However, we prove in this work that it is true for every Delaunay triangulation which is a triangulation of the Euclidean plane, see Corollary 3.14. Furthermore, Theorem 3.13 characterizes the Delaunay triangulations contained in the Euclidean plane that are hyperbolic in terms of only two geometric parameters associated with the triangulation (they may or may not be a tessellation of the plane).

2.   Background on hyperbolic spaces

If $X$ is a metric space, the curve $\gamma: [a, b] \rightarrow X$ is a geodesic if $L(\gamma|_{[t, s]}) = d(\gamma(t), \gamma(s)) = s-t$ for every $s, t\in [a, b]$ with $t < s$. The metric space $X$ is said geodesic if for every couple of points in $X$ there exists a geodesic joining them; we denote by $[xy]$ any geodesic joining $x$ and $y$. Hence, any geodesic metric space is connected. If the metric space $X$ is a graph, then the edge joining the vertices $u$ and $v$ will be denoted by $uv$.

In order to consider a graph $G$ as a geodesic metric space, we must identify any edge $uv\in E(G)$ with a real interval with length $L(uv)$; thus, any point in the interior of any edge is a point of $G$. Any connected graph $G$ is naturally equipped with a distance defined on its points, induced by taking shortest paths in $G$. Therefore, we consider $G$ as a geodesic metric graph.

If $X$ is a geodesic metric space and $x_1, x_2, x_3$ are points in $X$, then the union of three geodesics $[x_1 x_2]$, $[x_2 x_3]$ and $[x_3 x_1]$ is a geodesic triangle, and we denote it by $T = \{x_1, x_2, x_3\}$ or $T = \{[x_1x_2], [x_2x_3], [x_3x_1]\}$. The geodesic triangle $T$ is $\delta$-thin if any side of $T$ is contained in the $\delta$-neighborhood of the union of the two other sides. We denote by $\delta(T)$ the sharp thin constant of $T$, i.e., $\delta(T): = \inf\{ \delta\ge 0: \, T \, \text{ is }\delta -\text{thin}\, \}.$ We say that the space $X$ is $\delta$-hyperbolic $($or satisfies the Rips condition with constant $\delta)$ if every geodesic triangle in $X$ is $\delta$-thin. We will denote by $\delta(X)$ the sharp hyperbolicity constant of $X$, i.e., $\delta(X): = \sup\{ \delta(T): \, T \, \text{ is a geodesic triangle in}\, X\, \}.$ We say that $X$ is hyperbolic if $X$ is $\delta$-hyperbolic for some $\delta \ge 0$, i.e., if $\delta(X) < \infty$.

Given any graph $G$ and $x, y \in G$, we define the distance $d_G(x, y)$ (or simply $d(x, y)$) as the minimum of the lengths of the curves in $G$ joining $x$ and $y$.

Throughout the paper, we deal with graphs that are connected and such that each ball of finite radius contains just a finite number of edges; we also allow edges of arbitrary length. Then, the graphs are geodesic metric spaces.

There are several equivalent definitions of hyperbolicity ^[2,25,26,27]. It is natural to chose this definition by its deep geometric meaning ^[2]. See ^{[27,28,29,30,31]} for more details about hyperbolic graphs.

Given two geodesic metric spaces $(X, d_X)$ and $(Y, d_Y)$, a map $f: X\longrightarrow Y$ is said to be an $(\alpha, \beta)$-quasi-isometric embedding, with constants $\alpha\geq 1, \ \beta\geq 0,$ if the inequalities

hold for every $x, y\in X$. We say that $f$ is $\varepsilon$-full if for each $y \in Y$ there exists $x\in X$ with $d_Y(f(x), y)\leq \varepsilon$. The map $f$ is a quasi-isometry if there exist constants $\alpha\geq 1, \ \beta, \varepsilon \geq 0$ such that $f$ is an $\varepsilon$-full $(\alpha, \beta)$-quasi-isometric embedding.

A fundamental property of hyperbolic spaces is the following:

Theorem 2.1 (Invariance of hyperbolicity). Let $f: X \longrightarrow Y$ be an $(\alpha, \beta)$-quasi-isometric embedding between the geodesic metric spaces $X$ and $Y$. If $Y$ is hyperbolic, then $X$ is hyperbolic.

Furthermore, if $f$ is $\varepsilon$-full for some $\varepsilon\ge0$ (a quasi-isometry), then $X$ is hyperbolic if and only if $Y$ is hyperbolic.

Given a geodesic triangle $T = \{x, y, z\}$ in a geodesic metric space $X$, let $T_E$ be an Euclidean triangle with sides of the same length than $T$. Since there is no possible confusion, denote the corresponding points in $T$ and $T_E$ by the same letters. The maximum inscribed circle in $T_E$ meets the side $[xy]$ (respectively $[yz]$, $[zx]$) in a point $z'$ (respectively $x'$, $y'$) such that $d(x, z') = d(x, y')$, $d(y, x') = d(y, z')$ and $d(z, x') = d(z, y')$. We call the points $x', y', z',$ the internal points of $\{x, y, z\}$. By [2, p. 28 and 38], there is a unique map $f$ of the triangle $\{x, y, z\}$ onto a tripod (a star graph with one vertex $w$ of degree $3$, and three vertices $x_0, y_0, z_0$ of degree one, such that its restriction on each side of the triangle is an isometry, $d(x_0, w) = d(x, z') = d(x, y')$, $d(y_0, w) = d(y, x') = d(y, z')$ and $d(z_0, w) = d(z, x') = d(z, y')$). Note that $d(x, z') = d(x, y') = 1/2 (d(x, y)+d(x, z)-d(y, z))$, this quantity is usually denoted by $(y|z)_x$, the Gromov product of $y$ and $z$ with base point $x$. The triangle $\{x, y, z\}$ is $\delta$-fine if $f(p) = f(q)$ implies that $d(p, q)\le \delta$. The space $X$ is $\delta$-fine if every geodesic triangle in $X$ is $\delta$-fine.

The following is an important result in the theory of hyperbolicity (see, e.g, [2, Proposition 2.21, p.41]):

Theorem 2.2. Let us consider a geodesic metric space $X$.

(1) If $X$ is $\delta$-hyperbolic, then it is $4 \delta$-fine.

(2) If $X$ is $\delta$-fine, then it is $\delta$-hyperbolic.

Given a geodesic metric space $X$ and a geodesic triangle $T$ in $X$, let us define the fine constant of $T$ as $\delta_{fine}(T): = \inf \big\{ \delta: \, T \text{ is} \delta -\text{fine} \big\},$ and the fine constant of $X$ as

3.   Hyperbolicity of Delaunay triangulations in $\mathbb R^2$

In this section, we deal with triangulations contained in the Euclidean plane.

A Voronoi diagram $V(S)$ of a set $S$ of points in the plane is a partition of the plane into regions $\{V_s\}_{s \in S}$, called Voronoi cells, each corresponding to a point $s$ in $S$, such that for each $s \in S$, every point within its corresponding region $V_s$ is closer to $s$ than to any other point of $S$.

We say that $S \subset \mathbb{R}^2$ is a set in general position if it is not contained in a straight line, it contains at least three points and if no four points of $S$ belongs to some circle. $S$ is locally finite if any Euclidean ball in $\mathbb{R}^2$ contains just a finite amount of points in $S$.

Although Voronoi diagrams can be defined for any set $S$ in any metric space, the more usual framework is $\mathbb{R}^2$ with a finite set $S$ in general position. We consider along this work locally finite sets $S$ in general position in $\mathbb{R}^2$.

In this paper, we study the dual graph $T(S)$ of the Voronoi diagram $V(S)$: Consider the straight-line embedding of $T(S)$, where the vertex corresponding to the Voronoi cell $V_s$ is the point $s$, and the edge connecting the vertices $s_1$ and $s_2$ is the Euclidean segment $s_1s_2$ (with its Euclidean length) when $V_{s_1}$ and $V_{s_2}$ share a side. We call this embedding the Delaunay graph $T(S)$ of $S$. Note that this definition makes sense since $S$ is a locally finite set, although $T(S)$ is an infinite graph when $S$ is an infinite set.

Recall that the convex hull $CH(P)$ of $P \subset \mathbb{R}^d$ is the intersection of all convex sets containing $P$. Thus,

since this union is a convex set, and every convex set containing $P$ must contain every point $\sum_{j = 1}^{n} \lambda_j p_j$ with $p_j \in P$, $\lambda_j \ge 0$ and $\sum_{j = 1}^{n} \lambda_j = 1$.

In [23, pp. 206–207], the following results are found for finite sets. The arguments in their proofs allow to prove the same conclusions for locally finite sets.

Proposition 3.1. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$.

(1) Every vertex of the Voronoi diagram $V(S)$ is the common intersection of exactly three edges of the diagram.

(2) Every vertex $v$ in the Voronoi diagram $V(S)$ is the center of a circumference $C(v)$ defined by three points of $S$, and the Voronoi graph $($the $1$-skeleton of $V (S))$ is regular of degree three.

(3) For each vertex $v$ in the Voronoi diagram, the circumference $C(v)$ contains no other point of $S$.

(4) Every nearest neighbor of $s \in S$ defines an edge of the Voronoi polygon $\partial V_s$.

(5) The polygon $\partial V_s$ is unbounded if and only if $s$ is a point on the boundary of the convex hull $CH(S)$ of the set $S$.

The following theorem of Delaunay ^[32] shows the importance of the Delaunay graph.

Theorem 3.2. Let $S$ be a finite set in general position in $\mathbb{R}^2$. Then the Delaunay graph $T(S)$ is a triangulation of the convex hull $CH(S)$ of $S$.

The Delaunay graph $T(S)$, which can be written also as

is a triangulation of $CH(S)$, where $T(v)$ denotes the triangle in $T(S)$ associated to the Voronoi vertex $v$, see [23, pp. 209–210]. Note that item $(2)$ in Proposition 3.1 gives that the Voronoi graph is regular of degree three.

The following fact is direct when $S$ is a finite set, as is the case in Theorem 3.2.

Proposition 3.3. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$. Then, for each $x, q \in CH(S)$ there exists just a finite amount of Voronoi vertices $v_1, \dots, v_k,$ such that $T(v_j)$ intersects the Euclidean segment $xq$.

Proof. Since $x, q \in CH(S)$, there exist two convex polygons $P_x, P_q$ with points in $S$ and such that $x\in P_x, q\in P_q$. The third item in Proposition 3.1 gives that for each vertex $v$ in the Voronoi diagram, the circumference $C(v)$ contains no other point of $S$. The result follows from these facts since the Euclidean segment $xq$ is a compact set and $S$ is a locally finite set. □

Proposition 3.3 is a useful technical result, since an Euclidean ball can intersect infinitely many triangles of a Delaunay graph, as the following example shows:

Example 3.4. If

then any ball centered at $(0, 1)$ intersects infinitely many triangles in $T(S)$.

The extended results for locally finite set of points in general position in Proposition 3.1, Proposition 3.3 and the argument in the proof of Theorem 3.2 in [23, pp. 209-210] give the following result.

Proposition 3.5. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$. Then the Delaunay graph $T(S)$ is a triangulation of the convex hull $CH(S)$ of $S$.

By Theorem 3.2 and Proposition 3.5, from now on we call Delaunay triangulation given by $S$ to the Delaunay graph $T(S)$.

Note that if $T(S)$ is a triangulation of $\mathbb{R}^2$, then Proposition 3.5 gives that $CH(S) = \mathbb{R}^2$ and so, $S$ is not a finite set.

Recall that if $V_0$ is a subset of the vertices of a graph $G$, the subgraph $G_0$ induced by $V_0$ is the subgraph of $G$ with vertices $V_0$ and edges $\{ uv \in E(G):\, u, v \in V_0\}$.

Lemma 3.6. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$ and $S_1 \subseteq S$. Then the subgraph of $T(S)$ induced by $S_1$ is also a subgraph of $T(S_1)$.

Proof. Assume that $p, q \in S_1$ and $pq \in E(T(S))$. Thus, the Voronoi cells of $p$ and $q$ in $V(S)$ share a Voronoi edge $e$, and

for every $x \in e$ and $s\in S$. Therefore,

for every $x \in e$ and $s\in S_1$, and so, $e$ is contained in the Voronoi cells of $p$ and $q$ in $V(S_1)$. This implies that $pq \in E(T(S_1))$. Hence, the subgraph of $T(S)$ induced by $S_1$ is also a subgraph of $T(S_1)$. □

In ^[33] appears the following result.

Lemma 3.7. Given a set $S$ of $n$ points in the plane, for any two points $p, q \in S$,

independent of $S$ and $n$.

Next, we prove a similar result for locally finite sets.

Theorem 3.8. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$. Then, for any two points $p, q \in S$,

Proof. Fix $p, q \in S,$ and let $B_1$ be the Euclidean closed ball with center $p$ and radius $d_{T(S)}(p, q)$. Note that any geodesic in $T(S)$ joining $p$ and $q$ is contained in $B_1$, and so, $q \in B_1$.

Since $S$ is a locally finite set, $S_1 = S \cap B_1$ is a finite set. Let us define $r = \max \{ d_{T(S)}(p, v) : \, v \in S_1 \}$, $B_2$ the Euclidean closed ball with center $p$ and radius $r$, and $S_2 = S \cap B_2$.

Let $\mathfrak{T}$ be the set of triangles of $T(S)$ containing at least an edge in $B_2$. Since $T(S)$ is a triangulation of $CH(S)$ by Proposition 3.5, each edge in $T(S)$ belongs at most to two triangles in $T(S)$, and so, $\mathfrak{T}$ is a finite set of triangles. Let $S_3$ be the union of $S_2$ and the set of vertices of the triangles in $\mathfrak{T}$.

Lemma 3.6 gives that the subgraph $\Gamma$ of $T(S)$ induced by $S_3$ (which includes any geodesic in $T(S)$ joining $p$ and any point in $S_1$) is also a subgraph of $T(S_3)$. Hence, $d_{T(S_3)}(p, q) = d_{T(S)}(p, q)$.

Seeking a contradiction assumes that there exists an edge $uv \in E(T(S_3)) \setminus E(T(S))$ with $u, v \in S_1$. Since $\Gamma \cap B_2$ includes any geodesic in $T(S)$ joining $p$ and any point in $S_1$, there exists a curve $g$ in $\Gamma \cap B_2$ joining $u$ and $v$. Since $\Gamma$ is a subgraph of the planar graph $T(S_3)$, we have $uv \cap g = \{u, v\}$.

Let $F$ be the compact set in $\mathbb{R}^2$ bounded by $g$ and $uv$. Fix an edge $e$ in $g$. Since $F \subseteq CH(S)$, there exists a triangle $T_1$ in the Delaunay triangulation $T(S)$ such that $e$ is a side of $T_1$ and the interior of $T_1$ intersects the interior of $F$. Let $s_1$ be the vertex of $T_1$ in the interior of $F$ (recall that $T(S_3)$ is a planar graph). Let $g_1$ be the curve obtained from $g$ by replacing $e$ for the two other sides of the triangle $T_1$, and $F_1$ the compact set in $\mathbb{R}^2$ bounded by $g_1$ and $uv$.

Fix an edge $e_1$ in $g_1$. Since $F_1 \subseteq CH(S)$, there exists a triangle $T_2$ in the Delaunay triangulation $T(S)$ such that $e_1$ is a side of $T_2$ and the interior of $T_2$ intersects the interior of $F_1$. Let $s_2$ be the vertex of $T_2$ in the interior of $F_1$. Let $g_2$ be the curve obtained from $g_1$ by replacing $e_1$ by the two other sides of the triangle $T_2$, and $F_2$ the compact set in $\mathbb{R}^2$ bounded by $g_2$ and $uv$.

By iterating this argument we obtain an infinite sequence $\{s_n\} \subset S$ contained in the compact set $F$. This is a contradiction since $S$ is a locally finite set, and so, $E(T(S_3)) \cap B_1 = E(T(S)) \cap B_1$.

Seeking for a contradiction assume that $d_{T(S_3)}(p, q) < d_{T(S)}(p, q)$. Hence, there exists a geodesic $\eta$ in $T(S_3)$ joining $p$ and $q$, with $L(\eta) < d_{T(S)}(p, q)$. Note that $\eta$ is contained in $B_1\cap E(T(S_3))$ and it is not contained in $E(T(S))$. Therefore, $\eta$ contains an edge in

a contradiction. Thus, $d_{T(S_3)}(p, q) = d_{T(S)}(p, q)$.

Since $S$ is a locally finite set, $S_3$ is a finite set. Thus, the inequality for finite sets in Lemma 3.7 gives

This finishes the proof, since $p$ and $q$ are arbitrary points in $S$. □

Corollary 3.9. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$. If $d_2$ denotes the Euclidean distance, then

for any two points $p, q \in S$. Consequently, the identity map is a quasi-isometry between the metric spaces $(S, d_{T(S)})$ and $(S, d_2)$.

In Proposition 3.12 below, we need the following definition. Given a normed vector space $(X, \| \; \|)$, we denote by $B(x, r)$ the ball of radius $r$ centered at $x$ with respect to $\| \; \|$. If $K$ is a convex set in a normed vector space $X$, we define

Remark 3.10. Note that if $X = \mathbb{R}^2$, then

Example 3.11. (1) If $K_0$ is any convex set in $\mathbb{R}^{n-1} \subset X = \mathbb{R}^n$, then

(2) If

then $R(K) = 1 < \infty$.

The following technical result is interesting by itself.

Proposition 3.12. If $K$ is a convex set in a normed finite-dimensional vector space $X$, then $\delta_{fine}(K) \le 2R(K)$ and $R(K) \le 4 \delta(K)/3$, and so, $K$ is hyperbolic if and only if $R(K) < \infty$.

Proof. Let $T$ be a geodesic triangle in $K$. Since $K$ is a convex set in $X$, $T$ is also a geodesic triangle in $X$. Let $r$ be the radius of the maximum inscribed circle in $T$, and $x$ its center. Let $L$ be the two-dimensional affine subspace of $X$ containing $T$. Thus, this inscribed circle to $T$, i.e., $B(x, r)\cap L$, is contained in $K$ and

Hence, $\delta_{fine}(K) \le 2R(K)$.

If $B(x, r)\cap L \subseteq K$ for some two-dimensional affine subspace $L\subseteq X$ and $x\in K \cap L$, then let $T$ be an equilateral triangle such that $\partial B(x, r)$ is its circumcircle; thus, $T$ is contained in $K \cap L$. The length of any side of $T$ is $\sqrt{3}\, r$ and $\delta(T)$ is the distance of the midpoint of any side of $T$ to the union of the other sides, i.e., $\delta(T) = 3r/4$. Therefore, $\delta(K) \ge \delta(T) = 3r/4$ and so, $\delta(K) \ge 3R(K)/4$. □

Although most of the graphs embedded in $\mathbb{R}^2$ are not hyperbolic, there are many hyperbolic graphs, as the Cayley graphs of the groups $\mathbb{Z}$ and $\mathbb{Z} \times \mathbb{Z}_m$ $(m \in \mathbb{Z}^+)$ embedded in $\mathbb{R}^2$. Also, one of the authors shows in ^[24] a hyperbolic tessellation of the Euclidean plane with convex tiles. The following result characterizes the Delaunay triangulations contained in the Euclidean plane that are hyperbolic.

For each locally finite set $S$ in general position in $\mathbb{R}^2$, let us define

Theorem 3.13. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$. Then, $T(S)$ is hyperbolic if and only if $R(CH(S)) < \infty$ and $\ell(S) < \infty$.

Proof. Assume first that $R(CH(S)) < \infty$ and $\ell(S) < \infty$. Since $R(CH(S)) < \infty$, Proposition 3.12 gives that $CH(S)$, with its induced Euclidean metric, is hyperbolic.

Let us consider the inclusion $i: T(S) \rightarrow CH(S) \subseteq \mathbb{R}^2$. It is clear that $|x-y| \le d_{T(S)}(x, y)$ for every $x, y \in T(S)$. Fix $x, y \in T(S)$. Let $p$ and $q$ be two vertices in $S$ with $d_{T(S)}(x, p) \le \ell(S)/2$ and $d_{T(S)}(y, q) \le \ell(S)/2$. If we define

then Theorem 3.8 gives

Hence,

for every $x, y \in T(S)$, and the inclusion is a $\ell(S)$-full $(c_0, (c_0+1) \ell(S)/c_0)$-quasi-isometry. Since $CH(S)$ is hyperbolic, Theorem 2.1 gives that $T(S)$ is hyperbolic.

Assume now that $T(S)$ is hyperbolic. Given any edge $e$ in $T(S)$, let us choose a triangle $T_0 = \{e, e_1, e_2\}$ in the Delaunay triangulation $T(S)$. Note that $T_0$ is a geodesic triangle in $T(S)$. If $x$ is the midpoint of $e$, then

and so, $\ell(S) \le 2 \delta(T(S)) < \infty$. We have proved that the inclusion $i: T(S) \rightarrow CH(S)$ is a $\ell(S)$-full $(c_0, (c_0+1) \ell(S)/c_0)$-quasi-isometry between $T(S)$ and $CH(S)$. Since $T(S)$ is hyperbolic, Theorem 2.1 gives that $CH(S)$ is hyperbolic. Finally, Proposition 3.12 gives $R(CH(S)) < \infty$. □

The following result shows that the Delaunay triangulations of the Euclidean plane are not hyperbolic.

Corollary 3.14. Let $S$ be a locally finite set in general position in $\mathbb{R}^2$ such that $T(S)$ is a triangulation of the Euclidean plane. Then $T(S)$ is not hyperbolic.

Proof. Since $T(S)$ is a triangulation of $\mathbb{R}^2$, we have $CH(S) = \mathbb{R}^2$ and, since $R(CH(S)) = R(\mathbb{R}^2) = \infty$, Theorem 3.13 gives that $T(S)$ is not hyperbolic. □

4.   Conclusions

In conclusion, this work investigates the concept of hyperbolicity in geodesic metric spaces, with a specific focus on Delaunay triangulations within the Euclidean plane. The study presented here explores the hyperbolicity of Delaunay triangulations and provides insights into the conditions under which Delaunay triangulations in the Euclidean plane are hyperbolic. This research contributes to our understanding of geometric structures and their hyperbolicity, in Gromov sense.

Open problem

Note that part of the arguments in the proofs of the results in this paper work for $n$-dimensional space. It therefore seems natural to raise the open problem of generalising our results to dimension $n$.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This publication is part of the grant PID2019-106433GB-I00 funded by Agencia Estatal de Investigación MCIN/AEI/ 10.13039/501100011033. The research of Jose M. Rodríguez is supported by a grant from the Madrid Government (Comunidad de Madrid-Spain) under the Multiannual Agreement with UC3M in the line of Excellence of University Professors (EPUC3M23), and in the context of the V PRICIT (Regional Programme of Research and Technological Innovation).

We would like to thank the reviewers by their careful reading of the manuscript and their suggestions which have improved the presentation of this work.

Conflict of interest

The authors declare that there are no conflicts of interest. Prof. Jose M. Rodriguez is a Guest Editor for AIMS Mathematics and was not involved in the editorial review or the decision to publish this article. All authors declare that there are no competing interests.