Computing distances on Riemann surfaces (2024)

The distance between two points in a space is the length of the shortest geodesic, or locally minimal path,that connects them in the space. If the space is a compact Riemann surface, then the number of geodesics connecting a given pair of points dependson its genus, which is the number of holes the surface has. Given two points on the genus${0}$ sphere (Fig.1(a)), there arealways two geodesics between them, and thus the distance is simply a minimum of two lengths. In contrast, the number of geodesics between twopoints on the torus${\mathbb{R}^{2}/\mathbb{Z}^{2}}$ is infinite (four are shown in Fig.1(b)),which could make computingdistances on the torus difficult. Nevertheless, due to its symmetry, the distance${d}$ on the torus is given by the simple formula:

where${(x_{1},y_{1})}$ and${(x_{2},y_{2})\in\left[-1/2,+1/2\right]^{2}}$ are the coordinates of the representatives of two points on the torus, whichis the unit square with vertices at${(\pm 1/2,\pm 1/2)}$ whose opposite sides are paired, Fig.1(c). For genus${g>1}$ (hyperbolic) surfaces,the number of geodesic paths connecting two points is also infinite. Yet there are no closed-form distanceformulas analogous to Eq.(1) for any of these surfaces.

We will use the Poincaré disk model of${\mathbb{H}^{2}}$, which is thecomplex unit disk equipped with the metric

The group of orientation-preserving isometries of the Poincaré disk is the projective specialunitary group${\text{PSU}(1,1)}$, the quotient of the special unitary group${\text{SU}(1,1)}$ byits center${\{I,-I\}}$. In matrix form, these isometries are

which act on points${z\in\mathbb{C}}$ via fractional linear transformations,

A subgroup${\Gamma}$ of the isometry group${\text{PSU}(1,1)}$is called Fuchsian if it acts discontinuouslyon${\mathbb{H}^{2}}$. This means that for any point${z}$, the orbit${\Gamma z}$ has no accumulationpoints${w,~{}|w|<1}$. An accumulation point${w}$ is one for which there are elements of${\Gamma z}$in any arbitrarily small punctured disk around${w}$. Every Fuchsian group defines a quotientsurface,

Points${[z]}$ on${S}$ are orbits of points${z}$ in${\mathbb{H}^{2}}$ under actions by${\Gamma}$,

The distance${\delta^{\star}(z,w)}$ between two points${[z]}$ and${[w]}$ on${S}$ isa distance between orbits${\Gamma z}$ and${\Gamma w}$ in${\mathbb{H}^{2}}$. It is given by

where${\delta}$ is the distance in${\mathbb{H}^{2}}$.This formula cannot be directly evaluated, since${\Gamma}$ has infinitely manyelements. To find${\delta^{\star}(z,w)}$, one must consider infinitely many geodesics from${z}$to${\gamma w}$. Every such geodesic corresponds to a different minimal path between thesame pair of points on${S}$, like those illustrated in Fig.1 for the sphere and torus,or in Fig.6 for the Bolza surface.

Let us call a pair of images of${P}$ neighbors if they share either a common edge or a common vertex.Let${T\subset\Gamma}$ denote the subset of isometries from the Fuchsian group which map${P}$to all of its neighbors and itself. Then we define the${k^{\text{th}}}$shell${L_{k}}$,for${k\geq 1}$, to be the difference

and for${k=0}$, we define${L_{0}=P}$, as illustrated in Fig.3.

We next compute an upper bound on the minimum value of${k}$,${k_{\min}}$, for which the correct valueof the distance${\delta^{\star}(z,w)}$ is obtained by minimizing${\delta(z,\gamma w)}$over${\forall\gamma\in T^{k}}$. Thus${k_{\min}}$ is the minimum positive integer${k}$ satisfying

for all${z}$ and${w}$. In other words, the finite subset${\Gamma_{0}\subset\Gamma}$ mentioned abovecan be taken to be

We bound${k_{\min}}$ for an arbitrary surface by the ratio of two distances: the surfacediameter${\mathscr{D}}$, i.e., the maximum possible distance between two points on the surface, andthe minimal distance${\mathscr{T}}$ required to traverse a shell.To traverse here means to cross from the outer boundary of${L_{k}}$ to the outerboundary of${L_{k+1}}$ for${k\geq 0}$. In AppendixA, we show that this distance does not dependon${k}$, and satisfies the inequality

where${\delta}$ is the minimum distance between any pair of non-adjacent sides of${P}$, and${\epsilon}$ isthe minimum distance from the midpoint of an side to any adjacent side as illustrated inFig.4.

Then the distance required to cross from a starting point in${L_{0}=P}$ to a pointin${L_{k}}$ is lower-bounded by${(k-1)\mathscr{T}}$. Since${\mathscr{D}}$ is the surface diameter,then${k_{\min}}$ must satisfy the inequality

But the surface diameter${\mathscr{D}}$ is trivially upper bounded by the diameterof its fundamental polygon${P}$,${\text{diam}(P)}$:

where the${v_{i}}$ are the vertices of${P}$.Combining Eqs.(11),(12), and(13) leadsto an upper bound on${k_{\min}}$ in terms of geometric properties of${P}$, which we denote${k^{\star}}$:

Substituting this bound in Eq.(9) yields an explicit computable formula for the distance betweena pair of points on the surface:

At every step of the search, we set${\gamma}$ to be the last elementof${\Delta}$, and remove it from${\Delta}$.If${\delta(z,\gamma w)<\delta(z,\gamma_{\min}w)}$, we update${\gamma_{\min}}$to${\gamma}$. We then append to${\Delta}$ the group elements${\gamma g_{i}}$,${1\leq i\leq N}$,corresponding to polygons that are edge-adjacent to the currently searched polygon, but only if theyare at a greater distance from${z}$:

Here, the distances${\delta(z,\gamma P)}$ and${\delta(z,\gamma g_{i}P)}$ from${z}$to the polygons${\gamma P}$ and${\gamma g_{i}P}$ are defined to be the minimum distancefrom${z}$ to one of their sides, with the exception${\delta(z,P)=0}$.

The reason not to search the polygons${\gamma P}$ forwhich${\delta(z,\gamma P)}$ exceeds${\text{diam}(P)}$ is this:

where${\gamma_{\min}}$ is the group element we are looking for, i.e., the one thatminimizes${\delta(z,\gamma w)}$, and${\mathscr{D}}$ is the surface diameter.

The generalized Bolza surface${S_{g}}$ has as its fundamental polygon${P}$ the regular${4g}$-gon withinterior angles${\pi/2g}$ and vertices

where${R}$ is the radius of${P}$, which satisfies

The Fuchsian group${\Gamma_{g}}$ of${S_{g}}$ is generated by the following${2g}$ isometries(Fig.6), which pair opposite sides of the fundamental polygon:

where${s}$ is the length of a side of${P}$, which satisfies

Applying the distance formula to these surfaces, we observe that${\delta<2\epsilon}$(cf. Fig.4), and then upper bound${\delta}$using hyperbolic trigonometry to obtain

The diameter${\mathscr{D}_{g}}$ of${S_{g}}$ is knownStepanyantsetal. (2024),

and therefore we can substitute the actual diameter, instead the upper bound inEq.(13), into Eq.(14) for${k^{\star}}$ to obtain

The number of polygons in${T^{k^{\star}}}$ is upper bounded by the number of sequences of${2k^{\star}}$generators,

and since${k^{\star}\approx\log g/\text{arccosh}~{}2}$ for large${g}$, the time required to evaluate the distanceformula is${O\left(g^{\alpha\log g}\right)}$,where${\alpha=2/\text{arccosh}~{}2\approx 1.52}$.

For the Bolza surface${S_{2}}$, evaluating Eq.(24) yields${k^{\star}=2}$, but in AppendixBwe compute${k_{\min}}$ exactly using different methods:

This distance is

where${L_{n}=T^{n}(P)}$ is the${n^{\text{th}}}$ shell,${T\subseteq\Gamma}$ is the set consisting of all maps from${P}$ toan edge- or vertex-adjacent polygon and the identity, and${\partial L_{n}}$ is the boundary of${L_{n}}$.

First, observe that for${\gamma\in T^{n}}$ we have

Hence,

Since${\mathscr{T}}$ is the minimum of the right hand side over all${n\geq 0}$ and${\gamma\in T^{n}}$, and the left hand side isequal to${\delta\Bigl{(}\partial P,\partial\left(T(P)\right)\Bigr{)}}$, which is${\geq\mathscr{T}}$ by definition of${\mathscr{T}}$,we conclude that

Now we will prove the main result of this section:

where${\delta_{ij}}$ denotes the distance between edges${i}$ and${j}$ which are distinct andnonadjacent, and${\epsilon_{k}}$ denotes theminimal distance from the midpoint of edge${k}$ to either of the adjacent edges${k\pm 1}$.

Starting once more with arbitrary points${p\in\partial L_{0}}$ and${q\in\partial L_{1}}$, webreak${\overline{pq}}$ into smaller segments so that each segment is contained in a polygon${\gamma(P)}$and has both endpoints on its boundary. For such a segment, suppose the endpoints lie on edges withlabels${i,j}$. We categorize a segment (see Fig.8) as

1. 1.

   type I if${i-j=1}$,

2. 2.

   type II if${j-i=1}$, and

3. 3.

   type III if${|i-j|>1}$.

The segments cannot be all typeI, since this would imply that${\overline{pq}}$ circles around avertex indefinitely without ever reaching${\partial L_{1}}$, which cannot happen. Similarly,the segments cannot all be typeII. This leaves two cases: there is either (1) aconsecutive pair of typeI and typeII segments in either order, or (2) a typeIII segment.In the first case, we can show using elementary geometry thata lower bound on the combined length of the typeI and typeII segments, yielding a lower boundon${\mathscr{T}}$, is

In the second case,${\mathscr{T}}$ is lower bounded by the minimum length of a typeIII segment,

Therefore, in either case, Eq.(27) holds.

We prove this by contradiction.Assume that there exist points${z\in P,w\notin L_{1}}$ that contradict the aboveassertion:${\delta(z,w)\leq\delta(z,\gamma w)}$ for all${\gamma}$. This meansthat${w}$ is either inside the Dirichlet polygon of${z}$ or on its boundary.Using the argument from AppendixA, thegeodesic${\overline{zw}}$ must contain either

• Case (1):

  a segment composed of a pair of typeI and typeII segments in either order, or

• Case (2):

  a typeIII segment.

Denote the endpoints of this segment${p,q}$ such that${z}$ is closer to${p}$than to${q}$. Since the Dirichlet polygon of${z}$ is convex, contains${z}$ and${w}$,and${z,p,q,w}$ are on a line,${q}$ must bein the interior of the Dirichlet polygon of${z}$. This implies that${z}$ is in the interiorof the Dirichlet polygon of${q}$, and so by the same argument${p}$ must lie in the interior ofthe Dirichlet polygon of${q}$. This means that

Consider now case(1) above, where${p}$ and${q}$ are endpoints of a typeI segment joined to a typeIIsegment (Fig.9). Assume without loss of generality that${q}$ is on side${1}$. Let${a=\delta(q,v_{2})}$and${b=\delta(p,v_{1})}$. Label-chasing, we find that there must be an image${q^{\prime}}$ of${q}$located on the same side as${p}$. Applying the triangleinequality to triangles${\triangle v_{1}Ip}$ and${\triangle v_{2}Iq}$, where${I}$is the intersection between${\overline{pq}}$ and${\overline{v_{1}v_{2}}}$, gives

which is a contradiction with Eq.(30).

Next, assume without loss of generality that${q}$ is on side${1}$ (Fig.11), and uselabel-chasing to determine the location of another image of${q}$, denoted${q^{\prime\prime}}$.Let${a=\delta(q,v_{1})}$ and${b=\delta(p,v_{2})}$. From Fig.10, we have${0<\{a,b\}<s/2}$.Applying hyperbolic trigonometry to quadrilateral${pqv_{1}v_{2}}$ and righttriangle${\triangle pv_{2}q^{\prime\prime}}$, one can show that