The Deformation Spaces of Geodesic Triangulations of Flat Tori

Let $\mathbb{T}^{2}=\mathbb{R}^{2}/\mathbb{Z}^{2}=[0,1]^{2}/\sim$ be the flat torus constructed by gluing the opposite sides of the unit square in $\mathbb{R}^{2}$.

A topological triangulation of $\mathbb{T}^{2}$ can be identified as a homeomorphism $\psi$ from $|\mathcal{T}|$ to $\mathbb{T}^{2}$, where $|\mathcal{T}|$ is the carrier of a 2-dimensional simplicial complex $\mathcal{T}=(V,E,F)$ with the vertex set $V$, and the edge set $E$, and the face set $F$. For convenience, we label the vertices as $v_{1},...,v_{n}$ where $n=|V|$ is the number of the vertices. Denote $|E|$ as the number of the edges, and $\vec{e}_{ij}$ as the directed edge from the vertex $i$ to its neighbor $j$, and $\vec{E}=\{\vec{e}_{ij}:ij\in E\}$ as the set of directed edges, and $N(i)$ as the indices of neighbored vertices of $v_{i}\in V$.

A geodesic triangulation with the combinatorial type $(\mathcal{T},\psi)$ is an embedding $\varphi$ from the one-skeleton $\mathcal{T}^{(1)}$ to $\mathbb{T}^{2}$ 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 of constant speed, and

2. (b)

   $\varphi$ is homotopic to the restriction of $\psi$ on $\mathcal{T}^{(1)}$.

Let $X=X(\mathbb{T}^{2},\mathcal{T},\psi)$ denote the set of all such geodesic triangulations, which is so-called a deformation space of geodesic triangulations of $\mathbb{T}^{2}$. This space can be defined for other flat tori in a similar fashion. Perturbing each vertex locally, we can construct a family of geodesic triangulations from an initial geodesic triangulation. Therefore, the space $X$ is naturally a $2n$-dimensional manifold.

For any geodesic triangulation $\varphi\in X$, we can always translate $\varphi$ on $\mathbb{T}^{2}$ to make the image $\varphi(v_{1})$ of the first vertex $v_{1}$ be at the (quotient of the) origin $(0,0)$. By this normalization, we can decompose $X$ as $X=X_{0}\times\mathbb{T}^{2}$, where

Since there are affine transformations between any two flat tori, and an affine transformation always preserves the geodesic triangulations, Theorem 1.1 reduces to the following.

Let $\varphi$ be a map from $\mathcal{T}^{(1)}$ to $\mathbb{T}^{2}$. Assume $\varphi$ maps every edge in $E$ to a geodesic arc parametrized by constant speed on $\mathbb{T}^{2}$. A positive assignment $w\in\mathbb{R}_{+}^{\vec{E}}$ on the set of directed edges is called a weight of $\mathcal{T}$. We say $\varphi$ is $w$-balanced at $v_{i}$ if

where $\dot{\varphi}_{ij}=\dot{\varphi}_{ij}(0)\in T_{\varphi(v_{i})}\mathbb{T}^{2}\cong\mathbb{R}^{2}$. Then $\dot{\varphi}_{ij}$ indicates the direction of the edge $\varphi(e_{ij})$ and $\|\dot{\varphi}_{ij}\|$ equals to the length of $\varphi(e_{ij})$. A map $\varphi$ is called $w$-balanced if it is $w$-balanced at each vertex in $V$. We have the following version of Tutte’s embedding theorem, which is a special case of Gortler-Gotsman-Thurston’s embedding result in [11] and Theorem 1.6 in [13].

To be self-contained, we will give a simple proof for Theorem 1.3 , which is adapted from Gortler-Gotsman-Thurston’s argument in [11].

The classical Tutte’s embedding theorem [14] states that a straight-line embedding of a simple 3-vertex-connected planar graph can be constructed by fixing an outer face as a convex polygon and solving interior vertices on the condition that each vertex is in the convex hull of its neighbors. Various new proofs of Tutte’s embedding theorem have been proposed by Floater [9], Gortler-Gotsman-Thurston [11], et al.

Tutte’s embedding theorem has been generalized by Colin de Verdière [5], Delgado-Friedrichs [6], and Hass-Scott [12] to surfaces with non-positive Gaussian curvatures. They showed that the minimizer of a discrete Dirichlet energy is a geodesic triangulation. Here the fact that $\varphi$ is a minimizer of a discrete Dirichlet energy means that $\varphi$ is $w$-balanced for some symmetric weight $w$ in $\mathbb{R}^{\vec{E}}_{+}$ with $w_{ij}=w_{ji}$. Their result also implies that $X=X(\mathbb{T}^{2},\mathcal{T},\psi)$ is not an empty set for any topological triangulation $(\mathcal{T},\psi)$. Recently, Luo-Wu-Zhu [13] proved a new version of Tutte’s embedding theorem, for nonsymmetric weights and triangulations of orientable closed surfaces with non-positive Gaussian curvature.

Gortler-Gotsman-Thurston [11] generalized Tutte’s embedding theorem to flat tori. In contrast to the case of convex polygons and surfaces of negative curvatures, it is not always possible to construct a geodesic triangulation of $\mathbb{T}^{2}$ such that it is $w$-balanced with respect to a given non-symmetric weight $w$. See [3] Section 1.1 for a detailed discussion.

Fix a lifting $(\tilde{x}_{i},\tilde{y}_{i})\in\mathbb{R}^{2}$ of $\psi(v_{i})\in\mathbb{T}^{2}$ for each $i=1,...,n$. Then for any $\vec{e}_{ij}\in\vec{E}$, there exists a unique lifting $\tilde{\psi}_{ij}:[0,1]\rightarrow\mathbb{R}^{2}$ of $\psi_{ij}=\psi|_{e_{ij}}:[0,1]\rightarrow\mathbb{T}^{2}$ such that $\tilde{\psi}_{ij}(0)=(\tilde{x}_{i},\tilde{y}_{i})$. Then

for some lattice point $(b_{ij}^{x},b_{ij}^{y})\in\mathbb{Z}^{2}$.

A geodesic triangulation $\varphi$ in $X_{0}$ can be represented by $(x_{i},y_{i})\in\mathbb{R}^{2}$ for $i=1,...,n$ with $(x_{1},y_{1})=(0,0)$. Under this representation, $\varphi_{ij}:[0,1]\rightarrow\mathbb{T}^{2}$ is the quotient of the linear map

and the equations for $w$-balanced conditions at all the vertices can be written as

In a closed matrix form, we can write

where the weight matrix $A(w)$ is

and

Here we denote $w_{ij}=0$ if $e_{ij}\notin E$.

A weight $w$ in $\mathbb{R}^{\vec{E}}_{+}$ is called admissible if the equation (1) is solvable. Let $W$ be the space of admissible weights. For any $w\in W$, a solution $\mathbf{x}$ to the equation (1) uniquely determines the coordinates of the vertices, and a $w$-balanced map $\varphi$ that is homotopic to $\psi|_{\mathcal{T}^{(1)}}$. By Theorem 1.3, such $\varphi$ is an embedding, and $\varphi\in X$. Noticing that $A(w)$ is weakly diagonal dominant and the graph $\mathcal{T}^{(1)}$ is connected, the solution to equation (1) is unique up to a 2-dimensional translation, and is unique if we require $(x_{1},y_{1})=(0,0)$. Define the Tutte map as

sending an admissible weight $w$ to the unique $w$-balanced geodesic triangulation in ${X}_{0}$. The Tutte map is continuous by the continuous dependence of the solutions to the coefficients in a linear system.

The Tutte map is also surjective, since there exists a smooth map $\sigma$ from ${X}_{0}$ to $W$ by the “mean value coordinates”

introduced by Floater [10]. Here $\alpha_{i}^{j},\beta_{i}^{j}$ are two inner angles adjacent to $e_{ij}$ at the vertex $v_{i}$, and $l_{ij}$ is the edge length of $\varphi_{ij}$. See Figure 1 for an illustration. Floater [10] showed that any geodesic triangulation $\varphi$ is $\sigma(\varphi)$-balanced, i.e., $\Phi\circ\sigma=Id_{X_{0}}$.

Having the knowledge of the Tutte map and the mean value coordinates, Theorem 1.2 reduces to the following proposition.

In Section 2, we will prove Proposition 1.4 by constructing a flow. In Section 3, we prove Theorem 1.3 following the idea in Gortler-Gotsman-Thurston’s work [11].

We really appreciate Professor Jeff Erickson for providing valuable insights and references about this problem.

Assume $\Theta(w)$ and $C=C(w^{0})$ are as in Lemma 2.1. Given $w^{0}\in\mathbb{R}_{+}^{\vec{E}}\backslash W$, assume $w(t)$ is the flow defined by equation (2), and $[0,T)$ is the maximum existing interval.

We claim that $T=T(w^{0})<\infty$ and $w(t)$ converge to some $\bar{w}$ as $t\rightarrow T$. Since

we have that

and

which implies

Since

we have that

Then by the monotone convergence theorem, $w(t)$ converge to some $\bar{w}$. By the maximality of $T$, $\bar{w}$ has to be in $W$. Let $\Phi:\mathbb{R}^{\vec{E}}_{+}\rightarrow W$ be such that $\Phi(w^{0})=\bar{w}$ if $w^{0}\notin W$, and $\Phi(w)=w$ if $w\in W$.

Now we prove that $\Phi$ is continuous, i.e., for any $w\in\mathbb{R}^{\vec{E}}_{+}$ and $\epsilon>0$, there exists $\delta>0$ such that $|\Phi(w^{\prime})-\Phi(w)|_{\infty}\leq\epsilon$ for any $w^{\prime}$ with $|w^{\prime}-w|_{\infty}<\delta$. We consider the two cases $w\in W$ and $w\notin W$.

Denote $\mathbf{x}(w)$ as the minimizer of the second minimization problem in the definition of the energy function $\mathcal{E}(w)$. Define the residual $\mathbf{r}(w)$ as

where

The vector $\mathbf{r}_{i}$ is the residual at the vertex $v_{i}\in V$, and $\mathbf{r}^{x}$, $\mathbf{r}^{y}$ are the projections of the total residual in the directions of the $x$-axis and the $y$-axis respectively. Then by the minimality of $\mathbf{x}(w)$,

Equivalently,

Since $rank(A(w))=n-1$, $\mathbf{r}^{x}\|\mathbf{r}^{y}$. So $rank(\mathbf{r})\leq 1$, and $\mathbf{r}_{i}\|\mathbf{r}_{j}$ for any $1\leq i,j\leq n$. Here $u\|v$ means that vectors $u$ and $v$ are parallel, i.e., linearly dependent.

Assume $\mathbf{n}=\mathbf{n}(w)\in\mathbb{R}^{2}$ is the unit vector that is parallel to $\mathbf{r}_{1}$ and $\langle\mathbf{n},\mathbf{r}_{1}\rangle>0$. Define for each directed edge,

where $\mathbf{x}_{i}=(x_{i},y_{i})$ is given by the minimizer $\mathbf{x}(w)$. Note that

We define the smooth flow $\Theta$ on the domain $\mathbb{R}_{+}^{\vec{E}}\backslash W$ on each edge as follows

where $g$ and $h$ are smooth non-increasing functions such that

1. (a)

   The function $g\equiv 1$ on $(-\infty,-1)$ and $g\equiv 0$ on $[0,+\infty)$, and

2. (b)

   The function $h\equiv 1$ on $(-\infty,1)$, and $h\equiv 0$ on $[2,+\infty)$, and

3. (c)

   $$\alpha=\alpha(w)=\beta\cdot\bigg{(}2|E|+\sum_{\vec{e}_{ij}\in\vec{E}}w_{ij}^{-1}\bigg{)}^{-1}.$$

Roughly speaking, the function $g$ tends be positive if $u_{ij}<0$, meaning that $w_{ij}u_{ij}$ will decrease so as to reduce the residual $\|\mathbf{r}_{i}\|_{2}$. The function $h$ controls the difference between $w_{ij}$ and $w_{ji}$. $\alpha(w)$ is smooth and very small. Specifically we have that

where $L(w)=\min_{\vec{e}_{ij}\in\vec{E}}w_{ij}$ is a continuous function on $w\in\mathbb{R}^{\vec{E}}_{+}$. Denote

which is another continous function on $\mathbb{R}^{\vec{E}}_{+}$.