# Discrete Yamabe problem for polyhedral surfaces

Dal Poz Kouřimská, Hana Institute of Science and Technology Austria, Am Campus
1, 3400 Klosterneuburg, Austria<EMAIL_ADDRESS>
###### Abstract

We study a new discretization of the Gaussian curvature for polyhedral
surfaces. This discrete Gaussian curvature is defined on each conical
singularity of a polyhedral surface as the quotient of the angle defect and
the area of the Voronoi cell corresponding to the singularity.
We divide polyhedral surfaces into discrete conformal classes using a
generalization of discrete conformal equivalence pioneered by Feng Luo. We
subsequently show that, in every discrete conformal class, there exists a
polyhedral surface with constant discrete Gaussian curvature. We also provide
explicit examples to demonstrate that this surface is in general not unique.

57M50, 52B10, 52C26

##  1 Introduction

The Yamabe problem asks if every closed Riemannian manifold is conformally
equivalent to one with constant scalar curvature. More precisely:

######  Yamabe Problem.

Let $g$ be a Riemannian metric on a closed smooth manifold $M$. Does there
exist a smooth function $u$ on $M$ such that the Riemannian metric $e^{2u}g$
has constant scalar curvature?

For two-dimensional manifolds the scalar and the Gaussian curvature are
equivalent, and thus the Yamabe problem is answered by the celebrated
_Poincaré-Koebe uniformization theorem_ , which states that any closed
oriented Riemannian surface is conformally equivalent to one with constant
Gaussian curvature.

The purpose of this article is to translate the Yamabe problem for two-
dimensional manifolds into the setting of polyhedral surfaces. The essential
ingredient of the translation is the introduction of a new discretization of
Gaussian curvature.

Defining the discrete Gaussian curvature requires a little preparation. We
characterize a  _polyhedral_ or a _piecewise flat surface_ by a triple
$(S,V,d)$, where $S$ is the underlying topological surface, $d$ denotes the
_PL-metric_ (PL stands for piecewise linear), and $V\subseteq S$ is a finite
set containing the conical singularities of $d$.

Let $\alpha_{i}$ denote the cone angle at a point $i\in V$. The _angle defect_
,

$W:V\to\mathbb{R},\qquad W_{i}:=2\pi-\alpha_{i},$

evaluates for each $i\in V$ how far the piecewise flat surface is from being
flat at a neighborhood of $i$. This notion, introduced by Tullio Regge [9], is
best understood as the discretization of the Gaussian curvature two-form.

The _Voronoi cell_ of a point $i\in V$ consists of all points on the piecewise
flat surface $(S,V,d)$ that are as close or closer to $i$ than to any other
point in $V$. It arises as a natural neighborhood of the point $i$.

######  Definition 1.1.

The discrete Gaussian curvature at a point $i\in V$ is the quotient of the
angle defect $W_{i}$ and the area $A_{i}$ of the Voronoi cell of $i$:

$\displaystyle K:V\to\mathbb{R},\qquad i\mapsto K_{i}:=\frac{W_{i}}{A_{i}}.$

_Discrete Yamabe problem_ asks if for every PL-metric there exists a discrete
conformally equivalent one with constant discrete Gaussian curvature. It can
be answered affirmatively by the following theorem.

######  Theorem 1.2 (Discrete uniformization theorem).

For every PL-metric $d$ on a marked surface $(S,V)$, there exists a discrete
conformally equivalent PL-metric $\tilde{d}$ such that the piecewise flat
surface $(S,V,\tilde{d})$ has constant discrete Gaussian curvature.

The proof of Theorem 1.2 presented here is variational in nature. We translate
the problem into a non-convex optimization problem with inequality
constraints, which we solve using a classical theorem from calculus.

The PL-metric $\tilde{d}$ of constant curvature from Theorem 1.2 is, in
general, not unique.

_Discrete conformal equivalence_ for piecewise flat surfaces with a fixed
triangulation was introduced by Martin Roček and Ruth Williams [10], and Feng
Luo [6], and is a straightforward discretization of the conformal equivalence
on smooth surfaces. Recall that two Riemannian metrics $g$ and $\tilde{g}$ on
a surface $S$ are conformally equivalent if there exists a smooth function $u$
on $S$ such that

$\tilde{g}=e^{2u}g.$

To discretize conformal equivalence, triangulate the piecewise flat surface
$(S,V,d)$ such that $V$ is the set of vertices and every edge $e\in E$ is a
geodesic. The metric $d$ is then uniquely determined by the edge lengths

$\ell:E\to\mathbb{R}_{>0},\qquad\ell_{ij}=d(i,j).$

Two PL-metrics on a surface with a fixed triangulation are _discrete
conformally equivalent_ if their edge lengths
$\ell,\tilde{\ell}:E\to\mathbb{R}_{>0}$ are related by a factor
$u:V\to\mathbb{R}$:

$\tilde{\ell}_{ij}=\exp\left(\frac{u_{i}+u_{j}}{2}\right)\ell_{ij}.$

We work with a generalization of discrete conformal equivalence to piecewise
flat surfaces (Definition 2.11), introduced by Alexander Bobenko, Ulrich
Pinkall and Boris Springborn in [2, Definition 5.1.4]. This generalization,
which is equivalent to the generalization by Xianfeng Gu, Feng Luo, Jian Sun
and Tianqi Wu [4, Definition 1.1], reveals that hyperbolic geometry is the
right setting for problems involving discrete conformal equivalence. The
essential relation between piecewise flat surfaces and its hyperbolic
equivalent – decorated ideal hyperbolic polyhedra – has been explored and
described in detail by Boris Springborn in [11].

Another formulation of the discrete Yamabe problem for polyhedral surfaces due
to Feng Luo [6] asks for the existence of PL-metrics with a constant _angle
defect_ within a discrete conformal class. It was solved affirmatively by Gu
et al. [4], as well as by Boris Springborn [11]. For surfaces of genus one,
Luo’s and our formulation of the discrete Yamabe problem are indeed
equivalent. However, we believe that Luo’s formulation is not a suitable
discretization of the smooth Yamabe problem in general, since the angle defect
is not a proper discretization of the smooth Gaussian curvature. This claim is
supported by the discussions by Bobenko et al. in [2, Appendix B] and by
Huabin Ge and Xu Xu in [3, Section 1.2].

This article is organized as follows. In Section 2 we revise the basic
concepts and provide a dictionary between piecewise flat surfaces and
decorated ideal hyperbolic polyhedra. Section 3 is devoted to the discussion
of (non)-uniqueness of PL-metrics with constant discrete Gaussian curvature.
In Section 4 we translate the statement of Theorem 1.2 into a non-convex
optimization problem with inequality constraints. In Section 5 we prove
Theorem 1.2.

##  2 Fundamental definitions and results

In this section we explain the correspondence between piecewise flat surfaces
and decorated ideal hyperbolic polyhedra. Since the results in this section
are well-known, we omit the proofs.

Throughout the article we work with a closed oriented topological surface $S$
and a non-empty finite set $V\subseteq S$ of _marked points_. A _triangulation
of the marked surface_ $(S,V)$ is a triangulation of $S$ with the vertex set
equal to $V$. We denote a triangulation by $\Delta$ and the _set of edges_ and
_faces_ of $\Delta$ by $E_{\Delta}$ and $F_{\Delta}$, respectively.

A metric $d$ on $(S,V)$ is called _piecewise linear_ or a _PL-metric_ if is
flat everywhere but on a finite set of points contained in $V$, where it
develops conical singularities. A _geodesic triangulation_ of the piecewise
flat surface $(S,V,d)$ is any triangulation of $(S,V)$ where the edges are
geodesics with respect to the metric $d$.

###  2.1 Tessellations of piecewise flat surfaces, discrete metric

#### Voronoi tessellation

Every piecewise flat surface $(S,V,d)$ possesses a unique _Voronoi
tessellation_. For $p\in S$ let $d(p,V)$ denote the distance of $p$ to the set
$V$, and let $\Gamma_{V}(p)$ be the set of all geodesics realizing this
distance. The open 2-, 1- and 0-cells of the Voronoi tessellation of $(S,V,d)$
are the connected components of

$\\{p\in S\mid|\Gamma_{V}(p)|=1\\},$ $\\{p\in
S\mid|\Gamma_{V}(p)|=2\\},\quad\text{and}\quad\\{p\in S\mid|\Gamma_{V}(p)|\geq
3\\},$

respectively. We denote the closure of the open Voronoi 2-cell containing
$i\in V$ by $V_{i}$.

#### Delaunay tessellation and triangulation

_Delaunay tessellation_ of a piecewise flat surface is the dual of the Voronoi
tessellation. A _Delaunay triangulation_ arises from the Delaunay tessellation
by adding edges to triangulate the non-triangular faces.

Let $\Delta$ be a geodesic triangulation of a piecewise flat surface
$(S,V,d)$. The edge $ij\in E_{\Delta}$ is called a _Delaunay edge_ if the
vertex $l$ of the adjacent triangle $ijl\in F_{\Delta}$ is not contained in
the interior of the circumcircle of the other adjacent triangle $ijk\in
F_{\Delta}$.

######  Proposition 2.1.

A geodesic triangulation of a piecewise flat surface is Delaunay if and only
if each of its edges is Delaunay.

#### Discrete metric

Let $\Delta$ be a triangulation of the marked surface $(S,V)$.

######  Definition 2.2.

A discrete metric on $(S,V,\Delta)$ is a function

$\ell:E_{\Delta}\to\mathbb{R}_{>0},\qquad\ell(ij)=\ell_{ij},$

such that for every triangle $ijk\in F_{\Delta}$, the (sharp) triangle
inequalities are satisfied. That is,

$\displaystyle\ell_{ij}+\ell_{jk}>\ell_{ki},\quad\ell_{jk}+\ell_{ki}>\ell_{ij},\quad\ell_{ki}+\ell_{ij}>\ell_{jk}.$

The logarithm of the discrete metric $\ell$,

$\displaystyle\lambda_{ij}=2\log\ell_{ij},$ (1)

is called the logarithmic lengths.

######  Fact 2.3.

Let $\Delta$ be a geodesic triangulation of the piecewise flat surface
$(S,V,d)$. Then the PL-metric $d$ induces a discrete metric on $(S,V,\Delta)$
by measuring the lengths of the edges in $E_{\Delta}$.

Vice versa, each discrete metric $\ell$ on a marked triangulated surface
$(S,V,\Delta)$ induces a PL-metric on $(S,V)$.

Indeed, $\ell$ imposes a Euclidean metric on each triangle $ijk\in F_{\Delta}$
by transforming it into a Euclidean triangle with edge lengths
$\ell_{ij},\ell_{jk},\ell_{ki}$. The metrics on two neighboring triangles fit
isometrically along the common edge. Thus, by gluing each pair of neighboring
triangles in $\Delta$ along their common edge we equip the marked surface with
a PL-metric.

###  2.2 Ideal hyperbolic polyhedra, ideal tessellations and Penner
coordinates

An _ideal hyperbolic polyhedron_ is a marked surface $(S,V)$ equipped with a
complete finite area hyperbolic metric $d_{hyp}$ with cusps at the marked
points.

We _decorate_ the ideal hyperbolic polyhedron $(S,V,d_{hyp})$ with a horocycle
$\mathcal{H}_{i}$ at each cusp $i\in V$. Each horocycle is small enough such
that, altogether, the horocycles bound disjoint cusp neighborhoods. The set of
all horocycles decorating $(S,V,d_{hyp})$ is denoted by $\mathcal{H}$.

#### Ideal Delaunay tessellations and triangulations

######  Definition 2.4.

An ideal Delaunay tessellation of a decorated ideal hyperbolic polyhedron
$(S,V,d_{hyp},\mathcal{H})$ is an ideal geodesic cell decomposition of
$(S,V,d_{hyp})$, such that for each face $f$ of the lift of $(S,V,d_{hyp})$ to
the hyperbolic plane $H^{2}$ via an isometry of the universal cover, the
following condition is satisfied. There exists a circle that touches all
lifted horocycles anchored at the vertices of $f$ externally and does not meet
any other lifted horocycles.

An ideal Delaunay triangulation is any refinement of an ideal Delaunay
tessellation by decomposing the non-triangular faces into ideal triangles by
adding geodesic edges.

######  Theorem 2.5.

For each decorated ideal hyperbolic polyhedron with at least one cusp, there
exists a unique ideal Delaunay tessellation.

Let $\Delta$ be a geodesic triangulation of a decorated ideal hyperbolic
polyhedron $(S,V,d_{hyp},\mathcal{H})$. An edge $ij\in E_{\Delta}$ is called
_Delaunay_ if the circle touching the horocycles at vertices $i,j,k$ of one
adjacent triangle $ijk\in F_{\Delta}$ and the horocycle at vertex $l$ of the
other adjacent triangle $ijl\in F_{\Delta}$ are externally disjoint or
externally tangent. We illustrate the difference between a Delaunay and a non-
Delaunay edge in Figure 2.1.

2pt $i$ [ ] at 24 137 $k$ [ ] at 106 476 $j$ [ ] at 444 458 $l$ [ ] at 481 91

(a)  The orange circle and the horocycle at $l$ are disjoint, the edge $ij$ is
Delaunay.

2pt $i$ [ ] at 24 137 $k$ [ ] at 106 476 $j$ [ ] at 444 468 $l$ [ ] at 491 91

(b)  The orange circle and the horocycle at $l$ intersect, the edge $ij$ is
not Delaunay.

Figure 2.1:  A Delaunay and a non-Delaunay edge.

######  Proposition 2.6.

An ideal geodesic triangulation of a decorated ideal hyperbolic polyhedron is
Delaunay if and only if each of its edges is Delaunay.

#### Penner coordinates

Penner coordinates, introduced by Robert Penner in [8], are the analogue of
the discrete metric (see Definition 2.2) for decorated ideal hyperbolic
polyhedra.

######  Definition 2.7.

Let $i$ and $j$ be two ideal points of the hyperbolic plane. Let
$\mathcal{H}_{i}$ and $\mathcal{H}_{j}$ be two horocycles, anchored at ideal
points $i$ and $j$, respectively. The signed horocycle distance between
$\mathcal{H}_{i}$ and $\mathcal{H}_{j}$ is the length of the segment of the
geodesic line connecting the cusps $i$ and $j$, truncated by the horocycles.
The length is taken negative if $\mathcal{H}_{i}$ and $\mathcal{H}_{j}$
intersect.

The signed distances between horocycles of a decorated ideal hyperbolic
triangle are illustrated in Figure 2.2. The distance $\lambda_{ij}$ is
negative, whereas the distances $\lambda_{jk}$ and $\lambda_{ki}$ are
positive.

2pt $i$ [ ] at 146 488 $j$ [ ] at 62 74 $k$ [ ] at 518 270 $\lambda_{ki}$ [ ]
at 349 321 $\lambda_{jk}$ [ ] at 328 203 $\lambda_{ij}$ [ ] at 209 258

Figure 2.2: Penner coordinates of a decorated ideal hyperbolic triangle $ijk$,
in the Poincaré disc model.

######  Definition 2.8.

Penner coordinates is a pair consisting of a triangulation $\Delta$ of $(S,V)$
and a map

$\lambda:E_{\Delta}\to\mathbb{R},\qquad ij\mapsto\lambda_{ij}.$

######  Fact 2.9.

Penner coordinates $(\Delta,\lambda)$ on a marked surface $(S,V)$ define a
decorated ideal hyperbolic polyhedron $(S,V,d_{hyp},\mathcal{H})$, such that
the signed distance between the horocycles $\mathcal{H}_{i}$ and
$\mathcal{H}_{j}$, with $ij\in E_{\Delta}$, is $\lambda_{ij}$.

Vice versa, let $\Delta$ be a geodesic triangulation of a decorated ideal
hyperbolic polyhedron $(S,V,d_{hyp},\mathcal{H})$. Then
$(S,V,d_{hyp},\mathcal{H})$ induces Penner coordinates $(\Delta,\lambda)$ by
measuring the signed horocycle distance between horocycles $\mathcal{H}_{i}$
and $\mathcal{H}_{j}$ for each $ij\in E_{\Delta}$.

###  2.3 From piecewise flat surfaces to decorated ideal hyperbolic polyhedra
and back again

Piecewise flat surfaces and decorated ideal hyperbolic polyhedra are, in fact,
equivalent structures.

######  Theorem 2.10.

Let $(S,V)$ be a marked surface with a triangulation $\Delta$.

Let $\ell:E_{\Delta}\to\mathbb{R}_{>0}$ be a discrete metric on $(S,V,\Delta)$
such that $\Delta$ is a Delaunay triangulation of the piecewise flat surface
$(S,V,d_{\ell})$. Let $\lambda$ be the logarithmic lengths of $\ell$ defined
by Equation (1). Then $\Delta$ is an ideal Delaunay triangulation of the
decorated ideal hyperbolic polyhedron defined on the marked surface $(S,V)$ by
Penner coordinates $(\Delta,\lambda)$.

Vice versa, let $(\Delta,\lambda)$ be Penner coordinates on $(S,V)$ such that
$\Delta$ is an ideal Delaunay triangulation of the decorated ideal hyperbolic
polyhedron defined on $(S,V)$ by $(\Delta,\lambda)$. Then the map
$\ell:E_{\Delta}\to\mathbb{R}_{\geq 0}$, defined by Equation (1), is a
discrete metric on $(S,V,\Delta)$, and $\Delta$ is a Delaunay triangulation of
the polyhedral surface $(S,V,d_{\ell})$.

###  2.4 Discrete conformal classes

Theorem 2.10 tells us that each piecewise flat surface induces a decorated
ideal hyperbolic polyhedron, and vice versa.

######  Definition 2.11.

Two PL-metrics on a marked surface $(S,V)$ are discrete conformally equivalent
if the two induced decorated ideal hyperbolic polyhedra are isometric.

Discrete conformal equivalence is an equivalence relation on the space of PL-
metrics of a marked surface $(S,V)$. The corresponding equivalence classes are
called _conformal classes_. In particular, discrete conformally equivalent PL-
metrics induce different decorations on the – up to isometry – same ideal
hyperbolic polyhedron.

Let $d$ and $\tilde{d}$ be two discrete conformally equivalent PL-metrics on
$(S,V)$, and let $\mathcal{H}$ and $\tilde{\mathcal{H}}$ denote the two
decorations induced on the ideal hyperbolic polyhedron $(S,V,d_{hyp})$ by $d$
and $\tilde{d}$, respectively.

Let $u_{i}$ denote the signed distance from the horocycle $\mathcal{H}_{i}$ to
the horocycle $\tilde{\mathcal{H}}_{i}$. The distance is taken positive if
$\tilde{\mathcal{H}}_{i}$ is closer to the cusp at $i$ than $\mathcal{H}_{i}$
– as illustrated in Figure 2.3 in the halfplane model – and negative
otherwise. The map

$u:V\to\mathbb{R},\qquad i\mapsto u_{i},$

is called a _conformal factor_ , or a _conformal change_ from $d$ to
$\tilde{d}$.

2pt $\mathcal{H}_{i}$ [ ] at 229 108 $\tilde{\mathcal{H}}_{i}$ [ ] at 229 230
$u_{i}$ [ ] at 72 135 $i$ [ ] at 152 250

Figure 2.3:

The position of each horocycle in $\tilde{\mathcal{H}}$ is completely
determined by the decorated ideal hyperbolic polyhedron
$(S,V,d_{hyp},\mathcal{H})$ and the conformal factor $u$. Thus, for a fixed
marked surface $(S,V)$, each PL-metric $\tilde{d}$ in the conformal class of
the PL-metric $d$ is uniquely defined by $d$ and the conformal factor $u$.

To express this relation, we denote PL-metric $\tilde{d}$ and the decoration
$\tilde{\mathcal{H}}$ by $d(u)$ and $\mathcal{H}(u)$, respectively. Further,
if $\tilde{\Delta}$ is a Delaunay triangulation of $(S,V,\tilde{d})$, the
Penner coordinates $(\tilde{\Delta},\tilde{\lambda})$ are denoted by
$(\Delta(u),\lambda(u))$.

Vice versa, each conformal factor defines a PL-metric in the conformal class
of $d$. In other words:

######  Proposition 2.12.

The conformal class of the piecewise flat surface $(S,V,d)$ is parametrized by
the vector space

$\mathbb{R}^{V}=\\{u:V\to\mathbb{R}\\}.$

As shown by Robert Penner in [8], the vector space $\mathbb{R}^{V}$ admits a
cell decomposition into Penner cells.

######  Definition 2.13.

Let $(S,V,d)$ be a piecewise flat surface, and let $\Delta$ be a triangulation
of the marked surface $(S,V)$. The Penner cell of $\Delta$ in the conformal
class of $(S,V,d)$ is the set

$\mathcal{A}_{\Delta}=\\{u\in\mathbb{R}^{V}\mid\Delta\text{ is a Delaunay
triangulation of }(S,V,d(u))\\}.$

The set of all triangulations with non-empty Penner cells in the conformal
class of $(S,V,d)$ is denoted by $\mathfrak{D}(S,V,d)$.

Discrete conformal equivalence also induces a relation on discrete metrics.

######  Proposition 2.14.

Let $d$ and $\tilde{d}$ be two conformally equivalent PL-metrics on a marked
surface $(S,V)$, related by the conformal factor $u:V\to\mathbb{R}$, and let
$\Delta$ be a geodesic triangulation of the surface $(S,V,d)$, as well as the
surface $(S,V,\tilde{d})$. Then the discrete metrics $\ell$ and
$\tilde{\ell}$, induced by $d$ and $\tilde{d}$, respectively, satisfy

$\tilde{\ell}_{ij}=\ell_{ij}e^{\frac{u_{i}+u_{j}}{2}}$

for every edge $ij\in E_{\Delta}$.

######  Remark.

Proposition 2.14 is the definition of discrete conformal equivalence for
piecewise flat surfaces with fixed triangulation, introduced by Feng Luo [6].

##  3 Counterexamples to uniqueness of metrics with constant curvature

Uniqueness of PL-metrics with constant discrete Gaussian curvature up to
global scaling in discrete conformal classes holds in three special cases:

  * •

_$S$ is of genus zero and $|V|=3$._
This follows from the positive semi-definiteness of the second derivative of
the function $\mathbb{F}$, defined in Fact 4.11.

  * •

_$S$ is of genus one._
In this case the Yamabe problem is equivalent to the discrete uniformization
problem. The uniqueness follows from the positive semi-definiteness of the
second derivative of function $\mathbb{E}$ (Definition 4.3) and was proved by
Xianfeng Gu, Feng Luo, Jian Sun and Tianqi Wu in [4].

  * •

_$S$ is of genus larger than one and $|V|=1$._
This case is trivial, since every discrete conformal class consists of one PL-
metric up to a global scaling.

In order to show that uniqueness does not hold in general, we construct
several examples of pairs of discrete conformally equivalent PL-metrics with
constant discrete Gaussian curvature on the _sphere with four marked points_ –
that is, a tetrahedron – and the _surface of genus two with two marked
points_.

2pt $1$ [ ] at 235 354 $3$ [ ] at 126 172 $2$ [ ] at 426 157 $4$ [ ] at 10 377
$4$ [ ] at 471 399 $4$ [ ] at 262 0 $b$ [ ] at 164 268 $a$ [ ] at 339 261 $c$
[ ] at 267 195 $\bar{a}$ [ ] at 60 267 $\bar{a}$ [ ] at 190 73 $\bar{b}$ [ ]
at 447 274 $\bar{b}$ [ ] at 334 76 $\bar{c}$ [ ] at 126 363 $\bar{c}$ [ ] at
339 379

2pt $a$ [ ] at 391 289 $b$ [ ] at 132 320 $c$ [ ] at 263 254 $\bar{a}$ [ ] at
145 127 $b$ [ ] at 398 107 $F_{a}$ [ ] at 313 271 $F_{a}$ [ ] at 399 220
$F_{b}$ [ ] at 327 121 $F_{b}$ [ ] at 398 170 $F_{c}$ [ ] at 292 223 $F_{c}$ [
] at 294 156 $F_{\bar{a}}$ [ ] at 192 142 $F_{\bar{a}}$ [ ] at 143 181
$F_{\bar{b}}$ [ ] at 138 246 $F_{\bar{b}}$ [ ] at 199 267 $F_{\bar{c}}$ [ ] at
249 220 $F_{\bar{c}}$ [ ] at 246 154

Figure 3.1: A tetrahedron (left) and a division of areas in the two triangles
(right).

#### Tetrahedra with constant curvature

We start with a combinatorial tetrahedron, denoting the vertices and edges as
in Figure 3.1 (left). On this tetrahedron we define the PL-metric $d_{0}$ by
prescribing the following lengths to the edges:

$a=\overline{a}=1,\qquad b=\overline{b}=b_{0},\qquad c=\overline{c}=c_{0}.$

######  Fact 3.1.

Let $\Delta$ be a geodesic triangulation of a piecewise flat surface $(S,V,d)$
and let $ijk$ and $ijl$ be two neighboring triangles in $F_{\Delta}$. Let
$\alpha_{k},\alpha_{l}$ be the angles opposite of the edge $ij$ in the
triangles $ijk$ and $ijl$, respectively. The edge $ij$ is Delaunay if one of
the following equivalent Delaunay conditions holds:

  1. a)

$\cot\alpha_{k}+\cot\alpha_{l}\geq 0$,

  2. b)

$\alpha_{k}+\alpha_{l}\leq\pi$,

  3. c)

$\cos\alpha_{k}+\cos\alpha_{l}\geq 0.$

The values of $b_{0}$ and $c_{0}$ need to be greater than 1 and chosen so that
the edges of the tetrahedron are Delaunay. This is the case if and only if the
triangle with edge lengths $1,b_{0},c_{0}$ is acute. Due to condition _c)_ in
Fact 3.1, this is further equivalent to the following inequality:

$\displaystyle c_{0}^{2}\leq a_{0}^{2}+b_{0}^{2}=1+b_{0}^{2}.$ (2)

Denoting the area of the triangle with edge lengths $1,b_{0},c_{0}$ by $A$,
one sees that the PL-metric $d_{0}$ has constant discrete Gaussian curvature,

$K_{i}=\frac{\pi}{A}\qquad\text{for }i\in\\{1,\dots,4\\}.$

We now apply the following family of discrete conformal changes to $d_{0}$:

$\displaystyle u\circ v:\mathbb{R}\to\mathbb{R}^{4},\qquad
u(v)=(u_{1},u_{2},u_{3},u_{4})(v):=(0,0,v,v).$

######  Lemma 3.2.

Let

$\mathcal{S}_{(b_{0},c_{0})}:=\left[-\log(b_{0}^{2}+c_{0}^{2}),\log(b_{0}^{2}+c_{0}^{2})\right].$

The PL-metric $d(v)$, defined by applying the discrete conformal change $u(v)$
to the metric $d_{0}$, has Delaunay edges if
$v\in\mathcal{S}_{(b_{0},c_{0})}$. Its discrete Gaussian curvature at two
pairs of vertices is equal,

$K_{1}=K_{2},\qquad\text{and}\qquad K_{3}=K_{4}.$

###### Proof.

For each $v\in\mathbb{R}$ the tetrahedron with metric $d(v)$ has edge lengths

$a=1,\qquad b=\overline{b}=b_{0}e^{v/2},\qquad
c=\overline{c}=c_{0}e^{v/2},\qquad\bar{a}=e^{v}.$

The tetrahedron thus consists of two triangles with edge lengths $a,b,c$ and
two triangles with edge lengths $\bar{a},b,c$. The equality of the curvatures
follows immediately from the fact that $W_{1}=W_{2},W_{3}=W_{4},A_{1}=A_{2}$
and $A_{3}=A_{4}.$

The minimal and maximal value of the parameter $v$ follow from the properties
of Delaunay edges (Fact 3.1) and Equation (2). ∎

Lemma 3.2 implies that the PL-metric $d(v)$ has constant discrete Gaussian
curvature if $K_{1}=K_{3}$. In order to test if, for a fixed value of $b_{0}$
and $c_{0}$, this equality holds, we transform it into an expression more
favorable for calculations.

Let $A$ and $\bar{A}$ denote the area of the triangles with side lengths
$a,b,c$ and $\bar{a},b,c,$ respectively, and let $F_{a},\dots,F_{\bar{c}}$
denote the areas as in Figure 3.1 (right).

######  Lemma 3.3.

The PL-metric $d(v)$ has constant discrete Gaussian curvature if and only if
$v$ is a zero of the map

$\displaystyle
g_{(b_{0},c_{0})}:\mathcal{S}_{(b_{0},c_{0})}\to\mathbb{R},\qquad v\mapsto
2\pi(F_{\bar{a}}-F_{a})+(\alpha-\bar{\alpha})(A+\bar{A}).$

###### Proof.

Follows by a straightforward calculation:

$\displaystyle K_{1}=K_{3}\iff W_{1}A_{3}=W_{3}A_{1}\iff
2\pi(F_{\bar{a}}-F_{a})=(\bar{\alpha}-\alpha)(A+\bar{A}).$

∎

We plotted the graphs of the function $g_{(b_{0},c_{0})}$ for various values
of $b_{0}$ and $c_{0}$ in Figure 3.3.

2pt $2$ [ ] at 205 327 $2$ [ ] at 340 237 $2$ [ ] at 505 205 $2$ [ ] at 679
240 $2$ [ ] at 821 328 $1$ [ ] at 893 120 $1$ [ ] at 672 8 $1$ [ ] at 405 6
$1$ [ ] at 190 76 $1$ [ ] at 16 229 $a^{4}$ [ ] at 274 286 $a^{3}$ [ ] at 424
220 $a^{4}$ [ ] at 593 219 $a^{3}$ [ ] at 748 283 $a^{2}$ [ ] at 787 71
$a^{1}$ [ ] at 549 7 $a^{2}$ [ ] at 304 36 $a^{1}$ [ ] at 94 155 $b^{1}$ [ ]
at 93 302 $c^{1}$ [ ] at 173 214 $b^{2}$ [ ] at 260 177 $c^{2}$ [ ] at 356 118
$b^{3}$ [ ] at 457 116 $c^{3}$ [ ] at 571 96 $b^{4}$ [ ] at 660 124 $c^{4}$ [
] at 778 156 $b^{1}$ [ ] at 836 231

Figure 3.2:

#### Surfaces of genus two with two marked points and constant curvature

The initial metric $d_{0}$ is defined on a triangulation with combinatorics as
in Figure 3.2, with edge lengths prescribed as follows:

$a^{1}=...=a^{4}=1,\quad b^{1}=...=b^{4}=b_{0},\quad c^{1}=...=c^{4}=c_{0},$

for two values $b_{0},c_{0}\geq 1$ satisfying Condition (2). As in the
previous paragraph, one can easily check that $d_{0}$ has constant discrete
Gaussian curvature

$K_{i}=-\frac{\pi}{2A},$

where $A$ is the area of the triangle with edge lengths $1,b_{0},c_{0}$. We
now apply the following family of discrete conformal changes to $d_{0}$:

$\displaystyle u\circ v:\mathbb{R}\to\mathbb{R}^{2},\qquad
u(v)=(u_{1},u_{2})(v):=(0,v).$

The following lemma is the analogon of Lemmata 3.2 and 3.3.

######  Lemma 3.4.

The PL-metric $d(v)$, given by applying the discrete conformal change $u(v)$
to the metric $d_{0}$, has Delaunay edges if
$v\in\mathcal{S}_{(b_{0},c_{0})}$. It has constant discrete Gaussian curvature
if and only if $v$ is a zero of the map

$\displaystyle
h_{(b_{0},c_{0})}:\mathcal{S}_{(b_{0},c_{0})}\to\mathbb{R},\qquad
v\mapsto\pi(F_{\bar{a}}-F_{a})+(\bar{\alpha}-\alpha)(A+\bar{A}).$

###### Proof.

Analogous to the proofs of Lemmata 3.2 and 3.3. ∎

2pt  $g_{(1.6,1.75)}(v)$ [ ] at 5 235  $g_{(1.8,1.95)}(v)$ [ ] at 5 210
$g_{(2.0,2.15)}(v)$ [ ] at 5 185  $g_{(2.2,2.35)}(v)$ [ ] at 5 160

2pt  $h_{(2.6,2.75)}(v)$ [ ] at 21 305  $h_{(2.8,2.95)}(v)$ [ ] at 21 285
$h_{(3.0,3.15)}(v)$ [ ] at 21 265  $h_{(3.2,3.35)}(v)$ [ ] at 21 245

Figure 3.3: Graphs of the functions $g$ (left) and $h$ (right) for various
values of $b_{0}$ and $c_{0}$.

The number of critical points of the maps $g_{(b_{0},c_{0})}$ and
$h_{(b_{0},c_{0})}$ varies depending on the choice of $(b_{0},c_{0})$. Figure
3.3 illustrates the graphs of $g_{(b_{0},c_{0})}$ and $h_{(b_{0},c_{0})}$ for
various values of $(b_{0},c_{0})$. In each graph the red and green curves
correspond to discrete conformal classes with more than one metric with
constant discrete Gaussian curvature.

##  4 Variational principles

The goal of this article is to prove the existence of piecewise flat surfaces
with constant Gaussian curvature, where the discrete Gaussian curvature is the
quotient of the angle defect and the area of the corresponding Voronoi cell.
In this section we translate this setting into an optimization problem which
we describe by three variational principles. To this end, we define two
functions – $\mathbb{E}$ and $A_{tot}$ – whose partial derivatives correspond
to the angle defect and the area of the Voronoi cell, respectively. The
functions $\mathbb{E}$ and $A_{tot}$ form the two essential building blocks of
the variational principles.

###  4.1 Two essential building blocks

#### The function $\mathbb{E}$

The function $\mathbb{E}$, which we will introduce shortly, was defined by
Alexander Bobenko et al. in [2]. As we will see, it is locally convex and its
partial derivatives correspond to the angle defects at the vertices. Its
building block is a peculiar function $f$.

######  Definition 4.1.

Consider a Euclidean triangle with edge lengths $a,b,c$ and angles
$\alpha,\beta,\gamma$, opposite to edges $a,b,c$, respectively. Let

$x=\log a,\qquad y=\log b,\qquad z=\log c,$

as illustrated in Figure 1(a). Let $\mathfrak{A}$ be the set of all triples
$(x,y,z)\in\mathbb{R}^{3}$, such that $(a,b,c)$ satisfy the triangle
inequalities:

$\mathfrak{A}=\\{(x,y,z)\in\mathbb{R}^{3}\mid a+b-c>0,a-b+c>0,-a+b+c>0\\}.$

The function $f$ is defined as follows:

$f:\mathfrak{A}\to\mathbb{R},\quad f(x,y,z)=\alpha x+\beta y+\gamma
z+\mathbb{L}(\alpha)+\mathbb{L}(\beta)+\mathbb{L}(\gamma),$

where

$\mathbb{L}(\alpha)=-\int_{0}^{\alpha}\log|2\sin(t)|\>dt$

is Milnor’s Lobachevsky function, introduced by John Milnor in [7].

2pt $\alpha$ [ ] at 133 120 $\beta$ [ ] at 433 79 $\gamma$ [ ] at 291 295
$c=e^{z}$ [ ] at 261 40  $b=e^{y}$ [ ] at 180 251  $a=e^{x}$ [ ] at 420 220

(a) Logarithmic edge lengths of a triangle.

(b) Graph of Milnor’s Lobachevsky function, $y=\mathbb{L}(x)$.

Figure 4.1:

######  Fact 4.2.

Milnor’s Lobachevsky function $\mathbb{L}(x)$ is odd, $\pi$-periodic, and
smooth except at $x\in\pi\mathbb{Z}$.

Recall that the discrete conformal class of a piecewise flat surface $(S,V,d)$
is parameterized by the vector space $\mathbb{R}^{V}$ (see Proposition 2.12),
which can be decomposed into Penner cells (see Definition 2.13). We first
define the function $\mathbb{E}_{\Delta}$ on each Penner cell
$\mathcal{A}_{\Delta}$ and then extend its domain to obtain the function
$\mathbb{E}$ on $\mathbb{R}^{V}$.

######  Definition 4.3.

Let $(S,V,d)$ be a piecewise flat surface, and let
$\Delta\in\mathfrak{D}(S,V,d)$. On the Penner cell $\mathcal{A}_{\Delta}$, the
function $\mathbb{E}_{\Delta}$ is defined as follows:

$\displaystyle\mathbb{E}_{\Delta}:\mathcal{A}_{\Delta}\to\mathbb{R},$
$\displaystyle\mathbb{E}_{\Delta}(u)=\sum_{ijk\in
F_{\Delta}}\left(2f\left(\frac{\tilde{\lambda}_{ij}}{2},\frac{\tilde{\lambda}_{jk}}{2},\frac{\tilde{\lambda}_{ki}}{2}\right)-\frac{\pi}{2}(\tilde{\lambda}_{ij}+\tilde{\lambda}_{jk}+\tilde{\lambda}_{ki})\right)+2\pi\sum_{i\in
V}u_{i},$

where $\tilde{\lambda}_{ij}$ are the logarithmic lengths of the discrete
metric induced by the PL-metric $d(u)$ on $\Delta$.

######  Lemma 4.4.

The partial derivatives of the function $\mathbb{E}_{\Delta}$ satisfy the
equation

$\frac{\partial\mathbb{E}_{\Delta}}{\partial u_{i}}=W_{i},$ (3)

where $W_{i}$ is the angle defect at vertex $i$ of the piecewise flat surface
$(S,V,d(u))$.

###### Proof.

Follows from [2, Proposition 4.1.2]. ∎

The functions $f$ and $\mathbb{E}_{\Delta}$ have the following properties:

######  Proposition 4.5 (Properties of $f$ and $\mathbb{E}_{\Delta}$).

The functions $f$ and $\mathbb{E}_{\Delta}$ are analytic and locally convex on
$\mathfrak{A}$ and $\mathcal{A}_{\Delta}$, respectively. Their second
derivatives are positive semidefinite quadratic forms with one-dimensional
kernels, spanned by $(1,1,1)\in\mathbb{R}^{3}$,
$(1,\dots,1)\in\mathbb{R}^{V}$, respectively. Further,

$\displaystyle f(x+t,y+t,z+t)$ $\displaystyle=f(x,y,z)+\pi t$
$\displaystyle\text{for all }(x,y,z)\in\mathfrak{A},$
$\displaystyle\mathbb{E}_{\Delta}(u+c(1,\dots,1))$
$\displaystyle=\mathbb{E}_{\Delta}(u)+2\pi\chi(S)c$ $\displaystyle\text{for
all }u\in\mathcal{A}_{\Delta},$

where $\chi(S)$ denotes the Euler characteristic of the surface $S$.

###### Proof.

See [2, Equation (4-5)] or [11, Propositions 7.2 and 7.7]. ∎

######  Theorem 4.6 (Extension).

For a conformal factor $u\in\mathbb{R}^{V}$, let $\Delta(u)$ be a Delaunay
triangulation of the surface $(S,V,d(u))$. The map

$\mathbb{E}:\mathbb{R}^{V}\to\mathbb{R},\qquad
u\mapsto\mathbb{E}_{\Delta(u)}(u),$

is well-defined and twice continuously differentiable. Its second derivative
is a positive semidefinite quadratic form with one-dimensional kernel, spanned
by $(1,\dots,1)\in\mathbb{R}^{V}$. Explicitly,

$\displaystyle d^{2}\mathbb{E}=\frac{1}{4}\sum_{ij\in
E}(\cot\alpha_{k}^{ij}+\cot\alpha_{l}^{ij})(du_{i}-du_{j})^{2}.$

###### Proof.

Follows from [2, Proposition 4.1.6] and [11, Section 7 and 8]. ∎

#### The function $\mathbf{A_{tot}}$

The function $A_{tot}$, whose first partial derivatives correspond to the area
of the Voronoi cells, denotes the total area of the surface. We first define
the function $A_{tot}^{\Delta}$ on each Penner cell $\mathcal{A}_{\Delta}$ and
then extend its domain to obtain the function $A_{tot}$ on $\mathbb{R}^{V}$.

######  Definition 4.7.

Let $(S,V,d)$ be a piecewise flat surface, and let
$\Delta\in\mathfrak{D}(S,V,d)$. On the Penner cell $\mathcal{A}_{\Delta}$, the
function $A_{tot}^{\Delta}$ is defined as follows:

$A_{tot}^{\Delta}:\mathcal{A}_{\Delta}\to\mathbb{R},\qquad
A_{tot}^{\Delta}(u)=\sum_{ijk\in F_{\Delta}}A_{ijk}(u),$

where $A_{ijk}(u)$ is the area of the triangle with vertices $i,j,k\in V$ on
the piecewise flat surface $(S,V,d(u))$.

######  Lemma 4.8.

The function $A_{tot}^{\Delta}$ is analytic. Its partial derivatives satisfy
the equation

$\displaystyle\frac{\partial A_{tot}^{\Delta}}{\partial u_{i}}=2A_{i}.$ (4)

Its second derivative is

$\displaystyle d^{2}A_{tot}^{\Delta}$ $\displaystyle=\sum_{ij\in
E_{\Delta}}2A_{ij}(du_{i}+du_{j})^{2}-\frac{1}{2}\sum_{ij\in
E_{\Delta}}(R_{ijk}^{2}\cot\alpha_{k}^{ij}+R_{ijl}^{2}\cot\alpha_{l}^{ij})(du_{i}-du_{j})^{2},$

where the vertices $k,l\in V$ are the opposite vertices in the neighboring
triangles $ijk,ijl\in F_{\Delta(u)}$,
$A_{ij}=\frac{\ell_{ij}^{2}}{8}\left(\cot\alpha_{k}^{ij}+\cot\alpha_{l}^{ij}\right)$,
and $R_{ijk}$ denotes the radius of the circumcircle of the triangle $ijk$.

2pt $i$ [ ] at 34 181 $j$ [ ] at 417 124 $k$ [ ] at 229 414 $\alpha_{i}^{jk}$
[ ] at 110 209 $\alpha_{j}^{ki}$ [ ] at 330 178 $\alpha_{k}^{ij}$ [ ] at 223
337 $A_{jk}^{i}$ [ ] at 257 266 ${\ell}_{jk}$ [ ] at 349 274 ${\ell}_{ij}$ [ ]
at 253 118 ${\ell}_{ki}$ [ ] at 105 300 $R_{ijk}$ [ ] at 228 70

Figure 4.2:

###### Proof.

The function $A_{tot}^{\Delta}$ is analytic since the area $A_{ijk}$ of each
triangle $ijk\in F_{\Delta}$ is an analytic function with respect to the
conformal factors.

Let $A_{jk}^{i}$ denote the part of the triangle depicted in Figure 4.2. Then

$A_{jk}^{i}=\frac{\ell_{jk}^{2}}{8}\cot\alpha_{i}^{jk},$

and the area of the Voronoi cell $V_{i}$ of a piecewise flat surface $(S,V,d)$
satisfies the equation

$A_{i}=\sum_{jk\mid ijk\in F_{\Delta}}A^{j}_{ki}+A^{k}_{ij}.$

Thus,

$\displaystyle\frac{\partial A_{ijk}}{\partial
u_{i}}=2A^{j}_{ki}+2A^{k}_{ij}-R_{ijk}^{2}\frac{\partial}{\partial
u_{i}}(\underbrace{\alpha_{i}^{jk}+\alpha_{j}^{ki}+\alpha_{k}^{ij}}_{=\pi})=2A^{j}_{ki}+2A^{k}_{ij}.$

Due to the linearity of the area function,

$\displaystyle\frac{\partial A_{tot}^{\Delta}}{\partial u_{i}}=\sum_{jk\mid
ijk\in F_{\Delta}}2A^{j}_{ki}+2A^{k}_{ij}=2A_{i}.$

In the upcoming calculations we use the following formula from [2, Equation
(4-8)].

######  Lemma.

Let $a,b,c$ be edge lengths of a triangle, $\alpha,\beta,\gamma$ angles
opposite of $a,b,c$, respectively, and let
$\lambda_{a},\lambda_{b},\lambda_{c}$ be the logarithmic lengths. Then

$2d\alpha=(\cot\beta+\cot\gamma)d\lambda_{a}-\cot\gamma d\lambda_{b}-\cot\beta
d\lambda_{c}.$

Since

$\displaystyle\frac{\partial A^{j}_{ki}}{\partial u_{i}}$
$\displaystyle=A^{j}_{ki}-\frac{1}{2}R_{ijk}^{2}\frac{\partial\alpha_{j}^{ki}}{\partial
u_{i}}=A^{j}_{ki}-\frac{1}{4}R_{ijk}^{2}\cot\alpha_{k}^{ij},$

we obtain the equation

$\displaystyle\frac{\partial^{2}A_{tot}}{\partial
u_{i}^{2}}=2A_{i}-\frac{1}{2}\sum_{jk\mid ijk\in
F_{\Delta}}R_{ijk}^{2}(\cot\alpha_{k}^{ij}+\cot\alpha_{j}^{ki}).$

Let $i,j\in V$ be two vertices. If $j$ is not adjacent to $i$,

$\frac{\partial^{2}A_{tot}}{\partial u_{i}\partial u_{j}}=0.$

If $j$ is adjacent to $i$, let $k,l\in V$ be the two opposite vertices in the
neighboring triangles $ijk,ijl\in F_{\Delta}$. Since

$\displaystyle\frac{\partial A^{i}_{jk}}{\partial u_{i}}$
$\displaystyle=-\frac{1}{2}R_{ijk}^{2}\frac{\partial\alpha_{i}^{jk}}{\partial
u_{i}}=\frac{1}{4}R_{ijk}^{2}(\cot\alpha_{j}^{ki}+\cot\alpha_{k}^{ij}),$

the mixed partial derivative equals

$\frac{\partial^{2}A_{tot}}{\partial u_{i}\partial
u_{j}}=\underbrace{2A^{k}_{ij}+2A^{l}_{ij}}_{=2A_{ij}}+\frac{1}{2}(R^{2}_{ijk}\cot\alpha_{k}^{ij}+R^{2}_{ijl}\cot\alpha_{l}^{ij}).$

Thus,

$\displaystyle d^{2}A_{tot}$ $\displaystyle=\sum_{ij\in
E_{\Delta}}2A_{ij}(du_{i}+du_{j})^{2}-\frac{1}{2}\sum_{ij\in
E_{\Delta}}(R_{ijk}^{2}\cot\alpha_{k}^{ij}+R_{ijl}^{2}\cot\alpha_{l}^{ij})(du_{i}-du_{j})^{2}.$

∎

######  Theorem 4.9 (Extension).

For a conformal factor $u\in\mathbb{R}^{V}$, let $\Delta(u)$ be a Delaunay
triangulation of the surface $(S,V,d(u))$. The map

$A_{tot}:\mathbb{R}^{V}\to\mathbb{R},\qquad u\mapsto A_{tot}^{\Delta(u)}(u),$

is well-defined and once continuously differentiable.

###### Proof.

Due to Lemma 4.8 the function $A_{tot}$ is once continuously differentiable in
the interior of every Penner cell. At the boundary between two (or more)
Penner cells the triangulations induce the same Delaunay tessellation and thus
the same Voronoi tessellation. The areas of the Voronoi cells induced by
either of the triangulations are therefore equal. ∎

######  Remark.

The function $A_{tot}$ is, in fact, twice continuously differentiable. This
can be proved by a long and unilluminating calculation [5, Chapter 8].

###  4.2 The variational principles

######  Theorem 4.10 (Variational principle with equality constraints).

Let $(S,V,d)$ be a piecewise flat surface. Up to global rescaling, the PL-
metrics with constant discrete Gaussian curvature in the conformal class of
the metric $d$ are in one-to-one correspondence with the critical points of
the function

$\mathbb{E}:\mathbb{R}^{V}\to\mathbb{R},\qquad u\mapsto\mathbb{E}(u),$

under the constraint

$A_{tot}(u)=1.$

###### Proof.

We use the method of Lagrange multipliers. A conformal factor
$u\in\mathbb{R}^{V}$ is a critical point of the function $\mathbb{E}$ under
the constraint $A_{tot}=1$ if and only if there exists a Lagrange multiplier
$\lambda\in\mathbb{R}$, such that

$0=\frac{\partial(\mathbb{E}-\lambda A_{tot})}{\partial
u_{i}}\overset{\eqref{eq:E_functional_first_par_derivative},\eqref{eq:area_functional_first_par_derivative}}{=}W_{i}-2\lambda
A_{i}.$

This holds if and only if

$\frac{W_{i}}{A_{i}}=2\lambda=const.$

∎

The Lagrange multiplier $\lambda$ satisfies

$\lambda=\pi\chi(S)$

by the discrete Gauss-Bonnet theorem.

######  Theorem (Discrete Gauss-Bonnet theorem).

Let $(S,V,d)$ be a piecewise flat surface with constant discrete Gaussian
curvature $K_{av}$ at every vertex. Denote the total area of the surface by
$A_{tot}$. Then,

$K_{av}=\frac{2\pi\chi(S)}{A_{tot}}.$

######  Fact 4.11 (Alternative variational principle to Theorem 4.10).

Up to global rescaling, the PL-metrics with constant discrete Gaussian
curvature in the conformal class of the metric $d$ are in one-to-one
correspondence with the critical points of the function

$\mathbb{F}:\mathbb{R}^{V}\to\mathbb{R},\qquad
u\mapsto\mathbb{F}(u)=\mathbb{E}(u)-\pi\chi(S)\log(A_{tot}).$

Indeed,

$0=\frac{\partial\mathbb{F}}{\partial
u_{i}}\overset{\eqref{eq:E_functional_first_par_derivative},\eqref{eq:area_functional_first_par_derivative}}{=}W_{i}-\frac{2\pi\chi(S)}{A_{tot}}A_{i}.$

This holds if and only if

$\frac{W_{i}}{A_{i}}=\frac{2\pi\chi(S)}{A_{tot}}.$

######  Theorem 4.12 (Variational principle with inequality constraints).

Let $(S,V,d)$ be a piecewise flat surface with $\chi(S)\neq 0$. The existence
of PL-metrics with constant discrete Gaussian curvature in the conformal class
of the metric $d$ follows from the existence of minima of the function
$\mathbb{E}$ under the following inequality constraints:

  * •

if the Euler characteristic of $S$ satisfies $\chi(S)=2$, the inequality
constraint is

$A_{tot}\geq 1,$

  * •

if the Euler characteristic of $S$ satisfies $\chi(S)<0$, the inequality
constraint is

$A_{tot}\leq 1.$

###### Proof.

Proposition 4.14 shows that if $u\in\mathbb{R}^{V}$ is a minimum of the
function $\mathbb{E}$ under one of these constraints, then $A_{tot}(u)=1$.
Since a minimum is a critical point, the claim follows from Theorem 4.10. ∎

######  Proposition 4.13.

The sets

$\mathcal{A}_{+}=\\{u\in\mathbb{R}^{V}\mid A_{tot}(u)\geq
1\\},\qquad\mathcal{A}_{-}=\\{u\in\mathbb{R}^{V}\mid A_{tot}(u)\leq 1\\},$

have the following properties:

  1. a)

The sets $\mathcal{A}_{+}$ and $\mathcal{A}_{-}$ are closed subsets of
$\mathbb{R}^{V}$.

  2. b)

Let $\mathbb{I}=(1,\dots,1)\in\mathbb{R}^{V}$, and let $u\in\mathbb{R}^{V}$ be
a conformal factor. Then the rays

$\mathcal{R}^{+}_{u}=\left\\{u+c\>\mathbb{I}\mid c\geq-\frac{1}{2}\log
A_{tot}(u)\right\\},\leavevmode\nobreak\
\mathcal{R}^{-}_{u}=\left\\{u+c\>\mathbb{I}\mid c\leq-\frac{1}{2}\log
A_{tot}(u)\right\\}$

are completely contained in the sets $\mathcal{A}_{+}$ and $\mathcal{A}_{-}$,
respectively. The sets $\mathcal{A}_{+}$ and $\mathcal{A}_{-}$ are thus
unbounded.

###### Proof.

  1. a)

The proof follows from the fact that the sets $\mathcal{A}_{+}$ and
$\mathcal{A}_{-}$ satisfy the equation

$\mathcal{A}_{+}=A_{tot}^{-1}([1,\infty)),\qquad\mathcal{A}_{-}=A_{tot}^{-1}([0,1]).$

  2. b)

The statement follows from the fact that

$A_{tot}(u+c\>\mathbb{I}))=A_{tot}(u)\exp(2c).$

∎

######  Proposition 4.14.

Let $(S,V,d)$ be a piecewise flat surface. If

  * •

the Euler characteristic of $S$ satisfies $\chi(S)=2$ and the function
$\mathbb{E}$ attains a minimum in the set $\mathcal{A}_{+}$, or

  * •

the Euler characteristic of $S$ satisfies $\chi(S)<0$ and the function
$\mathbb{E}$ attains a minimum in the set $\mathcal{A}_{-}$,

the minimum lies at the boundary of the sets,

$\partial\mathcal{A}_{+}=\partial\mathcal{A}_{-}=\left\\{u\in\mathbb{R}^{V}\mid
A_{tot}(u)=1\right\\}.$

###### Proof.

Let $\chi(S)=2$ and let $u\in\mathcal{A}_{+}$ be a minimum of the function
$\mathbb{E}$ in $\mathcal{A}_{+}$. We show that $A_{tot}(u)=1$. Let

$c=-\frac{1}{2}\log A_{tot}(u).$

Since $A_{tot}(u)\geq 1$, we know that $c\leq 0$. Further,
$u+c\>\mathbb{I}\in\mathcal{A}_{+}$ due to Proposition 4.13. Due to the
additive property of the function $\mathbb{E}$ (Proposition 4.5),

$\displaystyle\mathbb{E}(u)\leq\mathbb{E}(u+c\>\mathbb{I})=\mathbb{E}(u)+2\chi(S)\pi
c\Longrightarrow c\geq 0.$

This implies that $c=0$, and thus $A_{tot}(u)=1$.

For surfaces with $\chi(S)<0$ the proof is analogous. ∎

##  5 Existence of metrics with constant Gaussian curvature

In this section we prove Theorem 1.2. We build the proof on several key
observations of the behaviour of the sequence $(u_{n})_{n\in\mathbb{N}}$ of
conformal factors in $\mathbb{R}^{V}$. These observations are central for the
application of Theorem 5.1, from which the proof of Theorem 1.2 follows almost
immediately.

In Section 5.1 we reduce the proof of Theorem 1.2 to the proofs of Theorem 5.2
and Theorem 5.3. In Section 5.2 we study the behaviour of sequences of
conformal factors. Finally, in Section 5.3 we prove Theorem 5.2 and Theorem
5.3.

###  5.1 Reduction to Theorem 5.2 and Theorem 5.3

For surfaces of genus one ($\chi(S)=0$) the Yamabe problem is equivalent to
the discrete uniformization problem, which has been proved in [4, Theorem 1.2]
and [11, Theorem 11.1]. We prove Theorem 1.2 for surfaces with $\chi(S)<0$ and
$\chi(S)=2$. Due to Theorem 4.12, finding metrics with constant Gaussian
curvature is equivalent to finding the minima of the function $\mathbb{E}$ in
the set $\mathcal{A}_{-}$ if $\chi(S)<0$, and in the set $\mathcal{A}_{+}$ if
$\chi(S)=2$. To prove the existence of these minima we apply Theorem 5.1 – a
traditional theorem from calculus.

A sequence of real numbers $(x_{n})_{n\in\mathbb{N}}$ diverges properly to
$\mathbf{+\infty}$ if

$\lim_{n\to\infty}x_{n}=+\infty,$

that is if, for each $M\in\mathbb{R}$, there exists an $N\in\mathbb{N}$, such
that $x_{n}>M$ for all $n>N$.

A sequence of real numbers $(x_{n})_{n\in\mathbb{N}}$ diverges properly to
$\mathbf{-\infty}$ if the sequence $(-x_{n})_{n\in\mathbb{N}}$ diverges
properly to $+\infty$.

######  Theorem 5.1.

Let $A\subseteq\mathbb{R}^{m}$ be a closed set and let $f:A\to\mathbb{R}$ be a
continuous function. If every unbounded sequence $(x_{n})_{n\in\mathbb{N}}$ in
$A$ has a subsequence $(x_{n_{k}})_{k\in\mathbb{N}}$ such that

$\lim_{k\to\infty}f(x_{n_{k}})=+\infty,$

then $f$ attains a minimum in $A$.

We already verified that the majority of the conditions of Theorem 5.1 is
satisfied. Proposition 4.13 ensures that the sets $\mathcal{A}_{+}$ and
$\mathcal{A}_{-}$ are closed. Theorem 4.6 tells us that the function
$\mathbb{E}$ is continuous. To obtain the minima of $\mathbb{E}$ in the sets
$\mathcal{A}_{+}$ and $\mathcal{A}_{-}$, the following two theorems are left
to prove.

######  Theorem 5.2.

Let $\chi(S)<0$ and let $(u_{n})_{n\in\mathbb{N}}$ be an unbounded sequence in
$\mathcal{A}_{-}$. Then there exists a subsequence
$(u_{n_{k}})_{k\in\mathbb{N}}$ of $(u_{n})_{n\in\mathbb{N}}$, such that

$\lim_{k\to\infty}\mathbb{E}(u_{n_{k}})=+\infty.$

######  Theorem 5.3.

Let $\chi(S)=2$ and let $(u_{n})_{n\in\mathbb{N}}$ be an unbounded sequence in
$\mathcal{A}_{+}$. Then there exists a subsequence
$(u_{n_{k}})_{k\in\mathbb{N}}$ of $(u_{n})_{n\in\mathbb{N}}$, such that

$\lim_{k\to\infty}\mathbb{E}(u_{n_{k}})=+\infty.$

###  5.2 Behaviour of sequences of conformal factors

Fix a piecewise flat surface $(S,V,d)$ and let $(u_{n})_{n\in\mathbb{N}}$ be
an unbounded sequence in its discrete conformal class $\mathbb{R}^{V}$. We
denote its coordinate sequence at vertex $j\in V$ by
$(u_{j,n})_{n\in\mathbb{N}}$.

######  Convention 5.4.

Throughout this section we assume that the sequence $(u_{n})_{n\in\mathbb{N}}$
possesses the following properties:
• It lies in one Penner cell $\mathcal{A}_{\Delta}$ of $\mathbb{R}^{V}$. •
There exists a vertex $i^{*}\in V$ such that for all $j\in V$ and
$n\in\mathbb{N}$ $u_{i^{*},n}\leq u_{j,n}$. • Each coordinate sequence
$(u_{j,n})_{n\in\mathbb{N}}$ either converges, diverges properly to $+\infty$,
or diverges properly to $-\infty$. • For all $j\in V$ the sequences
$(u_{j,n}-u_{i^{*},n})_{n\in\mathbb{N}}$ either converge or diverge properly
to $+\infty$.

We may adopt Convention 5.4 without loss of generality because every sequence
in $\mathbb{R}^{V}$ possesses a subsequence that satisfies these properties.
The first property follows from a theorem by Hirotaka Akiyoshi.

######  Theorem (Hirotaka Akiyoshi [1]).

The set $\mathfrak{D}(S,V,d)$ of non-empty Penner cells is finite.

In addition, we use the following notation:

$\displaystyle\ell_{ij}^{n}:=\ell_{ij}\exp\left(\frac{u_{i,n}+u_{j,n}}{2}\right),$
(5)

where $\ell$ is the discrete metric induced by the PL-metric $d$ on
$(S,V,\Delta)$ (see Fact 2.3). Since the sequence $(u_{n})_{n\in\mathbb{N}}$
lies inside the Penner cell $\mathcal{A}_{\Delta}$, $\Delta$ is a Delaunay
triangulation of $(S,V,d(u_{n}))$ for all $n\in\mathbb{N}$ (see Definition
2.13). Furthermore, the map $\ell^{n}$ defined by Equation (5) is the discrete
metric induced on $(S,V,\Delta)$ by the PL-metric $d(u_{n})$ (see Proposition
2.14).

#### Behaviour of $\mathbf{(u_{n})_{n\in\mathbb{N}}}$ in one triangle

Consider a triangle in $F_{\Delta}$ with vertices labeled by $1,2,3\in V$ and
initial edge lengths $\ell_{12},\ell_{23},\ell_{31}$, uniquely determined by
$d$. Define

$\displaystyle\mathcal{A}_{123}:=\\{(u_{1},u_{2},u_{3})\mid
u\in\mathcal{A}_{\Delta}\\}.$ (6)

2pt $1$ [ ] at 48 81 $2$ [ ] at 532 21 $3$ [ ] at 329 363 $\alpha_{n}$ [ ] at
143 115 $\ell_{12}^{n}$ [ ] at 281 20 $\ell_{31}^{n}$ [ ] at 160 261
$\ell_{23}^{n}$ [ ] at 430 220

Figure 5.1: Sequences of edge lengths on triangle 123.

Let $(u_{1,n},u_{2,n},u_{3,n})_{n\in\mathbb{N}}$ be a sequence in
$\mathcal{A}_{123}$. Then the edge lengths
$\ell_{12}^{n},\ell_{23}^{n},\ell_{31}^{n}$ satisfy the triangle inequalities
for all $n\in\mathbb{N}$.

######  Lemma 5.5.

If
$u_{1,n}\xrightarrow{n\to\infty}\infty,u_{2,n}\xrightarrow{n\to\infty}\infty$
and the sequence $(u_{3,n})_{n\in\mathbb{N}}$ is bounded from above, there
exists an $n\in\mathbb{N}$ such that

$\ell_{12}^{n}>\ell_{23}^{n}+\ell_{31}^{n}.$

In other words, there exists no sequence in $\mathcal{A}_{123}$ where two of
the coordinate sequences would diverge properly to $+\infty$ and the third one
would be bounded from above.

###### Proof.

Without loss of generality we may assume that $u_{1,n}\leq u_{2,n}$ for all
$n\in\mathbb{N}$. Then

$\displaystyle 0$
$\displaystyle<\ell_{12}=\exp\left(\frac{-u_{1,{n}}-u_{2,{n}}}{2}\right)\ell_{12}^{n}$
$\displaystyle\overset{\Delta\text{-ineq.}}{\leq}\exp\left(\frac{-u_{1,{n}}-u_{2,{n}}}{2}\right)(\ell_{23}^{n}+\ell_{31}^{n})$
$\displaystyle=\exp\left(\frac{u_{3,{n}}-u_{1,{n}}}{2}\right)\left(\ell_{23}+\ell_{31}\underbrace{\exp\left(\frac{u_{1,{n}}-u_{2,{n}}}{2}\right)}_{\leq
1}\right)$
$\displaystyle\leq\exp\left(\frac{u_{3,{n}}-u_{1,{n}}}{2}\right)(\ell_{23}+\ell_{31})\xrightarrow{{n}\to\infty}0.$

This contradicts the triangle inequality

$\ell_{12}^{n}\leq\ell_{23}^{n}+\ell_{31}^{n}.$

∎

Lemma 5.5 yields the following key observation:

######  Corollary 5.6.

At every triangle $ijk\in F_{\Delta}$, at least two of the three sequences
$(u_{i,n}-u_{i^{*},n})_{n\in\mathbb{N}}$,
$(u_{j,n}-u_{i^{*},n})_{n\in\mathbb{N}}$,
$(u_{k,n}-u_{i^{*},n})_{n\in\mathbb{N}}$ converge.

###### Proof.

The claim holds for any triangle with vertex $i^{*}$ due to Lemma 5.5. It
holds for all remaining triangles in $F_{\Delta}$ due to the connectivity of
the triangulation. ∎

######  Lemma 5.7.

Assume that the sequence $(u_{1,{n}})_{n\in\mathbb{N}}$ diverges properly to
$+\infty$ and the sequences $(u_{2,{n}})_{n\in\mathbb{N}}$ and
$(u_{3,{n}})_{n\in\mathbb{N}}$ converge. Then

$\frac{\ell_{12}^{n}}{\ell_{31}^{n}}\xrightarrow{n\to\infty}1,$

and the sequence of angles $\alpha_{n}$, opposite to the edge $23$ in the
triangle with edge lengths $\ell_{12}^{n},\ell_{23}^{n},\ell_{31}^{n}$,
satisfies

$\alpha_{n}\xrightarrow{n\to\infty}0.$

###### Proof.

Dividing both sides of the triangle inequality
$\ell_{31}^{n}\leq\ell_{23}^{n}+\ell_{12}^{n}$ by $\ell_{31}^{n}$ yields the
inequality

$\displaystyle
1\leq\frac{\ell_{23}^{n}}{\ell_{31}^{n}}+\frac{\ell_{12}^{n}}{\ell_{31}^{n}}=\frac{\ell_{23}}{\ell_{31}}\exp\left(\frac{1}{2}(u_{2,n}-u_{1,n})\right)+\frac{\ell_{12}^{n}}{\ell_{31}^{n}}.$

Dividing both sides of the triangle inequality
$\ell_{12}^{n}\leq\ell_{23}^{n}+\ell_{31}^{n}$ by $\ell_{12}$ yields the
inequality

$\displaystyle
1\leq\frac{\ell_{23}}{\ell_{12}}\exp\left(\frac{1}{2}(u_{3,n}-u_{1,n})\right)+\frac{\ell_{31}^{n}}{\ell_{12}^{n}}.$

Since, for
$i=2,3,\exp\left(\frac{1}{2}(u_{i,n}-u_{1,n})\right)\xrightarrow[]{n\to\infty}0,$
we obtain

$\frac{\ell_{23}^{n}}{\ell_{31}^{n}}\xrightarrow[]{n\to\infty}0,\qquad\frac{\ell_{23}^{n}}{\ell_{12}^{n}}\xrightarrow[]{n\to\infty}0.$

The convergence of the fraction $\frac{\ell_{12}^{n}}{\ell_{31}^{n}}$ follows
from the inequalities

$1\leq\lim_{n\to\infty}\frac{\ell_{12}^{n}}{\ell_{31}^{n}}\leq 1.$

From the cosine rule we obtain the convergence

$\displaystyle
2\cos\alpha_{n}=\frac{\ell_{12}^{n}}{\ell_{31}^{n}}+\frac{\ell_{31}^{n}}{\ell_{12}^{n}}-\frac{(\ell_{23}^{n})^{2}}{\ell_{31}^{n}\ell_{12}^{n}}\xrightarrow[]{n\to\infty}2,$

and thus $\alpha_{n}\xrightarrow[]{n\to\infty}0.$ ∎

#### Behaviour of $\mathbf{(u_{n})_{n\in\mathbb{N}}}$ around a vertex star

Let $i\in V$ be a vertex such that the sequence $(u_{i,n})_{n\in\mathbb{N}}$
diverges properly to $+\infty$ and the sequences $(u_{j,n})_{n\in\mathbb{N}}$
at any neighbour $j\in V$ converge. We investigate the behaviour of angles in
triangles with vertex $i$.

2pt $0$ [ ] at 278 330 $1$ [ ] at 423 497 $j$ [ ] at 161 0 $j+1$ [ ] at 462 22
$2$ [ ] at 179 442 $s$ [ ] at 602 306

$\alpha_{j}^{0,j+1}$ [ ] at 208 37 $\alpha_{j+1}^{0,j}$ [ ] at 395 73
$\alpha_{0}^{j,j+1}$ [ ] at 286 214 $\ell_{0,j}^{n}$ [ ] at 178 159
$\ell_{0,j+1}^{n}$ [ ] at 402 195

Figure 5.2:  Labeling in a vertex star.

A vertex star around vertex $i$ is the subset $F_{\Delta}^{i}\subseteq
F_{\Delta}$ of triangles in $F_{\Delta}$ that contain the vertex $i$. We
denote the degree of the vertex $i$ by $s$ and label the vertices as in Figure
5.2. We drop the index $n$ that denotes the elements in the sequence when we
label angles. Whenever the labeling requires it we use the conventions $1-1=s$
and $s+1=1$.

######  Proposition 5.8.

The sequences of angles in the triangles of $F_{\Delta}^{i}$ satisfy

$\lim_{n\to\infty}\alpha^{j,j+1}_{0}=0,\qquad\lim_{n\to\infty}\alpha^{j,0}_{j+1}=\lim_{n\to\infty}\alpha^{j+1,0}_{j}=\pi/2,\qquad
j\in\\{1,\dots,s\\}.$

###### Proof.

Denote the limit of a sequence of angles $\alpha^{i,j}_{k}$ along
$(u_{n})_{n\in\mathbb{N}}$ by $\bar{\alpha}^{i,j}_{k}$. Due to Lemma 5.7,

$\bar{\alpha}_{0}^{j,j+1}=0,$

and thus, for all $j=1,\dots,s$,

$\displaystyle\bar{\alpha}_{j}^{0,j+1}+\bar{\alpha}_{j+1}^{0,j}=\pi.$ (7)

Since the edges $0j$ are Delaunay, the Delaunay inequality

$\displaystyle\bar{\alpha}_{j-1}^{0,j}+\bar{\alpha}_{j+1}^{0,j}\leq\pi$ (8)

is satisfied for each $j\in\\{1,\dots,s\\}$. Summing up the Delaunay
inequalities we obtain

$\displaystyle\pi
s\overset{\eqref{eq:Delaunay_ineq_eq}}{\geq}\sum_{j=1}^{s}(\bar{\alpha}_{j-1}^{0,j}+\bar{\alpha}_{j+1}^{0,j})=\sum_{j=1}^{s}(\bar{\alpha}_{j}^{0,j+1}+\bar{\alpha}_{j+1}^{0,j})\overset{\eqref{eq:angle_sum}}{=}\pi
s.$

In other words, each Delaunay inequality (8) becomes an equality in the limit.
Due to equality (7),

$\displaystyle\bar{\alpha}_{j-1}^{0,j}=\bar{\alpha}_{1}^{0,2},\qquad\bar{\alpha}_{j}^{0,j-1}=\pi-\bar{\alpha}_{1}^{0,2},$

for all $j\in\\{1,\dots,s\\}$.

To show that $\bar{\alpha}_{1}^{0,2}=\pi/2$, we apply the following equation:

In a triangle with sides $a,b,c$, and opposite angles $\alpha,\beta,\gamma$,

$\displaystyle
b-a=c\frac{\sin\left(\frac{\alpha-\beta}{2}\right)}{\cos\left(\frac{\gamma}{2}\right)}.$
(9)

Denote the limit of the lengths of edges $\ell_{j,j+1}^{n}$ by
$\lim_{n\to\infty}\ell_{j,j+1}^{n}=\bar{\ell}_{j,j+1}.$ Since, for all
$n\in\mathbb{N}$, holds

$\sum_{j=1}^{s}\left(\ell_{0,j+1}^{n}-\ell_{0,j}^{n}\right)=0,$

in the limit

$\displaystyle
0=\lim_{n\to\infty}\sum_{j=1}^{s}\left(\ell_{0,j+1}^{n}-\ell_{0,j}^{n}\right)\overset{\eqref{eq:edge_difference}}{=}\sin\left(\frac{\pi-2\bar{\alpha}_{1}^{0,2}}{2}\right)\sum_{j=1}^{s}\bar{\ell}_{j,j+1}.$

Since, for all $j=1,\dots,s$, the sequences of conformal factors
$(u_{j,n})_{n\in\mathbb{N}}$ converge,

$\sum_{j=1}^{s}\bar{\ell}_{j,j+1}>0.$

We deduce that

$\sin\left(\frac{\pi-2\bar{\alpha}_{1}^{0,2}}{2}\right)=0,$

and thus $\bar{\alpha}_{1}^{0,2}=\pi/2.$ ∎

#### Behaviour of the function $\mathbb{E}$ along
$\mathbf{(u_{n})_{n\in\mathbb{N}}}$

Recall the definitions of the function $f$ (Definition 4.1) and the set
$\mathcal{A}_{123}$ (Equation (6)). Let

$h:\mathcal{A}_{123}\to\mathbb{R},\qquad
h(u_{1},u_{2},u_{3}):=2f\left(\frac{\tilde{\lambda}_{12}}{2},\frac{\tilde{\lambda}_{23}}{2},\frac{\tilde{\lambda}_{31}}{2}\right)-\frac{\pi}{2}(\tilde{\lambda}_{12}+\tilde{\lambda}_{23}+\tilde{\lambda}_{31}).$

######  Lemma 5.9.

For any real number $v\in\mathbb{R}$, the function $h$ satisfies the equation

$h((u_{1},u_{2},u_{3})+v(1,1,1))=h(u_{1},u_{2},u_{3})-\pi v.$

###### Proof.

Follows from the property of the function $f$ from Proposition 4.5. ∎

######  Proposition 5.10.

Let $(u_{1,n},u_{2,n},u_{3,n})_{n\in\mathbb{N}}$ be a sequence in
$\mathcal{A}_{123}$. Suppose that

$u_{1,n}\xrightarrow{n\to\infty}\infty,\qquad
u_{2,n}\xrightarrow{n\to\infty}\overline{u_{2}},\qquad
u_{3,n}\xrightarrow{n\to\infty}\overline{u_{3}}.$

Then the sequence $(h(u_{1,n},u_{2,n},u_{3,n}))_{n\in\mathbb{N}}$ converges,
and in particular

$\lim_{n\to\infty}h(u_{1,n},u_{2,n},u_{3,n})=-\pi\left(\log\ell_{23}+\frac{1}{2}(\overline{u_{2}}+\overline{u_{3}})\right).$

###### Proof.

2pt $1$ [ ] at 48 81 $2$ [ ] at 532 21 $3$ [ ] at 329 363 $\alpha_{n}$ [ ] at
133 120 $\beta_{n}$ [ ] at 433 79 $\gamma_{n}$ [ ] at 291 295
$\ell_{12}^{n}=\exp(z_{n})$ [ ] at 261 40  $\ell_{31}^{n}=\exp(y_{n})$ [ ] at
180 251  $\ell_{23}^{n}=\exp(x_{n})$ [ ] at 420 220

Figure 5.3:

Consider the notation as in Figure 5.3. Then,

$\displaystyle\frac{1}{2}h(u_{1,n},u_{2,n},u_{3,n})=$
$\displaystyle\alpha_{n}x_{n}+\beta_{n}y_{n}+\gamma_{n}z_{n}+\mathbb{L}(\alpha_{n})+\mathbb{L}(\beta_{n})+\mathbb{L}(\gamma_{n})$
$\displaystyle\qquad-\frac{\pi}{2}(x_{n}+y_{n}+z_{n}).$

In the limit, the sequences
$(x_{n})_{n\in\mathbb{N}},(y_{n})_{n\in\mathbb{N}}$ and
$(z_{n})_{n\in\mathbb{N}}$ satisfy

$\lim_{n\to\infty}x_{n}=\log\ell_{23}+\frac{1}{2}(\overline{u_{2}}+\overline{u_{3}})=:\overline{x},\qquad\lim_{n\to\infty}y_{n}=+\infty,\qquad\lim_{n\to\infty}z_{n}=+\infty,$

and, due to Proposition 5.8,

$\lim_{n\to\infty}(\alpha_{n},\beta_{n},\gamma_{n})=\left(0,\frac{\pi}{2},\frac{\pi}{2}\right).$

Thus,

$\lim_{n\to\infty}\alpha_{n}x_{n}=0,$

and, since the Lobachevsky function is continuous and satisfies the equality
$\mathbb{L}(0)=\mathbb{L}\left(\frac{\pi}{2}\right)=0$ (see Fact 4.2), in the
limit we obtain

$\lim_{n\to\infty}(\mathbb{L}(\alpha_{n})+\mathbb{L}(\beta_{n})+\mathbb{L}(\gamma_{n}))=0.$

In summary,

$\displaystyle\lim_{n\to\infty}h(u_{1,n},u_{2,n},u_{3,n})=2\lim_{n\to\infty}\left[\left(\beta_{n}-\frac{\pi}{2}\right)y_{n}+\left(\gamma_{n}-\frac{\pi}{2}\right)z_{n}\right]-\pi\overline{x}.$

We rearrange the expression
$\left(\beta_{n}-\frac{\pi}{2}\right)y_{n}+\left(\gamma_{n}-\frac{\pi}{2}\right)z_{n}$
to obtain

$\left(\beta_{n}-\frac{\pi}{2}\right)y_{n}+\left(\gamma_{n}-\frac{\pi}{2}\right)z_{n}=-\frac{1}{2}\alpha_{n}(y_{n}+z_{n})+\frac{1}{2}(\beta_{n}-\gamma_{n})(y_{n}-z_{n}).$

In the limit, $\lim_{n\to\infty}(\beta_{n}-\gamma_{n})=0,$ and

$\displaystyle\lim_{n\to\infty}(y_{n}-z_{n})$
$\displaystyle=\log\ell_{31}-\log\ell_{12}+\frac{1}{2}(\overline{u_{3}}-\overline{u_{2}}).$

Thus,

$\displaystyle\lim_{n\to\infty}\frac{1}{2}(\beta_{n}-\gamma_{n})(y_{n}-z_{n})=0.$

It is left to determine the limit

$\displaystyle\lim_{n\to\infty}\alpha_{n}(y_{n}+z_{n})$
$\displaystyle=\lim_{n\to\infty}\alpha_{n}\log\ell_{31}^{n}+\lim_{n\to\infty}\alpha_{n}\log\ell_{12}^{n}.$

We apply the sine rule and the L’Hospital’s rule to obtain the expression

$\displaystyle\lim_{n\to\infty}\alpha_{n}\log\ell_{31}^{n}$
$\displaystyle=\lim_{n\to\infty}({\alpha_{n}}{\log\ell_{23}^{n}}+\alpha_{n}{\log\sin\beta_{n}}-\alpha_{n}\log\sin\alpha_{n})$
$\displaystyle=-\lim_{n\to\infty}\alpha_{n}\log\sin\alpha_{n}=0.$

Similarly, $\lim_{n\to\infty}\alpha_{n}\log\ell_{12}^{n}=0.$

Altogether, we see that

$\lim_{n\to\infty}h(u_{1,n},u_{2,n},u_{3,n})=-\pi\overline{x}.$

∎

######  Lemma 5.11.

There exists a convergent sequence $(C_{n})_{n\in\mathbb{N}}$ such that the
function $\mathbb{E}$ satisfies

$\displaystyle\mathbb{E}(u_{n})=C_{n}+2\pi\left(u_{i^{*},n}\chi(S)+\sum_{j\in
V}(u_{j,n}-u_{i^{*},n})\right).$

###### Proof.

Due to the Euler formula, $2|V|-|F_{\Delta}|=2\chi(S).$ Applying Lemma 5.9 we
obtain the equality

$\displaystyle\mathbb{E}(u_{n})$ $\displaystyle=\sum_{ijl\in
F_{\Delta}}h(u_{i,n},u_{j,n},u_{l,n})+2\pi\sum_{j\in V}u_{j,n}$
$\displaystyle=\underbrace{\sum_{ijl\in
F_{\Delta}}h((u_{i,n},u_{j,n},u_{l,n})-u_{i^{*},n}(1,1,1))}_{=:C_{n}}-\pi|F_{\Delta}|u_{i^{*},n}+2\pi\sum_{j\in
V}u_{j,n}$ $\displaystyle=C_{n}+2\pi\left(u_{i^{*},n}\chi(S)+\sum_{j\in
V}(u_{j,n}-u_{i^{*},n})\right).$

The sequence $(C_{n})_{n\in\mathbb{N}}$ converges due to Corollary 5.6 and
Proposition 5.10. ∎

#### Influence of $\mathbf{(u_{n})_{n\in\mathbb{N}}}$ on the area of a
triangle

######  Lemma 5.12.

Let $ijk\in F_{\Delta}$ such that the sequences
$(u_{j,{n}}-u_{i^{*},{n}})_{n\in\mathbb{N}}$ and
$(u_{k,{n}}-u_{i^{*},{n}})_{n\in\mathbb{N}}$ converge. Denote by $A_{ijk}^{n}$
the area of the triangle with edge lengths
$\ell_{ij}^{n},\ell_{jk}^{n},\ell_{ki}^{n}.$

  1. a)

If the sequence $(u_{i,{n}}-u_{i^{*},{n}})_{n\in\mathbb{N}}$ converges, there
exists a convergent sequence of real numbers $(C_{n})_{n\in\mathbb{N}}$, such
that the area of the triangle with edge lengths
$\ell_{ij}^{n},\ell_{jk}^{n},\ell_{ki}^{n}$ satisfies

$\log A_{ijk}^{n}=C_{n}+2u_{i^{*},{n}}.$

  2. b)

If the sequence $(u_{i,{n}}-u_{i^{*},{n}})_{n\in\mathbb{N}}$ diverges to
$+\infty$, there exists a convergent sequence of real numbers
$(C_{n})_{n\in\mathbb{N}}$, such that the area of the triangle with edge
lengths $\ell_{ij}^{n},\ell_{jk}^{n},\ell_{ki}^{n}$ satisfies

$\log A_{ijk}^{n}=C_{n}+\frac{1}{2}(u_{i,{n}}+3u_{i^{*},{n}}).$

###### Proof.

The proof follows from the continuity of the area function, from Convention
5.4 and from Corollary 5.6. ∎

###  5.3 Proofs of Theorem 5.2 and Theorem 5.3

######  Theorem (Theorem 5.2).

Let $\chi(S)<0$ and let $(u_{n})_{n\in\mathbb{N}}$ be an unbounded sequence in
$\mathcal{A}_{-}$. Then there exists a subsequence
$(u_{n_{k}})_{k\in\mathbb{N}}$ of $(u_{n})_{n\in\mathbb{N}}$, such that

$\lim_{k\to\infty}\mathbb{E}(u_{n_{k}})=+\infty.$

###### Proof.

We assume that the sequence $(u_{n})_{n\in\mathbb{N}}$ satisfies Convention
5.4. Due to Lemma 5.11 there exists a convergent sequence
$(C_{n})_{n\in\mathbb{N}}$ such that

$\displaystyle\mathbb{E}(u_{n})=C_{n}+2\pi\left(u_{i^{*},n}\chi(S)+\sum_{j\in
V}(u_{j,n}-u_{i^{*},n})\right).$

The sequence

$\left(\sum_{j\in V}(u_{j,n}-u_{i^{*},n})\right)_{n\in\mathbb{N}}$

is bounded from below by zero due to Convention 5.4.

Since the sequence $(u_{n})_{n\in\mathbb{N}}$ lies in $\mathcal{A}_{-}$, the
area of each triangle is bounded from above. At the same time
$(u_{n})_{n\in\mathbb{N}}$ is unbounded. Applying Lemma 5.12 we conclude that
the sequence $(u_{i^{*},n})_{n\in\mathbb{N}}$ diverges properly to $-\infty$.
Thus,

$\lim_{n\to\infty}\mathbb{E}(u_{n})=+\infty.$

∎

######  Theorem (Theorem 5.3).

Let $\chi(S)=2$ and let $(u_{n})_{n\in\mathbb{N}}$ be an unbounded sequence in
$\mathcal{A}_{+}$. Then there exists a subsequence
$(u_{n_{k}})_{k\in\mathbb{N}}$ of $(u_{n})_{n\in\mathbb{N}}$, such that

$\lim_{k\to\infty}\mathbb{E}(u_{n_{k}})=+\infty.$

###### Proof.

We assume that the sequence $(u_{n})_{n\in\mathbb{N}}$ satisfies Convention
5.4. Due to Lemma 5.11 there exists a convergent sequence
$(C_{n})_{n\in\mathbb{N}}$ such that

$\displaystyle\mathbb{E}(u_{n})=C_{n}+2\pi\left(2u_{i^{*},n}+\sum_{j\in
V}(u_{j,n}-u_{i^{*},n})\right).$

The sequence

$\left(\sum_{j\in V}(u_{j,n}-u_{i^{*},n})\right)_{n\in\mathbb{N}}$

is bounded from below by zero due to Convention 5.4. We distinguish three
cases.

Case 1: The sequence $\mathbf{(u_{i^{*},n})_{n\in\mathbb{N}}}$ diverges
properly to $\mathbf{+\infty}.$
It follows immediately that

$\lim_{n\to\infty}\mathbb{E}(u_{n})=+\infty.$

Case 2: The sequence $\mathbf{(u_{i^{*},n})_{n\in\mathbb{N}}}$ converges.
Since the sequence $(u_{n})_{n\in\mathbb{N}}$ is unbounded, there exists a
vertex $j\in V$ with $\lim_{n\to\infty}(u_{j,n}-u_{i^{*},n})=+\infty$. Thus,

$\lim_{n\to\infty}\mathbb{E}(u_{n})=+\infty.$

Case 3: The sequence $\mathbf{(u_{i^{*},n})_{n\in\mathbb{N}}}$ diverges
properly to $\mathbf{-\infty}.$
There exists a vertex $i\in V$, such that the sequence
$(u_{i,{n}}+3u_{i^{*},{n}})_{n\in\mathbb{N}}$ is bounded from below. This is
due to Lemma 5.12 and the fact that the sequence $(u_{n})_{n\in\mathbb{N}}$
lies in $\mathcal{A}_{+}$, and thus there exists a triangle whose area is non-
zero in the limit. We obtain

$\displaystyle 2u_{i^{*},n}+\sum_{j\in V}(u_{j,n}-u_{i^{*},n})$
$\displaystyle=-2u_{i^{*},n}+(u_{i,n}+3u_{i^{*},n})+\sum_{j\in V,j\neq
i}(u_{j,n}-u_{i^{*},n}).$

Since both sequences

$\left(\sum_{j\in V,j\neq
i}(u_{j,n}-u_{i^{*},n})\right)_{n\in\mathbb{N}}\qquad\text{and}\qquad(u_{i,n}+3u_{i^{*},n})_{n\in\mathbb{N}}$

are bounded from below, and the sequence $(-2u_{i^{*},n})_{n\in\mathbb{N}}$
diverges properly to $+\infty$,

$\lim_{n\to\infty}\mathbb{E}(u_{n})=+\infty.$

∎

#### Acknowledgements.

This research was supported by DFG SFB/Transregio 109 “Discretization in
Geometry and Dynamics”.

## References

  * [1] H. Akiyoshi.  Finiteness of polyhedral decompositions of cusped hyperbolic manifolds obtained by the Epstein-Penner’s method.  Proc. Amer. Math. Soc., 129(8):2431–2439, 2001.
  * [2] A. I. Bobenko, U. Pinkall, and B. A. Springborn.  Discrete conformal maps and ideal hyperbolic polyhedra.  Geom. Topol., 19(4):2155–2215, 2015.
  * [3] H. Ge and X. Xu.  A combinatorial Yamabe problem on two and three dimensional manifolds.  Calc. Var. Partial Differential Equations, 60(1):Paper No. 20, 45, 2021.
  * [4] X. D. Gu, F. Luo, J. Sun, and T. Wu.  A discrete uniformization theorem for polyhedral surfaces.  J. Differential Geom., 109(2):223–256, 2018.
  * [5] H. Kouřimská.  Polyhedral surfaces of constant curvature and discrete uniformization.  PhD thesis, Technische Universität Berlin, 2020.
  * [6] F. Luo.  Combinatorial Yamabe flow on surfaces.  Commun. Contemp. Math., 6(5):765–780, 2004.
  * [7] J. Milnor.  Hyperbolic geometry: the first 150 years.  Bull. Amer. Math. Soc. (N.S.), 6(1):9–24, 1982.
  * [8] R. C. Penner.  The decorated Teichmüller space of punctured surfaces.  Comm. Math. Phys., 113(2):299–339, 1987.
  * [9] T. Regge.  General relativity without coordinates.  Nuovo Cimento (10), 19:558–571, 1961.
  * [10] M. Roček and R. M. Williams.  The quantization of Regge calculus.  Zeitschrift für Physik C Particles and Fields, 21(4):371–381, Dec 1984.
  * [11] B. Springborn.  Ideal hyperbolic polyhedra and discrete uniformization.  Discrete Comput. Geom., 64(1):63–108, 2020.


# Experimental Evaluation of Air-to-Ground VHF Band Communication for UAV
Relays

Boris Galkin1 1 Tyndall National Institute, Ireland; 2 Irish Defence Forces; 3
A-techSYN Ltd.
4 University College Cork, Ireland; 5 Trinity College Dublin, Ireland
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Lester Ho1 1 Tyndall
National Institute, Ireland; 2 Irish Defence Forces; 3 A-techSYN Ltd.
4 University College Cork, Ireland; 5 Trinity College Dublin, Ireland
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Ken Lyons2 1 Tyndall
National Institute, Ireland; 2 Irish Defence Forces; 3 A-techSYN Ltd.
4 University College Cork, Ireland; 5 Trinity College Dublin, Ireland
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Gokhan Celik3 1 Tyndall
National Institute, Ireland; 2 Irish Defence Forces; 3 A-techSYN Ltd.
4 University College Cork, Ireland; 5 Trinity College Dublin, Ireland
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>and Holger
Claussen1,4,5 1 Tyndall National Institute, Ireland; 2 Irish Defence Forces; 3
A-techSYN Ltd.
4 University College Cork, Ireland; 5 Trinity College Dublin, Ireland
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Unmanned Aerial Vehicles (UAVs) are a disruptive technology that is
transforming a range of industries. Because they operate in the sky, UAVs are
able to take advantage of strong Line-of-Sight (LoS) channels for radio
propagation, allowing them to communicate over much larger distances than
equivalent hardware located at ground level. This has attracted the attention
of organisations such as the Irish Defence Forces (DF), with whom we are
developing a UAV-based radio relay system as part of the MISTRAL project. This
relay system will support digital Very High Frequency (VHF) band communication
between ground personnel, while they are deployed on missions. In this paper
we report on the initial set of experimental measurements which were carried
out to verify the feasibility of VHF signal relaying via UAV. In our
experiments, a UAV carrying a lightweight Software-Defined Radio (SDR)
receiver is positioned at a height of 500 meters above ground, while two 5W
transmitters travel in vehicles on the ground. The SDR receiver measures the
received signal power, while the Global Positioning System (GPS) coordinates
of the vehicles are logged. This is combined to measure the signal pathloss
over distance. Our results show that the signal is received successfully at
distances of over 50 kilometers away. While the signals still appear to suffer
from a degree of obstacle blockage and multipath effects, these communication
ranges are a substantial improvement over the ground communication baseline,
and validate the use of UAVs to support wide area emergency communication.

###### Index Terms:

UAV, VHF, aerial, relay, experimental measurements

##  I Introduction

Unmanned Aerial Vehicles (UAVs) are a disruptive technology that is being
adopted in a wide variety of applications, from performing rapid medical
deliveries[1], to inspecting hard-to-reach infrastructure such as wind
turbines[2]. The telecommunications community have also recognised the
potential that UAVs can play in wireless communications applications [3].
Because they operate in the sky, UAVs experience unobstructed Line-of-Sight
(LoS) across very long distances, which means that radio signals coming to and
from a UAV node will avoid signal blockage caused by obstacles such as trees,
buildings, and even terrain features like mountains. This can allow a
relatively small number of UAVs equipped with radio equipment to provide
connectivity over a much larger area, compared to an equivalent network of
ground-based infrastructure. The capability of UAV-based emergency backup
networks was demonstrated by the Alphabet Loon project in Puerto Rico in
response to the devastation caused by Hurricane Maria [4].

UAV-based radio networks are an attractive solution for organisations that
operate in remote areas with unreliable or unavailable infrastructure, such as
the Irish Defence Forces (DF). The Irish DF make use of Very High Frequency
(VHF) radio communications during their deployments. During overseas missions,
DF vehicle convoys may travel hundreds of kilometers on missions that last
several days. Due to the distances involved, personnel often find themselves
out of range for reliable VHF communications, and have to rely on slower High
Frequency (HF) communication.

The Science Foundation Ireland (SFI)-funded project MISTRAL is developing a
network of UAVs that will fly in the air at heights of several hundred meters
to several kilometers, and retransmit radio communications between ground
personnel, taking advantage of the LoS channel conditions. As part of this
project, an experimental measurement campaign is carried out, to determine the
propagation conditions of VHF-band radio signals over ground-to-air links. In
this paper, we report the results of our first round of measurements.

Prior experimental work on UAV communication published by the research
community tends to investigate UAVs supporting data communication in the
higher-frequency bands, such as the ISM or cellular bands [5]. In [6] the
authors investigated UAV communication via the 2.4 GHz and GPRS bands, and
have shown successful video transmission at distances of 50 km. In [7] the
authors investigated UAV connectivity to Long Term Evolution (LTE) networks
belonging to multiple operators in a rural environment. In [8] the authors
investigated UAV LTE connectivity in a suburban environment, with an
exploration of the impact of antenna downtilt on performance. In [9] the
authors investigated short range UAV communication in the $3.1-4.8$ GHz bands.
A similar analysis was carried out in [10] for an urban environment, where
building reflections were taken into consideration. The works [11] and [12]
explored the performance of UAVs connecting to 5G macrocells and small cells,
respectively, in urban environments. In [13] the authors investigated
millimeter-wave UAV communication in the 60GHz band, and demonstrated the
issues surrounding beam alignment.

To the best of our knowledge, there has been no published set of experimental
results on the communication performance of UAVs in the VHF band. Furthermore,
with the exception of [6] and [7] above, published results on experimental UAV
communication trials tend to focus on short-range communication scenarios,
which are of less relevance to the scenario of basic emergency communication
across a wide area. Given this, there is a significant lack of published
information on the performance of UAVs acting as long-range VHF relays,
despite the prevalent use of VHF communication systems in maritime, emergency
response, and military applications. Our work differs from the state of the
art by focusing on VHF-band voice communication across distances in the order
of tens of kilometers, with UAVs operating at heights of several hundred
meters. The results in this paper are therefore of relevance to scenarios
where UAVs are used to support emergency communication across long distances.

This paper is structured as follows. In Section II we describe the
experimental setup, including a description of the test location and the
equipment used. In Section III we present the results of our experiments and
discuss our findings. In Section IV we summarise our conclusions and propose
future directions for our work.

##  II Experiment Description

The experimental measurements are intended to mimic the typical behaviour of a
convoy of Irish DF vehicles, when performing a humanitarian mission. These
convoys travel away from a forward operating base (FOB) towards a destination
such as a village. Throughout their journey, they must maintain continuous
communication links with the FOB.

To replicate this behaviour, we consider an area around the Curragh military
camp located in County Kildare, Ireland, as shown in Figure 1. The camp is
situated in a rural region, with fields surrounding it on all sides. The
terrain is relatively flat, with gradual height variations of several meters.
There are several built-up areas in the region of interest, these are suburban
towns and housing estates with low-rise buildings. The M7 motorway passes
close to the camp in an approximately east-west heading.

Figure 1: Satellite photograph of the Curragh camp and its surroundings, Co.
Kildare, Ireland

The experiment consists of two measurement phases. In the first phase, we
measure the VHF channel at ground level. A VHF transmitter is used to
broadcast a signal at regular intervals, from inside a moving vehicle which is
travelling around the camp surroundings. The Global Positioning System (GPS)
coordinates of the vehicle are logged at the transmitter, while the receiver
stores the received signal power with timestamps. In the second phase, the
receiver is attached to a UAV which is positioned 500 meters above the camp.
Two transmitters broadcast from inside moving vehicles which are travelling in
opposite directions on the motorway. As before, the GPS tracks of these
vehicles are logged, alongside the timestamped received signal powers.

We make use of Motorola DP4801e digital VHF handsets for transmitting the
signals under investigation. These handsets have a 5W transmit power with a
digital wideband waveform shown in Figure 2, and are tuned to a center
frequency of 160.4 MHz. These handset models are currently in use by the Irish
DF which motivates our decision to use them in the experiments; however, they
are civilian-grade handsets which are not subject to any export regulations,
and are designed for a variety of commercial and industrial applications in
the civilian space. As such, the measurement results obtained from using these
handsets are widely applicable to other civilian VHF equipment. We choose the
160.4 MHz frequency as it falls inside spectrum that is allocated for maritime
and business radio in Ireland, and is therefore commonly used by civilian
organisations in outdoor scenarios.

Figure 2: waterfall plot of the handset waveform

Our Software-Defined Radio (SDR) receiver is an RTL-SDR dongle connected to a
Raspberry Pi 3, which is powered by a USB powerbank as shown in Figure 3. The
dongle has a telescopic whip antenna which is fully extended to a length of 88
cm. The small form factor and light weight of this setup allows us to attach
it to a UAV for the aerial measurements. We use the RTL Python libraries to
run a script on the Raspberry Pi which periodically checks the signal power on
the 160.4MHz band. From testing, we confirm that the noise floor of the SDR is
in the order of $-$105 dBm.

1$N=64$

2$n=1024$

3while  _(Recording is not manually terminated)_ do

4

5 for  _$i=1...N$_ do

6 $s=$ ReadSamples($n$) $\triangleright$ Read $n$ samples from SDR

7 $PSD_{i}=(\textrm{FFT}(s)/n)^{2}$ $\triangleright$ Calculate PSD for
$i^{th}$ measurement

8 end for

9

10
$\overline{PSD}_{\textrm{max}}=\textrm{max}(\frac{1}{N}\sum_{i=1}^{N}PSD_{i}$)

11 Record $\overline{PSD}_{\textrm{max}}$ and timestamp to disk.

12 end while

13

Algorithm 1 Measurement of Power Spectral Density from SDR Figure 3:
Powerbank-powered Raspberry Pi 3 with an RTL-SDR receiver.

We use a DJI Matrice 200 UAV to carry the SDR equipment, as shown in Fig. 4.
The airspace above the Curragh camp is restricted airspace which is
exclusively reserved for military use, this allows us to perform our UAV
flights above the typical 120 meter legal flight ceiling of civilian UAVs. We
position the UAV 500 meters above ground (the hard limit imposed by DJI in
their flight software) before the experiments commence, and have the UAV hover
at a fixed position during the handset movements.

Figure 4: DJI Matrice 200 UAV, with the Raspberry Pi SDR suspended underneath.

##  III Experimental Results

Figures 5 and 6 show the vehicle paths taken for the ground and aerial
measurement parts of the experiment, respectively. For the ground
measurements, the vehicle was travelling at speeds of 30$-$50 km/h, whereas
for the aerial measurements the vehicles were on the motorway, travelling at
speeds between 80$-$130 km/h. The raw data measurement files are available
published by us online at [14].

We wish to compare our experimentally obtained signal power measurements
against the commonly used Free Space Pathloss (FSPL) model [15], which gives
the pathloss in dB as

$PL_{dB}=10\alpha\text{log}_{10}(d)+10\alpha\text{log}_{10}(f)+10\alpha\text{log}_{10}(4\pi/c),$
(1)

such that the received signal power is given in dBm as

$Rx_{dBm}=Tx_{dBm}-PL_{dB}.$ (2)

Figure 5: GPS trace of the vehicle track for the ground measurements. 5 km
line shown for scale. Figure 6: GPS trace of the vehicle tracks for the aerial
measurements. 100 km line shown for scale.

$Tx_{dbm}$ denotes the transmit power in dBm, $\alpha$ denotes the pathloss
exponent, $d$ denotes the 3D distance between the transmitter and receiver,
$f$ denotes the center frequency in Hz and $c$ is the speed of light in
meters/sec. Of these values, $Tx_{dBm}$, $c$ and $f$ are known in advance, and
$d$ is found via the GPS logging data. The pathloss exponent is the parameter
that is not known in advance, and which we would seek to estimate based on our
measurements. The research community generally suggests exponent values
between 2 and 4 [5], with 2 representing the perfect free space pathloss that
can occur under direct LoS conditions, and 4 being for the case of strongly
obstructed non-Line of Sight (NLoS) channels.

Figure 7 shows the measured performance for the ground-to-ground channel. We
observe that there is significant fluctuation in the received signal strength
values, with measurements at 600 meters ranging anywhere from $-$75 to $-$105
dBm. We attribute this to two factors. First, for the environment in question
we expect the channels to be largely NLoS, which means that the signal
experiences strong multipath effects. VHF band radio signals are also known to
experience strong signal diffraction effects, which also contribute to the
power fluctuations. Despite the fluctuations, there is a visible signal power
decay as the distance increases. Applying the pathloss model given in Eq. (1)
we find that this decay can be accurately approximated using the expression,
given a pathloss exponent of 3.3. This falls into the range of values
typically used by the research community; as expected, the exponent value is
closer to the NLoS extreme of 4 identified in prior works such as [5],
suggesting that at ground altitude wireless communication between two VHF
devices tends to behave as an NLoS signal.

Figure 7: Received signal power as a function of horizontal distance, for the
ground measurements. Figure 8: Received signal power as a function of
horizontal distance, for the aerial measurements at 500m height.

Figure 8 shows the measured power as a function of distance for the UAV-
mounted receiver. As before, we notice a fluctuation in power due to the
pulse-like waveform of the Motorola handset; however, there is a very clear
and consistent decay of the maximum received power with increasing distance,
for both vehicles. Compared to the ground-to-ground results, the signal is
able to travel a much greater distance, with signals being detectable at tens
of kilometers away. The maximum detectable distance in our experiment was for
the vehicle moving west, at almost 55 kilometers. The east vehicle signal was
lost sooner, due to the vehicle entering into a more densely populated
environment around the Dublin suburbs, with more signal blockage. Both
vehicles experience a signal strength drop that is consistent with Eq. (1),
given a pathloss exponent of 2.6. This is a higher value than the free space
pathloss of 2, which suggests that there is still some additional attenuation
occurring to the signal despite the UAV being positioned 500 meters in the
air. Part of this can be attributed to smaller obstructions such as trees and
other vehicles on the motorways which cause a degree of signal blockage,
albeit not nearly as strong as in the ground-to-ground case. Another
contributing factor is the effect of the so-called Fresnel zone. The Fresnel
zone is an ellipsoid region surrounding the direct path between a transmitter
and a receiver; if obstacles (such as terrain) are found inside this region
then we expect them to cause multipath signal reflections and (potentially)
destructive interference at the receiver. The width of this region is
inversely proportional to the frequency band used; in the cellular bands it
may be in the order of a few meters and therefore easily ignored; however, for
the VHF band frequencies it may reach a width of over a hundred meters given
our horizontal distances. For this reason, we consider that there is some
multipath attenuation occurring, even in circumstances where the UAV is
expected to maintain LoS to the ground vehicles.

##  IV Discussion and Future Work

In this work we detail the first set of experimental measurements obtained as
part of work on creating a UAV relay system to support long-range VHF
communications. Our initial measurements have clearly demonstrated a dramatic
improvement in the effective communication distance that can be achieved via
an aerial relay, due to the LoS propagation that can be achieved at large
altitudes. This corroborates the research community’s findings regarding UAV
communications; however, by experimentally demonstrating signal reception
across distances of tens of kilometers using a handheld radio, we validate the
idea of using UAV relays to support long-range emergency communication, such
as communication used by military and civilian emergency services in a
disaster scenario.

Our results raise a number of questions which we intend to explore in
subsequent trials. It is clear that the height of the UAV plays a critical
part in determining the propagation conditions of the wireless channel and the
resulting communication quality; we intend to explore how the channel
parameters (namely the pathloss and the random fluctuations) vary at different
heights of the UAV. Because we are performing our measurements in reserved
military airspace we are capable of operating our UAVs at heights of several
kilometers above ground without restrictions; in our future tests we plan to
replace our DJI UAVs with ones that are capable of operating at these heights,
while carrying several kilograms of radio equipment. This will also allow us
to mount a larger variety of radio equipment on-board the UAV, including radio
transmitters and signal repeaters. This will give us the opportunity to
perform measurement tests where the UAV is acting as a transmitter and the
measurement equipment is on the ground. Additionally, we intend to perform
tests closer to the Irish coastline, to measure channel conditions between the
UAV and sea vessels. This will allow us to explore the capabilities of the
UAVs as maritime relay systems.

## Acknowledgements

This work was funded by Science Foundation Ireland under the MISTRAL project,
grant number 21/FIP/DO/9949, as well as the project ”GUARD: Drug Interdiction
Using Smart Drones” funded under Enterprise Ireland’s Disruptive Technologies
Innovation Fund, Project ref. DT20200268A. The authors would like to thank the
members of the Communication & Information Services (CIS) Corps of the Irish
DF for their assistance with carrying out the experiments.

## References

  * [1] CNN, “First Drone Delivery of a Donated Kidney Ends with Successful Transplant,” May 2019, Available: https://edition.cnn.com/2019/05/01/health/drone-organ-transplant-bn-trnd
  * [2] H. Shakhatreh et al., ”Unmanned Aerial Vehicles (UAVs): A Survey on Civil Applications and Key Research Challenges,” in IEEE Access, vol. 7, pp. 48572-48634, 2019
  * [3] G. Geraci, A. Garcia-Rodriguez, M. Mahdi Azari, A. Lozano, M. Mezzavilla et al., ”What Will the Future of UAV Cellular Communications Be? A Flight From 5G to 6G,” in IEEE Communications Surveys & Tutorials, vol. 24, no. 3, pp. 1304-1335, third quarter 2022
  * [4] Business Insider, ”Google’s parent company has made internet balloons available in Puerto Rico, the first time it’s offered Project Loon in the US”, Oct. 2017, Available: https://www.businessinsider.com/ap-google-parent-turns-on-internet-balloons-in-puerto-rico-2017-10
  * [5] W. Khawaja, I. Guvenc, D. W. Matolak, U.-C. Fiebig and N. Schneckenburger, ”A Survey of Air-to-Ground Propagation Channel Modeling for Unmanned Aerial Vehicles,” in IEEE Communications Surveys & Tutorials, vol. 21, no. 3, pp. 2361-2391, third quarter 2019
  * [6] V. E. Hovstein, A. Sægrov and T. A. Johansen, ”Experiences with coastal and maritime UAS BLOS operation with phased-array antenna digital payload data link,” 2014 International Conference on Unmanned Aircraft Systems (ICUAS), 2014, pp. 261-266
  * [7] R. Amorim, H. Nguyen, P. Mogensen, I. Z. Kovács, J. Wigard and T. B. Sørensen, ”Radio Channel Modeling for UAV Communication Over Cellular Networks,” in IEEE Wireless Communications Letters, vol. 6, no. 4, pp. 514-517, Aug. 2017
  * [8] A. Al-Hourani and K. Gomez, ”Modeling Cellular-to-UAV Path-Loss for Suburban Environments,” in IEEE Wireless Communications Letters, vol. 7, no. 1, pp. 82-85, Feb. 2018
  * [9] W. Khawaja, O. Ozdemir, F. Erden, I. Guvenc and D. W. Matolak, ”UWB Air-to-Ground Propagation Channel Measurements and Modeling Using UAVs,” 2019 IEEE Aerospace Conference, 2019, pp. 1-10
  * [10] F. Fuschini, M. Barbiroli, E. M. Vitucci, V. Semkin, C. Oestges et al., ”An UAV-Based Experimental Setup for Propagation Characterization in Urban Environment,” in IEEE Transactions on Instrumentation and Measurement, vol. 70, pp. 1-11, 2021
  * [11] S. Seo, S. Kim and S. -L. Kim, ”A Public Safety Framework for Immersive Aerial Monitoring through 5G Commercial Network,” 2020 IEEE Wireless Communications and Networking Conference Workshops (WCNCW), 2020, pp. 1-6
  * [12] B. Galkin, E. Fonseca, G. Lee, C. Duff, M. Kelly et al., ”Experimental Evaluation of a UAV User QoS from a Two-Tier 3.6GHz Spectrum Network,” 2021 IEEE International Conference on Communications Workshops (ICC Workshops), 2021, pp. 1-6
  * [13] S. G. Sanchez, S. Mohanti, D. Jaisinghani and K. R. Chowdhury, ”Millimeter-Wave Base Stations in the Sky: An Experimental Study of UAV-to-Ground Communications,” in IEEE Transactions on Mobile Computing, vol. 21, no. 2, pp. 644-662, 1 Feb. 2022
  * [14] MISTRAL Project, VHF Drone Radio Measurement Dataset, 2022. Available: https://github.com/MistralProject/VHFDroneMeasurements
  * [15] C. A. Balanis, ”Antenna Theory: Analysis and Design”, Wiley-Interscience, 2005