# ViNTER: Image Narrative Generation
with Emotion-Arc-Aware Transformer

Kohei Uehara<EMAIL_ADDRESS>The University of TokyoTokyoJapan ,
Yusuke Mori<EMAIL_ADDRESS>The University of TokyoTokyoJapan ,
Yusuke Mukuta<EMAIL_ADDRESS>The University of Tokyo /
RIKENTokyoJapan and  Tatsuya Harada<EMAIL_ADDRESS>The University
of Tokyo / RIKENTokyoJapan

(2022)

###### Abstract.

Image narrative generation is a task to create a story from an image with a
subjective viewpoint. Given the importance of the subjective feelings of
writers, readers, and characters in storytelling, an image narrative
generation method should consider human emotion. In this study, we propose a
novel method of image narrative generation called ViNTER (Visual Narrative
Transformer with Emotion arc Representation), which takes “emotion arc” as
input to capture a sequence of emotional changes. Since emotion arcs represent
the trajectory of emotional change, it is expected that we can include
detailed information about the emotional changes in the story to the model. We
present experimental results of both automatic and manual evaluations on the
Image Narrative dataset and demonstrate the effectiveness of the proposed
approach.

Vision and Language, Emotion Arc, Creative AI, Narrative / Storytelling

††journalyear: 2022††copyright: acmcopyright††conference: Companion
Proceedings of the Web Conference 2022; April 25–29, 2022; Virtual Event,
Lyon, France††booktitle: Companion Proceedings of the Web Conference 2022 (WWW
’22 Companion), April 25–29, 2022, Virtual Event, Lyon, France††price:
15.00††doi: 10.1145/3487553.3524649††isbn: 978-1-4503-9130-6/22/04††ccs:
Information systems Multimedia content creation

##  1\. Introduction

Figure 1.  ViNTER is able to control the emotional changes in the generated
narratives by utilizing “emotion arc.” For example, if the input emotion arc
is “neutral $\rightarrow$ sadness $\rightarrow$ neutral”, the model produces a
narrative in which the middle part represents a sad feeling. In contrast, if
we input “neutral $\rightarrow$ joy $\rightarrow$ joy” as the emotion arc, the
model produces a narrative filled with happy emotions from the midpoint
onward.

Image captioning is a representative and essential task in research on vision
and language. Beyond the generation of accurate descriptive caption about
images, recent research efforts have focused on creative text generation, such
as narrative generation from a single image (Shin et al., 2018), narrative
generation from sequences of images (Huang et al., 2016a; Liu et al., 2017),
and poetry generation from an image (Liu et al., 2018). These methods, which
are designed to generate creative text from an image or sequence of images,
can be considered as an important step toward creative artificial intelligence
(creative AI).

In this paper, the term image narrative is used according to its definition in
(Shin et al., 2018). That is, an image narrative is characterized by the
presence of a broader range of subjective and inferential elements, unlike
descriptive image caption, which describe factual aspects of the visual
contents in the image.

In this paper, we focus on “emotion” as an essential element of image
narratives. The relationship between narratives and emotions has been an
essential area of research in the humanities, represented by scientific
investigations into the cognitive and effective impacts of literature (Hogan,
2006; Pandit and Hogan, 2006; Johnson-Laird and Oatley, 2008; Hogan, 2010,
2019). These findings have been introduced in natural language processing
(NLP) field (Anderson and McMaster, 1982) and various studies have been
conducted on understanding and generating narratives, such as story generation
with sentiment control (Luo et al., 2019; Dathathri et al., 2020; Xu et al.,
2020).

In this study, we propose a novel image narrative generation model called
ViNTER (Visual Narrative Transformer with Emotion Arc Representation), which
is designed to generate a narrative from an image using Transformer-based pre-
trained models. To give the model the ability of controlling emotional change
while generating narratives, we utilize “emotion arc,” which represents the
trajectory of emotion changes (Reagan et al., 2016).

Emotion arc is denoted as a sequence of three words that describe the emotion,
e.g., “joy $\rightarrow$ fear $\rightarrow$ surprise.” Each emotion word
represents the emotion of the begin, body, and end parts of the narrative,
respectively. In this study, an image narrative consists of five sentences, so
the begin part is defined as the first sentence, the body part as the next
three sentences, and the end part as the last sentence.

For example, in the example in Figure 1, the input for the emotion arc is
“neutral $\rightarrow$ sadness $\rightarrow$ neutral.” Hence, the model is
expected to generate narratives in which the body part represents a sad
emotion (e.g., “They are hungry. They seems to be sad. Some trees are behind
them”). In contrast, if the input emotion arc is “neutral $\rightarrow$ joy
$\rightarrow$ joy”, the model is expected to generate narratives with happy
emotions after the middle part.

Inspired by recent studies in multi-modal Transformer models (Chen et al.,
2020), we designed an encoder that takes multi-modal input, an image and
emotion arc. Here, emotion arc is considered as the sequence of emotion words.
Then, a Transformer-based decoder generates narratives from the fused feature
obtained from the encoder.

We evaluated our model with both of the automatic and manual evaluation. The
results show that our model demonstrates sufficiently promising performance
for generating narratives that take into account emotion changes.

Our main contributions are summarized as follows:

  * •

We propose ViNTER, a novel image-narrative generation method. Benefiting from
recent advances in multi-modal Transformer-based pre-trained models and
emotion-awareness, ViNTER exhibited notable performance on image-narrative
generation tasks.

  * •

We discuss the applicability of Transformer-based models to creative AI in the
fields of computer vision and language processing.

##  2\. Related Work

Figure 2.  Overview of ViNTER. First, we extract region-based features from an
image and tokenize emotion arc into a sequence of emotion word tokens. Then,
they are fed into the bi-directional Transformer encoder. The output feature
from the encoder is fed into the auto-regressive Transformer decoder and the
decoder generates each word of the narrative sequentially.

###  2.1. Emotion in Narratives

Emotion is an essential element in storytelling. Referring to Ackerman and
Puglisi (2012), Kim and Klinger (2019a) observed that emotion is a key
component of every character, and analyzed how emotions were expressed non-
verbally in a corpus of short fanfiction stories. Lugmayr et al. (2017) also
noted emotions as a fundamental aspect of storytelling as part of the
cognitive aspects evoked by a story in its audience.

As described by Anderson and McMaster (1982), numerous efforts have been made
to elucidate the relationship between emotions and stories. Based on the 1,000
most frequently used English words for which Heise (1965) obtained semantic
differential scores, Anderson and McMaster (1982) reported the development of
a computer program designed to assist in the analysis and modeling of
emotional tone in text by identifying those words in passages of discourse.
Emotional analysis of text is closely related to lexicons annotated with
emotions, and psychological findings have been referred to in these
annotations and analyses.

Kim and Klinger (2019b) pointed out three theories of emotion commonly used in
computational analyses, including Ekman’s theory of basic emotions (Ekman,
1993), Plutchik’s wheel of emotion (Plutchik, 1980), and Russell’s circumplex
model (Russell, 1980).

Several studies have attempted to control story generation by considering
emotions (Chandu et al., 2019; Luo et al., 2019; Brahman and Chaturvedi, 2020;
Dathathri et al., 2020; Xu et al., 2020). Most of these works have focused on
sentiment control, that is, positive or negative control of story generation.
Story generation with a greater variety of emotions had not been addressed
until recently. To the best of our knowledge, Brahman and Chaturvedi (2020)
performed the first work on emotion-aware storytelling, which considered the
“emotion arc” of a protagonist.

Referring to a talk by Kurt Vonnegut (Vonnegut, 1995), a famous American
writer, attempts have been made to classify stories by drawing an “emotion
arc” (Reagan et al., 2016; Chu and Roy, 2017; Somasundaran et al., 2020;
Vecchio et al., 2020). Reagan et al. (2016) showed that stories collected from
Project Gutenberg111http://www.gutenberg.org/ could be classified into six
styles by considering their emotion arcs (i.e., the trajectory of average
emotional tone expressed over the course of a story).

Based on this idea, Brahman and Chaturvedi (2020) considered variations in the
emotions expressed by story protagonists as time series to generate emotion-
aware stories. They split a five-sentence story into three segments, including
a beginning (the first sentence), a body (the second to fourth sentences), and
an ending (the last sentence). They applied labels for emotions in each
segment to represent the emotional arc, and utilized them in story generation.

###  2.2. Transformer-based Language Models for Vision and Language

Transformer was proposed as an encoder-decoder model. Both the encoder and
decoder parts include a self-attention mechanism. Language models designed to
be pre-trained using large unsupervised datasets have been proposed and have
been shown to perform well in various natural language processing tasks.
Typical examples include Generative Pre-trained Transformer (GPT) (Radford et
al., 2018) and Bidirectional Encoder Representations from Transformers (BERT)
(Devlin et al., 2019). Whereas these methods use only decoder and encoder
parts, respectively, the Bidirectional and Auto-Regressive Transformer (BART)
(Lewis et al., 2020) has been proposed as an encoder-decoder model with the
intention of becoming more versatile model.

In recent years, the Transformer architecture has made a significant impact,
not only on NLP, but also on other modalities. Moreover, multimodal
applications such as those combining vision and language, have attracted the
attention of researchers. There are two main approaches that combine vision
and language processing in Transformer models, including two-stream and
single-stream models. Two-stream models (Lu et al., 2019; Tan and Bansal,
2019) utilize separate Transformers for each modality, and a cross-modality
module is adopted. Single-stream models (Su et al., 2020) directly input the
text and visual embeddings into a single Transformer. Su et al. (2020) argued
for the usefulness of using single-stream methods, as opposed to ViLBERT (Lu
et al., 2019) and LXMERT (Tan and Bansal, 2019), each of which adopts a two-
stream approach. They explained that the network architecture of the attention
pattern in the cross-modal Transformer is restricted in ViLBERT and LXMERT,
and proposed VL-BERT as a unified architecture based on Transformer models,
without any restriction on the attention patterns, in which the visual and
linguistic contents interact early and freely. Their LXMERT indicated that the
single-stream method is promising.

The proposed method is based on UNITER (Universal Image-Text Representation)
(Chen et al., 2020) as a single-stream model. UNITER has shown excellent
performance in many vision and language tasks, such as visual question
answering (VQA) and image-text retrieval, with a relatively simple
configuration of a single stream.

The method proposed in Yu et al. (2021) is the closest approach to our work in
the literature. The authors considered the Transitional Adaptation of a
Pretrained Model (TAPM), which showed state-of-the-art performance on a visual
storytelling task. The main difference between the proposed approach and that
of (Yu et al., 2021) is that we focus on image-narrative generation, whereas
Yu et al. (2021) applied their method to visual storytelling. The task of
visual storytelling was proposed by Huang et al. (2016b), along with an
associated dataset called VIST. They explored visual storytelling as a
sequential vision-to-language task. In contrast image narrative generation is
a single vision-to-language task. VIST has a one-to-one alignment between
images and text. In other words, visual storytelling generates a single
sentence per image, while considering the preceding and subsequent images as
well. In contrast, the image narrative generation task, an entire narrative is
generated from a single image. We believe that image narrative generation is a
more creative task, in which a narrative sequence must be imagined from the
relatively limited data contained in a single image. Moreover, to the best of
our knowledge, the present work is the first to incorporate emotion arcs in
image narrative generation to consider the importance of emotions in a story.

####  2.2.1. Attention Mechanism in Transformers

Transformer’s attention mechanism was proposed based on the flow of
introducing the attention mechanism into sequence-to-sequence model for
machine translation (Bahdanau et al., 2015; Luong et al., 2015). Although the
attention mechanism was introduced into the field of NLP as an auxiliary
mechanism to compensate for information that cannot be captured by the
recurrent neural network, Vaswani et al. (2017) proposed the Transformer as a
model with attention as the main mechanism.

Transformer’s attention mechanism maps a query and key-value pairs to an
output. Their particular “Scaled Dot-Product Attention” can be described as
follows.

(1)
$\rm{Attention}(Q,K,V)=\rm{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)$

$Q$, $K$, $V$ stand for query, key, and value, respectively. $d_{k}$ is the
dimension of $K$, and scaling factor $\frac{1}{\sqrt{d_{k}}}$ was introduced
to prevent from dot product $QK^{T}$ growing large in magnitude and causing
extremely small gradients in softmax function.

The encoder of the vanilla transformer contains self-attention layers. In a
self-attention layer, queries and key-value pairs are come from the same
place. The relationship, or attention, between each element of the sequence
given as input and all other elements is calculated. In the decoder, each
layer uses an output of the previous layer as queries, and key-value pairs
come from the output of the encoder.

UNITER is a model that uses only the Encoder part of the Transformer, and
embeds the input image and text, and then processes them with the self-
attention mechanism.

Our method, ViNTER, is an encoder-decoder model like BART, and its encoder is
a modified version based on UNITER.

##  3\. Proposed Method

We propose ViNTER (Visual Narrative Transformer with Emotion arc
Representation) as a method to utilize emotion changes in narratives. The
overview of the model is shown in Figure 2. To encode an image and the desired
emotions simultaneously, we developed ViNTER’s encoder based on UNITER (Chen
et al., 2020), which is a well-known multimodal pre-trained Transformer model.
UNITER is a vision-and-language pre-trained model that can encode both visual
and textual features with a single Transformer encoder. After the image and
emotion features are encoded, the Transformer decoder was trained to generate
the corresponding narratives. We describe each of the encoder and decoder in
detail in the following sections.

Figure 3.  Visualization of the frequency of each emotion that appears in each
segment of the emotion arc in the entire Image Narrative dataset. From the
center to the outside of the graph, the number of emotions contained in each
segment (beginning, body, and end) is shown.

###  3.1. Emotion Arc

The proposed approach adopts emotion arcs as an emotional representation of
the input of the model. Emotion arc represents the sequence of emotions
expressed over the course of a story. In this study, we consider a story that
consists of five sentences. We then split the story into three segments,
including a beginning, a body, and an ending, as in (Brahman and Chaturvedi,
2020). We consider the sequences of emotions that match each segment as an
emotion arc. For example, if the story begins with a joyful sentence, the body
segment expresses fear, and the end segment expresses surprise, then the
emotion arc is represented as “joy $\rightarrow$ fear $\rightarrow$ surprise.”

To label sentences with emotion, we use an emotion classifier fine-tuned with
GoEmotions. GoEmotions is a corpus created to fine-tune emotion prediction
models.222https://github.com/google-research/google-
research/tree/master/goemotions Referring to (Brahman and Chaturvedi, 2020),
we rely on Ekman’s theory of basic emotions and use 6 + 1 categories (anger,
disgust, fear, joy, sadness, surprise, and neutral). We split the narratives
into beginning, body, and end segments, and applied the emotion classifier to
obtain the emotions corresponding to each segment. A visualization of the
number of each emotion that appeared for each segment of the emotion arc is
shown in Figure 3.

###  3.2. Encoder

####  3.2.1. Visual Embeddings

One of the inputs for the ViNTER encoder is image feature
$\mathbf{I}\in\mathbb{R}^{n\times d}$. $n$ indicates the number of object
regions proposed by the object detector and $d$ indicates the dimensions of
the image feature. We use Faster R-CNN (Ren et al., 2017) as an objection
detection model, which is pre-trained with the Visual Genome dataset (Krishna
et al., 2017; Anderson et al., 2018). To explicitly provide positional
information on the image region, we add positional embeddings based on the
region coordinates, as used in UNITER. Specifically, we use the region
coordinates represented as the 7-dimensional vector consisted of normalized
top/left/bottom/right coordinates, width, height, and area.

####  3.2.2. Emotion Embeddings

In order to obtain the emotion labels of each segments, we use the BERT model
fine-tuned with GoEmotions333https://github.com/monologg/GoEmotions-pytorch.
As a taxonomy of emotions, we adopt seven emotions (anger, disgust, fear, joy,
sadness, surprise, and neutral) based on Ekman’s six basic emotions.

To input the emotion arc into the encoder, the proposed approach uses a
special [EMOTION SEP] token to concatenate the words denoting each emotion
(e.g., $[$ joy, [EMOTION SEP], fear, [EMOTION SEP], surprise$]$). We used the
learned word embeddings from BERT (Devlin et al., 2019) to convert the
emotion-word tokens into emotion vectors
$\mathbf{E}=\\{\bm{w}_{\textrm{begin}},\;\bm{w}_{\texttt{SEP}},\;\bm{w}_{\textrm{body}},\;\bm{w}_{\texttt{SEP}},\;\bm{w}_{\textrm{end}}\\}$.
We add the relative positional embeddings to indicate which word corresponds
to which part of the story.

####  3.2.3. Encoder Architecture

Having obtained both visual and emotional embeddings, we concatenate them and
input them into the Transformer encoder to obtain fused feature $\bm{h}$:

(2) $\bm{h}=\textrm{Enc}([\bm{I};\,\bm{E}])$

We use Transformer-based encoder to encode both of visual and emotional
embeddings. Each Transformer block consists of a stack of self-attention
layers.

###  3.3. Decoder

The decoder of ViNTER follows the decoder architecture of BART (Lewis et al.,
2020). Our decoder is composed of a stack of Transformer blocks. Each block
includes multi-headed self-attention and cross-attention layers, and two
fully-connected layers. To avoid seeing the information of a future word, we
apply a causal mask to the input of the self-attention layer. Finally, we
employ the fully-connected layer to compute the probability distribution over
the entire vocabulary. We trained our model parameters $\theta$ by minimizing
the negative log-likelihood over the probability distribution of the ground-
truth narrative $y$, as follows.

(3) $\mathcal{L}=-\sum^{|y|}_{n=1}\log
P_{\theta}(y_{n}\,|\,y_{<n},\;\mathbf{h}).$

##  4\. Experiment

###  4.1. Dataset

We used the Image Narrative dataset (Shin et al., 2018) to conduct our
experiments to validate the performance of the proposed approach. This dataset
contains 11,001 images drawn from MS COCO (Lin et al., 2014) and 12,245 image
narratives annotated through crowdsourcing. Each narrative consists of five
sentences. The crowd workers were instructed to include local elements and
sentiments that could be inferred or imagined from the images, not only
accurately describe the contents of the images. Because the test set of the
Image Narrative dataset is not publicly available, we further split the
training data of the original dataset into training and evaluation data,
taking care to avoid overlapping images. Consequently, we obtained a dataset
with 5,398 narratives allocated to training and 1,813 to evaluation.

The narratives in this dataset contain noisy sentences; for example, some do
not start with a capital letter or have extra or missing space around the
period. Therefore, we preprocess the sentences by removing or adding spaces
around periods as needed, capitalizing the beginning of the sentences, and
ensuring that the remainder was correctly spelled in lowercase.

###  4.2. Implementation Details

We set the image-feature dimension $d$ to 2,048 and the object region number
$n$ to 36. The number of hidden units of the Transformer block in the encoder
and the decoder was set to 768. The number of Transformer blocks in the
encoder and decoder was set to 12. We start our encoder training with the pre-
trained checkpoints of UNITER444downloaded from
https://github.com/ChenRocks/UNITER. We used the AdamW optimizer (Loshchilov
and Hutter, 2019) with $(\beta_{1}=0.9,\;\beta_{2}=0.999)$. We applied the
cosine annealing schedule with an initial learning rate of $5.0\times 10^{-5}$
and a warmup step of 1,000. We trained the model for 5,000 steps with a batch
size of 32. The training took about two hours using a single Tesla A-100 GPU.

Figure 4.  Screenshot of the evaluation interface presented to AMT workers.
The workers are asked to evaluate the quality of the narratives generated by
ViNTER and the narratives generated by one of the comparison methods.

###  4.3. Baselines

We compared our method with the following baselines.

DenseCap (Johnson et al., 2016): This is a captioning model that generates
captions focusing on a specific region. Using DenseCap as a baseline is
derived from the previous research (Shin et al., 2018).

Shin et al. (2018): This model generates narratives based on the user’s
interests through their answers to questions about the image. For the above
methods, we list the values as they appear in (Shin et al., 2018), which
proposed the Image Narrative dataset. Note that their results are evaluated on
the test set of the dataset, which is not publicly available. Hence, their
scores are not directly comparable to ours; however, we include them for
reference.

Image Only: This has the same model architecture as the proposed model, but
used only image region features as input.

ViNTER${}_{\mathbf{begin,\;body,\;end}}$: These methods are designed to
control emotions in narratives in a simpler manner, using only a single
emotion as input. Each model uses an emotion corresponding to the beginning,
body, and end segments as inputs.

Models | BLEU-4 | BERTScore
---|---|---
DenseCap (Johnson et al., 2016) (†) | 1.90 | -
Shin et al. (2018) (†) | 1.41 | -
Image Only | 7.288 | 88.40
ViNTERbegin | 7.292 | 88.46
ViNTERbody | 7.702 | 88.44
ViNTERend | 7.316 | 88.46
ViNTER | 7.684 | 88.50
Table 1. Automatic evaluation results in terms of the quality of the generated narratives. For the models marked with (†), we put the values provided in (Shin et al., 2018). Note that these models are evaluated on the test data of the dataset and cannot be directly compared to the results of the other models. The best values are shown in bold and the second best values are underlined.  Models | Begin-acc | Body-acc | End-acc | Seg-acc | Arc-acc
---|---|---|---|---|---
Image Only | 92.06 | 48.65 | 55.38 | 65.36 | 26.31
ViNTERbegin | 93.16 | 51.85 | 53.83 | 66.28 | 27.25
ViNTERbody | 91.23 | 66.46 | 55.43 | 71.04 | 33.65
ViNTERend | 91.73 | 52.73 | 61.89 | 68.78 | 30.72
ViNTER | 93.05 | 65.97 | 60.89 | 73.30 | 38.61
Table 2. Automatic evaluation results in terms of emotional accuracy. The best
values are shown in bold and the second best values are underlined.

###  4.4. Evaluation Metrics

####  4.4.1. Automatic

For evaluation by comparison with the ground-truth narratives, we use BLEU
(Papineni et al., 2002) and the F1 score of BERTScore (Zhang* et al., 2020).
BLEU is a widely used metric in image captioning calculated based on n-gram
matching between the generated and reference texts. In recent years, research
has been conducted on metrics that use text features obtained from a large-
scale pre-trained language model. BERTScore is a typical example of such a
metric. It calculates the matching of tokens in generated and reference texts
as conventional metrics, but it uses contextual embeddings calculated with
BERT (Devlin et al., 2019) instead of string matching or matching heuristics.

We also evaluated the accuracy of the emotions expressed in the generated
narratives. We use Begin-acc, Body-acc, and End-acc as metrics to evaluate
whether the emotions estimated for the generated narratives for the segments
begin, body, and end, respectively, are consistent with the corresponding
parts of the input emotion arc. Seg-acc is the fraction of matches between the
correct emotion for each segment of the ground-truth and the estimated emotion
for each segment of the generated narrative. Arc-acc similarly measures the
agreement of the estimated emotions; however, here we measure the agreement of
the entire emotion arc, not each segment.

####  4.4.2. Human Evaluation

We conducted the human evaluation with Amazon Mechanical
Turk.555https://www.mturk.com/ An example screenshot of the AMT task is shown
in Figure 4.

For comparison, we used four methods from the aforementioned baselines: Image
Only, ViNTERbegin, ViNTERbody, and ViNTERend. We paired the proposed method
with each of the four comparison methods and conducted an evaluation
experiment using 100 images. 13 workers were asked to evaluate a pair of image
narratives generated by our proposed method and one of the comparison methods.

In order to compare how the change in emotion arc affects the methods, we also
prepared the generated narratives in which the target emotion arcs were
limited to those that changed in the middle of a narrative, i.e., always
included two or more emotions. We distinguish these methods as “w/ change,”
i.e. with change. For each of the proposed and comparison methods, we also
evaluated the generation of w/ change.

We asked following two questions to each worker for the evaluation: (1) Does
this text relate to the reference image? (2) Does this text match the target
emotion arc? These criteria are designed to evaluate whether the generated
text is suitable as an image narrative and matches the required emotion arc. A
five-point scale evaluation was used for each criterion: higher is better (5:
Excellent, 4: Good, 3: Fair, 2: Poor, 1: Bad).

##  5\. Results and Discussion

| Better / Tie / Worse (%)
---|---
| Image | Emotion | Image (w/ change) | Emotion (w/ change)
ViNTER vs. Image Only |  27.38 / 46.38 / 26.23 | 27.54 / 44.08 / 28.38 |  22.62 / 54.92 / 22.46 |  24.62 / 55.38 / 20.00
ViNTER vs. ViNTERbegin | 23.23 / 45.38 / 31.38 |  27.54 / 45.23 / 27.23 |  26.08 / 49.92 / 24.00 |  27.38 / 46.31 / 26.31
ViNTER vs. ViNTERbody | 25.23 / 47.62 / 27.15 | 27.23 / 45.54 / 27.23 |  31.69 / 39.85 / 28.46 | 26.54 / 42.15 / 31.31
ViNTER vs. ViNTERend |  28.38 / 44.46 / 27.15 |  27.08 / 47.54 / 25.38 | 29.15 / 41.46 / 29.38 |  33.77 / 37.77 / 28.46
Table 3.  Human evaluation results of the generated narratives in terms of the
relevance to the image and emotion arc. Here, “Better” means the percentage of
cases where the proposed method was evaluated as better quality than the
baseline, “Worse” means the opposite, and “Tie” means the percentage of cases
where the two methods were evaluated as equal. We highlight the larger of the
Better or Worse value in each set.

###  5.1. Automatic Evaluation

The evaluation results of the automatic metrics in terms of the quality of the
generated narratives are presented in Table 1.

In BLEU and BERTScore, ViNTER outperforms the existing methods (ViNTER vs.
DenseCap, Shin et al.). This suggests that our method is superior to
conventional methods, even though considering that these evaluations were
performed using test data that cannot be used. ViNTER also performs
considerably better than the Image Only model. However, when comparing the
proposed method to models with a single emotion as input, in particular,
ViNTERbody, the difference in scores becomes smaller, or the comparison method
scores slightly better. This may be due to the shortage of metrics using
comparisons with ground-truth data in the evaluation of narrative generation.
It is difficult to accurately evaluate the performance of models in reference-
based metrics, when a variety of outputs are expected for the same input,
which is exactly the case for narrative generation.

We also present the results in terms of the accuracy of the emotions of the
generated narratives in Table 2. The model with the emotion input for each
segment has the best score for each corresponding segment (ViNTERbegin for
Begin-acc, ViNTERbody for Body-acc, and ViNTERend for End-acc). However,
models that input emotions for a single segment have much lower accuracy
compared to the other segments. These results are in contrast to the results
of ViNTER with an emotion arc as input, which scored the second-best for all
segments. In addition, ViNTER with an emotion arc input performs significantly
better than the other methods in evaluating the accuracy of the emotions
across the entire generated narrative (Seg-acc, Arc-acc). These results show
that our proposed method is capable of controlling emotional changes, not only
in a part of the narrative but also in the complete narrative.

###  5.2. Human Evaluation

The results of the human evaluation are shown in Table 3. First, looking at
the case of no change in emotion (left half of the table), ViNTER tends to be
rated as having equal or slightly higher quality of emotional control compared
to baseline. In some cases, ViNTER is rated as worse in terms of the match
between the image and the content of the generated narrative. However, this is
not particulary suprising given the fact that ViNTER is trained to generate
narratives that follow not only the content of the image but also the emotion
arc. This suggests that ViNTER may have prioritized the emotion arc-based
narrative generation over the image content in some cases.

In the case where there is a change in the emotion arc (right side of the
Table. 3), the superiority of ViNTER in terms of the quality of emotion is
even more pronounced, except for vs. ViNTER${}_{\textrm{body}}$. This is an
expected result, considering that when there is no change in the emotion arc,
there is less likely to be a large difference in the generated narratives
compared to the other methods. Since the body part is the major part of the
overall narrative, it is likely that humans would have tended to give a better
evaluation of the overall emotion if the emotion of the body part had been
generated correctly. From these results, we can conclude that ViNTER is able
to generate narratives that better capture the changes in emotion arc than the
baseline method.

Figure 5.  Qualitative examples for the same image with two different emotion
arc inputs.

###  5.3. Case Studies

To demonstrate the controllability of the narratives generated by the proposed
model, we show examples of the narratives generated from the same image with
different emotion arcs in Figure 5. Overall, our ViNTER could generate
different narratives for the same image, depending on the input emotion arc.
For example, in the top left image, when describing an animal, if “joy” is
input as the middle emotion, a positive sentence, such as “He looks happy,”
will be generated, whereas if “sadness” is input as the middle emotion, a
negative sentence, such as “He seems to be sad,” will be generated. However,
in some cases, such as when “joy” is followed by a negative emotion (e.g.,
“disgust” or “anger”), the output may be inconsistent with the previous
sentence.

##  6\. Conclusion

In this study, we have addressed the task of generating narrative sentences
from an image using a Transformer-based method to process multimodal vision
and language data. Our proposed method has shown promising results on both
automatic and human evaluation, and case studies showed that our method could
control generation with an emotion arc.

However, some room for improvement remains in terms of the way these emotions
are modeled. The emotion arc only considers emotions from one perspective, but
multiple emotions are typically associated with a given narrative. Iglesias
(2005) insisted on the importance of distinguishing character and reader
emotions. Although the handling of emotions in this study was simplistic, we
believe that this work is an important step toward utilizing more diverse and
difficult-to-handle emotions in story generation.

In parallel with creating a more sophisticated method, it is also essential to
build a dataset to train and measure the performance of that method. A larger
dataset that includes more diverse range of emotions with less bias is
desirable.

For further discussion on the importance of “creativity” in image narrative
generation for the social implementation of creative AI, we refer to the idea
of creative systems. Colton (2008) introduced the notion of the creative
tripod. The three legs represent the three behaviors required in their system,
including skill, appreciation, and imagination. Later, Elgammal et al. (2017)
rephrased this notion as the ability to produce novel artifacts (imagination),
the ability to generate high-quality artifacts (skill), and the ability of a
model to assess its own creations. Among these three goals of creative
systems, our proposed method has achieved “imagination” and “skill.” However,
the ability to assess creativity has not been established. To achieve this, a
system must be developed that can evaluate the image narratives it generates
by itself; that is, the system must be able to learn criteria for a good image
narrative. As may be noted from the discussions of the results of the human
evaluation, the assessment of creativity is not an easy task, even for humans.
We expect the development of methods to automatically evaluate narratives
would be of considerable benefit in enabling great strides towards the
realization of creative AI.

## Acknowledgements

This work was partially supported by JST AIP Acceleration Research JPMJCR20U3,
Moonshot R&D Grant Number JPMJPS2011, JSPS KAKENHI Grant Number JP19H01115,
and JP20H05556 and Basic Research Grant (Super AI) of Institute for AI and
Beyond of the University of Tokyo. We would like to thank Thomas Westfechtel,
Kenzo Lobos-Tsunekawa, and Yuki Kawana for the helpful discussions.

## References

  * (1)
  * Ackerman and Puglisi (2012) Angela Ackerman and Becca Puglisi. 2012.  _The Emotion Thesaurus: A Writer’s Guide to Character Expression_.  JADD Publishing.
  * Anderson and McMaster (1982) C. W. Anderson and G. E. McMaster. 1982.  Computer assisted modeling of affective tone in written documents.  _Computers and the Humanities_ 16, 1 (01 Sep 1982), 1–9.  https://doi.org/10.1007/BF02259727
  * Anderson et al. (2018) Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. 2018.  Bottom-Up and Top-Down Attention for Image Captioning and Visual Question Answering. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015\.  Neural Machine Translation by Jointly Learning to Align and Translate. In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Yoshua Bengio and Yann LeCun (Eds.).  http://arxiv.org/abs/1409.0473
  * Brahman and Chaturvedi (2020) Faeze Brahman and Snigdha Chaturvedi. 2020.  Modeling Protagonist Emotions for Emotion-Aware Storytelling. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Online, 5277–5294.  https://doi.org/10.18653/v1/2020.emnlp-main.426
  * Chandu et al. (2019) Khyathi Chandu, Shrimai Prabhumoye, Ruslan Salakhutdinov, and Alan W Black. 2019.  “My Way of Telling a Story”: Persona based Grounded Story Generation. In _Proceedings of the Second Workshop on Storytelling_. Association for Computational Linguistics, Florence, Italy, 11–21.  https://doi.org/10.18653/v1/W19-3402
  * Chen et al. (2020) Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu. 2020\.  Uniter: Universal image-text representation learning. In _ECCV_.
  * Chu and Roy (2017) E. Chu and D. Roy. 2017\.  Audio-Visual Sentiment Analysis for Learning Emotional Arcs in Movies. In _2017 IEEE International Conference on Data Mining (ICDM)_. 829–834.
  * Colton (2008) S. Colton. 2008\.  Creativity Versus the Perception of Creativity in Computational Systems. In _AAAI Spring Symposium: Creative Intelligent Systems_.
  * Dathathri et al. (2020) Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. 2020\.  Plug and Play Language Models: A Simple Approach to Controlled Text Generation. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=H1edEyBKDS
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. Association for Computational Linguistics, Minneapolis, Minnesota, 4171–4186.  https://doi.org/10.18653/v1/N19-1423
  * Ekman (1993) Paul Ekman. 1993\.  Facial expression and emotion.  _American Psychologist_ 48(4) (1993), 384–392.
  * Elgammal et al. (2017) Ahmed Elgammal, Bingchen Liu, Mohamed Elhoseiny, and Marian Mazzone. 2017.  Can: Creative adversarial networks, generating” art” by learning about styles and deviating from style norms.  _arXiv preprint arXiv:1706.07068_ (2017).
  * Heise (1965) David R. Heise. 1965\.  Semantic differential profiles for 1,000 most frequent English words.  _Psychological Monographs: General and Applied_ 79, 8 (1965), 1 – 31.  http://search.ebscohost.com/login.aspx?direct=true&db=pdh&AN=2011-19203-001&lang=ja&site=ehost-live
  * Hogan (2006) Patrick Colm Hogan. 2006\.  Narrative Universals, Heroic Tragi-Comedy, and Shakespeare’s Political Ambivalence.  _College Literature_ 33, 1 (2006), 34–66.  http://www.jstor.org/stable/25115327
  * Hogan (2010) Patrick Colm Hogan. 2010\.  A Passion for Plot: Prolegomena to Affective Narratology.  _symplokē_ 18, 1-2 (2010), 65–81.  http://www.jstor.org/stable/10.5250/symploke.18.1-2.0065
  * Hogan (2019) Patrick Colm Hogan. 2019\.  Description, Explanation, and the Meanings of ”Narrative”.  _Evolutionary Studies in Imaginative Culture_ 3 (2020/10/19/ 2019), 45+.  https://link.gale.com/apps/doc/A595569753/AONE?u=unitokyo&sid=AONE&xid=0e1a136b 1, 45, Critical essay.
  * Huang et al. (2016a) Ting-Hao Kenneth Huang, Francis Ferraro, Nasrin Mostafazadeh, Ishan Misra, Aishwarya Agrawal, Jacob Devlin, Ross Girshick, Xiaodong He, Pushmeet Kohli, Dhruv Batra, C. Lawrence Zitnick, Devi Parikh, Lucy Vanderwende, Michel Galley, and Margaret Mitchell. 2016a.  Visual Storytelling. In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. Association for Computational Linguistics, San Diego, California, 1233–1239.  https://doi.org/10.18653/v1/N16-1147
  * Huang et al. (2016b) Ting-Hao K. Huang, Francis Ferraro, Nasrin Mostafazadeh, Ishan Misra, Jacob Devlin, Aishwarya Agrawal, Ross Girshick, Xiaodong He, Pushmeet Kohli, Dhruv Batra, et al. 2016b.  Visual Storytelling. In _15th Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL 2016)_.
  * Iglesias (2005) Karl Iglesias. 2005\.  _Writing for emotional impact : advanced dramatic techniques to attract, engage, and fascinate the reader from beginning to end_.  WingSpan Press.  https://ci.nii.ac.jp/ncid/BB15467795
  * Johnson et al. (2016) Justin Johnson, Andrej Karpathy, and Li Fei-Fei. 2016\.  DenseCap: Fully Convolutional Localization Networks for Dense Captioning. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Johnson-Laird and Oatley (2008) R. N. Johnson-Laird and Keith Oatley. 2008.  _Emotions, music, and literature._ The Guilford Press, New York, NY, US, 102–113.
  * Kim and Klinger (2019a) Evgeny Kim and Roman Klinger. 2019a.  An Analysis of Emotion Communication Channels in Fan-Fiction: Towards Emotional Storytelling. In _Proceedings of the Second Workshop on Storytelling_. Association for Computational Linguistics, Florence, Italy, 56–64.  https://doi.org/10.18653/v1/W19-3406
  * Kim and Klinger (2019b) Evgeny Kim and Roman Klinger. 2019b.  A Survey on Sentiment and Emotion Analysis for Computational Literary Studies.  _Zeitschrift fuer Digitale Geisteswissenschaften_ 4 (2019).  https://doi.org/10.17175/2019_008
  * Krishna et al. (2017) Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-jia Li, David A Shamma, et al. 2017\.  Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations.  _International Journal of Computer Vision_ 123, 1 (2017), 32\.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Online, 7871–7880.  https://doi.org/10.18653/v1/2020.acl-main.703
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. 2014.  Microsoft coco: Common objects in context. In _European conference on computer vision_. Springer, 740–755.
  * Liu et al. (2018) Bei Liu, Jianlong Fu, Makoto P Kato, and Masatoshi Yoshikawa. 2018.  Beyond narrative description: Generating poetry from images by multi-adversarial training. In _Proceedings of the 26th ACM international conference on Multimedia_. 783–791.
  * Liu et al. (2017) Yu Liu, Jianlong Fu, Tao Mei, and Chang Wen Chen. 2017\.  Let Your Photos Talk: Generating Narrative Paragraph for Photo Stream via Bidirectional Attention Recurrent Neural Networks. AAAI Conference on Artificial Intelligence.  https://www.microsoft.com/en-us/research/publication/let-photos-talk-generating-narrative-paragraph-photo-stream-via-bidirectional-attention-recurrent-neural-networks/
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled Weight Decay Regularization. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=Bkg6RiCqY7
  * Lu et al. (2019) Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee. 2019\.  ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks. In _Advances in Neural Information Processing Systems_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2019/file/c74d97b01eae257e44aa9d5bade97baf-Paper.pdf
  * Lugmayr et al. (2017) Artur Lugmayr, Erkki Sutinen, Jarkko Suhonen, Carolina Islas Sedano, Helmut Hlavacs, and Calkin Suero Montero. 2017.  Serious storytelling - a first definition and review.  _Multimedia Tools and Applications_ 76 (07 2017), 15707–15733.  https://doi.org/10.1007/s11042-016-3865-5
  * Luo et al. (2019) Fuli Luo, Damai Dai, Pengcheng Yang, Tianyu Liu, Baobao Chang, Zhifang Sui, and Xu Sun. 2019.  Learning to Control the Fine-grained Sentiment for Story Ending Generation. In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Florence, Italy, 6020–6026.  https://doi.org/10.18653/v1/P19-1603
  * Luong et al. (2015) Thang Luong, Hieu Pham, and Christopher D. Manning. 2015\.  Effective Approaches to Attention-based Neural Machine Translation. In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Lisbon, Portugal, 1412–1421.  https://doi.org/10.18653/v1/D15-1166
  * Pandit and Hogan (2006) Lalita Pandit and Patrick Colm Hogan. 2006.  Introduction: morsels and modules: on embodying cognition in Shakespeare’s plays (1).  _College Literature_ 33 (2020/10/19/ 2006), 1+.  https://link.gale.com/apps/doc/A142620223/ITOF?u=unitokyo&sid=ITOF&xid=d8ead2c9 1, Article.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002\.  Bleu: a Method for Automatic Evaluation of Machine Translation. In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Philadelphia, Pennsylvania, USA, 311–318.  https://doi.org/10.3115/1073083.1073135
  * Plutchik (1980) R. Plutchik. 1980\.  _Emotion, a Psychoevolutionary Synthesis_.  Harper & Row.  https://books.google.co.jp/books?id=G5t9AAAAMAAJ
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018.  Improving language understanding by generative pre-training.  (2018).
  * Reagan et al. (2016) Andrew J. Reagan, Lewis Mitchell, Dilan Kiley, Christopher M. Danforth, and Peter Sheridan Dodds. 2016\.  The emotional arcs of stories are dominated by six basic shapes.  _EPJ Data Science_ 5, 1 (04 Nov 2016), 31\.  https://doi.org/10.1140/epjds/s13688-016-0093-1
  * Ren et al. (2017) S. Ren, K. He, R. Girshick, and J. Sun. 2017\.  Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 39, 6 (2017), 1137–1149.  https://doi.org/10.1109/TPAMI.2016.2577031
  * Russell (1980) James A. Russell. 1980\.  A circumplex model of affect.  _Journal of personality and social psychology_ 39 (1980), 1161–1178.
  * Shin et al. (2018) Andrew Shin, Yoshitaka Ushiku, and Tatsuya Harada. 2018\.  Customized Image Narrative Generation via Interactive Visual Question Generation and Answering. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Somasundaran et al. (2020) Swapna Somasundaran, Xianyang Chen, and Michael Flor. 2020\.  Emotion Arcs of Student Narratives. In _Proceedings of the First Joint Workshop on Narrative Understanding, Storylines, and Events_. Association for Computational Linguistics, Online, 97–107.  https://doi.org/10.18653/v1/2020.nuse-1.12
  * Su et al. (2020) Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai. 2020\.  VL-BERT: Pre-training of Generic Visual-Linguistic Representations. In _Eighth International Conference on Learning Representations (ICLR)_.  https://www.microsoft.com/en-us/research/publication/vl-bert-pre-training-of-generic-visual-linguistic-representations/
  * Tan and Bansal (2019) Hao Tan and Mohit Bansal. 2019.  LXMERT: Learning Cross-Modality Encoder Representations from Transformers. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. Association for Computational Linguistics, Hong Kong, China, 5100–5111.  https://doi.org/10.18653/v1/D19-1514
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017\.  Attention is All you Need. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc., 5998–6008.  https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * Vecchio et al. (2020) Marco Del Vecchio, Alexander Kharlamov, Glenn Parry, and Ganna Pogrebna. 2020.  Improving productivity in Hollywood with data science: Using emotional arcs of movies to drive product and service innovation in entertainment industries.  _Journal of the Operational Research Society_ 0, 0 (2020), 1–28.  https://doi.org/10.1080/01605682.2019.1705194 arXiv:https://doi.org/10.1080/01605682.2019.1705194
  * Vonnegut (1995) Kurt Vonnegut. 1995\.  Kurt Vonnegut on the Shapes of Stories.  https://www.youtube.com/watch?v=oP3c1h8v2ZQ.  Video. Accessed: September 3, 2021.
  * Xu et al. (2020) Peng Xu, Mostofa Patwary, Mohammad Shoeybi, Raul Puri, Pascale Fung, Anima Anandkumar, and Bryan Catanzaro. 2020.  MEGATRON-CNTRL: Controllable Story Generation with External Knowledge Using Large-Scale Language Models. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Punta Cana, Dominican Republic.  arXiv:arXiv:2010.00840
  * Yu et al. (2021) Youngjae Yu, Jiwan Chung, Heeseung Yun, Jongseok Kim, and Gunhee Kim. 2021.  Transitional Adaptation of Pretrained Models for Visual Storytelling. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. 12658–12668.
  * Zhang* et al. (2020) Tianyi Zhang*, Varsha Kishore*, Felix Wu*, Kilian Q. Weinberger, and Yoav Artzi. 2020\.  BERTScore: Evaluating Text Generation with BERT. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=SkeHuCVFDr


# Computing distances on Riemann surfaces

Huck Stepanyants  Department of Physics, Northeastern University, Boston,
Massachusetts 02115, USA  Network Science Institute, Northeastern University,
Boston, Massachusetts 02115, USA  Alan Beardon  Department of Pure Mathematics
and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK
Jeremy Paton  Department of Physics, Northeastern University, Boston,
Massachusetts 02115, USA  Network Science Institute, Northeastern University,
Boston, Massachusetts 02115, USA  Dmitri Krioukov  Department of Physics,
Northeastern University, Boston, Massachusetts 02115, USA  Network Science
Institute, Northeastern University, Boston, Massachusetts 02115, USA
Department of Mathematics, Northeastern University, Boston, Massachusetts
02115, USA  Department of Electrical and Computer Engineering, Northeastern
University, Boston, Massachusetts 02115, USA

###### Abstract

Riemann surfaces are among the simplest and most basic geometric objects. They
appear as key players in many branches of physics, mathematics, and other
sciences. Despite their widespread significance, how to compute distances
between pairs of points on compact Riemann surfaces is surprisingly unknown,
unless the surface is a sphere or a torus. This is because on higher-genus
surfaces, the distance formula involves an infimum over infinitely many terms,
so it cannot be evaluated in practice. Here we derive a computable distance
formula for a broad class of Riemann surfaces. The formula reduces the infimum
to a minimum over an explicit set consisting of finitely many terms. We also
develop a distance computation algorithm, which cannot be expressed as a
formula, but which is more computationally efficient on surfaces with high
genuses. We illustrate both the formula and the algorithm in application to
generalized Bolza surfaces, which are a particular class of highly symmetric
compact Riemann surfaces of any genus greater than 1.

##  I Introduction

Riemann surfaces Forster (1981) are one of the simplest geometric objects,
with widespread applications in physics, mathematics, network science, and
other areas. In physics, Riemann surfaces appear naturally in dynamical
systems. The simplest example is billiards Masur (1986); Gutkin (2012), i.e.,
a freely moving ball confined to a polygon-shaped table, and bouncing off its
sides. This system is equivalently formulated as a particle moving along a
straight line on a compact Riemann surface. In particular, a particle moving
on the Bolza surface, a compact Riemann surface of genus ${g=2}$, is one of
the simplest and earliest chaotic systems studied in physics Hadamard (1898).

Riemann surfaces also appear in integrable systems Babelon  _et al._ (2003);
Gieres (1993). The trajectory of such a system in its parameter space is
effectively confined to a Riemann surface. Elsewhere in mathematical physics,
Riemann surfaces are a part of string theory Kim  _et al._ (2018); Bonelli
_et al._ (2000), potential theory Gustafsson and Tkachev (2009); Chirka
(2018), and approximation theory Komlov  _et al._ (2017); Aptekarev  _et al._
(2014); Aptekarev and Lysov (2010). In quantum physics, Riemann surfaces
appear in the study of fractional quantum Hall states Wen and Niu (1990), spin
liquids Wen (1991), and quantum gravity Aldrovandi and Takhtajan (1997);
Distler and Kawai (1989).

In network science, Riemann surfaces have been used as latent spaces in some
models of networks. For example, networks embedded in hyperbolic spaces are
one of the first models that reproduce a collection of the most basic
properties common to many real-world networks Krioukov  _et al._ (2010). Yet
our main motivation for this paper comes from van der Hoorn  _et al._ (2021);
Hoorn  _et al._ (2023), where the convergence of the Ollivier curvature
Ollivier (2007) of random geometric graphs Penrose (2003); Dall and
Christensen (2002) to the Ricci curvature of their underlying Riemannian
manifolds was proven. Vertices in such graphs are random points in a
Riemannian manifold, and pairs of vertices are connected by edges if the
distance between the two vertices in the manifold is below a fixed threshold.
To build a random geometric graph in a manifold, one thus needs to be able to
compute distances between pairs of points in it.

Figure 1: (a) The two geodesic paths connecting a given pair of points on a
sphere. (b) A topological representation of the 2D torus
${\mathbb{R}^{2}/\mathbb{Z}^{2}}$. The dashed lines are its “seams.” Cutting
the torus along these seams produces the square in (c). The colored solid
lines indicate four of the infinitely many geodesic paths connecting the pair
of points ${1,2}$. (c) The corresponding points and geodesics in the
${\mathbb{R}^{2}}$ representation of the torus. The highlighted central square
is a fundamental domain of the torus and the arrows indicate its side pairing.
The distance between point 1 and 2 on the torus is between 2 and the image
${1^{\prime}}$ of point ${1}$ on ${\mathbb{R}^{2}}$.

Compact Riemann surfaces are two-dimensional Riemannian manifolds. They can be
equipped with a metric which defines the distance between a pair of points on
the surface. Genus ${g=0}$ (sphere), ${g=1}$ (torus), and ${g\geq 2}$ surfaces
admit the spherical, euclidean, and hyperbolic metrics, respectively. While
computing distances on the first two of these surfaces is trivial, the task is
much more difficult on a hyperbolic Riemann surface, where the distance is
given as an infimum over a countably infinite number of geodesics, i.e.,
locally minimal paths. There are no formulas for the distance between points
on any genus ${g\geq 2}$ surface which are computable in finite time. To be
precise, while it is known that the mentioned infimum is actually a minimum
since only a finite set of geodesics needs to be considered (Prop. 2.1, Lu and
Meng (2020)), it is not known what this set actually is for any ${g\geq 2}$
surface, which is surprising since distance plays a crucial role in many
applications of these surfaces mentioned above.

Here we compute distances on Riemann surfaces obtained by pairing the sides of
a convex hyperbolic polygon. We obtain an expression for a finite set of
geodesics whose minimum gives the correct distance between any two points on
these surfaces. This leads to a distance formula which can be evaluated in
finite time. We also develop a fast algorithm for computing distances on these
surfaces using a different set of ideas. For illustrative purposes, we show
how the formula and the algorithm can be applied to computing distances on
generalized Bolza surfaces Ebbens  _et al._ (2022). These are highly symmetric
hyperbolic Riemann surfaces of any genus ${g\geq 2}$. We prove that the time
required to evaluate the formula in this case is ${O\left(g^{\alpha\log
g}\right)}$, where ${\alpha\approx 1.52}$, and show experimentally that the
time required to run the algorithm is ${O\left(g^{4}\right)}$.

In Sec. II, we provide necessary background information on Riemann surfaces,
and a detailed introduction to the distance problem. In Sec. III and IV, we
present and discuss our results, a formula and an algorithm, respectively, for
computing distances on Riemann surfaces. In Sec. V, we apply our results to
generalized Bolza surfaces, and evaluate the resulting running times.

##  II Background and definitions

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 depends on its _genus_ , which is the number of holes the
surface has. Given two points on the genus ${0}$ sphere (Fig. 1(a)), there are
always two geodesics between them, and thus the distance is simply a minimum
of two lengths. In contrast, the number of geodesics between two points on the
torus ${\mathbb{R}^{2}/\mathbb{Z}^{2}}$ is infinite (four are shown in Fig.
1(b)), which could make computing distances on the torus difficult.
Nevertheless, due to its symmetry, the distance ${d}$ on the torus is given by
the simple formula:

$\displaystyle\begin{split}d^{2}=&\left(\frac{1}{2}-\Big{\lvert}\frac{1}{2}-|x_{1}-x_{2}|\Big{\rvert}\right)^{2}\\\
+&\left(\frac{1}{2}-\Big{\lvert}\frac{1}{2}-|y_{1}-y_{2}|\Big{\rvert}\right)^{2},\end{split}$
(1)

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, which is
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 distance formulas analogous to Eq. (1) for any of these surfaces.

Here, we address the distance problem for the hyperbolic Riemann surfaces
known as _quotient surfaces_. A quotient surface is constructed by taking the
quotient of the hyperbolic plane ${\mathbb{H}^{2}}$ with respect to a discrete
subgroup of its isometries, or distance-preserving transformations, called a
_Fuchsian group_ , which we describe next.

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

$\displaystyle ds^{2}=\frac{4dzd\bar{z}}{(1-|z|^{2})^{2}}.$ (2)

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

$\gamma=\left[\begin{matrix}a&\overline{c}\\\
c&\overline{a}\end{matrix}\right],\quad\forall a,c\in\mathbb{C}~{}:~{}\lvert
a\rvert^{2}-\lvert c\rvert^{2}=1,$ (3)

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

$\left[\begin{matrix}a&\overline{c}\\\
c&\overline{a}\end{matrix}\right](z)=\frac{az+\overline{c}}{cz+\overline{a}}.$
(4)

Figure 2: Quotient surface obtained by pairing the sides of a nonregular
pentagon in the order ${1\longleftrightarrow 1,~{}2\longleftrightarrow
3,~{}4\longleftrightarrow 5}$. The generators of the Fuchsian group ${\Gamma}$
map the fundamental polygon ${P}$ (dark gray) to its edge-adjacent neighbors
(light gray). To compute the distance ${\delta^{\star}(z,w)}$ between a pair
of points ${z}$ and ${w}$ on the surface, the lengths ${\delta(z,\gamma w)}$
of the infinite number of geodesics between ${z}$ (red dot) and all of the
images ${\gamma w}$ (blue dots) of ${w}$, ${\forall\gamma\in\Gamma}$, on the
hyperbolic plane ${\mathbb{H}^{2}}$ must be considered. The shortest such
distance, between ${z}$ and the circled image of ${w}$ in the figure, is then
${\delta^{\star}(z,w)}$.

A subgroup ${\Gamma}$ of the isometry group ${\text{PSU}(1,1)}$ is called
_Fuchsian_ if it acts discontinuously on ${\mathbb{H}^{2}}$. This means that
for any point ${z}$, the orbit ${\Gamma z}$ has no _accumulation points_
${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 quotient surface,

$\displaystyle S=\mathbb{H}^{2}\big{/}\Gamma.$ (5)

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

$\displaystyle[z]=\Gamma z.$ (6)

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

$\displaystyle\begin{split}\delta^{\star}(z,w)&=\inf_{\gamma_{1},\gamma_{2}\in\Gamma}\delta(\gamma_{1}z,\gamma_{2}w)\\\
&=\inf_{\gamma\in\Gamma}\delta(z,\gamma w),\end{split}$ (7)

where ${\delta}$ is the distance in ${\mathbb{H}^{2}}$. This formula cannot be
directly evaluated, since ${\Gamma}$ has infinitely many elements. 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 the same pair of points on ${S}$, like those illustrated in Fig.
1 for the sphere and torus, or in Fig. 6 for the Bolza surface.

Here we will focus on surfaces ${S}$ whose Fuchsian groups ${\Gamma}$ are
finitely generated and of the _first kind_. The latter means that any point on
the boundary of the unit disk, which is the boundary at infinity of the
hyperbolic plane ${\mathbb{H}^{2}}$, is an accumulation point of some orbit of
${\Gamma}$. This guarantees that ${S}$ is a compact surface, and by Theorem
10.1.2 in Beardon (2012), ${S}$ has a convex _fundamental_ polygon ${P}$ with
a finite number of sides. A fundamental polygon is one that contains exactly
one representative of each point on ${S}$, see Fig. 2. It is known Beardon
(2012) that in such settings, the generators of the group ${\Gamma}$ pair
sides of ${P}$ by mapping it to its edge-adjacent neighbors, shown in light
gray in Fig. 2. We will further assume that ${P}$ does not have any vertices
at infinity.

Using the geometry of ${P}$, we develop two methods for computing distances on
${S}$. In the next Sec. III, we present a distance formula which reduces the
infinities in Eq. (7) to finite sets. Then in Sec. IV, we develop a more
efficient algorithmic approach to the problem.

Figure 3: Shells ${L_{0}=P}$ (dark gray), ${L_{1}}$ (medium gray), and
${L_{2}}$ (light gray).

##  III Distance formula

Let ${S}$ be a quotient surface obtained by pairing the sides of a convex
fundamental polygon ${P}$, and let ${\Gamma}$ denote its Fuchsian group. Let
${z}$ and ${w}$ be representatives of two points on the surface. In this
section we obtain a computable version of Eq. (7), where instead of minimizing
${\delta(z,\gamma w)}$ over all ${\gamma\in\Gamma}$, we minimize over a finite
subset ${\Gamma_{0}\subset\Gamma}$. We will derive a formula for
${\Gamma_{0}}$ using the geometry of ${P}$.

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

$\displaystyle\bigcup_{\gamma\in T^{k}}\gamma
P\bigg{\backslash}\bigcup_{\gamma\in T^{k-1}}\gamma P,$ (8)

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 value of 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

$\displaystyle\delta^{\star}(z,w)=\min_{\gamma\in T^{k}}\delta(z,\gamma w)$
(9)

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

$\displaystyle\Gamma_{0}=T^{k_{\min}}.$ (10)

We bound ${k_{\min}}$ for an arbitrary surface by the ratio of two distances:
the surface diameter ${\mathscr{D}}$, i.e., the maximum possible distance
between two points on the surface, and the minimal distance ${\mathscr{T}}$
required to traverse a shell. _To traverse_ here means _to cross_ from the
outer boundary of ${L_{k}}$ to the outer boundary of ${L_{k+1}}$ for ${k\geq
0}$. In Appendix A, we show that this distance does not depend on ${k}$, and
satisfies the inequality

$\displaystyle\mathscr{T}\geq\min(\delta,2\epsilon),$ (11)

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

Figure 4: Left: Shortest paths between nonadjacent sides whose minimum gives
${\delta}$. Right: Shortest paths from the midpoint of a side to an adjacent
edge whose minimum gives ${\epsilon}$.

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

$\displaystyle(k_{\min}-1)\mathscr{T}<\mathscr{D}.$ (12)

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

$\displaystyle\mathscr{D}\leq\text{diam}(P)=\max_{ij}\delta(v_{i},v_{j}),$
(13)

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

$\displaystyle k_{\min}\leq
k^{\star}=\Bigg{\lfloor}1+\frac{\max_{ij}\delta(v_{i},v_{j})}{\min(\delta,2\epsilon)}\Bigg{\rfloor}.$
(14)

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

$\displaystyle\delta^{\star}(z,w)=\min_{\gamma\in
T^{k^{\star}}}\delta(z,\gamma w).$ (15)

##  IV Distance algorithm

In this section, we present an algorithm to compute ${\delta^{\star}(z,w)}$ by
minimizing ${\delta(z,\gamma w)}$ over an even smaller subset of ${\Gamma}$.
This subset depends on the location of ${z}$ and is unknown _a priori_
—instead, it is constructed via a search over the polygon tessellation. As we
will see in Sec. V, this method is generally more computationally efficient
than evaluating the distance formula in Sec. III.

Let ${N}$ be the number of sides of ${P}$, and ${g_{i},~{}i=1,2,\dots,N,}$ be
the generators of ${\Gamma}$ and their inverses. With these notations, the
algorithm is:

Algorithm 1 Distance calculation.

${\Delta\leftarrow\\{1\\}}$, ${\gamma_{\min}\leftarrow 1}$

while ${|\Delta|>0}$ do

${\gamma\leftarrow\text{pop}(\Delta)}$

if ${\delta(z,\gamma w)<\delta(z,\gamma_{\min}w)}$ then

${\gamma_{\min}\leftarrow\gamma}$

end if

for ${i=1:N}$ do

if ${\delta(z,\gamma P)<\delta(z,\gamma g_{i}P)<\text{diam}(P)}$ then

${\Delta\leftarrow\text{push}~{}(\gamma g_{i})}$

end if

end for

end while

return ${\gamma_{\min}}$

This algorithm is a depth-first search for an image ${\gamma w}$ of ${w}$,
${\gamma\in\Gamma}$, that minimizes ${\delta(z,\gamma w)}$, in the polygon
tessellation ${\Gamma P}$ illustrated in Fig. 5. We keep track of two
variables: the list of isometries ${\Delta\subset\Gamma}$ corresponding to the
polygons to be searched next, and the current best solution ${\gamma_{\min}}$
that minimizes ${\delta(z,\gamma w)}$ across all ${\gamma}$ searched so far.
Both ${\Delta}$ and ${\gamma_{\min}}$ are initialized to the identity:
${\Delta=\\{1\\},\gamma_{\min}=1}$, corresponding to ${P}$ itself.

Figure 5: Illustration of one branch of the depth-first search algorithm. The
search starts at the fundamental polygon ${P}$ and progresses outward. At
every step, the distance from ${z}$ to all edge-adjacent polygons (light gray)
of the last searched polygon (dark gray) are computed, and those polygons are
added to the list ${\Delta}$ if and only if they are at a greater the distance
from ${z}$. The branch terminates when this distance exceeds the diameter of
$P$.

At every step of the search, we set ${\gamma}$ to be the last element of
${\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 they are at a greater distance from ${z}$:

$\displaystyle\delta(z,\gamma P)<\delta(z,\gamma g_{i}P)<\text{diam}(P).$ (16)

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 distance from ${z}$ to one of their sides, with the exception
${\delta(z,P)=0}$.

The reason to consider only those polygons that increase the distance from
${z}$ is as follows. Consider a geodesic from ${z}$ to ${\gamma w}$, where
${\gamma\neq 1}$. It intersects an edge-adjacent polygon of ${\gamma P}$. This
edge-adjacent polygon is closer to ${z}$ than ${\gamma P}$. Continuing in this
way, we construct a chain of edge-adjacent polygons leading from ${\gamma P}$
to ${P}$ along which the distance to ${z}$ is decreasing, which guarantees
that ${\gamma_{\min}P}$ will be reached in the search.

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

$\displaystyle\begin{split}\delta(z,\gamma_{\min}P)&\leq\delta(z,\gamma_{\min}w)\\\
&\leq\mathscr{D}\\\ &\leq\text{diam}(P),\end{split}$ (17)

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

Figure 6: Top Left: A topological representation of the Bolza surface
${S_{2}}$. The colored lines indicate its “seams,” cutting which and unfolding
the surface produces the octagon on the right. Top Right: The
${\mathbb{H}^{2}}$ representation of ${S_{2}}$. The colors indicate its side
pairing, and arrows show the action of the generators
${\gamma_{i},i=0,2,\dots,7}$ on the fundamental domain. Bottom Left: Four of
the infinitely many geodesic paths connecting two points on ${S_{2}}$. The
dashed lines are the seams at the top. Bottom Right: The corresponding points
and geodesics in the ${\mathbb{H}^{2}}$ representation of ${S_{2}}$. The
distance between points ${z}$ and ${w}$ on the surface is between ${z}$ and
the image ${w^{\prime\prime}}$ of ${w}$ on ${\mathbb{H}^{2}}$.

Finally, the condition in Eq. (16) ensures that the search terminates after a
finite time. To see this, let ${M}$ denote the number of polygons within the
distance ${\text{diam}(P)}$ from ${z}$. Note that the number of branches of
the search cannot exceed the number of sequences of such polygons ordered by
increasing distance, which is ${2^{M}}$. Therefore, the number of polygons
searched does not exceed ${M\cdot 2^{M}}$. We also consider a total of ${N}$
nearest neighbors of ${\gamma P}$ at every search step, even though not all of
these neighbors are added to ${\Delta}$. Therefore the total number of steps
in the algorithm is ${O(NM\cdot 2^{M})}$. In practice, however, we find that
the number of steps is ${O(NM)}$, implying that most polygons are searched
only ${O(1)}$ times, as discussed in the next section.

##  V Application to Generalized Bolza Surfaces

In this section, we apply our general results to the _generalized Bolza
surfaces_ Ebbens  _et al._ (2022), highly symmetric surfaces of any genus
${g\geq 2}$. We denote them by ${S_{g}}$. ${S_{2}}$ is known as the Bolza
surface Bolza (1887).

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

$\displaystyle\begin{split}v_{k}&=\tanh(R/2)\exp\left(\left(k-\frac{1}{2}\right)\frac{\pi
i}{2g}\right),\\\ k&=0,1,\dots,4g-1,\end{split}$ (18)

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

$\displaystyle\cosh R=\cot^{2}\left(\frac{\pi}{4g}\right).$ (19)

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:

$\displaystyle\begin{split}\gamma_{k}&=\left[\begin{matrix}1&\tanh\left(\frac{s}{2}\right)e^{\frac{k\pi
i}{2g}}\\\ \tanh\left(\frac{s}{2}\right)e^{-\frac{k\pi
i}{2g}}&1\end{matrix}\right],\\\ k&=0,1,\dots,2g-1,\end{split}$ (20)

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

$\displaystyle\cosh\left(\frac{s}{2}\right)=\cot\left(\frac{\pi}{4g}\right).$
(21)

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

$\displaystyle\min\\{\delta,2\epsilon\\}=\delta<\text{arccosh}\left(2\cos\left(\frac{\pi}{2g}\right)\right).$
(22)

The diameter ${\mathscr{D}_{g}}$ of ${S_{g}}$ is known Stepanyants  _et al._
(2023),

$\displaystyle\mathscr{D}_{g}=\text{arccosh}\left(\cot\left(\frac{\pi}{4g}\right)\right),$
(23)

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

$\displaystyle
k^{\star}=\Bigg{\lfloor}1+\frac{\text{arccosh}\left(\cot\left(\frac{\pi}{4g}\right)\right)}{\text{arccosh}\left(2\cos\left(\frac{\pi}{2g}\right)\right)}\Bigg{\rfloor}.$
(24)

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

$\displaystyle|T^{k^{\star}}|<(4g)^{2k^{\star}},$ (25)

and since ${k^{\star}\approx\log g/\text{arccosh}~{}2}$ for large ${g}$, the
time required to evaluate the distance formula 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 Appendix B we compute ${k_{\min}}$ exactly using different methods:

$\displaystyle k_{\min}=1.$ (26)

Therefore, the number of ${P}$’s images one must search through to compute the
distance is ${|T^{k_{\min}}|=49}$, corresponding to all polygons adjacent to
${P}$ via either a side or a vertex.

To apply the distance algorithm, we substitute the diameter of the surface for
${\text{diam}(P)}$ in Algorithm 1, and find experimentally in Fig. 7 that the
algorithm running time is ${O(g^{4})}$. We cannot prove this observation
because we cannot estimate the overcount—the average number of times the same
polygon is searched. However, we can show that a maximum of ${O(g^{4})}$
polygons can intersect a hyperbolic circle of radius ${R}$. Therefore, Fig. 7
indicates that each polygon is searched ${O(1)}$ times, so overcounting
appears to be minimal.

Figure 7: Distance algorithm running time ${t}$ on generalized Bolza surfaces
${S_{g}}$ for ${g=2,\dots,100}$. The red line shows the linear fit of the
running times and has slope ${3.94}$.

##  Appendix A Lower bound on ${\mathscr{T}}$

In this section, we prove an upper bound on the shell-crossing distance
${\mathscr{T}}$ for any quotient surface ${S}$ obtained by pairing the sides
of a convex polygon ${P}$.

This distance is

$\displaystyle\mathscr{T}=\min\bigg{\\{}\delta\left(\partial T^{n}(P),\partial
T^{n+1}(P)\right),\quad n\geq 0\bigg{\\}},$

where ${L_{n}=T^{n}(P)}$ is the ${n^{\text{th}}}$ shell, ${T\subseteq\Gamma}$
is the set consisting of all maps from ${P}$ to an 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

$\displaystyle\gamma(P)\subseteq\gamma T(P)\subseteq L_{n+1}.$

Hence,

$\displaystyle\delta\Bigl{(}\partial\gamma(P),\partial\left(\gamma
T(P)\right)\Bigr{)}\leq\delta\Bigl{(}\partial\gamma(P),\partial
L_{n+1}\Bigr{)}.$

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 is equal to
${\delta\Bigl{(}\partial P,\partial\left(T(P)\right)\Bigr{)}}$, which is
${\geq\mathscr{T}}$ by definition of ${\mathscr{T}}$, we conclude that

$\displaystyle\mathscr{T}=\delta\Bigl{(}\partial
P,\partial\left(T(P)\right)\Bigr{)}.$

Figure 8: Type I, II, and III segments (dotted black lines), and edge labels
(green).

Next, we introduce edge labels, which are positive integers modulo the number
${N}$ of distinct (in the quotient sense) sides of ${L_{0}}$. First, the label
${1}$ is assigned to an edge of ${L_{0}}$ without loss of generality. Then,
the ${N-1}$ edges to the left of this edge are labeled ${2,3,\dots,N-1}$ (Fig.
8). Finally, these labels are copied onto all images of ${L_{0}}$ via the
elements of the Fuchsian group ${\mathscr{F}}$. Thus, edges are distinct in
the quotient sense if and only if they have different labels. The process of
filling in labels, which we call _label chasing_ , will be useful later.

Now we will prove the main result of this section:

$\displaystyle\mathscr{T}\geq\min\left(\big{\\{}\delta_{ij},~{}|i-j|\neq
0,1\big{\\}}\bigcup\big{\\{}2\epsilon_{k}\big{\\}}\right),$ (27)

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

Figure 9: Points ${p,q}$ and image ${q^{\prime}}$ in case (1) considered in
Appendix B. In this case, the geodesic ${\overline{pq}}$ crosses from one
polygon into another through the edge ${\overline{v_{1}v_{2}}}$. The
intersection point is denoted by ${I}$. The figure shows the relevant edges
from both polygons, including their common edge ${\overline{v_{1}v_{2}}}$.
Segment ${\overline{pI}}$ is a type I segment while ${\overline{qI}}$ is a
type II segment. Distances ${a=\delta(q,v_{2})}$ and ${b=\delta(p,v_{1})}$ and
edge labels are also shown.

Starting once more with arbitrary points ${p\in\partial L_{0}}$ and
${q\in\partial L_{1}}$, we break ${\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 with labels ${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 type I, since this would imply that
${\overline{pq}}$ circles around a vertex indefinitely without ever reaching
${\partial L_{1}}$, which cannot happen. Similarly, the segments cannot all be
type II. This leaves two cases: there is either (1) a consecutive pair of type
I and type II segments in either order, or (2) a type III segment. In the
first case, we can show using elementary geometry that a lower bound on the
combined length of the type I and type II segments, yielding a lower bound on
${\mathscr{T}}$, is

$\displaystyle\mathscr{T}\geq\min\big{\\{}2\epsilon_{k}\big{\\}}.$ (28)

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

$\displaystyle\mathscr{T}\geq\min\big{\\{}\delta_{ij},~{}|i-j|\neq
0,1\big{\\}}.$ (29)

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

##  Appendix B $k_{\min}=1$ for the Bolza surface

In this section, we prove that ${k_{\min}=1}$ for the Bolza surface.

For an arbitrary point ${z\in P}$, it suffices to show that for any point
${w}$ not in the first shell ${L_{1}}$, defined in Sec. III, there exists a
group element ${\gamma}$ such that ${\delta(z,\gamma w)<\delta(z,w)}$.
Equivalently, this means that the Dirichlet polygon of ${z}$ is contained
inside ${L_{1}}$.

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

  * Case (1):

a segment composed of a pair of type I and type II segments in either order,
or

  * Case (2):

a type III 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 be in the interior
of the Dirichlet polygon of ${z}$. This implies that ${z}$ is in the interior
of the Dirichlet polygon of ${q}$, and so by the same argument ${p}$ must lie
in the interior of the Dirichlet polygon of ${q}$. This means that

$\displaystyle\delta(p,q)<\delta(p,\gamma q)~{}\text{for}~{}\forall\gamma\neq
1.$ (30)

Figure 10: Points ${p,q}$ and images ${p^{\prime},q^{\prime}}$ in case (2). In
this case, ${p}$ and ${q}$ are on the same polygon. Perpendicular bisectors of
${\overline{pp^{\prime}}}$ (red) and ${\overline{qq^{\prime}}}$ (blue),
vertices ${v_{1}}$ and ${v_{2}}$ nearest to ${p}$ and ${q}$, distances
${a=\delta(q,v_{1})}$ and ${b=\delta(p,v_{2})}$, and side length ${s}$ are
also shown.

Consider now case (1) above, where ${p}$ and ${q}$ are endpoints of a type I
segment joined to a type II segment (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
triangle inequality 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

$\displaystyle\begin{split}\delta(p,q)&=\delta(p,I)+\delta(q,I)\\\
&\geq|\delta(v_{1},I)-b|+|\delta(v_{2},I)-a|\\\
&\geq|\delta(v_{1},I)-b+\delta(v_{2},I)-a|\\\ &=|s-a-b|\\\
&=\delta(p,q^{\prime}),\end{split}$ (31)

which is a contradiction with Eq. (30).

In case (2), points ${p}$ and ${q}$ are endpoints of a type III segment, so
they lie on sides of the same polygon. Consider the images
${p^{\prime},q^{\prime}}$ of ${p,q}$ located on the opposite sides of the
polygon, and draw the perpendicular bisectors of ${\overline{pp^{\prime}}}$
and ${\overline{qq^{\prime}}}$ (Fig. 10). Observe that ${q}$ must be closer to
${p}$ than to ${p^{\prime}}$ (on the same side of the vertical perpendicular
bisector as ${p}$), and ${p}$ must be closer to ${q}$ than to ${q^{\prime}}$
(on the same side of the horizontal perpendicular bisector as ${q}$). This is
only possible when ${p}$ and ${q}$ are exactly 2 edges apart and lie in the
same quarter-polygon, as shown in Fig. 10.

Figure 11: Points ${p,q}$ and image ${q^{\prime\prime}}$ in case (2). Vertices
${v_{1},v_{2}}$, distances ${a,b}$, side length ${s}$, and edge labels are
also shown.

Next, assume without loss of generality that ${q}$ is on side ${1}$ (Fig. 11),
and use label-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 right triangle
${\triangle pv_{2}q^{\prime\prime}}$, one can show that

$\displaystyle\begin{split}\cosh(\delta(p,q))&=\cosh^{2}\left(\frac{s}{2}\right)\cosh\left(\frac{s}{2}-b\right)\\\
&\times\cosh\left(\frac{s}{2}-a\right)\\\
&-\sinh\left(\frac{s}{2}\right)\sinh(s-a-b),\end{split}$ (32)
$\displaystyle\cosh(\delta(p,q^{\prime\prime}))$ $\displaystyle=\cosh a\cosh
b.$ (33)

Rearranging the first equation gives

$\displaystyle\frac{\cosh(\delta(p,q))}{\cosh b}=$
$\displaystyle\sinh\left(\frac{s}{2}\right)\cosh\left(\frac{s}{2}-a\right)$
$\displaystyle\times\bigg{[}\sinh\left(\frac{s}{2}\right)\tanh\left(\frac{s}{2}-a\right)$
$\displaystyle+\cosh\left(\frac{s}{2}\right)-\cosh^{2}\left(\frac{s}{2}\right)\bigg{]}\tanh
b$ $\displaystyle+C,$ (34)

where ${C}$ is a function of ${s}$ and ${a}$ only. The coefficient in front of
${\tanh b}$ is a decreasing function of ${a}$ and is negative at ${a=0}$. It
is therefore negative for all ${0\leq a\leq s/2}$. It follows that as a
function of ${b}$, ${\cosh(\delta(p,q))/\cosh b}$ is minimized at ${b=s/2}$.
It also follows from Eq. (33) that ${\cosh(\delta(p,q^{\prime\prime}))/\cosh
b}$ does not depend on ${b}$. To obtain a contradiction, it therefore suffices
to show that

$\displaystyle\frac{\cosh(\delta(p,q))}{\cosh
b}\geq\frac{\cosh(\delta(p,q^{\prime\prime}))}{\cosh b}$ (35)

for ${0\leq a\leq s/2}$ and ${b=s/2}$. Plugging ${b=s/2}$ into Eq. (32) gives

$\displaystyle\begin{split}\frac{\cosh(\delta(p,q))}{\cosh(s/2)}&=\cosh\left(\frac{s}{2}\right)\cosh\left(\frac{s}{2}-a\right)\\\
&-\tanh\left(\frac{s}{2}\right)\sinh\left(\frac{s}{2}-a\right).\end{split}$
(36)

Using ${\cosh(s/2)>1}$ in the last equation, we get

$\displaystyle\begin{split}\frac{\cosh(\delta(p,q))}{\cosh(s/2)}&\geq\cosh\left(\frac{s}{2}\right)\cosh\left(\frac{s}{2}-a\right)\\\
&-\sinh\left(\frac{s}{2}\right)\sinh\left(\frac{s}{2}-a\right)\\\ &=\cosh a\\\
&=\frac{\cosh(\delta(p,q^{\prime\prime}))}{\cosh(s/2)},\end{split}$ (37)

which is a contradiction completing the proof.

###### Acknowledgements.

We thank Florent Balacheff, Maxime Fortier Bourque, Antonio Costa, Benson
Farb, Svetlana Katok, Gabor Lippner, Marissa Loving, Curtis McMullen, Hugo
Parlier, John Ratcliffe, and Chaitanya Tappu for useful discussions and
suggestions. This work was supported by NSF grant Nos. IIS-1741355 and
CCF-2311160.

## References

  * Forster (1981) O. Forster,  _Lectures on Riemann Surfaces_ (Springer New York, 1981).
  * Masur (1986) H. Masur,  _Closed trajectories for quadratic differentials with an application to billiards,_Duke Mathematical Journal 53, 307 (1986).
  * Gutkin (2012) E. Gutkin,  _Billiard dynamics: An updated survey with the emphasis on open problems,_Chaos: An Interdisciplinary Journal of Nonlinear Science 22, 026116 (2012).
  * Hadamard (1898) J. Hadamard,  _Les surfaces à courbures opposées et leurs lignes géodésiques. Journal de Mathématiques Pures et Appliquées 4, 27–74, _http://eudml.org/doc/235168 (1898).
  * Babelon  _et al._ (2003) O. Babelon, D. Bernard, and M. Talon,  _Introduction to classical integrable systems_ (Cambridge University Press, 2003).
  * Gieres (1993) F. Gieres,  _Conformally covariant operators on Riemann surfaces (with applications to conformal and integrable models),_International Journal of Modern Physics A 8, 1 (1993).
  * Kim  _et al._ (2018) H.-C. Kim, S. S. Razamat, C. Vafa, and G. Zafrir,  _E-string theory on Riemann surfaces,_Fortschritte der Physik 66, 1700074 (2018).
  * Bonelli  _et al._ (2000) G. Bonelli, L. Bonora, F. Nesti, and A. Tomasiello,  _Heterotic matrix string theory and Riemann surfaces,_Nuclear Physics B 564, 86 (2000).
  * Gustafsson and Tkachev (2009) B. Gustafsson and V. G. Tkachev,  _The resultant on compact Riemann surfaces,_Communications in Mathematical Physics 286, 313 (2009).
  * Chirka (2018) E. M. Chirka,  _Potentials on a compact Riemann surface,_Proceedings of the Steklov Institute of Mathematics 301, 272 (2018).
  * Komlov  _et al._ (2017) A. V. Komlov, R. V. Palvelev, S. P. Suetin, and E. M. Chirka,  _Hermite–Padé approximants for meromorphic functions on a compact Riemann surface,_Russian Mathematical Surveys 72, 671 (2017).
  * Aptekarev  _et al._ (2014) A. Aptekarev, G. Lagomasino, and A. Martínez-Finkelshtein,  _On Nikishin systems with discrete components and weak asymptotics of multiple orthogonal polynomials,_Russian Mathematical Surveys 72, 3 (2014).
  * Aptekarev and Lysov (2010) A. I. Aptekarev and V. G. Lysov,  _Systems of Markov functions generated by graphs and the asymptotics of their Hermite-Padé approximants,_Sbornik: Mathematics 201, 183 (2010).
  * Wen and Niu (1990) X.-G. Wen and Q. Niu,  _Ground-state degeneracy of the fractional quantum Hall states in the presence of a random potential and on high-genus Riemann surfaces,_Physical Review B 41, 9377 (1990).
  * Wen (1991) X.-G. Wen,  _Mean-field theory of spin-liquid states with finite energy gap and topological orders,_Physical Review B 44, 2664 (1991).
  * Aldrovandi and Takhtajan (1997) E. Aldrovandi and L. A. Takhtajan,  _Generating functional in CFT and effective action for two-dimensional quantum gravity on higher genus Riemann surfaces,_Communications in Mathematical Physics 188, 29 (1997).
  * Distler and Kawai (1989) J. Distler and H. Kawai,  _Conformal field theory and 2D quantum gravity,_Nuclear Physics B 321, 509 (1989).
  * Krioukov  _et al._ (2010) D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá,  _Hyperbolic geometry of complex networks,_Physical Review E 82 (2010).
  * van der Hoorn  _et al._ (2021) P. van der Hoorn, W. J. Cunningham, G. Lippner, C. Trugenberger, and D. Krioukov,  _Ollivier-Ricci curvature convergence in random geometric graphs,_Physical Review Research 3, 013211 (2021).
  * Hoorn  _et al._ (2023) P. v. d. Hoorn, G. Lippner, C. Trugenberger, and D. Krioukov,  _Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds,_Discrete & Computational Geometry 70, 671 (2023).
  * Ollivier (2007) Y. Ollivier,  _Ricci curvature of metric spaces,_Comptes Rendus Mathematique 345, 643 (2007).
  * Penrose (2003) M. Penrose,  _Random Geometric Graphs_ (Oxford University Press, Oxford, 2003).
  * Dall and Christensen (2002) J. Dall and M. Christensen,  _Random geometric graphs,_Physical Review E 66, 016121 (2002).
  * Lu and Meng (2020) Z. Lu and X. Meng,  _Erdős distinct distances in hyperbolic surfaces,_arXiv:2006.16565 (2020).
  * Ebbens  _et al._ (2022) M. Ebbens, I. Iordanov, M. Teillaud, and G. Vegter,  _Delaunay triangulations of generalized Bolza surfaces,_Journal of Computational Geometry 13, 125– (2022).
  * Beardon (2012) A. F. Beardon,  _The Geometry of Discrete Groups_ (Springer Science & Business Media, New York, 2012).
  * Bolza (1887) O. Bolza,  _On binary sextics with linear transformations into themselves,_American Journal of Mathematics 10, 47 (1887).
  * Stepanyants  _et al._ (2023) H. Stepanyants, A. Beardon, J. Paton, and D. Krioukov,  _Diameter of Compact Riemann Surfaces,_arXiv:2301.10844 (2023).