# Stable Discrete Minimization of Conformal Energy for Disk Conformal
Parameterization

Zhong-Heng Tan School of Mathematics, Southeast University, Nanjing, 210096,
and Nanjing Center for Applied Mathematics, Nanjing, 211135, People’s Republic
of China. (Email<EMAIL_ADDRESS>Zhenyue Zhang Corresponding author,
Nanjing Center for Applied Mathematics, Nanjing, 211135, and Zhejiang
University, Hangzhou, 310027, People’s Republic of China. (Email:
<EMAIL_ADDRESS>
###### Abstract

Conformal energy minimization is an efficient approach to compute conformal
parameterization. In this paper, we develop a stable algorithm to compute
conformal parameterization of simply connected open surface, termed Stable
Discrete Minimization of Conformal Energy (SDMCE). The stability of SDMCE is
reflected in the guarantee of one-to-one and on-to property of computed
parameterization and the insensitivity on the initial value. On one hand,
SDMCE can avoid degeneration and overlap of solution, also, SDMCE is folding
free. On the other hand, even if given poor initial value, it can still
correct it in very little computational time. The numerical experiments
indicate SDMCE is stable and competitive with state-of-the-art algorithms in
efficiency.

Key words— disk conformal parameterization, conformal energy, adaptive
parameters, folding free

##  1 Introduction

Conformal parameterization aims to find a conformal mapping that maps a given
manifold $\mathcal{M}$ to another manifold $\mathcal{M}^{*}$ with a regular
shape, such as square, disk and sphere. The conformal mapping, also known as
angle-preserving mapping, means the intersection angle of every pair of
intersecting arcs on $\mathcal{M}^{*}$ equals to that of corresponding pre-
images on $\mathcal{M}$. Conformal parameterization has been widely applied in
texture mapping [3, 6], image morphing [17, 18], medical imaging [8] and
physical analysis [20]. Therefore, how to compute the conformal mapping
efficiently, accurately and stably is a significant problem.

The computation of discrete conformal mapping has been developed in variant
approaches so far. Some are to solve equation such as partial differential
equations to compute it. [3] solves Laplace-Beltrami equation by finite
element method to obtain the conformal mapping from closed surface to sphere.
FLASH [15], FDCP [16] and LDCP [19] utilize the compound of multiple quasi-
conformal mappings to construct a conformal mapping onto sphere/disk.
Different from these approaches, some are to minimize defined energy
funcationals or angle distortions to compute it. ABF [5] and ABF++ [10]
directly compute the optimal intersection angles by minimizing the angle
distortion first and then align the vertices on the planar domain. Discrete
Ricci flow [12] and its generalization [14] compute the conformal mapping by
minimizing the Ricci energy, which can be used on surface with arbitrary
topologies. MIPS [4] minimizes sum of ratio of Dirichlet energy and area on
each triangle, called as deformation distortion, which flattens the open
surface on the planar domain. LSCM [6] and DCP [7] minimize the conformal
energy to compute conformal mapping onto a free boundary domain on
$\mathcal{R}^{2}$. Spectral conformal parameterization [13] transform the
conformal energy minimization into a generalized eigenvalue problem. Whereas,
CEM [18] and CCEM [21] compute conformal mapping from simply connected open
surface to disk by minimizing the conformal energy.

In this paper, we focus on the disk conformal parameterization by minimizing
the conformal energy, that is, the computation of discrete conformal mapping
from open surface to the 2D unit disk. According to the uniformization
theorem, the existence of this mapping is guaranteed. Compared with other
approaches, conformal energy minimization is efficient since it yields a
linear system without extra constraints. However, there are two issues that
should be addressed in numerical computation:

######  Question 1.

How can we guarantee a computed solution obeying the onto-restriction to the
unit disk?

Generally, the boundary vertices are restricted to be unit for mapping the
surface to the unit disk. However, this constraint cannot preserve the
required onto-property automatically. Actually, minimization of discrete
conformal energy under the boundary constraint has a degeneration solution
that maps the whole vertices onto a single point with unit length. The
centralization strategy used in [] may partially address this degeneration,
though this strategy may change the boundary distribution.

######  Question 2.

How can we guarantee a computed solution preserving the one-to-one property?
Or equivalently, how can we avoid folding that may appear in the numerical
solution?

The folding phenomenon exists in many algorithms [9, 13]. There are some
issues that may result in the foldings. First, no special strategies are taken
into accounted in discretization modeling generally. Second, numerical
computation errors may also result in foldings. For instance, it is required
to solving a linear system for determining the interior vertices from boundary
vertices. However, an ill-conditioned coefficient matrix may yield relative
large computational errors. Third, unsuitable distribution of vertices may
result in relative large discrete errors even for Delaunay triangulation.

In this paper, we aim to address these issues. The main technique is to modify
discrete conformal energy by adding a penalty term to penalize the deviation
of the discrete area to the true one, assuming that the area of the target
surface is known, and the discrete area is computable. It is important to
suitably choose the penalty constant for many penalty methods. In our case, we
propose an adaptive approach to address the problem of penalty setting. We
call the approach as Stable Discrete Minimization of Conformal Energy (SDMCE)
since it can address the onto and folding issues with the three advantages:

  * •

SDMCE is insensitive on the initial value and of strong ability to correct for
degeneration. Even if given a pool initial value, such as random order
boundary vertices and partial degeneration boundary, it has a strong ability
on correcting these boundary points.

  * •

SDMCE can avoid overlap phenomenon and eliminate both boundary and interior
folding triangles. That is, the parameterization computed by SDMCE is one-to-
one.

  * •

SDMCE is of fast computation. It has similar computational efficiency to FDCP,
LDCP and CCEM, which are very efficient algorithm in recent years. Meanwhile,
The computational time does not depend on the initial value.

The SDMCE can be easily implemented when the target surface is a 2D unit disk
since the true area is known and the discrete area can be measured by the
mapping $f$ of the boundary vertices.

##  2 Stable discrete minimization of conformal energy

Theoretically, the continuous conformal energy ${\cal E}_{C}(f)={\cal
E}_{D}(f)-{\cal A}^{*}$ can be approximated by the discrete conformal energy.
Since the continuous conformal energy is ${\cal E}_{C}(f)={\cal
E}_{D}(f)-{\cal A}^{*}$, we use the discrete conformal energy

$\displaystyle{\cal E}_{C}^{d}(f)={\cal E}_{D}^{d}(f)-{\cal A}^{*}.$ (2.1)

By the convergence analysis for discrete Dirichlet energy, we also conclude
that the optimal conformal transformation that minimizes the conformal energy
${\cal E}_{C}(f)$ can also be converged by the optimal discrete conformal
transformation that minimizes the discrete conformal energy

$\displaystyle\min_{f\in{\cal F}}\Big{\\{}{\cal E}_{C}^{d}(f)={\cal
E}_{D}^{d}(f)-{\cal A}^{*}\Big{\\}},$ (2.2)

or equivalently, minimizes the discrete Dirichlet energy, as $d\to 0$,
provided that the discrete solution $f_{d}$ guarantees the one-to-one mapping
from ${\cal M}$ to ${\cal M}^{*}$. The discrete conformal energy ${\cal
E}_{C}^{d}(f)={\cal E}_{D}^{d}(f)-{\cal A}^{*}$ can also be taken as a
reliable measurement for the approximation of optimal discrete Dirichlet
energy to the optimal continuous Dirichlet energy ${\cal E}_{D}(f)={\cal
A}^{*}$.

###  2.1 Stable discrete minimization

Clearly, minimizing the discrete Dirichlet energy or discrete conformal energy
is a constrained problem since it asks for a mapping from ${\cal M}$ onto a
given ${\cal M}^{*}$. However it is not easy to obey the constraint $f({\cal
M})={\cal M}^{*}$ when one looks for a discrete solution. The difficulties
involved in numerical computation may include the two issues that are tightly
related with each other:

  * •

the restriction of imaged points $\\{f_{i}=f(v_{i})\\}$ lying on the surface
${\cal M}^{*}$, and

  * •

the approximation to the whole surface ${\cal M}^{*}$ by the piece-wisely
linear triangular faces.

The restriction issue may be easily addressed for some simple surfaces such as
a 2D disk or a 3D ball. The approximation issue tightly depends on the
distribution of $\\{f_{i}\\}$ on the surface ${\cal M}^{*}$. To our
acknowledge, no algorithms for discrete conformal transformation can address
this issue well.

The approximation issue is implicitly and partially touched in [18, 21] by two
strategies when ${\cal M}^{*}$ is a 2D disk: imposing zero mean for
$\\{f_{i}\\}$ and minimizing a discrete conformal energy $\frac{1}{2}\langle
Lf,f\rangle-A(f)$ with a discrete area $A(f)$ in term of $\\{f_{i}\\}$ as
shown in (3.3) later. Starting with a good initial guess that solves a
discrete harmonic equation, the approach performs well in some examples. If
the initial guess is suitably chosen, a perplexity mistake may happen: a poor
solution has a very small value of the measurement. This phenomenon may also
happen when the true area ${\cal A}^{*}=\pi$ is used to replace the estimated
area $A(f)$, if only ask $\\{f_{i}\\}$ belong to the disk and the boundary
points have unit length, together with the zero mean, since the discrete
solution may be folded under these restrictions, as shown later in Figure 3-1.

To address the approximation issue, we propose a penalized model of (2.2).
Suppose that the restriction issue on ${\cal M}^{*}$ is addressed, i.e.,
$\\{f_{i}\\}\subset{\cal M}^{*}$, and the area ${\cal A}^{*}$ of ${\cal
M}^{*}$ is known or well estimated.111These assumptions are easily satisfied
for some special ${\cal M}^{*}$. If no foldings happen on the imaged points
$\\{f_{i}\\}$, that is, all the triangle vertices $\\{f_{i},f_{j},f_{k}\\}$
have the consistent anticlockwise order,222Theoretically, the folding should
not also happen on the interior points. the area of ${\cal M}^{*}$ can be well
approximate by the discrete area $A(f)$, i.e. the area of piecewise constant
surface of the triangulation $\\{F_{ijk}=[f_{i},f_{j},f_{k}]\\}$,

$\displaystyle A(f)=\frac{1}{2}\sum_{V_{ijk}\in
V}\|(f_{i}-f_{k})\times(f_{j}-f_{k})\|=\frac{1}{2}\sum_{V_{ijk}\in
V}\sin\theta_{ij}\|f_{jk}\|_{2}\|f_{ki}\|_{2},$ (2.3)

where $\theta_{ij}$ is the interior angle opposite to the edgy connection
$f_{i}$ and $f_{j}$ in the triangle $F_{ijk}=\\{f_{i},f_{j},f_{k}\\}$. Suppose
that the approximation of the discrete area $A(f)$ to ${\cal A}^{*}$ is
measured by an error function $\varepsilon_{A}(f)$. We can transform the
minimization of discrete conformal energy (2.2) to the penalized problem

$\displaystyle\min_{f_{i}\in{\cal M}^{*}}\Big{\\{}\frac{1}{2}\langle
Lf,f\rangle-{\cal A}^{*}+\mu\varepsilon_{A}(f)\Big{\\}}$ (2.4)

for stably minimizing the discrete conformal energy, where $f=f(V)$ is the
discrete form of $f$ and each row is a point $f_{\ell}$. We call it as Stable
Discrete Minimization of Conformal Energy (SDMCE). In this paper, we suggest
$\varepsilon_{A}(f)=\frac{1}{2}\big{(}{\cal A}^{*}-A(f)\big{)}^{2}$.

By the way, the true area ${\cal A}^{*}$ can also be replaced by the estimated
discrete ares $A(f)$ if this inequality $A(f)\leq{\cal A}^{*}$ is always true
for $f({\cal M})\subset{\cal M}^{*}$. That is, (2.4) is approximately
equivalent to

$\displaystyle\min_{f_{i}\in{\cal M}^{*}}\Big{\\{}\frac{1}{2}\langle
Lf,f\rangle-A(f)+\mu\varepsilon_{A}(f)\Big{\\}}.$ (2.5)

Generally,

$\displaystyle\min_{f_{i}\in{\cal M}^{*}}\Big{\\{}\frac{1}{2}\langle
Lf,f\rangle-{\cal A}^{*}+\mu\varepsilon_{A}(f)\Big{\\}}$
$\displaystyle\leq\min_{f_{i}\in{\cal M}^{*}}\Big{\\{}\frac{1}{2}\langle
Lf,f\rangle-A(f)+\mu\varepsilon_{A}(f)\Big{\\}}$
$\displaystyle\leq\frac{1}{2}\langle
LF^{*},F^{*}\rangle-A(f^{*})+\mu\varepsilon_{A}(f),$

where $F^{*}=\\{f_{i}^{*}=f^{*}(v_{i})\\}$ is the optimal solution of (2.4).

It is a bit complicated to solve (2.4) or (2.5), due to the computational
difficulty of the estimated area function $A(f)$. We may have to generate a
new approach to estimate the area in terms of the imaged points $\\{f_{i}\\}$.
This will be one of the topics in our coming work. However, when ${\cal
M}^{*}$ is a 2D disk, this difficulty can be released since a simple formula
of $A(f)$ exists. We will propose a modification of SDMCE for the unit 2D disk
that releases the onto-restriction in Section 3.

###  2.2 Adaptive setting of the penalty parameter

A suitable value of the penalty parameter $\mu$ should yield a small discrete
conformal energy ${\cal E}_{C}^{d}(f)={\cal E}_{D}^{d}(f)-{\cal A}^{*}$ in
absolute value, and meanwhile, the area deviation ${\cal A}^{*}-A(f)$ is also
small and positive theoretically. The latter is important to preserve a one-
to-one mapping. These two metrics are computable given a solution $f$.
Meanwhile, the angle preserving is also checkable via the angle errors
$\\{\epsilon_{\theta_{\ell}}(f)\\}$ or their average $\bar{\epsilon}(f)$.
Hence, the parameter $\mu$ can be easily tuned to get a solution as good as
possible via a simple tuning rule. Below we show such a tuning role for $\mu$.

  * •

Initially, we set $\mu=0$. If the solution $f$ gives a negative ${\cal
E}_{C}^{d}(f)$ or a negative $\epsilon_{A}(f)$, we increase $\mu$ as
$\mu:=\mu+s_{\mu}$ successively, where $s_{\mu}$ is a constant step length or
increased step length step-by-step. We use the later one as
$s_{\mu}:=s_{\mu}+10$ before $\mu$ is updated. The initial $s_{\mu}=0$.

  * •

As soon as both ${\cal E}_{C}^{d}(f)$ and $\epsilon_{A}(f)$ are nonnegative
with a chosen $\mu$, we set $\mu^{\prime}=\mu$, $f^{\prime}=f$. Then, modify
$s_{\mu}:=\max\\{s_{\mu},10\\}$ and increase $\mu^{\prime}$ to
$\mu^{\prime\prime}=\mu^{\prime}+s_{\mu}$, and compute a solution
$f^{\prime\prime}=f$ with $\mu=\mu^{\prime\prime}$. If one of ${\cal
E}_{C}^{d}(f^{\prime\prime})$ and $\epsilon_{A}(f)$ is negative,
$\mu^{\prime\prime}$ should be also increased as above for
$\mu^{\prime}$.333In our experiments, this case never happens.

  * •

If the gap between $\bar{\epsilon}(f^{\prime})$ and
$\bar{\epsilon}(f^{\prime\prime})$ is a bit large, we can further tuning the
$\mu^{\prime}$ or $\mu^{\prime\prime}$ to get a better solution than
$f^{\prime}$ and $f^{\prime\prime}$. Algorithm 1 gives the details of the
strategy of tuning $\mu$.

  * •

By nonnegative ${\cal E}_{C}^{d}(f)$ or $\epsilon_{A}(f)$ numerically, we mean
${\cal E}_{C}^{d}(f)>-\tau$ and $\epsilon_{A}(f)>-\tau$ with a given accuracy
$\tau>0$.

Algorithm 1 Adaptive parameter tuning of $\mu$.

0: Accuracy $\tau$

1: Choose initial boundary points with central angles $T_{0}=\\{t_{i}\\}$ and
set $\mu=0$, $s_{\mu}=0$

2: while one of $\mu^{\prime}$ and $\mu^{\prime\prime}$ is empty do

3: repeat

4: Update $\mu:=\mu+s_{\mu}$ and $s_{\mu}=s_{\mu}+10$, and compute $f$ by
SDMCE starting with $T_{0}$.

5: If $|\epsilon_{A}(f)|<0.1$, update $T_{0}$ by the central angles $T$ of the
boundary points of $f$.

6: until ${\cal E}_{C}^{d}(f)>-\tau$ and $\epsilon_{A}(f)>-\tau$.

7: If $\mu^{\prime}$ is empty, set $\mu^{\prime}=\mu$ and $f^{\prime}=f$,
otherwise set $\mu^{\prime\prime}=\mu$ and $f^{\prime\prime}=f$.

8: end while

9: if $\bar{\epsilon}(f^{\prime})<(1-\tau)\bar{\epsilon}(f^{\prime\prime})$
and $\mu^{\prime}>0$ then

10: while $s_{\mu}>5$ do

11: repeat

12: Update $s_{\mu}:=s_{\mu}/2$, $\mu=\lfloor\mu^{\prime}-s_{\mu}\rfloor$, and
compute $f$ by SDMCE again.

13: until ${\cal E}_{C}^{d}(f)>-\tau$ and $\epsilon_{A}(f)>0$.

14: If $\epsilon_{\theta}(f)<(1-\tau)\bar{\epsilon}(f^{\prime})$, update
$\mu^{\prime}$ and $f^{\prime}$ by $\mu$ and $f$ respectively.

15: end while

16: end if

17: if $\bar{\epsilon}(f^{\prime\prime})<(1-\tau)\bar{\epsilon}(f^{\prime})$
then

18: repeat

19: Update $\mu=\mu^{\prime\prime}+s_{\mu}$ and compute $f$ by SDMCE again.

20: If $\epsilon_{\theta}(f)<(1-\tau)\bar{\epsilon}(f^{\prime\prime})$, update
$\mu^{\prime\prime}$ and $f^{\prime\prime}$ by $\mu$ and $f$, respectively.

21: until $f^{\prime\prime}$ does not updated.

22: end if

23: return $f=f^{\prime}$ if
$\bar{\epsilon}(f^{\prime})<\bar{\epsilon}(f^{\prime\prime})$, or
$f=f^{\prime\prime}$ otherwise.

##  3 The SDMCE for unit 2D disk

For the 2D disk ${\cal M}^{*}=\big{\\{}\mathbf{y}\in{\cal
R}^{2}:\|\mathbf{y}\|_{2}\leq 1\big{\\}}$, a discrete conformal energy
different from (2.1)

$\displaystyle\widetilde{\cal E}_{C}^{d}(f)=\frac{1}{2}\langle
Lf,f\rangle-A(f)$ (3.1)

was considered in [21], where $A(f)$ is the discrete are of the unit disk as
(2.3), and it has a simple representation in terms of the boundary points of
$\\{f_{i}\\}$ as shown in (3.3). The approach CCEM proposed in [21] minimizes
$\widetilde{\cal E}_{C}^{d}(f)$, i.e., solves

$\displaystyle\min\Big{\\{}\frac{1}{2}\langle Lf,f\rangle-A(f)\Big{\\}}$ (3.2)

subject to the unit and exactly separate boundary points of $f$ in a correct
order.

###  3.1 The model of SDMCE for unit disk

For the unit 2D disk ${\cal M}^{*}=\big{\\{}\mathbf{y}\in{\cal
R}:\|\mathbf{y}\|_{2}\leq 1\big{\\}}$, the area ${\cal A}^{*}=\pi$ and its
approximate area $A(f)$ is determined by the polygon of boundary points
$\\{f_{i}:i\in\Gamma\\}$ of $\\{f_{i}\\}$. Without loss of generality, we
assume that the index set of the boundary points is
$\Gamma=\\{1,2,\cdots,n\\}$ with $n$ is the number of boundary points.
Representing the boundary points as $f_{i}=(x_{i},y_{i})$ with $x_{i}=\cos
t_{i}$, $y_{i}=\sin t_{i}$, a monotone sequence $\\{t_{i}\\}\subset[0,2\pi)$
for $i=1,2,\cdots,n$, and $t_{0}=t_{n}$, we have

$\displaystyle
A(f)=\frac{1}{2}\sum_{i}\sin(t_{i}-t_{i-1})=\frac{1}{2}\sum_{i}\big{(}y_{i}x_{i-1}-x_{i}y_{i-1}\big{)}=\frac{1}{2}\langle
x_{\Gamma},D_{2}y_{\Gamma}\rangle,$ (3.3)

where $D_{2}$ is a second-order difference operator and skew-symmetric:
$D_{2}^{\top}=-D_{2}$, satisfying

$D_{2}(y_{1},\cdots,y_{n})^{\top}=\big{(}y_{2}-y_{n},y_{3}-y_{1},\cdots,y_{n}-y_{n-2},y_{1}-y_{n-1}\big{)}^{\top}.$

By $D_{2}^{\top}=-D_{2}$, we also have $A(f)=\frac{1}{2}\langle
y_{\Gamma},-D_{2}x_{\Gamma}\rangle$, and

$A(f)=\frac{1}{4}\big{\langle}[x_{\Gamma},y_{\Gamma}],D_{2}[y_{\Gamma},-x_{\Gamma}]\big{\rangle}=\frac{1}{4}\big{\langle}f_{\Gamma},D_{2}f_{\Gamma}\Theta\big{\rangle}$

with $\Theta=\left[{0\atop 1}\ {-1\atop 0}\right]$. Hence, the SDMCE model
(2.4) for unit disk becomes

$\displaystyle\min_{\|f_{j}\|_{2}<1,j\notin\Gamma,\|f_{i}\|_{2}=1,i\in\Gamma}\Big{\\{}\frac{1}{2}\langle
Lf,f\rangle-\pi+\frac{\mu}{2}\big{(}\pi-\frac{1}{4}\langle
D_{2}f_{\Gamma}\Theta,f_{\Gamma}\rangle\big{)}^{2}\Big{\\}}.$ (3.4)

The constrained optimization problem can be solved by classical optimization
algorithms such as trust-region method [2], gradient descent method [], or
nonlinear conjugated gradient (NCG) [1]. We use a modified version of NCG
proposed in [11] in the experiments reported in this paper. Notice that the
objective function has a relative simple structure: the first term is a
quadratic form whose coefficient matrix $L$ is diagonal dominant generally if
the triangulation is Delaunay [21], and the penalization term is the square of
a shifted quadratic form.

Let $\Gamma_{c}$ be the index set of interior points. It is also the
complement of $\Gamma$. For simplicity, we release the restriction
$\|f_{i}\|_{2}<1$ for interior points since it is automatically satisfied, and
keep $\|f_{i}\|_{2}=1$ for the boundary points in (3.4). Hence, partitioning
the Laplacian matrix $L$ in the $2\times 2$ block form with blocks
$L_{\Gamma,\Gamma}$, $L_{\Gamma,\Gamma_{c}}$, $L_{\Gamma_{c},\Gamma}$, and
$L_{\Gamma_{c},\Gamma_{c}}$, and $f$ in the two blocks $f_{\Gamma}$ and
$f_{\Gamma_{c}}$, we can rewrite

$\langle Lf,f\rangle=\langle
L_{\Gamma,\Gamma}f_{\Gamma}+L_{\Gamma,\Gamma_{c}}f_{\Gamma_{c}},f_{\Gamma}\rangle+\langle
L_{\Gamma_{c},\Gamma}f_{\Gamma}+L_{\Gamma_{c},\Gamma_{c}}f_{\Gamma_{c}},f_{\Gamma_{c}}\rangle,$

and the restriction on boundary points is ${\rm
rdot}(f_{\Gamma},f_{\Gamma})=e$, where ${\rm rdot}(A,B)$ for two matrices $A$
and $B$ in the same size is a column vector of the inner productions of
corresponding rows of $A$ and $B$, and $e$ is a column vector of all ones in a
suitable length. Let $\eta(f_{\Gamma})=\pi-\frac{1}{4}\langle
D_{2}f_{\Gamma}\Theta,f_{\Gamma}\rangle$ for simplicity. The KKT conditions of
optimal solutions of (3.4) are

$\displaystyle
L_{\Gamma,\Gamma}f_{\Gamma}+L_{\Gamma,\Gamma_{c}}f_{\Gamma_{c}}-\frac{\mu\eta(f_{\Gamma})}{2}D_{2}f_{\Gamma}\Theta=\Lambda
f_{\Gamma},$ (3.5) $\displaystyle
L_{\Gamma_{c},\Gamma}f_{\Gamma}+L_{\Gamma_{c},\Gamma_{c}}f_{\Gamma_{c}}=0,\quad{\rm
rdot}(f_{\Gamma},f_{\Gamma})=e.$ (3.6)

where $\Lambda=\mathrm{diag}(\lambda)$ with a column vector $\lambda$.

The restriction
$L_{\Gamma_{c},\Gamma}f_{\Gamma}+L_{\Gamma_{c},\Gamma_{c}}f_{\Gamma_{c}}=0$
for a KKT point shows the dependence of inner points to the boundary points.
This restriction is enforced on feasible solution in [21]. That is, take the
boundary points $f_{\Gamma}$ as variables and
$f_{\Gamma_{c}}=-L_{\Gamma_{c},\Gamma_{c}}^{-1}L_{\Gamma_{c},\Gamma}f_{\Gamma}$
before optimizing, assuming that $L_{\Gamma_{c},\Gamma_{c}}$ is invertible. In
this case,

$\langle Lf,f\rangle=\langle
L_{\Gamma,\Gamma}f_{\Gamma}+L_{\Gamma,\Gamma_{c}}f_{\Gamma_{c}},f_{\Gamma}\rangle=\big{\langle}(L_{\Gamma,\Gamma}-L_{\Gamma,\Gamma_{c}}L_{\Gamma_{c},\Gamma_{c}}^{-1}L_{\Gamma_{c},\Gamma})f_{\Gamma},f_{\Gamma}\big{\rangle}=\langle
Sf_{\Gamma},f_{\Gamma}\rangle,$

where
$S=L_{\Gamma,\Gamma}-L_{\Gamma,\Gamma_{c}}L_{\Gamma_{c},\Gamma_{c}}^{-1}L_{\Gamma_{c},\Gamma}$
is the Schur complement of $L_{\Gamma,\Gamma}$. Hence, the problem (3.4)
becomes

$\displaystyle\min_{\|f_{i}\|_{2}=1,i\in\Gamma}\Big{\\{}\frac{1}{2}\langle
Sf_{\Gamma},f_{\Gamma}\rangle-\pi+\frac{\mu}{2}\big{(}\pi-\frac{1}{4}\langle
D_{2}f_{\Gamma}\Theta,f_{\Gamma}\rangle\big{)}^{2}\Big{\\}}.$ (3.7)

The benefit of the above simplified SDMCE for disk is that it significantly
reduces the problem scale since the number of boundary points $|\Gamma|$ is
significantly smaller than the number of interior points $|\Gamma_{c}|$. The
coefficient matrix $S$ could be constructed explicitly or implicitly for
computing $Sf_{\Gamma}$. The former solves
$L_{\Gamma_{c},\Gamma_{c}}H=L_{\Gamma_{c},\Gamma}$ and forms
$S=L_{\Gamma,\Gamma}-L_{\Gamma,\Gamma_{c}}H$ once only, and computes
$Sf_{\Gamma}$ in each iteration. The later solves
$L_{\Gamma_{c},\Gamma_{c}}h=L_{\Gamma_{c},\Gamma}f_{\Gamma}$ at first and then
$Sf_{\Gamma}=L_{\Gamma,\Gamma}f_{\Gamma}-L_{\Gamma,\Gamma_{c}}h$ in each
iteration. Hence, if an iterative solver used for (3.7) needs a lot of
iterations more than $|\Gamma|$, the explicit strategy costs less than the
implicit strategy. In our experiments, we still use the explicit strategy. By
the way, computing interior points from boundary points strongly depends on
the condition number of $L_{\Gamma_{c},\Gamma_{c}}$; It may loss efficiency
when $L_{\Gamma_{c},\Gamma_{c}}$ is ill-conditioned since small perturbation
from boundary points will enlarged to the interior points.

Data |  Fixed $\mu=10$ |  Variant $\mu\in[a,b]$
---|---|---
ID | Name | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$ | Time(s) | $[a,b]$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$
Mean | Std | Mean | Std
1 | BimbaStatue | 9.64e-04 | 6.23e-03 | 18.37 | [ 0, 500] | 9.64e-04 | 5.26e-09 | 6.23e-03 | 8.32e-08
2 | Buddha | 6.60e-04 | 4.97e-03 | 203.08 | [ 0, 250] | 6.60e-04 | 1.38e-12 | 4.97e-03 | 4.58e-10
3 | CCH | 5.42e-03 | 1.16e-02 | 11.51 | [ 0, 250] | 5.42e-03 | 1.74e-07 | 1.16e-02 | 9.69e-06
4 | CHLin1 | 6.98e-03 | 1.30e-02 | 7.76 | [ 0, 250] | 6.98e-03 | 8.70e-06 | 1.31e-02 | 5.68e-05
5 | CYHo | 4.40e-04 | 4.84e-03 | 5.19 | [ 0, 250] | 4.40e-04 | 1.39e-11 | 4.84e-03 | 6.95e-09
6 | CYHo15 | 5.55e-04 | 5.36e-03 | 4.92 | [ 0, 250] | 5.55e-04 | 8.90e-11 | 5.36e-03 | 8.84e-09
7 | CYHo22 | 1.22e-02 | 1.84e-02 | 9.41 | [ 0, 250] | 1.22e-02 | 4.20e-06 | 1.86e-02 | 1.11e-04
8 | CYHo23 | 2.51e-02 | 1.93e-02 | 5.65 | [ 0, 250] | 2.51e-02 | 4.95e-07 | 1.93e-02 | 1.44e-05
9 | CYHo31 | 2.09e-02 | 1.89e-02 | 6.59 | [ 0, 250] | 2.09e-02 | 1.08e-06 | 1.89e-02 | 7.42e-06
10 | ChineseLion | 1.31e-02 | 2.50e-02 | 0.53 | [ 0, 250] | 1.31e-02 | 2.50e-07 | 2.50e-02 | 2.20e-06
11 | CowboyHat | -6.80e-03 | 1.47e-02 | 0.03 | [3600,5000] | 1.09e-03 | 6.15e-04 | 3.66e-02 | 1.23e-03
12 | Dress | 6.40e-02 | 6.10e-02 | 0.06 | [ 0, 250] | 6.42e-02 | 2.44e-04 | 6.09e-02 | 2.04e-05
13 | Ear | 6.99e-02 | 1.04e-01 | 0.01 | [ 5, 50] | 7.78e-02 | 1.22e-02 | 1.06e-01 | 1.68e-03
14 | Face | 1.36e-02 | 3.21e-02 | 16.06 | [ 0, 500] | 1.36e-02 | 2.67e-05 | 3.21e-02 | 8.96e-06
15 | FaceHo | 1.18e-04 | 2.66e-03 | 9.36 | [ 0, 500] | 1.18e-04 | 1.90e-11 | 2.66e-03 | 3.24e-10
16 | FaceLin | 9.27e-04 | 3.31e-03 | 17.93 | [ 0, 500] | 9.27e-04 | 3.99e-09 | 3.31e-03 | 5.44e-07
17 | Femur | -2.47e-03 | 1.65e-02 | 0.37 | [ 20, 500] | 2.00e-03 | 7.75e-04 | 1.63e-02 | 6.10e-05
18 | Foot | -1.40e-02 | 2.54e-02 | 0.13 | [150, 200] | 2.18e-04 | 1.49e-04 | 2.52e-02 | 8.51e-06
19 | Hand | -2.18e-03 | 2.12e-02 | 1.76 | [ 15, 500] | 5.27e-03 | 1.96e-03 | 2.09e-02 | 1.48e-04
20 | HumanBrain | 1.26e-03 | 2.66e-02 | 0.90 | [ 11, 500] | 1.43e-02 | 4.45e-03 | 2.60e-02 | 2.80e-04
21 | KnitCapMan | 5.17e-03 | 9.48e-03 | 2.50 | [ 0, 500] | 5.17e-03 | 7.78e-07 | 9.48e-03 | 2.06e-06
22 | LCH | 6.98e-03 | 1.30e-02 | 7.50 | [ 0, 500] | 6.98e-03 | 1.55e-05 | 1.30e-02 | 1.03e-04
23 | LeftHand | -2.32e-03 | 2.10e-02 | 1.69 | [ 50,4000] | 6.49e-03 | 8.19e-04 | 2.04e-02 | 1.10e-04
24 | MaxPlanckD | 7.22e-03 | 1.05e-02 | 1.06 | [ 0, 500] | 7.22e-03 | 3.47e-07 | 1.05e-02 | 3.21e-07
25 | Nefertiti | -2.91e-02 | 5.03e-02 | 0.01 | [110, 200] | 5.68e-03 | 3.20e-03 | 5.03e-02 | 2.16e-03
26 | NefertitiStatue | 1.67e-03 | 5.53e-03 | 275.70 | [ 0, 500] | 1.67e-03 | 3.09e-09 | 5.53e-03 | 2.84e-08
27 | StanfordBunny | 1.59e-02 | 1.91e-02 | 1.11 | [ 0, 500] | 1.59e-02 | 2.19e-06 | 1.91e-02 | 7.17e-07
28 | StanfordBunny2 | 8.87e-03 | 1.84e-02 | 1.08 | [ 0, 500] | 8.87e-03 | 1.24e-06 | 1.84e-02 | 8.15e-07

Table 3-1: Efficiency of the SDMCE starting with an equal distance boundary
points on 28 real world data sets, measured by the discrete energy ${\cal
E}_{C}^{d}(f)$, the average angle error $\epsilon_{\theta}(f)$, and
computational time

The SDMCE model (2.4) or (3.7) for unit disk works very well. It can
efficiently avoid the degeneration of solution. For instance, starting with a
set of equal-distance points on the unit circle, if we do not use the penalty
term, or set $\mu=0$ equivalently, the minimized discrete Dirichlet energy may
be wrongly zero on some data sets – the solutions degenerate to a single point
together. However, starting the same initial points, the SDMCE with a not very
small $\mu$ gives a good solution on these data sets as shown in the section
of numerical experiments.

Data |  True ordering with variant ratio $\rho=2\pi/\ell$ | Wrong ordering
---|---|---
$\rho=0.4$ | $\rho=0.8$ | $\rho=1.2$ | $\rho=1.6$ | $\rho=2.0$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$
${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{\theta}(f)$
BimbaStatue | 9.58e-04 | 6.23e-03 | 1.09e-03 | 6.29e-03 | 1.05e-03 | 6.26e-03 | 9.51e-04 | 6.23e-03 | 9.56e-04 | 6.24e-03 | 9.47e-04 | 6.24e-03
Buddha | 1.65e-03 | 5.32e-03 | 7.32e-04 | 5.01e-03 | 6.82e-04 | 4.98e-03 | 8.65e-04 | 5.03e-03 | 6.97e-04 | 4.99e-03 | 6.74e-04 | 4.98e-03
CCH | 1.10e-02 | 1.21e-02 | 5.42e-03 | 1.16e-02 | 5.43e-03 | 1.15e-02 | 5.41e-03 | 1.16e-02 | 5.42e-03 | 1.17e-02 | 1.10e-02 | 1.20e-02
CHLin1 | 9.86e-03 | 1.39e-02 | 6.97e-03 | 1.30e-02 | 6.94e-03 | 1.29e-02 | 6.95e-03 | 1.30e-02 | 9.86e-03 | 1.37e-02 | 9.86e-03 | 1.40e-02
CYHo | 3.97e-04 | 4.83e-03 | 4.17e-04 | 4.81e-03 | 4.33e-04 | 5.10e-03 | 5.56e-04 | 5.83e-03 | 3.99e-04 | 4.95e-03 | 9.39e-04 | 7.21e-03
CYHo15 | 4.77e-04 | 5.54e-03 | 6.51e-04 | 5.58e-03 | 5.51e-04 | 5.58e-03 | 6.62e-04 | 6.30e-03 | 4.82e-04 | 5.52e-03 | 8.19e-04 | 7.55e-03
CYHo22 | 1.22e-02 | 1.87e-02 | 1.22e-02 | 1.87e-02 | 2.20e-02 | 1.78e-02 | 1.83e-02 | 1.83e-02 | 1.22e-02 | 1.86e-02 | 1.83e-02 | 1.82e-02
CYHo23 | 1.51e-02 | 2.06e-02 | 1.51e-02 | 2.05e-02 | 1.89e-02 | 1.97e-02 | 1.89e-02 | 1.98e-02 | 1.51e-02 | 2.05e-02 | 1.51e-02 | 2.05e-02
CYHo31 | 1.90e-02 | 1.97e-02 | 1.90e-02 | 1.97e-02 | 2.10e-02 | 1.88e-02 | 2.10e-02 | 1.87e-02 | 1.90e-02 | 1.97e-02 | 4.06e-03 | 2.33e-02
ChineseLion | 1.31e-02 | 2.50e-02 | 1.31e-02 | 2.50e-02 | 1.31e-02 | 2.50e-02 | 1.31e-02 | 2.50e-02 | 1.31e-02 | 2.50e-02 | 1.31e-02 | 2.50e-02
CowboyHat | 5.75e-05 | 3.45e-02 | 5.44e-05 | 3.45e-02 | 1.17e-01 | 4.39e-02 | 1.17e-01 | 4.31e-02 | 1.18e-01 | 4.23e-02 | 1.41e-01 | 5.36e-02
Dress | 6.40e-02 | 6.10e-02 | 6.40e-02 | 6.10e-02 | 6.40e-02 | 6.10e-02 | 6.40e-02 | 6.10e-02 | 6.40e-02 | 6.10e-02 | 6.40e-02 | 6.10e-02
Ear | 6.98e-02 | 1.04e-01 | 6.99e-02 | 1.04e-01 | 6.99e-02 | 1.04e-01 | 6.99e-02 | 1.04e-01 | 6.99e-02 | 1.04e-01 | 6.99e-02 | 1.04e-01
Face | 1.36e-02 | 3.21e-02 | 1.36e-02 | 3.20e-02 | 1.35e-02 | 3.21e-02 | 1.36e-02 | 3.21e-02 | 1.36e-02 | 3.21e-02 | 1.41e-02 | 3.26e-02
FaceHo | 6.33e-05 | 4.35e-03 | 9.63e-05 | 2.90e-03 | 1.66e-04 | 2.78e-03 | 3.50e-04 | 3.32e-03 | 1.50e-04 | 4.05e-03 | 1.24e-04 | 3.52e-03
FaceLin | 1.05e-03 | 3.43e-03 | 1.06e-03 | 3.47e-03 | 9.88e-04 | 3.45e-03 | 1.07e-03 | 3.59e-03 | 1.03e-03 | 3.35e-03 | 1.04e-03 | 3.67e-03
Femur | 3.12e-04 | 1.64e-02 | 2.59e-04 | 1.64e-02 | 2.51e-04 | 1.64e-02 | 3.12e-04 | 1.64e-02 | 3.82e-04 | 1.64e-02 | 2.46e-04 | 1.64e-02
Foot | 2.60e-04 | 2.52e-02 | 2.56e-04 | 2.52e-02 | 2.63e-04 | 2.52e-02 | 2.59e-04 | 2.52e-02 | 2.64e-04 | 2.52e-02 | 2.59e-04 | 2.52e-02
Hand | 5.12e-04 | 2.11e-02 | 5.23e-04 | 2.11e-02 | 5.00e-04 | 2.11e-02 | 4.88e-04 | 2.11e-02 | 4.06e-04 | 2.11e-02 | 4.62e-04 | 2.11e-02
HumanBrain | 1.10e-03 | 2.66e-02 | 1.29e-03 | 2.66e-02 | 1.26e-03 | 2.66e-02 | 1.17e-03 | 2.66e-02 | 1.19e-03 | 2.66e-02 | 1.12e-03 | 2.66e-02
KnitCapMan | 5.17e-03 | 9.48e-03 | 5.17e-03 | 9.49e-03 | 5.17e-03 | 9.49e-03 | 5.17e-03 | 9.49e-03 | 5.17e-03 | 9.48e-03 | 5.17e-03 | 9.49e-03
LCH | 9.86e-03 | 1.39e-02 | 6.97e-03 | 1.30e-02 | 6.94e-03 | 1.29e-02 | 6.95e-03 | 1.30e-02 | 9.86e-03 | 1.37e-02 | 6.95e-03 | 1.32e-02
LeftHand | 4.19e-03 | 2.07e-02 | 4.34e-03 | 2.07e-02 | 4.23e-03 | 2.07e-02 | 4.32e-03 | 2.07e-02 | 4.26e-03 | 2.07e-02 | 4.24e-03 | 2.07e-02
MaxPlanckD | 7.21e-03 | 1.05e-02 | 7.21e-03 | 1.05e-02 | 7.22e-03 | 1.05e-02 | 7.21e-03 | 1.05e-02 | 7.21e-03 | 1.05e-02 | 7.21e-03 | 1.05e-02
Nefertiti | 1.32e-03 | 4.74e-02 | 1.32e-03 | 4.74e-02 | 1.31e-03 | 4.74e-02 | 1.32e-03 | 4.74e-02 | 1.32e-03 | 4.74e-02 | 1.32e-03 | 4.74e-02
NefertitiStatue | 1.68e-03 | 5.53e-03 | 1.82e-03 | 5.54e-03 | 1.74e-03 | 5.53e-03 | 1.72e-03 | 5.53e-03 | 1.68e-03 | 5.53e-03 | 1.69e-03 | 5.53e-03
StanfordBunny | 1.59e-02 | 1.91e-02 | 1.59e-02 | 1.91e-02 | 1.59e-02 | 1.91e-02 | 1.59e-02 | 1.91e-02 | 1.59e-02 | 1.91e-02 | 1.59e-02 | 1.91e-02
StanfordBunny2 | 8.87e-03 | 1.84e-02 | 8.87e-03 | 1.84e-02 | 8.87e-03 | 1.84e-02 | 8.87e-03 | 1.84e-02 | 8.87e-03 | 1.84e-02 | 8.87e-03 | 1.84e-02

Table 3-2: The stability of SDMCE on the wrong starting points.

###  3.2 Advantages of SDMCE for disk

The SDMCE model has some advantages for finding a discrete conformal mapping
as shown below.

  1. 1.

Fast computation. It can be solved by NCG or other classical optimization
problem as the algorithm CCEM given in [21]. In our experiments on 28 real
world data sets, starting with equal-distantly distributed boundary points on
the unit circle for each example, the NCG can give an good solution with
computational time slightly less than that of CCEM, due to the penalty to the
area deviation of solutions.

  2. 2.

Insensitivity on the parameter setting. The penalty model is not sensitive to
the penalization parameter $\mu$ variant in a large range if initially using
the equal-distantly distributed boundary points.

  3. 3.

Ability of avoiding negative discrete conformal energy. The computed solution
may give a negative discrete conformal energy ${\cal E}_{C}^{d}(f)$ as shown
in Table 3-1. Negative ${\cal E}_{C}^{d}(f)$ implies a partially degenerate
solution with a deficient area covering. Increasing the penalty parameter
$\mu$ can decrease the deficiency. Figure LABEL:fig:negative_energy
illustrates the improvement on Ear, Hand, and Nefertiti when $\mu$ is
increased. The improvement on Femur, Foot, LeftHand, and HumanBrain is similar
and omitted. As we mentioned before, minimizing the discrete conformal energy,
i.e., setting $\mu=0$ in SDMCE, will give a solution degenerated in a single
point on these seven examples. Slightly increasing $\mu$ can avoid the
degeneration efficiently. As $\mu$ increases, the negative discrete conformal
energy becomes to positive, and the covering of target domain is improved
significantly. Notice that it also improves the angle preserving of solutions.

  4. 4.

Global convergence. The penalty model can adaptively correct a wrong initial
setting. To show the advantage, we test two kinds of initial setting for
boundary points, each of which results in a very poor initial guess.

     * (a)

The initial setting keeps a correct neighboring order but the ordering points
cover an arc length $\ell$ much less than or over larger than $2\pi$. That is,
we choose the boundary points $f_{i}=(\cos t_{i},\sin t_{i})$ with the ordered
central angles $\\{t_{i}\\}$ distributed in the interval $[0,\ell]$ with equal
neighbor gaps.

     * (b)

The boundary points are uniformly distributed in the unit circle with a random
order. The random ordering means a seriously heavy folding of these points.

The SDMCE has a strong ability on correcting these wrong starting boundary
points. It can avoid the degeneration on all the tested data sets. Table 3-2
lists the discrete conformal energy, the mean of angle errors with the
starting points. By the way, the computational time does not depend the
starting points.

  5. 5.

One-to-one property. A small average value of relative angle errors does not
always means a good solution since the one-to-one property between ${\cal M}$
and ${\cal M}^{*}$ may be lost. The one-to-one can be checked by the
distribution of distances $\\{d_{i}\\}$, defined at each point $f_{i}$ of a
solution by

$\displaystyle d_{i}=\|v_{i}-v_{i^{\prime}}\|,$ (3.8)

where $v_{i}$ and $v_{i^{\prime}}$ are the original points of $f_{i}$ and
$f_{i^{\prime}}$, respectively, and $f_{i^{\prime}}$ is the nearest one of
$f_{i}$. Figure 3-1 illustrates the degeneration happened on FaceHo in which
the target domain is covered twice by the solution (see the middle panel),
starting with the boundary points set as (a) with $\rho=2\pi/\ell=2$ and
$\mu\leq 16$ is used. The required one-to-one property does not preserved in
this case, thought the average angle error is as small as the average error of
a good solution. This kind of degeneration disappears when we increase the
penalty parameter to $\mu=17$.

Figure 3-1: A phenomenon of degenerated solution on FaceHo: the disk is
covered twice by the solution of SDMCE with $\mu=15$, starting with boundary
points along the unit circle twice. The degeneration disappears when $\mu\geq
17$. Left: distribution of 1000 largest relative angle errors. Middle: partial
domain of the solution with $\mu=15$. Right: the distribution of distances
$\\{d_{i}\\}$ for checking the one-to-one.

The degeneration illustrated by the middle penal of Figure 3-1 will also
result in a positive discrete conformal energy ${\cal E}_{C}^{d}(f)\approx\pi$
since the discrete Dirichlet energy is computed twice, i.e., ${\cal
E}_{D}^{d}(f)\approx 2\pi$. Meanwhile, the area deviation
$\epsilon_{A}(f)=\pi-A(f)\approx-\pi$. Similar phenomenon happens for multiple
times of repeated covering. Hence, it is easy to check this kind of
degeneration using ${\cal E}_{C}^{d}(f)$ or $\epsilon_{A}(f)$.

The algorithm for adaptively tuning $\mu$ works well and is also stable for
starting boundary points. Notice that there are not big additional costs for
turning $\mu$.

  * •

It is not required to modify the Laplacian matrix $L$ or the Schur complement
$S$ that is the main cost in solving (3.7).

  * •

As soon as $\mu$ is updated, it is required to apply the NCG again. Since
(3.7) is very stable on $\mu$, the solution corresponding to the previous
$\mu$ is a very good starting point for reapplying the NCG. That means, the
NCG convergs quickly within few of iterations.

  * •

The iteration of turning $\mu$ terminates quickly on most of the tested data
sets. Only on CowboyHat, the turning number is larger than that on other data
sets, but the additional cost is ignorable.

Table 3-3 shows the results of SDMCE with adaptively chosen $\mu$, when the
starting points are equally distributed with correct ordering or randomly
chosen with completely wrong ordering.

Data | Equally distributed initial points | Randomly chosen initial points
---|---|---
$\mu$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{A}(f)$ | $\epsilon_{\theta}(f)$ | Time(s) | $\mu$ | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{A}(f)$ | $\epsilon_{\theta}(f)$ | Time(s)
BimbaStatue | 0 | 9.64e-04 | 6.40e-05 | 6.23e-03 | 21.73 | 20 | 9.50e-04 | 6.73e-05 | 6.23e-03 | 24.57
Buddha | 0 | 6.60e-04 | 2.67e-05 | 4.97e-03 | 118.16 | 20 | 6.68e-04 | 3.04e-05 | 4.98e-03 | 160.60
CCH | 0 | 5.42e-03 | 3.23e-04 | 1.16e-02 | 10.34 | 20 | 5.41e-03 | 2.96e-04 | 1.16e-02 | 10.99
CHLin1 | 10 | 6.98e-03 | 3.03e-04 | 1.30e-02 | 7.84 | 20 | 6.95e-03 | 2.80e-04 | 1.30e-02 | 13.13
CYHo | 10 | 4.40e-04 | 5.06e-05 | 4.84e-03 | 5.84 | 270 | 1.99e-05 | 1.68e-03 | 6.79e-03 | 14.24
CYHo15 | 10 | 5.55e-04 | 4.57e-05 | 5.36e-03 | 5.99 | 270 | 2.13e-04 | 1.56e-03 | 7.21e-03 | 12.66
CYHo22 | 10 | 1.22e-02 | 9.20e-04 | 1.87e-02 | 10.33 | 20 | 1.22e-02 | 9.55e-04 | 1.86e-02 | 7.08
CYHo23 | 0 | 2.51e-02 | 7.21e-05 | 1.93e-02 | 6.43 | 10 | 1.89e-02 | 4.16e-04 | 1.97e-02 | 7.60
CYHo31 | 0 | 2.09e-02 | 7.30e-05 | 1.90e-02 | 7.20 | 90 | 1.28e-02 | 5.50e-03 | 2.17e-02 | 14.78
ChineseLion | 10 | 1.31e-02 | 7.57e-04 | 2.50e-02 | 0.56 | 20 | 1.31e-02 | 7.67e-04 | 2.50e-02 | 0.81
CowboyHat | 3577 | 1.83e-05 | 9.13e-03 | 3.44e-02 | 0.08 | 3568 | 1.26e-05 | 9.13e-03 | 3.44e-02 | 0.14
Dress | 10 | 6.40e-02 | 1.16e-02 | 6.10e-02 | 0.06 | 20 | 6.40e-02 | 1.16e-02 | 6.10e-02 | 0.06
Ear | 10 | 6.99e-02 | 6.78e-02 | 1.04e-01 | 0.02 | 10 | 6.98e-02 | 6.79e-02 | 1.04e-01 | 0.02
Face | 0 | 1.36e-02 | 9.31e-05 | 3.21e-02 | 19.28 | 20 | 1.36e-02 | 1.01e-04 | 3.21e-02 | 19.38
FaceHo | 10 | 1.18e-04 | 2.03e-05 | 2.66e-03 | 10.93 | 20 | 1.31e-04 | 1.39e-04 | 4.07e-03 | 24.02
FaceLin | 0 | 9.27e-04 | 1.98e-05 | 3.31e-03 | 20.53 | 180 | 1.30e-03 | 2.43e-03 | 5.70e-03 | 40.16
Femur | 70 | 2.07e-03 | 4.61e-03 | 1.63e-02 | 0.58 | 70 | 2.07e-03 | 4.59e-03 | 1.63e-02 | 0.53
Foot | 210 | 5.22e-04 | 1.11e-02 | 2.52e-02 | 0.21 | 210 | 5.23e-04 | 1.11e-02 | 2.52e-02 | 0.20
Hand | 150 | 6.34e-03 | 3.10e-03 | 2.08e-02 | 3.26 | 110 | 5.99e-03 | 3.90e-03 | 2.08e-02 | 2.79
HumanBrain | 40 | 1.69e-02 | 3.57e-03 | 2.59e-02 | 1.35 | 40 | 1.69e-02 | 3.59e-03 | 2.59e-02 | 1.20
KnitCapMan | 10 | 5.17e-03 | 4.84e-04 | 9.48e-03 | 2.43 | 50 | 5.17e-03 | 4.88e-04 | 9.48e-03 | 2.94
LCH | 10 | 6.98e-03 | 3.03e-04 | 1.30e-02 | 8.15 | 10 | 6.94e-03 | 2.91e-04 | 1.30e-02 | 9.57
LeftHand | 130 | 5.50e-03 | 3.17e-03 | 2.06e-02 | 2.87 | 70 | 4.81e-03 | 5.04e-03 | 2.07e-02 | 2.69
MaxPlanckD | 10 | 7.22e-03 | 6.74e-04 | 1.05e-02 | 1.19 | 10 | 7.21e-03 | 6.79e-04 | 1.05e-02 | 1.34
Nefertiti | 100 | 2.92e-04 | 2.71e-02 | 4.67e-02 | 0.03 | 100 | 2.92e-04 | 2.71e-02 | 4.67e-02 | 0.04
NefertitiStatue | 0 | 1.67e-03 | 4.99e-05 | 5.53e-03 | 330.47 | 10 | 1.68e-03 | 4.96e-05 | 5.53e-03 | 402.01
StanfordBunny | 10 | 1.59e-02 | 8.37e-04 | 1.91e-02 | 3.24 | 20 | 1.59e-02 | 8.36e-04 | 1.91e-02 | 1.43
StanfordBunny2 | 0 | 8.87e-03 | 6.82e-04 | 1.84e-02 | 1.73 | 20 | 8.87e-03 | 6.95e-04 | 1.84e-02 | 5.20
Table 3-3: Comparison of SDMCE with adaptively chosen $\mu$, starting with
boundary points equally distributed in the correct ordering (left half) or
randomly chosen in a wrong ordering (right half).

##  4 Folding free

Given a solution $\\{f_{\ell}\\}$, folding happens on the solution if there is
at least a triangle $F_{ijk}$ of $\\{f_{\ell}\\}$ contains a vertex $f_{\ell}$
differ from the vertices of $F_{ijk}$. It contains the special case when a
triangle folds over a boundary edge. That is, the mapping $f_{\ell}$ of an
interior vertex $v_{\ell}$ appears out of the boundary formed by the boundary
points $f_{\Gamma}$.

We consider two kinds of folding for the unit disk: boundary folding and
triangle folding. By boundary folding, we mean that the central angle
$t_{i+1}$ of the boundary vertex $f_{j_{i+1}}$ is smaller than the central
angle $t_{i}$ of $f_{j_{i}}$ within mod $2\pi$. The triangle folding includes
interior triangle folding and boundary triangle folding. By interior triangle
folding, we mean that an interior triangle $F_{ijk}$ has its vertices
$f_{i},f_{j},f_{k}$ in clockwise, that is, its algebra area
$\det\big{(}[f_{ji},f_{kj}]\big{)}$ is negative. The boundary triangle folding
is a bit complicated – it contains three cases:

  * (1)

A boundary triangle folds over its boundary edge, and the boundary vertices
are not folded. Hence, the algebra area is positive.

  * (2)

A boundary triangle does not fold over its boundary edge, but the boundary
vertices are folded. In this case, the algebra area is also positive.

  * (3)

A boundary triangle folds over its folded boundary edge – the algebra area is
positive.

The panel (a) of Figure 4-2 illustrates the three kinds of folding of boundary
triangles. Hence, when we account the number of folding triangles according to
the negativity of algebra areas, the boundary triangles folding over folded
boundary edges are lost.

The boundary folding can be addressed by optimization. In the next subsection,
we consider a modified version of (3.7) for addressing this kind of folding by
adding an adaptive penalty on the boundary points. However, the triangle
folding is hard to address via optimization methods. Generally, the triangle
folding mainly due to the ill-conditional coefficient matrix $A$ – relative
large computational error in $S$ or the inverse of $L_{\Gamma_{c},\Gamma_{c}}$
will result in perturbation of the interior points $f_{\Gamma_{c}}$. After the
next subsection, we will also show how to handle the interior folding
technically in the later part of this subsection when the boundary folding has
been addressed.

|
---|---
(a) | (b)
Figure 4-2: Efficiency illustration of boundary penalty. (a): Three kinds of
folded boundary triangles without penalty. (b): The first class (left) still
exists, the second one (middle) disappears, and the third one (right) becomes
to the first class when the penalty strategy is used.

###  4.1 Folding free for boundary vertices

Let $f_{\Gamma}=\\{f_{j_{i}}\\}$, where $f_{j_{i}}=(\cos t_{i},\sin t_{i})$
with the central angles $\\{t_{i}\\}$. We assume that original boundary
vertices $\\{v_{j_{i}}\\}$ are in anticlockwise order. If no folding happens
on $f_{\Gamma}$, each sector area with arc length of adjacent points
$f_{j_{i}}$ and $f_{j_{i-1}}$, say

$\frac{1}{2}\sin(t_{i}-t_{i-1})=\frac{1}{2}\big{(}\sin t_{i}\cos t_{i-1}-\cos
t_{i}\sin t_{i-1}\big{)}=f_{j_{i}}\Theta f_{j_{i-1}}^{\top}$

must be nonnegative, where $j_{0}=j_{|\Gamma|}$. Hence, a negative
$f_{j_{i}}\Theta f_{j_{i-1}}^{\top}$ means the folding on boundary vertices.
We add the penalty term

$\sum_{i=1}^{|\Gamma|}\alpha_{i}\max\\{-f_{j_{i}}\Theta
f_{j_{i-1}}^{\top},0\\}=\alpha^{\top}\max\big{\\{}{\rm
rdot}(D_{1}f_{\Gamma}\Theta,f_{\Gamma}),0\big{\\}}=\alpha^{\top}{\rm
rdot}(D_{1}f_{\Gamma}\Theta,f_{\Gamma})_{+}$

into (3.7), where $D_{1}=[e_{2},\dots,e_{|\Gamma|},e_{1}]$. It yields the
following regularization problem

$\displaystyle\min_{\|f_{i}\|_{2}=1,i\in\Gamma}\Big{\\{}\frac{1}{2}\langle
Sf_{\Gamma},f_{\Gamma}\rangle-\pi+\frac{\mu}{2}\big{(}\pi-\frac{1}{4}\langle
D_{2}f_{\Gamma}\Theta,f_{\Gamma}\rangle\big{)}^{2}+\alpha^{\top}{\rm
rdot}(D_{1}f_{\Gamma}\Theta,f_{\Gamma})_{+}\Big{\\}}.$ (4.1)

The NCG can also work well on solving the above problem. Since the main cost
is the computation of the Laplacian matrix $L$ and the Schur complement $S$,
the computational cost for solving (4.1) is similar as that for (3.7).

The penalty vector $\alpha$ is nonnegative and adaptively set during the
iteration of the algorithm solving this problem in the rule: Starting with
$\alpha=0$ with all zeros, if $f_{j_{i}}\Theta f_{j_{i-1}}^{\top}$ is
negative, we modify $\alpha_{i}:=\alpha_{i}+\delta$, where $\delta$ is a small
positive constant, say $\delta=\frac{|\Gamma|}{|\Gamma_{c}|}$. The penalty
action $\alpha_{i}$ disappears if $f_{j_{i}}\Theta f_{j_{i-1}}^{\top}$ becomes
to nonnegative.

Taking this strategy of setting $\alpha$, the penalty method (4.1) performs
very well on the five data sets on which the boundary folding happens. The
folding of boundary vertices disappears on all these data set. That is, the
second kind of folding boundary triangles disappears, and the third one
becomes to the first one. See the panel (b) of Figure 4-2 for the improvement.
Unfortunately, the interior triangle folding and/or the negative boundary
triangle folding still exist. The first two lines of Table 4-4 compare the
efficiency of the SDMCE using adaptive turning of $\mu$ on Face when the
penalty strategy is used or not. The total 44 folded boundary vertices are
corrected, but there are also folded triangles (23 interior triangles and 76
boundary triangles in the first kind).

Strategy | ${\cal E}_{C}^{d}(f)$ | $\epsilon_{A}(f)$ | $\epsilon_{\theta}(f)$ | Folded | Folded triangles in
---|---|---|---|---|---
bound. v | total | interior | 1st b. | 2nd b. | 3th b.
No | 1.36e-02 | 9.3116e-05 | 3.2052e-02 | 44 | 120 | 24 | 52 | 21 | 23
Boundary V | 1.36e-02 | 9.2971e-05 | 3.2052e-02 | 0 | 99 | 23 | 76 | 0 | 0
Boundary T | 1.36e-02 | 9.2971e-05 | 3.2644e-02 | 0 | 8 | 8 | 0 | 0 | 0
Interior T | 1.36e-02 | 9.2971e-05 | 3.2703e-02 | 0 | 0 | 0 | 0 | 0 | 0
Table 4-4: Efficiency of adaptive SDMCE with the strategies for folding free
on Face

###  4.2 Folding free for boundary triangles

As soon as the boundary folding is address, there is only the first kind of
folding of boundary triangles, though the number of this folded boundary
triangles is increased. In this subsection, we show how to address the
boundary triangle folding.

Let $T_{ijk}=\\{v_{i},v_{j},v_{k}\\}$ be a boundary triangle of ${\cal M}$
with boundary edgy $e_{jk}=(v_{j},v_{k})$, corresponding to the folded
boundary triangle of a given solution $\\{f_{\ell}\\}$. Let
$V_{i}=\\{v_{i_{\ell}}\\}$ be the adjacent neighboring vertices including the
boundary vertices $v_{j}$ and $v_{k}$. We estimate the weights
$\\{w_{i\ell}\\}$ of $v_{i}$ in an approximate convex combination in terms of
its adjacent neighbors by solving

$\displaystyle\min_{\\{w_{i\ell}\\}}\Big{\|}v_{i}-\sum_{\ell:v_{\ell}\in
V_{i}}w_{i\ell}v_{i_{\ell}}\Big{\|}_{2},\quad{\rm s.t.}\quad w_{i\ell}\geq 0,\
\sum_{\ell:v_{\ell}\in V_{i}}w_{i\ell}=1.$ (4.2)

It is not difficult to solve this problem. As soon as the solution
$w_{i}=\\{w_{i\ell}\\}$ is available, $f_{i}$ is updated by

$\displaystyle f_{i}:=\sum_{\ell:v_{\ell}\in V_{i}}w_{i\ell}f_{i_{\ell}}.$
(4.3)

The updating rule (4.3) based on (4.2) for all first kind of folded boundary
triangles can easily be addressed. Due to the correction on this kind of
boundary triangles, some folded interior triangles connected with the
corrected vertices are also corrected simultaneously. For instance, the 76
folded boundary triangles in the first kind are corrected, and meanwhile,
there are 15 interior triangles are also unfolded. This is an interesting
advantage of the above approach for unfolding boundary triangles.

###  4.3 Folding free for interior triangles

The problem of unfording interior triangles is a bit complicated, compared
with that for boundary triangles, since (1) it is not clear which vertex of
the folded interior triangle results in the folding, and (2) folded vertices
of some folded interior triangles may be connected with each others.

Let $T_{ijk}=\\{v_{i},v_{j},v_{k}\\}$ be a interior triangle of ${\cal M}$
corresponding to a folded interior triangle of a given solution
$\\{f_{\ell}\\}$. Let $V_{i}^{\prime}=\\{v_{i_{\ell}}\\}$
$V_{j}^{\prime}=\\{v_{j_{\ell}}\\}$ and $V_{k}^{\prime}=\\{v_{k_{\ell}}\\}$ be
the adjacent neighboring vertices, not including the vertices $v_{i}$,
$v_{j}$, and $v_{k}$. As in the above subsection, we can obtain the weight
vectors $w_{i}=(w_{i}^{\prime},w_{ij},w_{ik})$,
$w_{j}=(w_{j}^{\prime},w_{jk},w_{ji})$, and
$w_{k}=(w_{k}^{\prime},w_{ki},w_{kj})$, each solves a similar minimization
problem as (4.2) for representing $v_{i}$, $v_{j}$, and $v_{k}$, in terms of
their connected neighbors. Hence, we have

$\left[\begin{array}[]{ccc}1&-w_{ij}&-w_{ik}\\\ -w_{ji}&1&-w_{jk}\\\
-w_{ki}&-w_{kj}&1\end{array}\right]\left(\begin{array}[]{c}v_{i}\\\ v_{j}\\\
v_{k}\end{array}\right)\approx\left[\begin{array}[]{c}w_{i}^{\prime}V_{i}^{\prime}\\\
w_{j}^{\prime}V_{j}^{\prime}\\\
w_{k}^{\prime}V_{k}^{\prime}\end{array}\right].$

We unfold the folded interior triangle $F_{ijk}=\\{f_{i},f_{j}.f_{k}\\}$ by
updating it to

$\displaystyle\left(\begin{array}[]{c}f_{i}\\\ f_{j}\\\
f_{k}\end{array}\right)=\left[\begin{array}[]{ccc}1&-w_{ij}&-w_{ik}\\\
-w_{ji}&1&-w_{jk}\\\
-w_{ki}&-w_{kj}&1\end{array}\right]^{-1}\left[\begin{array}[]{c}w_{i}^{\prime}F_{i}^{\prime}\\\
w_{j}^{\prime}F_{j}^{\prime}\\\
w_{k}^{\prime}F_{k}^{\prime}\end{array}\right],$ (4.13)

where $F_{i}^{\prime}$, $F_{j}^{\prime}$, and $F_{k}^{\prime}$ are the
connected neighbors of $F_{ijk}$ as $V_{i}^{\prime}$, $V_{j}^{\prime}$, and
$V_{k}^{\prime}$.

Algorithm 2 SDMCE for disk parameterization of open surfaces

0: vertices $\\{v_{i}\\}$, indices $T=\\{T_{ijk}\\}$ of triangles, initial

1: Determine index set $\Gamma$ of boundary vertices, initially set
$f_{\Gamma}$, $\alpha_{i}=0$, $c=|\Gamma|/|T|$.

2: Construct the Laplace matrix $L$ and the Schur complement $S$.

3: Apply Algorithm 1 to determine $\mu$ and a solution $\\{f_{i}\\}$.

4: while boundary vertex folding happens do

5: Update $\alpha_{i}:=\alpha_{i}+c$ for folded boundary vertices, and solve
(4.1) starting with the current $\\{f_{i}\\}$.

6: end while

7: while boundary triangle folding happens do

8: Solve (4.2) and update each interior vertex of the triangles.

9: end while

10: while interior triangle folding happens do

11: Compute the weight vectors $w_{i},w_{j},w_{k}$ by solving (4.2) and update
each folded triangle as (4.13).

12: end while

Applying the updating rule on all the folded interior triangles, these
triangles are unfolded generally. Since the modification on the vertices of
the folded interior triangles may slightly lead to folding of connected
triangles, or partial of the interior triangles are not completely unfolded
via one step of the unfolding, we might repeat this approach on the remaining
folded triangles. For instance, this approach can unfold all the 8 interior
triangles, however, three newly folded interior triangles appear. Applying
(4.13) on these three interior triangles, no other folding appears. The last
row of Table 4-4 shows the result when the (4.13) is applied twice on Face.

##  5 Numerical experiments and comparisons

In this section we will show the numerical behaviors of the algorithm SDMCE,
and compare it with algorithms FDCP [16], LDCP [19], and CCEM [21] on 28 real-
world data sets listed in Table LABEL:tab:. The SMDCE model is solved via the
modified NCG given in []. We use the relative angle change of each interior
angle $\\{\theta_{\ell}^{v}\\}$ of triangles

$\displaystyle\epsilon_{\theta_{\ell}}(f)=\frac{|\theta_{\ell}^{v}-\theta_{\ell}^{f}|}{\theta_{\ell}^{v}}$
(5.1)

to measure the angel preserving, where each angle $\theta_{\ell}^{v}$ is
measured in the anticlockwise order of the original triangle
$V_{ijk}=\\{v_{i},v_{j},v_{k}\\}$, and so does $\theta_{\ell}^{f}$ of the
transformed triangle $F_{ijk}=\\{f_{i},f_{j},f_{k}\\}$. The mean of all the
relative angle errors is denoted as $\epsilon_{\theta}(f)$. We will also use
the discrete conformal energy on the unit disk

$\displaystyle{\cal E}_{C}^{d}(f)={\cal E}_{D}^{d}(f)-{\cal
A}^{*}=\frac{1}{2}\langle Lf,f\rangle-\pi$ (5.2)

to measure the approximation of discrete conformal energy of the solution to
the minimal conformal energy for the ideal conformal transformation. Clearly,
the error (5.2) can also be used to measure the approximation error of
discrete Dirichlent energy ${\cal E}_{D}^{d}(f)$ to the continuous Dirichlet
energy ${\cal E}_{D}(f)={\cal A}^{*}$ for the ideal conformal transformation,

${\cal E}_{D}^{d}(f)-{\cal E}_{D}(f)={\cal E}_{D}^{d}(f)-{\cal A}^{*}.$

Here we do not take the absolute value for the approximation error since as we
show later, a negative error ${\cal E}_{C}^{d}(f)$ implies a solution not good
enough for preserving angles. We do not use an estimate area of ${\cal A}^{*}$
in a discretion of conformal energy such as the commonly used error ${\cal
E}_{D}^{d}(f)-A(f)$ in the literature since such an estimate area $A(f)$
depends on a solution and may result in a small ${\cal E}_{D}^{d}(f)-A(f)$ for
a degenerate solution $f$.

###  5.1 Efficiency of the penalty model

###  5.2 Stability of SDMCE

We first show the performance of the SDMCE on angel preserving

At first, the In our experiments on 28 real world data sets, starting with
equal-distantly distributed boundary points on the unit circle for each
example, the NCG can give an good solution within a time slightly less than
the time of CCEM, due to the penalty to the area deviation of solutions. Table
3-1 shows the discrete conformal energy ${\cal E}_{C}^{d}(f)$ defined as
(5.2), the mean of relative angle errors $\epsilon_{\theta}(f)$, and the
computational time for each of the 28 data sets, using the same $\mu=10$.

###  5.3 Efficiency of the folding-free technique

###  5.4 Comparisons

In this subsection we show the comparisons of the SDMCE with the algorithms
FDCP [16], LDCP [19], and CCEM [21] on all the 28 data sets. Below we briefly
describe these three algorithms.

The CCEM solves (3.2) subject to $\|f_{i}\|^{2}=1$ for boundary vertices by
the quasi-Newton method. It was shown in [21] that for a local minimal
solution of this constrained problem, the exact separation of boundary points
is satisfied. And hence, the separation restriction is released in
computation. It is clear that a set of $\\{f_{i}\\}$ degenerating to a single
point is an optimal solution of (3.2) since the discrete conformal energy
defined by (3.1) is zero. To avoiding degeneration, a good initial solution is
required.

Different from the CCEM for a conformal mapping directly, both the FDCP and
LDCF look for a conformal $f=g_{2}\circ g_{1}$ via two quasi-conformal
mappings $g_{1}:{\cal M}\to D$ and $g_{2}:D\to D$, and boundary-to-boundary,
such that $g_{1}^{-1}$ and $g$ have equal Beltrami coefficients [15, Theorem
1], i.e., both $g_{1}^{-1}$ and $g_{2}$ satisfy the Beltrami equation

$\displaystyle\frac{\partial g_{1}^{-1}}{\partial\bar{z}}=b(z)\frac{\partial
g_{1}^{-1}}{\partial z},\quad\frac{\partial
g_{2}}{\partial\bar{z}}=b(z)\frac{\partial g_{2}}{\partial z},\quad
g_{2}\big{|}_{\partial D}=\partial D,$ (5.3)

where the 2D variable $(x,y)$ is taken as a complex variable $z=x+iy$. Since
the $g_{1}$ could be arbitrarily chosen, the key is to solve the Beltrami
equation for $g_{2}$ given the Beltrami coefficient $b(z)=\frac{\partial
g_{1}^{-1}}{\partial\bar{z}}/\frac{\partial g_{1}^{-1}}{\partial z}$ of
$g_{1}^{-1}$. However, the nonlinear boundary restriction
$g_{2}\big{|}_{\partial D}=\partial D$ increases the difficulty of solving.

The FDCP and LDCP take different strategies to address the difficulty.
Basically, FDCP iteratively determines $g_{2}$ given $g_{1}$. It takes Cayley
transformation $c(z)=i\frac{1+z}{1-z}$ to linearize the boundary restriction,
which keeps the Beltrami equation unchanged, and uses the reflection $z\to
1/\bar{z}$, centralization, and normalization for correcting the solution
nearby the pole point $(1,0)$ of Cayley transformation. LDCP looks for an
approximately conformal $g_{1}$ and modifies the boundary condition to
$g_{2}\big{|}_{\partial D}=g_{1}\big{|}_{\partial{\cal M}}$ for simplicity.
Here $g_{1}$ is obtained by applying the couple-quasi-conformal method for
conformally mapping a genus-0 closed surface to the unit sphere ${\cal S}^{2}$
[15], copying the open surface to form a required genus-0 closed surface. The
similar difficulty from the restriction is address via the stereographic
projection, and using Möbius transformation and normalization for correction.
Though the normalization on the boundary points can obey the strict boundary
restriction, it may result in folding of boundary triangles.

By the way, the CCEM solves a inhomogeneous Laplace-Beltrami equation with a
right-hand function for an initial solution. Both FDCP and LDCP solve a
homogeneous Laplace-Beltrami equation – with a restriction on boundary points
whose distribution of arc length angles equal to the boundary vertices for the
open surface in FDCP. The SDMCE simply uses an initial solution with equal-
distance distributed arc length angles of boundary points.

Figure 5-3: Comparisons of the algorithms SDMCE, FDCP, LDCP, and CCEM on the
28 data sets. From top to bottom: discrete conformal energy, average value of
relative angle errors, computation time in log, and average value of Beltrami
coefficient.

Figure 5-3 shows the comparisons of the algorithms SDMCE, FDCP, LDCP, and CCEM
on discrete conformal energy, average value of relative angle errors, and
computational time of the computed solution on the 28 data sets. The SDMCE
provides a competitive result on each of the tested data sets. The FDCP, LDCP,
and CCEM give negative discrete conformal energies on CowboyHat, Foot,
Nefertiti with the identity number 11, 18, and 25, respectively. The SDMCE
costs much time than the LDCP and CCEM on the two largest data sets Buddha and
NefertitiStatue since it uses the explicit version of the Schur matrix $S$.
Using the implicit form of $S$, the SDMCE costs the same as the CCEM.

We also compare the mean of Beltrami coefficient of solutions since the
Beltrami coefficient of a conformal mapping should be zero. The FDCP or LDCP
could be taken as an iterative method for minimizing the Beltrami coefficient
of the compound function $g_{2}\circ g_{1}$. It is interesting that the mean
of Beltrami coefficient is approximately equal to the mean of relative angle
errors, though they are different. See Figure 5-4 for the difference on
solutions of the four algorithms, where the Beltrami coefficient function is
plotted corresponding to the sorted relative angle errors.

Figure 5-4: Sorted relative angle errors and the corresponding Distribution of
Beltrami coefficient function of the four solutions on the data set CYHo.

##  6 Conclusions

## References

  * [1] B.T. Polyak “The conjugate gradient method in extremal problems” In _USSR Computational Mathematics and Mathematical Physics_ 9.4, 1969, pp. 94–112 DOI: https://doi.org/10.1016/0041-5553(69)90035-4
  * [2] Thomas F. Coleman and Yuying Li “An Interior Trust Region Approach for Nonlinear Minimization Subject to Bounds” In _SIAM Journal on Optimization_ 6.2, 1996, pp. 418–445 DOI: 10.1137/0806023
  * [3] Steven Haker et al. “Conformal surface parameterization for texture mapping” In _IEEE Transactions on Visualization and Computer Graphics_ 6.2, 2000, pp. 181–189 DOI: 10.1109/2945.856998
  * [4] Kai Hormann “MIPS: An efficient global parametrization method” In _ACM Press/Addison-Wesley Publishing Co_ , 2000
  * [5] Alla Sheffer and Eric Sturler “Parameterization of faceted surfaces for meshing using angle-based flattening” In _Engineering with Computers_ 17.3, 2001, pp. 326–337 DOI: 10.1007/PL00013391
  * [6] Lévy Bruno, Petitjean Sylvain, Ray Nicolas and Maillot Jérome “Least Squares Conformal Maps for Automatic Texture Atlas Generation” In _ACM Transactions on Graphics_ 21.3, 2002, pp. 362–371 DOI: 10.1145/566654.566590
  * [7] Mathieu Desbrun, Mark Meyer and Pierre Alliez “Intrinsic parameterizations of surface meshes” In _Computer Graphics Forum_ 21.3, 2002, pp. 209–218 DOI: 10.1111/1467-8659.00580
  * [8] Xianfeng Gu et al. “Genus zero surface conformal mapping and its application to brain surface mapping” In _IEEE Transactions on Medical Imaging_ 23.8, 2004, pp. 949–958 DOI: 10.1109/TMI.2004.831226
  * [9] Michael S. Floater and Kai Hormann “Surface Parameterization: a Tutorial and Survey” In _Advances in Multiresolution for Geometric Modelling_ Springer Berlin Heidelberg, 2005, pp. 157–186 DOI: 10.1007/3-540-26808-1˙9
  * [10] Alla Sheffer, Bruno Lévy, Maxim Mogilnitsky and Alexander Bogomyakov “ABF++: Fast and robust angle based flattening” In _ACM Transactions on Graphics_ 24.2, 2005, pp. 311–330 DOI: 10.1145/1061347.1061354
  * [11] Gaohang Yu and L utai Guan “Modified PRP methods with sufficient descent property and their convergence properties” In _Acta Scientiarum Naturalium Universitatis Sunyatseni (Chinese)_ 45.4, 2006, pp. 11–14
  * [12] Miao Jin, Junho Kim, Feng Luo and Xianfeng Gu “Discrete surface Ricci flow” In _IEEE Transactions on Visualization and Computer Graphics_ 14.5, 2008, pp. 1030–1043 DOI: 10.1109/TVCG.2008.57
  * [13] Patrick Mullen, Yiying Tong, Pierre Alliez and Mathieu Desbrun “Spectral conformal parameterization” In _Computer Graphics Forum_ 27.5, 2008, pp. 1487–1494
  * [14] Yong-Liang Yang et al. “Generalized Discrete Ricci Flow” In _Computer Graphics Forum_ 28.7, 2009, pp. 2005–2014 DOI: 10.1111/j.1467-8659.2009.01579.x
  * [15] Pui Tung Choi, Ka Chun Lam and Lok Ming Lui “FLASH: Fast Landmark Aligned Spherical Harmonic Parameterization for Genus-0 Closed Brain Surfaces” In _SIAM Journal on Imaging Sciences_ 8.1, 2015, pp. 67–94 DOI: 10.1137/130950008
  * [16] Pui Tung Choi and Lok Ming Lui “Fast Disk Conformal Parameterization of Simply-Connected Open Surfaces” In _Journal of Scientific Computing_ 65.3, 2015, pp. 1065–1090 DOI: 10.1007/s10915-015-9998-2
  * [17] Xin Fan et al. “Image morphing with conformal welding” In _The Visual Computer_ 32.9, 2015, pp. 1191–1203 DOI: 10.1007/s00371-015-1188-6
  * [18] Mei-Heng Yueh, Wen-Wei Lin, Chin-Tien Wu and Shing-Tung Yau “An Efficient Energy Minimization for Conformal Parameterizations” In _Journal of Scientific Computing_ 73.1, 2017, pp. 203–227 DOI: 10.1007/s10915-017-0414-y
  * [19] Gary Pui-Tung Choi and Lok Ming Lui “A linear formulation for disk conformal parameterization of simply-connected open surfaces” In _Advances in Computational Mathematics_ 44.1, 2018, pp. 87–114 DOI: 10.1007/s10444-017-9536-x
  * [20] Maedeh Sadat Mirazimi and Arash Kiyoumarsi “Magnetic Field Analysis of SynRel and PMASynRel Machines With Hyperbolic Flux Barriers Using Conformal Mapping” In _IEEE Transactions on Transportation Electrification_ 6.1, 2020, pp. 52–61 DOI: 10.1109/TTE.2019.2959400
  * [21] Yueh-Cheng Kuo, Wen-Wei Lin, Mei-Heng Yueh and Shing-Tung Yau “Convergent Conformal Energy Minimization for the Computation of Disk Parameterizations” In _SIAM Journal on Imaging Sciences_ 14.4, 2021, pp. 1790–1815 DOI: 10.1137/21M1415443