# Measuring the Impact of Explanation Bias: A Study of Natural Language
Justifications for Recommender Systems

Krisztian Balog  GoogleStavangerNorway<EMAIL_ADDRESS>,  Filip
Radlinski  GoogleLondonUK<EMAIL_ADDRESS>and  Andrey Petrov
GoogleLondonUK<EMAIL_ADDRESS>
(2023)

###### Abstract.

Despite the potential impact of explanations on decision making, there is a
lack of research on quantifying their effect on users’ choices. This paper
presents an experimental protocol for measuring the degree to which positively
or negatively biased explanations can lead to users choosing suboptimal
recommendations. Key elements of this protocol include a preference
elicitation stage to allow for personalizing recommendations, manual
identification and extraction of item aspects from reviews, and a controlled
method for introducing bias through the combination of both positive and
negative aspects. We study explanations in two different textual formats: as a
list of item aspects and as fluent natural language text. Through a user study
with 129 participants, we demonstrate that explanations can significantly
affect users’ selections and that these findings generalize across explanation
formats.

Explainable recommendation; natural language justifications; evaluating
explanations; explanation types; explanation bias

††journalyear: 2023††copyright: rightsretained††conference: Extended Abstracts
of the 2023 CHI Conference on Human Factors in Computing Systems; April 23–28,
2023; Hamburg, Germany††booktitle: Extended Abstracts of the 2023 CHI
Conference on Human Factors in Computing Systems (CHI EA ’23), April 23–28,
2023, Hamburg, Germany††doi: 10.1145/3544549.3585748††isbn:
978-1-4503-9422-2/23/04††ccs: Human-centered computing User studies††ccs:
Human-centered computing Empirical studies in HCI††ccs: Information systems
Recommender systems

##  1\. Introduction

Recommender systems have become pervasive in modern society, leading to many
studies of the degree of trust people place in provided recommendations
(Harman et al., 2014; Kunkel et al., 2019). As a result, significant attention
has been paid to equip these systems with explanation facilities to help users
make informed decisions (Tintarev and Masthoff, 2015; Nunes and Jannach, 2017;
Zhang and Chen, 2020). In one of the earliest studies, Herlocker et al. (2000)
showed that explanations can make it more likely that people will adopt the
recommendations made. Yet, studies measuring the eventual satisfaction with
recommendations found that certain types of explanations can cause users to
over- or underestimate the real value of a recommended item (Bilgic and
Mooney, 2005; Gedikli et al., 2014). Even though explanations are known to be
able to significantly affect the decision-making process of users (Tintarev
and Masthoff, 2015), significant gaps remain when it comes to measuring and
understanding their effects (Piscopo et al., 2022). The bulk of studies of
explanations focus on the subjective question of how people perceive the
recommendations (Balog and Radlinski, 2020; Musto et al., 2019; Nunes and
Jannach, 2017; Chang et al., 2016; Gedikli et al., 2014). Less attention has
been paid to how to objectively quantify the degree to which explanations
affect the choices that people make. This is closely related to the concept of
_persuasiveness_ , which is the ability of an explanation “to convince the
user to accept or disregard certain items” (Gedikli et al., 2014). Past
research has differentiated between over- and underestimate-oriented
persuasiveness of _explanation types_ (Bilgic and Mooney, 2005; Gedikli et
al., 2014). Instead, we study in quantitative detail how bias in the _content_
of natural language explanations can impact users’ choices.

A key difference to past work is that prior research has focused almost
exclusively on explanations that highlight positive aspects of items, i.e.,
endorse a selection, perhaps by drawing similarities to other items the user
has previously indicated that they liked. Explanations can also help users
make decisions by highlighting why _not_ to select something. We perform the
first study that intentionally biases explanations towards positive or
negative aspects of items in a controlled manner in the context of items where
we have a prior understanding of which items users should find most relevant.
We can thus quantify the degree to which positively or negatively biased
explanations lead to users choosing suboptimal recommendations. To achieve
this, we are inspired by the work of Musto et al. (2019) who “ _processed and
analyzed the reviews in order to obtain a set of characteristics that are
often discussed in the reviews (with a positive sentiment, of course) and can
induce the user in enjoying the recommended item._ ” However, we identify
positive as well as _negative_ aspects—as argued by Bilgic and Mooney (2005),
“ _the goal of an explanation should not be to ‘sell’ the user on the item but
rather to help the user to make an informed judgment._ ”

The primary research question we address is how to quantify the degree to
which explanations influence user decisions, either in the positive or
negative direction when presented with a set of recommendations from which to
choose. Our key contribution is the design of an experiment protocol that
allows for a quantitative study of the impact of explanations on users’
choices. Our second contribution is a preliminary analysis of the results
obtained with 129 subjects. We provide baseline statistics showing how often
users presented with biased explanations can end up selecting less relevant
suggestions. Beyond this, we study the effect of the _format_ of explanations,
directly comparing two common formats, namely lists of item aspects and
natural language text. We show that while these formats lead to a similar
overall behavior, the effect of explanation bias is more pronounced in case of
aspect lists than for natural language text. These may be considered as
factors when designing explainable recommender systems. Overall, this work
provides a framework for measuring and optimizing explanations to help guide
users to make informed decisions.

##  2\. Related work

Research on explainable recommendation has focused on different dimensions,
including (1) explanation goal (e.g., transparency, trust, effectiveness,
persuasiveness), (2) style (e.g., content-based, collaborative-based,
knowledge/utility-based), (3) scope (e.g., user model, process, recommended
item), and (4) format (e.g., textual, visual) (Tintarev and Masthoff, 2015;
Nunes and Jannach, 2017; Zhang and Chen, 2020). Another way of categorization
is by the method used to generate explanations: self-explainable recommender
models vs. post-hoc explanations (i.e., _justifications_) (Biran and Cotton,
2017). Our approach can be classified as content-based, post-hoc, natural
language explanation generation. We do not aim to explain _why_ a given item
was recommended, but rather provide the user with additional information
(relevant characteristics of items) with the purpose of aiding them in their
decision making.

Various graphical and textual explanation formats have been considered in the
past (Herlocker et al., 2000; Gedikli et al., 2014), with natural language
being the most popular both historically (Nunes and Jannach, 2017) and in
recent years (Balog and Radlinski, 2020; Chang et al., 2016; Musto et al.,
2019; Ni et al., 2019; Penha et al., 2022). Text-based explanations range from
tags or keywords (Bilgic and Mooney, 2005; Vig et al., 2009) to single or
multiple sentences (Chang et al., 2016; Balog and Radlinski, 2020; Tintarev
and Masthoff, 2012; Penha et al., 2022; Musto et al., 2019). In this work, we
consider both short descriptive phrases (aspects) and fluent natural language
summaries as explanations. Unique to our approach is that the summaries are
generated directly from the aspects, allowing for a direct comparison between
the two explanation formats.

Reviews have been exploited for improving recommendations, leading to a line
of work on review-aware recommender systems (Chen et al., 2015; Hernández-
Rubio et al., 2019), naturally endowing them with a higher degree of
explainability and transparency (He et al., 2015). In contrast, our work
continues the thread of research on leveraging reviews for the purpose of
generating post-hoc recommendation justifications, treating the recommender
engine as a black box (Muhammad et al., 2016; Musto et al., 2019; Chang et
al., 2016; Ni et al., 2019; Penha et al., 2022). Muhammad et al. (2016)
highlight the most important features (pros and cons) of an item that are
likely to matter to the user (based on their own reviews). Similarly, Chen and
Wang (2014, 2017) extract sentiments on specific product attributes and use
them to present the user with alternatives to a given recommendation and
explaining the trade-offs, i.e., which attributes would be improved and which
ones would be compromised. Chang et al. (2016) employ a multi-step pipeline
for generating natural language explanations using crowdsourcing, by (1)
refining algorithmically generated tag clusters, (2) writing explanations for
these clusters by synthesizing review text, and (3) selecting the best
explanations by voting. We follow a similar approach, but present crowd
workers with a significantly simpler task: given a set of reviews, they only
need to extract positive and negative aspects from them. We then either
present these aspects as a list, or turn them into fluent natural language
text using state-of-the-art neural language modeling techniques. Ni et al.
(2019) identify review segments that can serve as justifications and explore
the use of neural language models to generate convincing and diverse
justifications. Penha et al. (2022) choose a helpful sentence for an item from
its review, predicted by a classifier, and use that to generate a template-
based explanation of an item or a pair of items. Most closely related to ours
is the work by Musto et al. (2019), which presents a fully automated pipeline
for generating natural language justifications by (1) extracting a set of
aspects that characterize the item, (2) identifying the most relevant ones,
and (3) extracting and aggregating review sentences discussing these aspects.
Though there are similarities in the explanation generation workflow, their
focus is on the algorithmic aspects of automation, while ours is on
understanding the _impact_ of explanations. Our aspects are short descriptive
phrases, not limited to nouns as in (Musto et al., 2019), which we extract and
curate manually. Most importantly, we include aspects with negative sentiment
as well, not only positive ones, in the explanations.

Evaluation of explanations may target interface-related aspects (Chen and
Wang, 2017; Muhammad et al., 2016; Bilgic and Mooney, 2005; Herlocker et al.,
2000; Gedikli et al., 2014), quantifiable properties of generation approaches
(e.g., readability of natural language (Costa et al., 2018) or fidelity of
post-hoc explanations (Peake and Wang, 2018)), or subjective perceptions of
quality (in terms of transparency, trust, effectiveness, etc.) through
questionnaires (Balog and Radlinski, 2020; Musto et al., 2019; Nunes and
Jannach, 2017; Chang et al., 2016; Gedikli et al., 2014). Most relevant to our
work is the evaluation protocol proposed in (Bilgic and Mooney, 2005) (also
followed in (Gedikli et al., 2014)) for measuring the _persuasiveness_ of
explanation types, in terms of differences between an initial rating, given
based on the explanation, and a second rating, given after the “consumption”
of the item. Consumption is approximated by subjects receiving more details
(description or user reviews) about the item. Then, they are asked adjust
their rating based on this additional information. Our experiment design is
more realistic in that we do not assume item consumption, but rather measure
the impact of explanations via the item selection choices users make, with a
prior understanding of what they would most likely pick.

##  3\. Study Design

This section presents the study we designed in order to answer the following
two research questions:

  * •

RQ1 How much can explanations influence users’ decisions when presented with a
set of item recommendations?

  * •

RQ2 How big a role does the presentation format of explanations play in the
results?

Our experiment centers around a set of item selection tasks, with participants
asked to choose among three items that are presented to them as
recommendations. These items are selected, based on an initial preference
elicitation phase, such that we know which of the three items the user would
probably like the most and which one the least. By applying a controlled
amount of bias via explanations to a randomly chosen item, we are able to
measure how much users may be influenced in their choices—it is of particular
interest to observe how often they would be inclined to pick a different item
than that which they would most likely choose (statistically speaking). Using
a within-subject design, participants are exposed to different experimental
conditions, varying the amount of bias and the format of explanations.

###  3.1. Overview

The study is conducted in the movies domain. As watching films is one of the
top media consumption and entertainment activities, most people can easily
relate to it without any training or prerequisite knowledge. Indeed, movies
have been one of the most studied domains for explainable recommendation
(Chang et al., 2016; Balog et al., 2019; Balog and Radlinski, 2020; Vig et
al., 2009; Tintarev and Masthoff, 2012; Musto et al., 2019; Ghazimatin et al.,
2021; Herlocker et al., 2000; Gedikli et al., 2014). Note that even though the
instructions are tailored specifically to movies, the proposed design is
generic and can be applied in other domains.

Figure 1. Overview of our experiment design.

Schematic view of the two stages of the experiment design. The top figure
corresponds to Stage 1 and has a 3-column tabular layout. The headings are:
”Item,” ”Seen?,” and ”Rating (if seen)”. Items have placeholders for image and
title, seen has radio buttons with Y and N values, and rating has a number of
radio buttons. The bottom figure corresponds to Stage 2, where three items are
shown next to each other with image, title, description placeholders and a
radio button next to each for the user to make a selection.

To be able to provide participants with personalized recommendations, the
study is divided into two stages, as shown in Fig. 1.111Additionally,
participants are asked to fill out a post-task questionnaire to allow for a
qualitative analysis of their preferences in the future. In Stage 1,
participants indicate for each movie, in our pool of 400 candidates items,
whether they have watched it, and if yes, how much they liked it (on a three-
point scale of disliked, neutral, and liked). In Stage 2, participants
complete a total of 12 item selection tasks, corresponding to various
experimental conditions in a random order (cf. Table 1). In each task, they
are offered three movies to choose from, selected among the items they have
not watched yet. For each movie the title, poster, and synopsis are shown,
followed (optionally) by an explanation (see Fig. 6 in Appendix A.3). The item
selection task is situated in the following scenario: _Imagine that you are
traveling alone, and while in transit, you have been offered a free movie
rental from a service that only allows you to choose from three possible
options. In each of the following tasks, select the movie you would prefer to
watch based on the information provided._

We hypothesize that the explanations accompanying the recommendations can
influence users’ item selection choices. To test this, we contrast a baseline
setting, showing neutral explanations for all three items, with a “biased”
setting: showing neutral explanations for two of the items, while making the
explanation for the third item overall more positive or negative in a
controlled manner. Next, we provide details on each element of the experiment
design.

Table 1. Experimental conditions. Each participant experiences each of the listed conditions exactly once (in random order). ID | Bias | Explanation | Aspects+ | Aspects-
---|---|---|---|---
_Baselines_
#1 | No bias | - | - | -
#2
#3 | Itemized | 2 | 2
#4 | Fluent-NL
_One random item biased by a more positive/negative explanation_
#5 | Bias + | Itemized | 3 | 1
#6 | Fluent-NL
#7 | Bias - | Itemized | 1 | 3
#8 | Fluent-NL
#9 | Bias ++ | Itemized | 4 | 0
#10 | Fluent-NL
#11 | Bias – | Itemized | 0 | 4
#12 | Fluent-NL

###  3.2. Item Collection

We use the MovieLens 25M collection (Harper and Konstan, 2015) along with the
Movies and TV subset of the Amazon Reviews 2018 dataset (Ni et al., 2019).
Mappings between the two are provided by the Reviews2Movielens dataset (v2
mappings) released in (Zemlyanskiy et al., 2021). A total of 400 movies are
sampled, using a slightly modified version of the stratified sampling approach
employed in (Balog et al., 2019): (i) the top 150 movies of all time by the
number of ratings received and (ii) a random movie for each year between 1992
and 2016, and for each of the top 10 most popular genres (action, adventure,
documentary, comedy, crime, drama, horror, romance, sci-fi, and thriller),
that is not already in the top-150 set.222If it was not possible, then a
random movie is sampled from the same year. We require each movie to have at
least 100 associated reviews.

###  3.3. Generating Personalized Recommendations

Study participants are presented with a set of item selection tasks. In each
task, they need to make a choice between three items $x_{a}$, $x_{b}$, and
$x_{c}$, shown in random order. These items are selected, based on the initial
preference elicitation phase, such that the user’s estimated preference
ordering is $x_{a}\succ x_{b}\succ x_{c}$. For that, we employ an ensemble of
three established recommender algorithms, representing different classes of
collaborative filtering approaches that performed best in a prior user study
on movie recommendations (Balog et al., 2019): Item-based k-Nearest Neighbors
(Sarwar et al., 2001), Weighted Regularized Matrix Factorization (Hu et al.,
2008), and a Sparse Linear Method (Ning and Karypis, 2011). The predictions of
these algorithms are combined into an ensemble recommendation using a
consensus-based voting system (Borda count). This ensemble is expected to
yield better performance than any of the individual recommenders. Crucially,
only movies not yet seen by the user are eligible for recommendation, as
showing already seen items might affect the measurements of the impact of
explanations (Balog and Radlinski, 2020).

| Bucket A | Bucket B | Bucket C
---|---|---|---
Item rank | $1$ | $\dots$ | $i$ | $\dots$ | $s$ | $s+1$ | $\dots$ | $s+i$ | $\dots$ | $2s$ | $2s+1$ | $\dots$ | $2s+i$ | $\dots$ | $n$

Figure 2. Sampling of items for item selection tasks to ensure the largest
distance between sampled items across all item samples.

Table with three columns: Bucket A, Bucket B, and Bucket C. Within each column
the item ranks are shown. In Bucket A these range from 1 to s, in Bucket B
from s+1 to 2s, and in Bucket C from 2s+1 to n. Item ranks i, s+i, and 2s+i
within Buckets A, B, and C, respectively, are highlighted.

| funny, silly, sweet |  | good, clean, and exciting movie |  | suspenseful
---|---|---|---|---|---
| awesome comedy |  | full of action |  | a bad remake
| a few little laughs but not enough |  | entertainment for the whole family |  | predictable
| lackluster direction |  | predictable attempt at comedy |  | low budget effects
This movie is said to be funny, silly, sweet, and an awesome comedy. However, others say it has a few little laughs but not enough, and a lackluster direction. |  This movie is said to be good, clean, and exciting, full of action, and an entertainment for the whole family, but some people find it to be a predictable attempt at comedy. |  This movie is said to be suspenseful, but others find it to be a bad remake and predictable, with low-budget effects.

Figure 3. Examples of itemized and fluent-NL explanations, based on the same
set of aspects.

Table with three columns and two rows. The columns illustrate different
explanations, the rows correspond to different explanation styles: itemized
and fluent text. Itemized explanations have green thumbs up and red thumbs
down icons as the bullet symbol. The left column has two positive and two
negative aspects, the middle column has three positive and one negative
aspects, and the right column has one positive and three negative aspects.

Given a total of $m=12$ item selection tasks to be completed by each
participant (cf. Table 1), $m\times 3$ items are sampled as
follows.333Participants with fewer than 3$\times$12 not yet seen movies are
excluded from the study. Let $n$ denote the number of movies the person has
not seen yet, which are sorted by recommendation score, such that $x_{1}$ is
the highest and $x_{n}$ is the lowest ranked suggestion. These items are
divided into three approximately equal-sized ($s=\lfloor n/3\rfloor$) buckets
A, B, and C. To sample $m$ sets of three items, the items picked in set
$i\in[1..m]$ are: $x_{a}=x_{i}$, $x_{b}=x_{s+i}$, and $x_{c}=x_{2s+i}$. This
ensures that the three items shown to the user are as far apart from each
other as possible, in terms of recommendation score, across all item selection
tasks; see Fig. 2 for a visual explanation. The $m$ sets of items ($x_{a}$,
$x_{b}$, and $x_{c}$) are assigned randomly to the $m$ experimental
conditions.

###  3.4. Generating Explanations

Table 2. Controlled generation of explanation sentiment based on the number of positive and negative aspects mentioned. | Extreme | Negative | Neutral | Positive | Extreme
---|---|---|---|---|---
| Negative | Positive
| (Bias –) | (Bias -) | (No bias) | (Bias +) | (Bias ++)
Aspects+ | 0 | 1 | 2 | 3 | 4
Aspects- | 4 | 3 | 2 | 1 | 0

To quantify how much explanations can influence user decisions, we need a
controlled way of generating explanations which are by default neutral, but
can be biased to have a more positive or negative overall sentiment. To
operationally define what it takes for an explanation to be overall
neutral/positive/negative we assume that for each item $M=4$ positive and $M$
negative aspects have been identified. An aspect in this context is a short
natural language text (typically 1–5 words in length) that expresses why a
movie might be liked or disliked, such as “action-packed,” “quite corny and
unrealistic,” or “classic literature brilliantly realized.” The sentiment of
an explanation can then be controlled by adjusting how many positive and
negative aspects it mentions, with Aspects+ $=$ Aspects- $=M/2$ representing a
neutral explanation (cf. Table 2). Aspects are extracted from reviews, as
detailed below in Section 3.4.1.

We consider two explanation formats: itemized and fluent natural language
text. _Itemized_ explanations are comprised of a list of aspects with their
corresponding sentiment symbolized by a thumbs up or down icon. Alternatively,
the _fluent-NL_ format presents the same information as fluent natural
language description; see Fig. 3 for an illustration. The generation of
fluent-NL explanations from a list of item aspects is detailed below in
Section 3.4.2.

####  3.4.1. Aspect Extraction

Positive and negative aspects are extracted manually using crowdsourcing.
Given 10 positive (4-5 stars) and 10 negative reviews (1-2 stars), workers are
asked to find aspects that complete the sentence: _This movie may be liked
(disliked) because it is/has/contains ____. The goal is not to be exhaustive,
but rather focus on high data quality (i.e., favor precision over recall). To
ensure that, extracted aspects are further checked and manually filtered by
authors of the paper to remove too harsh or offensive language, aspects that
are too generic (e.g., excellent, terrible) or are not about movie itself
(concern price, delivery, medium, etc.). Movies with fewer than 4 positive and
4 negative aspects after filtering are removed from the recommendation pool
(31 in total). Further details are in Appendix A.1.

####  3.4.2. Fluent-NL Explanation Generation

We turn the selected aspects into fluent natural language sentences using a
large language model with state-of-the-art few-shot performance (PaLM
(Chowdhery et al., 2022), 62b parameter model). A separate prompt is created
for each combination of Aspects+ and Aspects-, containing three hand-crafted
training examples.

###  3.5. Participant Condition Assignment

The study is performed through crowdsourcing via a web-based platform. Each
participant is presented with each of the 12 experimental conditions, shown in
Table 1, exactly once in a random order. In fact, there are only 11 unique
conditions, as #1 and #2 are the same, but this “no explanations” setting is
shown twice in order to establish a robust baseline. The other baseline is to
show neutral explanations, in two different formats (#3–#4). In the remaining
conditions (#5-#12) one of the three items shown to the rater is randomly
selected to be “biased,” by changing the number of positive and negative
aspects in the explanation that accompanies that item. The explanations for
the other two items stay neutral, i.e., showing exactly two positive and two
negative aspects. These conditions allow us to make comparisons between
different explanation types, i.e., no explanation (#1–#2) vs. itemized (#3,
#5, #7, #9, #11) vs. fluent-NL (#4, #6, #8, #10, #12) explanations, and
between the amount of bias, i.e., no bias (#1–#4) vs. moderate (#5–#8) vs.
large (#9–#12) bias.

We acknowledge that listing positive aspects first, followed by negative ones,
or the other way around, might have an impact. At the same time, to avoid
further complicating the design by introducing yet another dimension, we
control for this variable by balancing the two possible settings, i.e.,
positives-first and negatives-first. Specifically, when both positive and
negative aspects are displayed (#3–#8), we make those fully balanced for each
participant as well as across all participants by cycling through pre-defined
sequences in a Latin Square-like design (see Table 5 in Appendix A.2).

##  4\. Results

We now present quantitative results that show how biasing explanations that
accompany recommendations directly affects users’ preferences, as expressed by
their item selections.

###  4.1. Participants

A total of 129 participants participated in our study who are paid
contractors, and received a standard contracted wage (complying with living
wage laws in their country of employment). All of them are US-based and native
English speakers. In terms of gender, they are 62.7% women, 35.7% men, 1.6%
prefer not to say. Their distribution by age: 5.6% 18–24, 29.4% 25–34, 32.5%
35–44, 19.8% 45–54, 9.5% 55–64, 3.2% over 65. Their self-reported amount of
average time spent per week watching movies: 5.7% $<$2 hours, 37.9% 2–5 hours,
29% 6–10 hours, 16.9% 11-16 hours, 10.5% $>$ 16 hours. Participants on average
took 41 seconds to rate a batch of five movies in Stage 1 (seen/liked), and 43
seconds to choose the movie they would want to watch from the three
recommendations in Stage 2.

###  4.2. Effect of the Presence of Explanations

Figure 4. Baseline condition, no explanations.

Bar plots showing selection frequencies for (A) highest-scoring, (B) mid-
scoring, and (C) lowest-scoring buckets.

Recall that in each instance, participants are provided with three
recommendations where we know which the raters should prefer the most. Our
first test validates that the preferences obey the expected order, and whether
the presence of neutral explanations affects this order. Specifically, let the
three recommendations be $x_{a}\in A$, $x_{b}\in B$ and $x_{c}\in C$, where
$A$, $B$, and $C$ are buckets with the highest-scoring, mid-scoring, and
lowest-scoring items, respectively (cf. Fig. 2). Let the relative frequency
with which each bucket is chosen (corresponding to users’ item selections),
referred to as their _selection frequency_ , be denoted as $p_{A}$, $p_{B}$,
and $p_{C}$ respectively. We then have an expected ordering of $p_{A}\succ
p_{B}\succ p_{C}$.

When explanations are not shown, we find that across all participants,
$p_{A}=0.43\pm 0.07$, $p_{B}=0.31\pm 0.07$ and $p_{C}=0.26\pm 0.06$ with a 95%
confidence interval, computed using the Goodman method (Goodman, 1965); see
Fig. 4. Thus, the expected ordering holds, and the difference between the
highest- and lowest-scoring buckets is statistically significant.

When neutral explanations are included, we observe $p^{n}_{A}=0.4\pm 0.07$,
$p^{n}_{B}=0.28\pm 0.07$, and $p^{n}_{C}=0.32\pm 0.07$, as shown in Fig. 5.
While the highest-scoring bucket continues to receive the most selections, the
relative ordering between buckets B and C, surprisingly, is now swapped. Also,
the selection frequencies for all three buckets come closer together,
resulting in overlapping confidence intervals. This means that despite the
careful experiment design, explanations seem to have some uncontrolled
effects. It could be, for example, that mid- and low-scoring items are not
that well distinguished by the recommender system and it is a random effect
due to noise in the data. However, the “well-behaving” baseline setting
without explanations and the relatively large sample size (n=258) suggest
otherwise. It could also be that neutral explanations that highlight both
positive and negative aspects invite more “risky” selections by users, giving
lower-ranked suggestion a try. In the remainder of our analysis, we take the
neutral explanations setting (Fig. 5) as our baseline. However, the relative
ordering of buckets B and C warrants further investigation.

Figure 5. Baseline condition, neutral explanations.

Bar plots showing selection frequencies for (A) highest-scoring, (B) mid-
scoring, and (C) lowest-scoring buckets.

Table 3. Selection frequency of different buckets (rows) depending on the presence and direction of bias in explanations (columns). Grey cell background indicates when the bias happens in the same bucket as the selection. Green/red arrows show the change in selection frequency with respect to the no bias setting. Selection | No bias | Bias in A | Bias in B | Bias in C
---|---|---|---|---
+/++ | -/– | +/++ | -/– | +/++ | -/–
A | 0.40 $\pm$ 0.07 | 0.49 $\pm$ 0.09$\blacktriangle$ | 0.37 $\pm$ 0.09$\blacktriangledown$ | 0.37 $\pm$ 0.09$\blacktriangledown$ | 0.41 $\pm$ 0.09$\blacktriangle$ | 0.36 $\pm$ 0.08$\blacktriangledown$ | 0.50 $\pm$ 0.09$\blacktriangle$
B | 0.28 $\pm$ 0.07 | 0.25 $\pm$ 0.08$\blacktriangledown$ | 0.34 $\pm$ 0.08$\blacktriangle$ | 0.42 $\pm$ 0.09$\blacktriangle$ | 0.30 $\pm$ 0.08$\blacktriangle$ | 0.27 $\pm$ 0.08$\blacktriangledown$ | 0.29 $\pm$ 0.08$\blacktriangle$
C | 0.32 $\pm$ 0.07 | 0.26 $\pm$ 0.08$\blacktriangledown$ | 0.29 $\pm$ 0.08$\blacktriangledown$ | 0.21 $\pm$ 0.08$\blacktriangledown$ | 0.28 $\pm$ 0.08$\blacktriangledown$ | 0.38 $\pm$ 0.09$\blacktriangle$ | 0.21 $\pm$ 0.07$\blacktriangledown$
Table 4. Selection frequency of different buckets (rows) depending on the presence and direction of bias in explanations (columns), for itemized explanations (top block) vs. fluent-NL explanations (bottom block); cell annotations are the same as in Table 3. Selection | No bias | Bias in A | Bias in B | Bias in C
---|---|---|---|---
+/++ | -/– | +/++ | -/– | +/++ | -/–
Itemized explanations
A | 0.40 $\pm$ 0.10 | 0.49 $\pm$ 0.13$\blacktriangle$ | 0.35 $\pm$ 0.11$\blacktriangledown$ | 0.39 $\pm$ 0.12$\blacktriangledown$ | 0.47 $\pm$ 0.13$\blacktriangle$ | 0.34 $\pm$ 0.12$\blacktriangledown$ | 0.55 $\pm$ 0.12$\blacktriangle$
B | 0.28 $\pm$ 0.09 | 0.26 $\pm$ 0.11$\blacktriangledown$ | 0.34 $\pm$ 0.11$\blacktriangle$ | 0.45 $\pm$ 0.13$\blacktriangle$ | 0.19 $\pm$ 0.11$\blacktriangledown$ | 0.26 $\pm$ 0.11$\blacktriangledown$ | 0.27 $\pm$ 0.11$\blacktriangledown$
C | 0.32 $\pm$ 0.10 | 0.25 $\pm$ 0.11$\blacktriangledown$ | 0.31 $\pm$ 0.11$\blacktriangledown$ | 0.16 $\pm$ 0.10$\blacktriangledown$ | 0.33 $\pm$ 0.12$\blacktriangle$ | 0.40 $\pm$ 0.12$\blacktriangle$ | 0.19 $\pm$ 0.10$\blacktriangledown$
Fluent-NL explanations
A | 0.40 $\pm$ 0.10 | 0.49 $\pm$ 0.12$\blacktriangle$ | 0.40 $\pm$ 0.13$\blacktriangledown$ | 0.34 $\pm$ 0.12$\blacktriangledown$ | 0.36 $\pm$ 0.12$\blacktriangledown$ | 0.38 $\pm$ 0.12$\blacktriangledown$ | 0.45 $\pm$ 0.12$\blacktriangle$
B | 0.28 $\pm$ 0.09 | 0.24 $\pm$ 0.10$\blacktriangledown$ | 0.33 $\pm$ 0.12$\blacktriangle$ | 0.39 $\pm$ 0.13$\blacktriangle$ | 0.40 $\pm$ 0.12$\blacktriangle$ | 0.27 $\pm$ 0.11$\blacktriangledown$ | 0.31 $\pm$ 0.12$\blacktriangle$
C | 0.32 $\pm$ 0.10 | 0.26 $\pm$ 0.10$\blacktriangledown$ | 0.27 $\pm$ 0.12$\blacktriangledown$ | 0.27 $\pm$ 0.12$\blacktriangledown$ | 0.24 $\pm$ 0.11$\blacktriangledown$ | 0.35 $\pm$ 0.12$\blacktriangle$ | 0.23 $\pm$ 0.11$\blacktriangledown$

###  4.3. Effect of Explanations Biased towards Positive or Negative

By adjusting the number of positive and negative aspects, we can bias
explanations in a positive or negative direction either weakly (e.g., three
positive aspects and one negative aspect) or strongly (e.g., four negative
aspects and no positives). Table 3 shows the effect of bias on item selections
(rows) depending on the position and direction of bias (columns). For
simplicity, we do not distinguish between the amount of bias (weakly or
strongly positive/negative) nor the type of explanation (fluent-NL or
itemized), but report on aggregated counts.

Bias in a given bucket has an effect on selections both in the same bucket
(highlighted as grey in Table 3) and in other buckets. For example, biasing
positively items in C increases selections in C, but also decreases selections
in A and B. Similarly, negatively biasing items in A drives selections down in
A, while moving selections up in B. This intuitively makes sense, but there
are a few exceptions when this expected behavior cannot be observed, e.g.,
negative bias in A increases selections in B, but not in C. Despite these
anomalies that remain to be investigated in the future, it is clear that
biasing explanations has a large effect on the selections people make. Two
extremes are worth noting: (1) negatively biasing the most relevant
recommendation reduces the selection of what is believed to be the best
recommendation by 9%, and (2) positively biasing the least relevant
recommendation increases the selection of that item by twice as much, almost
19%, compared to the no bias baseline. Notice that the selection frequency of
the least relevant suggestion with a positive bias (0.38 $\pm$ 0.09) reaches
that of the most relevant suggestion with a negative bias (0.37 $\pm$ 0.09).

###  4.4. Effect of Explanation Format: Fluent-NL vs. Itemized Explanations

In our design, explanations were presented in two ways: as a list of
attributes, and as fluent text that mentions the same attributes. The last
question we ask is: To what extent do our findings depend on the particular
explanation format? Table 4 breaks down the previous results by explanation
format. Our main findings are as follows. First, there is no difference in
results in the no bias setting. Second, when explanations are biased, itemized
explanations behave more “as expected,” i.e., when bias happens in the same
bucket as the selection (grey cells), then positive bias always means an
increase and negative bias always causes a drop in selection frequency. This
is not the case for fluent-NL explanations. Third, we observe that the
differences between the positive and negative bias settings within a given
bucket tend to be much larger in case of itemized explanations. This
intuitively makes sense, as the positive and negative aspects are made
explicit with visual thumbs up/down icons, while fluent text can be more prone
to hiding differences. Despite these differences, results indicate a
consistent pattern of change across the two explanation formats: the arrows
indicating change point in the same direction in 14 out of the 18 cells.

##  5\. Conclusion

We have designed a protocol that allows for a quantitative study of the impact
of explanations on users’ choices in item recommendation. Key elements of this
design include preference elicitation that allows for the generation of
personalized recommendations, manual identification and extraction of item
aspects to include in explanations, a controlled way of introducing bias via
the combination of both positive and negative aspects, and the presentation of
explanations in two different textual formats. We have conducted a user study
and showed that explanations can indeed have a large effect on the item
selections that people make, and that these findings generalize across the two
explanation formats. The results have also yielded some unexpected findings
that warrant further investigation in future work. We also plan to conduct a
more detailed statistical analysis of the results and perform qualitative
evaluation based on post-survey responses. Further, the differences in terms
of absolute impact between itemized and fluent natural language explanations
suggest that the specific wording of the latter might play a role. Measuring
whether slight differences in phrasing have an impact is an interesting topic
for future research. Finally, we focused on movie recommendations, yet our
approach is generalizable to other domains where users rely on automatic
suggestions due to the size of the item collection (e.g., books, music,
recipes). It would be interesting to repeat the experiment in other domains.

## References

  * (1)
  * Balog and Radlinski (2020) Krisztian Balog and Filip Radlinski. 2020.  Measuring Recommendation Explanation Quality: The Conflicting Goals of Explanations. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ _(SIGIR ’20)_. 329–338.
  * Balog et al. (2019) Krisztian Balog, Filip Radlinski, and Shushan Arakelyan. 2019\.  Transparent, Scrutable and Explainable User Models for Personalized Recommendation. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ _(SIGIR’19)_. 265–274.
  * Bilgic and Mooney (2005) Mustafa Bilgic and Raymond J. Mooney. 2005.  Explaining Recommendations: Satisfaction vs. Promotion. In _Proceedings of Beyond Personalization 2005: A Workshop on the Next Stage of Recommender Systems Research at the 2005 International Conference on Intelligent User Interfaces_. 13–18.
  * Biran and Cotton (2017) Or Biran and Courtenay V. Cotton. 2017.  Explanation and Justification in Machine Learning: A Survey. In _IJCAI 2017 Workshop on Explainable Artificial Intelligence_.
  * Chang et al. (2016) Shuo Chang, F. Maxwell Harper, and Loren Gilbert Terveen. 2016\.  Crowd-Based Personalized Natural Language Explanations for Recommendations. In _Proceedings of the 10th ACM Conference on Recommender Systems_ _(RecSys ’16)_. 175–182.
  * Chen et al. (2015) Li Chen, Guanliang Chen, and Feng Wang. 2015.  Recommender Systems Based on User Reviews: The State of the Art.  _User Model. User-Adapt. Interact._ 25, 2 (jun 2015), 99–154.
  * Chen and Wang (2014) Li Chen and Feng Wang. 2014\.  Sentiment-Enhanced Explanation of Product Recommendations. In _Proceedings of the 23rd International Conference on World Wide Web_ _(WWW ’14)_. 239–240.
  * Chen and Wang (2017) Li Chen and Feng Wang. 2017\.  Explaining Recommendations Based on Feature Sentiments in Product Reviews. In _Proceedings of the 22nd International Conference on Intelligent User Interfaces_ _(IUI ’17)_. 17–28.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022.  PaLM: Scaling Language Modeling with Pathways.  arXiv:2204.02311 [cs.CL]
  * Costa et al. (2018) Felipe Costa, Sixun Ouyang, Peter Dolog, and Aonghus Lawlor. 2018.  Automatic Generation of Natural Language Explanations. In _Proceedings of the 23rd International Conference on Intelligent User Interfaces Companion_ _(IUI ’18)_.
  * Gedikli et al. (2014) Fatih Gedikli, Dietmar Jannach, and Mouzhi Ge. 2014\.  How Should I Explain? A Comparison of Different Explanation Types for Recommender Systems.  _Int. J. Hum. Comput. Stud._ 72, 4 (2014), 367–382.
  * Ghazimatin et al. (2021) Azin Ghazimatin, Soumajit Pramanik, Rishiraj Saha Roy, and Gerhard Weikum. 2021.  ELIXIR: Learning from User Feedback on Explanations to Improve Recommender Models. In _Proceedings of the Web Conference 2021_ _(WWW ’21)_. 3850–3860.
  * Goodman (1965) Leo A. Goodman. 1965\.  On Simultaneous Confidence Intervals for Multinomial Proportions.  _Technometrics_ 7, 2 (may 1965), 247–254.
  * Harman et al. (2014) Jason L. Harman, John O’Donovan, Tarek Abdelzaher, and Cleotilde Gonzalez. 2014.  Dynamics of Human Trust in Recommender Systems. In _Proceedings of the 8th ACM Conference on Recommender Systems_ _(RecSys ’14)_. 305–308.
  * Harper and Konstan (2015) F. Maxwell Harper and Joseph A. Konstan. 2015.  The MovieLens Datasets: History and Context.  _ACM Trans. Interact. Intell. Syst._ 5, 4, Article 19 (dec 2015), 19 pages.
  * He et al. (2015) Xiangnan He, Tao Chen, Min-Yen Kan, and Xiao Chen. 2015\.  TriRank: Review-Aware Explainable Recommendation by Modeling Aspects. In _Proceedings of the 24th ACM International on Conference on Information and Knowledge Management_ _(CIKM ’15)_. 1661–1670.
  * Herlocker et al. (2000) Jonathan L. Herlocker, Joseph A. Konstan, and John Riedl. 2000\.  Explaining Collaborative Filtering Recommendations. In _Proceedings of the 2000 ACM Conference on Computer Supported Cooperative Work_ _(CSCW ’00)_. 241–250.
  * Hernández-Rubio et al. (2019) María Hernández-Rubio, Iván Cantador, and Alejandro Bellogín. 2019.  A Comparative Analysis of Recommender Systems Based on Item Aspect Opinions Extracted from User Reviews.  _User Model. User-Adapt. Interact._ 29 (apr 2019), 381–441.
  * Hu et al. (2008) Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008.  Collaborative Filtering for Implicit Feedback Datasets. In _Proceedings of the 2008 Eighth IEEE International Conference on Data Mining_ _(ICDM ’08)_. 263–272.
  * Kunkel et al. (2019) Johannes Kunkel, Tim Donkers, Lisa Michael, Catalin-Mihai Barbu, and Jürgen Ziegler. 2019\.  Let Me Explain: Impact of Personal and Impersonal Explanations on Trust in Recommender Systems. In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_ _(CHI ’19)_. 1–12.
  * Muhammad et al. (2016) Khalil Ibrahim Muhammad, Aonghus Lawlor, and Barry Smyth. 2016\.  A Live-User Study of Opinionated Explanations for Recommender Systems. In _Proceedings of the 21st International Conference on Intelligent User Interfaces_ _(IUI ’16)_. 256–260.
  * Musto et al. (2019) Cataldo Musto, Pasquale Lops, Marco de Gemmis, and Giovanni Semeraro. 2019.  Justifying Recommendations through Aspect-Based Sentiment Analysis of Users Reviews. In _Proceedings of the 27th ACM Conference on User Modeling, Adaptation and Personalization_ _(UMAP ’19)_. 4–12.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing_. 188–197.
  * Ning and Karypis (2011) Xia Ning and George Karypis. 2011.  SLIM: Sparse Linear Methods for Top-N Recommender Systems. In _Proceedings of the 2011 IEEE 11th International Conference on Data Mining_ _(ICDM ’11)_. 497–506.
  * Nunes and Jannach (2017) Ingrid Nunes and Dietmar Jannach. 2017.  A Systematic Review and Taxonomy of Explanations in Decision Support and Recommender Systems.  _User Model. User-adapt. Interact._ 27, 3-5 (2017), 393–444.
  * Peake and Wang (2018) Georgina Peake and Jun Wang. 2018.  Explanation Mining: Post Hoc Interpretability of Latent Factor Models for Recommendation Systems. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ _(KDD ’18)_. 2060–2069.
  * Penha et al. (2022) Gustavo Penha, Eyal Krikon, and Vanessa Murdock. 2022\.  Pairwise Review-Based Explanations for Voice Product Search. In _ACM SIGIR Conference on Human Information Interaction and Retrieval_ _(CHIIR ’22)_. 300–304.
  * Piscopo et al. (2022) Alessandro Piscopo, Oana Inel, Sanne Vrijenhoek, Martijn Millecamp, and Krisztian Balog. 2022\.  Report on the 1st Workshop on Measuring the Quality of Explanations in Recommender Systems (QUARE 2022) at SIGIR 2022.  _SIGIR Forum_ 56, 2 (dec 2022).
  * Sarwar et al. (2001) Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001.  Item-based Collaborative Filtering Recommendation Algorithms. In _Proceedings of the 10th International Conference on World Wide Web_ _(WWW ’01)_. 285–295.
  * Tintarev and Masthoff (2012) Nava Tintarev and Judith Masthoff. 2012.  Evaluating the Effectiveness of Explanations for Recommender Systems.  _User Model. User-Adapt. Interact._ 22 (oct 2012), 399–439.
  * Tintarev and Masthoff (2015) Nava Tintarev and Judith Masthoff. 2015.  Explaining Recommendations: Design and Evaluation.  In _Recommender Systems Handbook_ (2nd ed.), Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor (Eds.). Springer US, Chapter 10, 353–382.
  * Vig et al. (2009) Jesse Vig, Shilad Sen, and John Riedl. 2009.  Tagsplanations: Explaining Recommendations Using Tags. In _Proceedings of the 14th International Conference on Intelligent User Interfaces_ _(IUI ’09)_. 47–56.
  * Zemlyanskiy et al. (2021) Yury Zemlyanskiy, Sudeep Gandhe, Ruining He, Bhargav Kanagal, Anirudh Ravula, Juraj Gottweis, Fei Sha, and Ilya Eckstein. 2021\.  DOCENT: Learning Self-Supervised Entity Representations from Large Document Collections. In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ _(EACL ’21)_. 2540–2549.
  * Zhang and Chen (2020) Yongfeng Zhang and Xu Chen. 2020.  Explainable Recommendation: A Survey and New Perspectives.  _Found. Trends Inf. Retr._ 14, 1 (2020), 1–101.

##  Appendix A Appendix: Study Design

We provide further details on the study design and data preparation.

###  A.1. Aspect Extraction

The data collected using crowdsourcing has been automatically cleaned and pre-
filtered; this includes fixing capitalization, removing trailing whitespace,
filtering too long aspects, and removing aspects that are substrings of other
aspects. However, the data needed further manual cleaning and filtering by the
paper authors, as not all extracted aspects fit the template (i.e., human
workers did not follow the instructions closely enough), aspects may be too
harsh or offensive, or sound too personal to be used as explanations. As part
of the manual cleaning process, some aspects were slightly rewritten and near-
duplicates were removed. Of the 9,635 movie-aspect pairs collected originally,
7,414 remained after automatic pre-filtering, and 5,948 after the end of the
manual filtering.

It is worth emphasizing that the recommendations are personalized, while the
explanations accompanying them are not, i.e., all participants receiving the
same recommendation under the same experimental condition will see the same
explanation for that item, to ensure that there is no uncontrolled bias.

Table 5. Sequences determining whether to list positive or negative aspects first in explanations. Sequence | Condition
---|---
#3 | #4 | #5 | #6 | #7 | #8
1 | N | P | P | N | N | P
2 | P | N | N | P | P | N
3 | N | P | P | N | N | P
4 | P | N | N | P | P | N
5 | N | P | P | N | N | P
6 | P | N | N | P | P | N

Figure 6. User interface for item selection (Stage 2).

Screenshot consisting of an instruction, three items in a table, and a submit
button. The instruction reads ”Indicate which movies you have watched and if
you have liked them.” The three items are shown below each other, as three
rows. The headings of the table are: ”Item,” ”Seen,” ”Rating.” The item column
shows the movie poster and title, seen has two radio buttons with ”Yes” and
”No” options, and Rating has three radio buttons with ”Disliked,” ”Neutral,”
and ”Liked” options.

###  A.2. Explanations

When both positive and negative aspects are displayed (conditions #3–#8), we
make those fully balanced for each participant as well as across all
participants by cycling through the sequences shown in Table 5. These
sequences follow a Latin Square design where the binary value P/N is
determined by the least significant bit.

###  A.3. User Interfaces

Figures 7 and 6 show screenshots of the user interfaces used in Stages 1 and
2, respectively.

Figure 7. User interface for item consumption and preference elicitation
(Stage 1).

Screenshot consisting of an instruction, three items in a table, and a submit
button. The instruction reads ”Select the movie that you would most likely
watch among these.” The three items are shown next to each other, as three
columns. Each has a movie poster, a title with a radio button in front, a
synopsis text, and a list of itemized explanations.


# The Deformation Space of Delaunay Triangulations of the Sphere

Yanwen Luo, Tianqi Wu, Xiaoping Zhu  Department of Mathematics, Rutgers
University, New Brunswick NJ, 08817<EMAIL_ADDRESS>Department of
Mathematics, Clark University, Worcester, MA, 01610<EMAIL_ADDRESS>Department of Mathematics, Rutgers University, New Brunswick New Jersey 08817
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we determine the topology of the spaces of convex polyhedra
inscribed in the unit $2$-sphere and the spaces of strictly Delaunay geodesic
triangulations of the unit $2$-sphere. These spaces can be regarded as
discretized groups of diffeomorphisms of the unit $2$-sphere. Hence, it is
natural to conjecture that these spaces have the same homotopy types as those
of their smooth counterparts. The main result of this paper confirms this
conjecture for the unit $2$-sphere. It follows from an observation on the
variational principles on triangulated surfaces developed by I. Rivin.

On the contrary, the similar conjecture does not hold in the cases of flat
tori and convex polygons. We will construct simple examples of flat tori and
convex polygons such that the corresponding spaces of Delaunay geodesic
triangulations are not connected.

###### Key words and phrases:

geodesic triangulations, angle structure, Delaunay triangulations

Acknowledgement: The authors were supported in part by NSF 1737876, NSF
1760471, NSF DMS FRG 1760527 and NSF DMS 1811878.

##  1\. Introduction

One of the fundamental problems in low dimensional topology is to identify the
homotopy types of groups of diffeomorphisms of a smooth manifold. Smale [18]
proved that the group of orientation preserving diffeomorphisms of the
$2$-sphere is homotopy equivalent to $SO(3)$.

This paper studies two types of finite dimensional spaces which may be
considered as discrete analogues of the group of orientation preserving
diffeomorphisms of the $2$-sphere. They are the deformation spaces of Delaunay
triangulations of the unit $2$-sphere and the deformation spaces of convex
polyhedra inscribed in the unit $2$-sphere. The main results of this paper
show that these discrete analogues are homotopy equivalent to $SO(3)$.

######  Theorem 1.1.

The deformation space of Delaunay triangulations of the unit $2$-sphere is
homeomorphic to $SO(3)\times\mathbb{R}^{k}$ for some $k>0$.

######  Theorem 1.2.

The deformation space of the convex polyhedra inscribed in the unit $2$-sphere
whose faces are all triangles is homeomorphic to $SO(3)\times\mathbb{R}^{k}$
for some $k>0$.

However, we will construct explicit examples of spaces of Delaunay
triangulations of convex polygons and flat tori which have different homotopy
types from their smooth counterparts. Specifically, we show the spaces of
Delaunay triangulations of some flat tori and spaces of Delaunay
triangulations of some convex polygons are not connected.

Let $T=(V,E,F)$ denote a $2$-dimensional simplicial complex, where $V$ is the
set of vertices, $E$ is the set of edges, and $F$ is the set of triangles. Any
edge of in $E$ is identified with the closed interval $[0,1]$, and any
triangle in $F$ is identified with a Euclidean equilateral triangle with unit
length. Denote $T^{(1)}$ as the 1-skeleton of $T$, and $|T|$ as the underlying
space of $T$ homeomorphic to a surface possibly with boundary.

###  1.1. Delaunay triangulations of the unit sphere

Assume $|T|$ is homeomorphic to the unit $2$-sphere denoted by
$\mathbb{S}^{2}$. An embedding $\varphi:T^{(1)}\rightarrow\mathbb{S}^{2}$ is
called a _geodesic triangulation_ of $\mathbb{S}^{2}$ if the restriction of
$\varphi$ on each edge is a geodesic parametrized with constant speed. A
geodesic triangulation $\varphi$ naturally divides $\mathbb{S}^{2}$ into
spherical geodesic triangles. For our convenience, we will only consider the
geodesic triangulations where all the spherical triangles are convex. A
geodesic triangulation $\varphi$ of $\mathbb{S}^{2}$ is called a convex
geodesic triangulation if any spherical triangle in $\varphi$ is contained in
some open hemisphere. Such a convex geodesic triangulation $\varphi$ is
uniquely determined by the images of the vertices of $T$.

A convex geodesic triangulation $\varphi$ is called Delaunay if it satisfies
the empty circle property, meaning that for any pair of adjacent spherical
triangles $\triangle ABC$ and $\triangle ABD$, $D$ is not inside the
circumcircle of $\triangle ABC$. This condition is equivalent to the following
condition on the angles of a convex geodesic triangulation:

(1) $b+c+b^{\prime}+c^{\prime}-a-a^{\prime}\geq 0,$

where $a,b,c,a^{\prime},b^{\prime},c^{\prime}$ are the inner angles of two
neighbored triangles as in Figure 1. Similarly, a convex geodesic
triangulation is called strictly Delaunay if for any pair of adjacent
spherical triangles $\triangle ABC$ and $\triangle ABD$, $D$ is strictly
outside the circumcircle of $\triangle ABC$. This condition is equivalent to
the following condition on the angles of a convex geodesic triangulation:

(2) $b+c+b^{\prime}+c^{\prime}-a-a^{\prime}>0,$

Delaunay and strictly Delaunay triangulations naturally appear in the study of
discrete differential geometry and geometry processing. They are widely
investigated and implemented in practice. See [7, 9] for example. We will
focus on strictly Delaunay triangulations in this paper.

Figure 1. The edge invariant.

Given an embedding $\psi:T^{(1)}\rightarrow\mathbb{S}^{2}$, we define _the
deformation space of Delaunay triangulations of the unit sphere_ determined by
$\psi$, denoted by $X(T,\psi)$, as the set of all strictly Delaunay convex
geodesic triangulations that are isotopic to $\psi$. Then $X(T,\psi)$ is
naturally a manifold of dimension $2|V|$ without boundary. Theorem 1.1 can be
rephrased as

######  Theorem 1.3.

Given a strictly Delaunay convex geodesic triangulation $\psi$, $X(T,\psi)$ is
homeomorphic to $\mathbb{R}^{2|V|-3}\times SO(3)$.

The topology of spaces of geodesic triangulations of surfaces has been studied
since Cairns [4]. These spaces are naturally discrete analogues of the
diffeomorphism groups of smooth surfaces. It was conjectured that for constant
curvature surfaces they are homotopy equivalent to their smooth counterparts
by Connelly et al. [5]. This conjecture has been confirmed by Bloch-Connelly-
Henderson [2] for convex polygons, and a new proof based on Tuttes’ embedding
theorem was provided by Luo [13]. Recently, this conjecture was proved for the
cases of flat tori and closed surfaces of negative curvature (see Erickson-Lin
[10] and Luo-Wu-Zhu [14, 15]).

For the case of the unit sphere, Awartani-Henderson [1] identified the
homotopy type of a subspace of the space of geodesic triangulations on the
unit $2$-sphere, but the general case remains open. Theorem 1.3 provides an
affirmative evidence about this conjecture, and we hope that it could be an
intermediate step to prove the conjecture for the unit sphere.

###  1.2. Convex polyhedra inscribed in the unit sphere

Assume $|T|$ is homeomorphic to $\mathbb{S}^{2}$. An embedding
$\varphi:|T|\rightarrow\mathbb{R}^{3}$ is called a _polyhedral realization
inscribed in the unit sphere_ if $\varphi$ maps any vertex to the unit sphere
and maps any face linearly to a Euclidean triangle. Such a polyhedral
realization $\varphi$ is called (strictly) convex if for any triangle
$\sigma\in F$, $\varphi(\sigma)$ is a face of the boundary of the convex hull
of $\varphi(V)$ in $\mathbb{R}^{3}$. Given $T$, denote $Y(T)$ as the set of
convex polyhedral realizations inscribed in the unit sphere.

We say a point $q$ is _inside_ a convex polyhedral surface $P$ if $q$ is in
the interior of the convex hull of $P$. Given a point $q$ in the unit open
ball, denote $p_{q}:\mathbb{R}^{3}\backslash\\{q\\}\rightarrow\mathbb{S}^{2}$
as the radial projection centered at $q$ to the unit sphere. We say two convex
polyhedral realizations $\varphi_{1},\varphi_{2}$ in $Y(T)$ _have the same
orientation_ if and only if $p_{q_{1}}\circ\varphi_{1}$ is isotopic to
$p_{q_{2}}\circ\varphi_{2}$ on $\mathbb{S}^{2}$ for $q_{1}$ inside
$\varphi_{1}(|T|)$ and $q_{2}$ inside $\varphi_{2}(|T|)$. It is
straightforward to check that the choice of $q_{1}$ and $q_{2}$ does not
matter.

Given a convex realization polyhedral realization $\psi$, we define _the
deformation space of convex polyhedra inscribed in the sphere_ determined by
$\psi$, denoted by $Y(T,\psi)\subset Y(T)$, as the set of all convex
realizations $\varphi$ of $\mathbb{S}^{2}$ having the same orientation with
$\psi$. Then $Y(T,\psi)$ is naturally a manifold of dimension $2|V|$ without
boundary. Theorem 1.2 can be rephrased as

######  Theorem 1.4.

Given a convex realization $\psi$, $Y(T,\psi)$ is homeomorphic to
$\mathbb{R}^{2|V|-3}\times SO(3)$.

The space of inscribed polyhedra is related to realization spaces of polytopes
with a fixed combinatorial type. Steinitz [19] proved that the realization
space of polyhedra is a cell after standard normalization. See [16] for a
detailed discussion about the realization spaces.

###  1.3. Connections between the two spaces

Denote $Y_{0}(T)$ as the subset of $Y(T)$ containing all the convex
realizations $\varphi$ such that the origin $O=(0,0,0)$ is inside
$\varphi(|T|)$. Given a convex realization $\psi$, denote
$Y_{0}(T,\psi)=Y(T,\psi)\cap Y_{0}(T)$. If $\varphi\in Y_{0}$, then the radial
projection $p_{O}$ maps the triangulation structure on $\varphi(|T|)$ to a
strictly Delaunay convex geometric triangulation of $\mathbb{S}^{2}$. This
naturally gives a homeomorphism from $Y_{0}(T,\psi)$ to
$X(T,p_{O}\circ\psi|_{T^{(1)}})$, for any convex realization $\psi$.
Therefore, Theorem 1.3 can be reformulated as

######  Theorem 1.5.

Given a convex realization $\psi\in Y_{0}$, $Y_{0}(T,\psi)$ is homeomorphic to
$\mathbb{R}^{2|V|-3}\times SO(3)$.

###  1.4. Organization and acknowledgement

In Section $2$, we will introduce the concept of angles structures. In Section
$3$, we will determine the topology of the spaces of Delaunay triangulations
of convex polygons with fixed angles. In Section $4$, we will prove Theorem
1.4 and Theorem 1.5. In Section $5$, we will provide examples showing the
homotopy types of spaces of Delaunay triangulations of flat tori and convex
polygons could be not that simple.

The authors would like to thank Professor Jeff Erickson for his insightful
comments.

##  2\. Angle structures on triangulated surfaces

The key concept to study spaces of Delaunay triangulations is _angle
structure_ on triangulated surfaces. This concept was proposed by Colin de
Vedière [6], and developed by Rivin [17], Leibon [11], Luo [12], Bobenko-
Springborn [3], and others. We briefly summarize the theory in the following.

###  2.1. Angle structures on triangulated surface

Assume $|T|$ is a $2$-dimensional manifold possibly with boundary. A corner in
$T$ is defined as a vertex-face pair $(v,f)$ in $T$ such that the face $f$
contains $v$. It represents the inner angle of the face $f$ at the vertex $v$.
A Euclidean angle structure $\theta$, or an angle structure in short, on $T$
is a positive function on the set of the corners such that
$\theta_{1}+\theta_{2}+\theta_{3}=\pi$ for the three angles in every face $f$.
Every angle structure can be presented as a positive vector in
$\mathbb{R}^{3|F|}$. Denote $V_{b}\subset V$ as the set of boundary vertices,
and then the _edge invariant_ $\alpha=\alpha(\theta)\in\mathbb{R}^{E\cup
V_{b}}$ is defined as

  1. (a)

$\alpha_{e}=\theta_{1}+\theta_{2}$, if $e$ is an inner edge, and $\theta_{1}$
and $\theta_{2}$ are the two angles opposite to $e$, and

  2. (b)

$\alpha_{e}=\theta_{1}$, if $e$ is a boundary edge, and $\theta_{1}$ is the
angle opposite to $e$, and

  3. (c)

$\alpha_{v}=\sum_{i}\theta_{i}$, if $v$ is a boundary vertex, and
$\theta_{i}$’s are the angles at $v$.

Denote the set of angle structures realizing a prescribed edge invariant
$\bar{\alpha}\in\mathbb{R}^{E\cup V_{b}}$ as $\mathcal{A}(T,\bar{\alpha})$.

Given an edge length function $l\in\mathbb{R}^{E}$ satisfying the triangle
inequalities, we can naturally determine a piecewise Euclidean metric on $T$
and induce an angle structure $\theta(l)$ using the inner angles in this
piecewise Euclidean metric. Notice that not every angle structure can be
induced from a piecewise Euclidean metric.

###  2.2. Variational principles of angle structures.

Variational methods are introduced to find piecewise Euclidean surfaces with a
prescribed edge invariant. The functionals in these variational principles
have elegant geometric interpretations in terms of volumes of polyhedra in the
hyperbolic $3$-space $\mathbb{H}^{3}$.

Figure 2. The volume of an ideal tetrahedron.

For each face $f$ in $F$, an energy functional is defined in terms of three
angles at the corners of the face in an angle structure. For a face in a
Euclidean angle structure with three angles $(\alpha,\beta,\gamma)$, the
energy functional is the volume of ideal hyperbolic tetrahedron whose
horospherical section is similar to a Euclidean triangle with three angles
$(\alpha,\beta,\gamma)$. See Figure 2. The volume is given by

$V(\alpha,\beta,\gamma)=\Lambda(\alpha)+\Lambda(\beta)+\Lambda(\gamma),$

where $\Lambda$ is the Lobachevsky function

$\Lambda(x)=-\int_{0}^{x}\log|2\sin\theta|d\theta.$

The total energy for a given angle structure is defined as the sum of
functionals on each face

$\mathcal{E}(\theta)=\sum_{f_{i}\in F}V_{i}(\alpha_{i},\beta_{i},\gamma_{i}).$

The variational principles for these energy functionals can be summarized as
follows.

######  Theorem 2.1.

[17] Assume $\bar{\alpha}\in(0,\pi]^{E\cup V_{b}}$ and
$\mathcal{A}(T,\bar{\alpha})$ is nonempty, then

  1. (a)

the energy functional $\mathcal{E}$ is strictly concave down on
$\mathcal{A}(T,\bar{\alpha})$, and

  2. (b)

there exists a unique critical point $\theta=\Theta(\bar{\alpha})$ of
$\mathcal{E}$ in $\mathcal{A}(T,\bar{\alpha})$, and

  3. (c)

$\Theta(\bar{\alpha})$ is the unique angle structure in
$\mathcal{A}(T,\bar{\alpha})$ that could be induced from a piecewise Euclidean
metric on $T$.

Denote ${\mathcal{A}}_{0}(T)$ as the set of angle structures $\theta$ such
that $\alpha(\theta)\in(0,\pi)^{E\cup V_{b}}$ and the angle sum
$\sum_{i}\theta_{i}$ around any interior vertex is $2\pi$. Denote
$\mathcal{A}_{E}(T)$ as the set of angle structures $\theta$ in
$\mathcal{A}_{0}(T)$ that can be induced from a piecewise Euclidean metric on
$T$. Notice that the angle structure induced from a Delaunay triangulation of
a convex polygon in the plane belongs to $\mathcal{A}_{E}(T)$. Then by Theorem
2.1, we have the following.

######  Lemma 2.2.

If $\mathcal{A}_{E}(T)$ is nonempty, then $\mathcal{A}_{E}(T)$ is homeomorphic
to $\mathbb{R}^{k}$ for some $k\geq 0$.

###### Proof.

If $\mathcal{A}_{E}(T)$ is nonempty, then $\mathcal{A}_{0}(T)$ is nonempty.
From the definition we can see that $\mathcal{A}_{0}(T)$ is an open convex
subset in an affine subspace of $\mathbb{R}^{3|F|}$. Then its image
$\alpha(\mathcal{A}_{0}(T))$ under the edge invariant map $\alpha$, which is a
linear map, is an open convex subset of an affine subspace of
$\mathbb{R}^{E\cup V_{b}}$. Hence, $\alpha(\mathcal{A}_{0}(T))$ is
homeomorphic to $\mathbb{R}^{k}$ for some $k\geq 0$.

It remains to show that $\bar{\alpha}\mapsto\Theta(\bar{\alpha})$ is a
homeomorphism from $\alpha(\mathcal{A}_{0}(T))$ to $\mathcal{A}_{E}(T)$. It is
straightforward to show that such a map is continuous from
$\alpha(\mathcal{A}_{0}(T))$ to $\mathbb{R}^{3|F|}$. Moreover,
$\bar{\alpha}\mapsto\Theta(\bar{\alpha})\mapsto\alpha(\Theta(\bar{\alpha}))$
is the identity map on $\alpha(\mathcal{A}_{0}(T))$. By Theorem 2.1,
$\theta\mapsto\alpha(\theta)\mapsto\Theta(\alpha(\theta))$ is the identity map
on $\mathcal{A}_{E}(T)$. Then we only need to show that the image
$\Theta(\bar{\alpha})$ is in $\mathcal{A}_{E}(T)$. By the definition we only
need to verify that for any interior vertex $v$, the angle sum around $v$ in
$\Theta(\bar{\alpha})$ is equal to the angle sum around $v$ in $\theta$. This
is because the angle sum of an angle structure $\theta$ around an interior
vertex $v$ is determined by the edge invariant $\alpha(\theta)$ as the
following.

$\sum_{f\in F:f\ni v}\theta_{v,f}=\sum_{f\in F:f\ni v}\pi-\sum_{e\in E:e\ni
v}\alpha_{e}.$

∎

##  3\. Delaunay Triangulations of Convex Polygons

Assume that $|T|$ is homeomorphic to a closed disk, an embedding
$\varphi:|T|\rightarrow\mathbb{R}^{2}$ is called a _triangulation of a
polygon_ if $\varphi$ is linear on any triangle of $T$. Further such $\varphi$
is called a _triangulation of a convex polygon_ if the inner angle of the
polygon $\varphi(|T|)$ at $\varphi(v_{i})$ is less than $\pi$ for any boundary
vertex $v_{i}$ of $T$. Such $\varphi$ is called strictly Delaunay if for any
pair of adjacent triangles $\triangle ABC$ and $\triangle ABD$ in
$\varphi(T)$, $D$ is strictly outside the circumcircle of $\triangle ABC$.
This condition is equivalent to that $a+a^{\prime}<\pi$, where $a,a^{\prime}$
are the inner angles of two neighbored triangles as in Figure 1.

Denote $\theta(\varphi)$ as the angle structure induced from the triangulation
$\varphi$, and $Z(T)=\\{\varphi:\theta(\varphi)\in\mathcal{A}_{E}(T)\\}$ as
the set of strictly Delaunay triangulations of a convex polygon. We say two
embeddings $\varphi,\psi$ from $|T|$ to $\mathbb{R}^{2}$ have the same
orientation if $\psi\circ\varphi^{-1}$ is an orientation preserving map on
$\varphi(|T|)$. Given a triangulation $\psi$ of a polygon, denote $Z(T,\psi)$
as the set of strictly Delaunay triangulations $\varphi$ of a convex polygon
that have the same orientation with $\psi$.

Furthermore, if we are given a directed edge $e_{ij}$ of $T$, denote
$Z(T,\psi,e_{ij})$ as the set of strictly Delaunay triangulations $\varphi\in
Z(T,\psi)$ satisfying that $\varphi(j)-\varphi(i)=(\lambda,0)$ for some
$\lambda>0$. Then it is elementary to see that a triangulation in
$Z(T,\psi,e_{ij})$ is uniquely determined by the induced angle structure
$\theta(\varphi)$, and $\varphi(i)$, and $\varphi(j)-\varphi(i)$. Therefore,
$\varphi\mapsto(\theta(\varphi),\varphi(i),\varphi(j)-\varphi(i))$ gives a
homeomorphism from $Z(T,\psi,e_{ij})$ to
$\mathcal{A}_{E}(T)\times\mathbb{R}^{2}\times\mathbb{R}_{+}$. On the other
hand, the space $Z(T,\psi,e_{ij})$ is a $(2|V|-1)$-dimensional manifold if not
empty, then we have the following from Lemma 2.2.

######  Corollary 3.1.

Given any Delaunay triangulation of a convex polygon $\psi$, and a directed
edge $e_{ij}$, $Z(T,\psi,e_{ij})$ is homeomorphic to $\mathbb{R}^{2|V|-1}$.

##  4\. Proof of the Main Theorems

It is well known that the stereographic projection

$\pi:(x,y,z)\mapsto\left(\frac{x}{1-z},\frac{y}{1-z}\right)$

gives an angle-preserving diffeomorphism from
$\mathbb{S}^{2}\backslash\\{(0,0,1)\\}$ to $\mathbb{R}^{2}$. For a circle
$\Gamma$ on $\mathbb{S}^{2}$, the stereographic projection maps $\Gamma$ to a
circle on $\mathbb{R}^{2}$ if $\Gamma$ does not contain $(0,0,1)$, and maps
$\Gamma\backslash\\{(0,0,1)\\}$ to a straight line in $\mathbb{R}^{2}$ if
$\Gamma$ contains $(0,0,1)$.

We also need to recall the concept of power of a point from a circle. Given a
point $p$ and a circle $C$ of radius $R$ centered at $q$ in the plane, the
power of $p$ from $C$ is defined as

$power(p,C)=d^{2}(p,q)-R^{2},$

where $d(p,q)$ is the Euclidean distance between $p$ and $q$. It reflects the
relative distance between a point and a circle. Notice that $power(p,C)<0$ if
$p$ is in the interior of $C$.

Assume $|T|$ is homeomorphic to $\mathbb{S}^{2}$, and $v_{0}$ is a vertex of
$T$, and $\psi\in Y(T)$ is a convex realization inscribed in the unit sphere.
Denote $Y(T,\psi,v_{0})$ (resp. $Y(T,v_{0})$, $Y_{0}(T,\psi,v_{0})$,
$Y_{0}(T,v_{0})$) as the set of $\varphi\in Y(T,\psi)$ (resp. $\varphi\in
Y(T)$, $Y_{0}(T,\psi)$, $Y_{0}(T)$) with $\varphi(v_{0})=(0,0,1)$.

Figure 3. The stereographic projection of an inscribed convex polyhedron.

######  Lemma 4.1.

Assume $|T|$ is homeomorphic to $\mathbb{S}^{2}$, $v_{0}$ is a vertex of $T$,
$T_{0}$ denotes the subcomplex of $T$ obtained by removing the open $1$-ring
neighborhood of $v_{0}$, and $e_{ij}$ is a directed edge in $T_{0}$.

  1. (a)

There exists a map $\tilde{\pi}:Y(T,v_{0})\to Z(T_{0})$ induced by $\pi$ such
that $\phi=\tilde{\pi}(\varphi)$ is the strictly Delaunay triangulation of a
convex polygon determined by $\phi(v)=\pi(\varphi(v))$ for any vertex $v$ of
$T_{0}$ (See Figure 3).

  2. (b)

There exists a map $\tilde{\eta}:Z(T_{0})\to Y(T,v_{0})$ induced by $\pi^{-1}$
such that $\varphi=\tilde{\eta}(\phi)$ is the convex realization determined by
$\varphi(v)=\pi^{-1}(\phi(v))$ for any vertex $v$ of $T_{0}$.

  3. (c)

$\tilde{\pi}$ and $\tilde{\eta}$ are inverse to each other and then
$\tilde{\pi}$ is a homeomorphism from $Y(T,v_{0})$ to $Z(T_{0})$.

  4. (d)

Given a convex realization $\psi\in Y(T,v_{0})$, $\tilde{\pi}$ gives a
homeomorphism from $Y(T,\psi,v_{0})$ to $Z(T_{0},\tilde{\pi}(\psi))$.

  5. (e)

$\tilde{\pi}(Y_{0}(T,v_{0}))$ contains all the strictly Delaunay
triangulations $\phi\in Z(T_{0})$ satisfying that

(i) the origin $(0,0)$ is in the interior of $\phi(|T_{0}|)$, and

(ii) the power of $(0,0)$ with respect to the circumcircle of the triangles in
$\phi(T_{0})$ containing $(0,0)$ is greater than $-1$.

  6. (f)

For any $\varphi\in Y(T,\psi)$, there exists a unique $\varphi_{0}\in
Y(T,\psi,v_{0})$ and $g\in SO(3)$, such that $\varphi=g\circ\varphi_{0}$ and
$\tilde{\pi}(\varphi_{0})\in Z(T_{0},\tilde{\pi}(\psi),e_{ij})$. Consequently,
$Y(T,\psi)$ is homeomorphic to $Z(T_{0},\tilde{\pi}(\psi),e_{ij})\times
SO(3)$.

  7. (g)

For any $\varphi\in Y_{0}(T,\psi)$, there exists a unique $\varphi_{0}\in
Y_{0}(T,\psi,v_{0})$ and $g\in SO(3)$, such that $\varphi=g\circ\varphi_{0}$
and $\tilde{\pi}(\varphi_{0})\in Z(T_{0},\tilde{\pi}(\psi),e_{ij})$.
Consequently, $Y_{0}(T,\psi)$ is homeomorphic to
$(\tilde{\pi}(Y_{0}(T,v_{0}))\cap Z(T_{0},\tilde{\pi}(\psi),e_{ij}))\times
SO(3)$.

###### Proof.

(a) and (b) are true by the empty circle property of the (strict) Delaunay
triangulations and the fact that the stereographic projection preserves
circles. (c) is a direct consequence from the definition.

  1. (d)

Given a convex realization $\varphi\in Y(T,v_{0})$ and $q_{1}$ inside
$\psi(|T|)$ and $q_{2}$ inside $\varphi(|T|)$, the following elementary facts
related to orientations are equivalent by the definition and properties of
stereographic projections.

    1. (i)

$\varphi\in Y(T,\psi,v_{0})$.

    2. (ii)

$\psi$ and $\varphi$ have the same orientation.

    3. (iii)

$\pi_{q_{1}}\circ\psi$ is isotopic to $\pi_{q_{2}}\circ\varphi$.

    4. (iv)

$\pi_{q_{1}}\circ\psi$ and $\pi_{q_{2}}\circ\varphi$ have the same
orientation.

    5. (v)

$\tilde{\pi}(\psi)$ and $\tilde{\pi}(\varphi)$ have the same orientation.

    6. (iv)

$\tilde{\pi}(\varphi)\in Z(T_{0},\tilde{\pi}(\psi))$.

  2. (e)

We will prove that any $\tilde{\pi}(\varphi)$ for $\varphi\in Y_{0}(T,v_{0})$
satisfies (i) and (ii). The other way could be proved by reversing our
argument. If $\varphi\in Y_{0}(T,v_{0})$, then the origin is inside
$\varphi(|T|)$. Then the ray starting from the north pole passing through the
origin intersects with $\varphi(|T|)$ at a unique point $q$ in the interior of
$\varphi(|T_{0}|)$. So part (i) is satisfied.

To prove part (ii) in (e), notice first that by the definition of
$Y_{0}(T,v_{0})$, the circumcircle $C$ of any triangle in $\varphi(T_{0})$ is
contained in the interior of some hemisphere bounded by a great circle
$\tilde{C}$ in $\mathbb{S}^{2}$. Then $\pi(C)$ is strictly inside
$\pi(\tilde{C})$, then $power((0,0),\pi(\tilde{C}))<power((0,0),\pi(C))$. By
the Intersecting Chords Theorem,

$power((0,0),\pi(\tilde{C}))=-1<power((0,0),\pi(C)).$

(f) and (g) follow from the fact that the rotation along the $z$-axis (or the
origin in the $xy$-plane) is invariant under the stereographic projection.

∎

###### Proof of Theorem 1.4.

This is an immediate consequence of Corollary 3.1 and part (f) of Lemma 4.1. ∎

###### Proof of Theorem 1.5.

By part (g) of Lemma 4.1, we only need to show that
$\tilde{\pi}(Y_{0}(T,v_{0}))\cap Z(T_{0},\tilde{\pi}(\psi),e_{ij})$ is
homeomorphic to $\mathbb{R}^{2|V|-3}$. It is straightforward to verify that

$\varphi\in\tilde{\pi}(Y_{0}(T,v_{0}))\cap Z(T_{0},\tilde{\pi}(\psi),e_{ij})$

is uniquely determined by $\theta(\varphi)$, $\varphi^{-1}(0,0)$ and
$d(\varphi)$, where $d(\varphi)$ is the Euclidean diameter of
$\varphi(|T_{0}|)$ and describes the scaling transformation needed to
determine $\varphi$. So
$\mathcal{F}:\varphi\mapsto(\theta(\varphi),\varphi^{-1}(0,0),d(\varphi))$
gives a continuous injective map from $\tilde{\pi}(Y_{0}(T,v_{0}))\cap
Z(T_{0},\tilde{\pi}(\psi),e_{ij})$ to $\mathcal{A}_{E}(T_{0})\times
int(|T_{0}|)\times(0,\infty)$, where
$int(|T_{0}|)=|T_{0}|\backslash\partial(|T_{0}|)$ is homeomorphic to
$\mathbb{R}^{2}$ and $\mathcal{A}_{E}(T_{0})$ is homeomorphic to
$\mathbb{R}^{2|V|-6}$ by Lemma 2.2 and a dimension counting.

It suffices to show that the image $Imag(\mathcal{F})$ of $\mathcal{F}$ is
homeomorphic to $\mathbb{R}^{2|V|-3}$. By part (e) of Lemma 2.2, for any
$(\theta,q)\in\mathcal{A}_{E}(T_{0})\times int(|T_{0}|)$,

$Imag(\mathcal{F})\cap\big{(}\\{(\theta,q)\\}\times(0,\infty)\big{)}=(\theta,q)\times(0,d_{\theta,q})$

where $(\theta,q)\mapsto d_{\theta,q}$ is a continuous map from
$\mathcal{A}_{E}(T_{0})\times int(|T_{0}|)$ to $(0,\infty]$. Let us assume
that $\arctan(\infty)=\pi/2$ and then

$(\theta,q,d)\mapsto\left(\theta,q,\frac{\arctan(d)}{\arctan(d_{\theta,q})}\right)$

is a homeomorphism from $Imag(\mathcal{F})$ to $\mathcal{A}_{E}\times
int(|T_{0}|)\times(0,1)$, which is homeomorphic to
$\mathbb{R}^{2|V|-6}\times\mathbb{R}^{2}\times\mathbb{R}=\mathbb{R}^{2|V|-3}$.
∎

##  5\. Delaunay triangulations of convex polygons and flat tori

In this section, we will discuss the space of Delaunay geodesic triangulations
of convex polygons and flat tori.

###  5.1. Convex polygons

A convex polygon $P$ in the plane is determined by the position of a sequence
of cyclically ordered vertices. For a fixed convex polygon $P$ in the plane
with a triangulation $\psi:T\to P$, denote the set of Delaunay triangulations
of $P$ which are isotopic to $\psi$ and identical restricted to the boundary
vertices with $\psi$ as $X(T,\psi)$. Notice that $X(T,\psi)$ is different from
the space $Z(T,\psi)$ in Section $3$, since the positions of boundary vertices
of $T$ for elements in $X$ are fixed. The following example shows that
$X(T,\psi)$ may not be connected.

Figure 4. Counterexample: a convex polygon.

In Figure 4, there are nine interior edges in the triangulation, eight of
which are Delaunay. The yellow edge might not be Delaunay. In Figure 4, if the
vertices $A$ and $B$ are close to the vertical boundaries, then $\alpha$ and
$\beta$ are both acute, so we can construct two Delaunay triangulations
$\tau_{1}$ and $\tau_{2}$ on the left and right. If there is a family of
Delaunay triangulations connecting $\tau_{1}$ and $\tau_{2}$, the vertex $A$
or $B$ will pass the perpendicular bisector of the horizontal boundary of this
rectangle. If the rectangle is flat enough, the angle sum $\alpha+\beta>\pi$
when one of $A$ and $B$ lies on the perpendicular bisector. This shows that
$X(T,\psi)$ for this rectangle $P$ is not connected.

###  5.2. Delaunay triangulations on flat tori.

Assume $|T|$ is homeomorphic to the torus $\mathbb{T}^{2}$ with a marking
homeomorphism whose restriction on $T^{(1)}$ is denoted as $\psi$. An
embedding $\varphi:{T}^{(1)}\to\mathbb{T}^{2}$ is a Delaunay geodesic
triangulation with the combinatorial type $({T},\psi)$ satisfying that

  1. (a)

the restriction $\varphi_{ij}$ of $\varphi$ on each edge $e_{ij}$, identified
with a unit interval $[0,1]$, is a geodesic parametrized with constant speed,
and

  2. (b)

$\varphi$ is homotopic to $\psi$, and

  3. (c)

equation (2) is satisfied for all edges in $T$.

Let $X=X(T,\psi)$ denote the set of all such geodesic triangulations, which is
called the deformation space of Delaunay geodesic triangulations of
$\mathbb{T}^{2}$ of combinatorial type $(T,\psi)$.

The following example shows that the space of Delaunay geodesic triangulations
$X=X(T,\psi)$ may not be connected.

Figure 5. Counterexample: a flat torus.

In Figure 5 , we draw two geodesic triangulations $\tau_{1}$ and $\tau_{2}$ on
a flat torus. For each geodesic triangulation, we draw two fundamental domains
of this torus. The triangulation has two vertices and six edges. Fixing the
vertex $A$ at a point in the universal covering, we can see that the position
of the vertex $B$ determines a geodesic triangulation of this flat torus.
Notice that $\tau_{1}$ and $\tau_{2}$ are both Delaunay, since all angles in
these triangulations are acute when $B$ is sufficiently close to the vertical
line connecting two adjacent copies of $A$ in the universal covering.

We can choose the shape of the fundamental domain of the flat torus as shown
in the picture. Then $\tau_{1}$ and $\tau_{2}$ are in two different connected
components of the space of Delaunay triangulations of this flat torus. This
observation is based on the following fact: any path connecting $\tau_{1}$ and
$\tau_{2}$ needs to move the vertex $B$ from the right to the left. However,
we can choose a flat enough fundamental domain such that when $B$ passes the
perpendicular bisector of the yellow edge, the yellow edge is never Delaunay.
This implies that the space $X=X(T,\psi)$ for this flat torus is not
connected.

## References

  * [1] Awartani, Marwan, and David W. Henderson. ”Spaces of geodesic triangulations of the sphere.” Transactions of the American Mathematical Society 304.2 (1987): 721-732.
  * [2] Bloch, Ethan D., Robert Connelly, and David W. Henderson. ”The space of simplexwise linear homeomorphisms of a convex 2-disk.” Topology 23.2 (1984): 161-175.
  * [3] Bobenko, Alexander, and Boris Springborn. ”Variational principles for circle patterns and Koebe’s theorem.” Transactions of the American Mathematical Society 356.2 (2004): 659-689.
  * [4] Cairns, Stewart S. ”Isotopic deformations of geodesic complexes on the 2-sphere and on the plane.” Annals of Mathematics (1944): 207-217.
  * [5] Robert Connelly, David W Henderson, Chung Wu Ho, and Michael Starbird, ”On the problems related to linear homeomorphisms, embeddings, and isotopies.” Continua, decompositions, manifolds, 1983, pp. 229–239.
  * [6] De Verdiere, Yves Colin. ”Un principe variationnel pour les empilements de cercles.” Inventiones mathematicae 104.1 (1991): 655-669.
  * [7] Devadoss, Satyan L., and Joseph O’Rourke. Discrete and computational geometry. Princeton University Press, 2011.
  * [8] Earle, Clifford J., and James Eells. ”A fibre bundle description of Teichmüller theory.” Journal of Differential Geometry 3.1-2 (1969): 19-43.
  * [9] Edelsbrunner, Herbert. Geometry and topology for mesh generation. Cambridge University Press, 2001.
  * [10] Erickson, Jeff, and Patrick Lin. ”Planar and Toroidal Morphs Made Easier.” (2021).
  * [11] Leibon, Gregory. ”Characterizing the Delaunay decompositions of compact hyperbolic surfaces.” Geometry and Topology 6.1 (2002): 361-391.
  * [12] Luo, Feng. ”A characterization of spherical polyhedral surfaces.” Journal of Differential Geometry 74.3 (2006): 407-424.
  * [13] Luo, Yanwen. ”Spaces of geodesic triangulations of surfaces.” Discrete & Computational Geometry (2022): 1-19.
  * [14] Luo, Yanwen, Tianqi Wu, and Xiaoping Zhu. ”The Deformation Spaces of Geodesic Triangulations of Flat Tori.” arXiv preprint arXiv:2107.05159 (2021).
  * [15] Luo, Yanwen, Tianqi Wu, and Xiaoping Zhu. ”The Deformation Space of Geodesic Triangulations and Generalized Tutte’s Embedding Theorem.” arXiv preprint arXiv:2105.00612 (2021).
  * [16] Richter-Gebert, Jürgen. Realization spaces of polytopes. Springer, 2006.
  * [17] Rivin, Igor. ”Euclidean structures on simplicial surfaces and hyperbolic volume.” Annals of mathematics (1994): 553-580.
  * [18] Smale, Stephen. ”Diffeomorphisms of the 2-sphere.” Proceedings of the American Mathematical Society 10.4 (1959): 621-626.
  * [19] Steinitz, Ernst. ”Polyeder und raumeinteilungen.” Encyk der Math Wiss 12 (1922): 38-43.