Convergence theory of the conformal energy minimization boundary iteration for disk conformal parameterizations

The conformal energy minimization (CEM) algorithm of Yueh, Lin, Wu, and Yau (2017) computes conformal parameterizations of simply connected open triangulated surfaces onto the unit disk by alternately extending the boundary values to the interior by a discrete harmonic map and updating the boundary values by a nonlinear fixed-point map: solving a linear system involving blocks of the cotangent Laplacian, then centralizing and radially normalizing the result onto the unit circle. For well-conditioned Delaunay meshes the paper proves that the boundary iterates possess a nontrivial accumulation point, and it observes numerically, without proof, that a practically important modified update decreases the conformal energy monotonically. It leaves open whether the iterates actually converge, whether the limit is unique, at what rate, and how the iteration behaves when the mesh hypotheses fail. Later work supplies provably convergent alternative algorithms for the same energy (a line-search gradient descent, CCEM, 2021; a penalty-based stable minimization, 2022), and convergence has been proved only for modified algorithms in neighboring spherical settings; a 2023 paper by the same research community still states that strict convergence proofs for the CEM family are lacking. The open problem is the missing convergence theory of the original CEM boundary iteration itself: convergence versus mere accumulation of subsequences, uniqueness of the limiting boundary map, convergence rate, monotonicity of the modified update, and well-definedness and convergence on meshes violating the stated hypotheses.

Background

A surface parameterization maps a surface onto a planar domain so that geometry-processing tasks such as remeshing, texture mapping, and registration can be carried out in two dimensions. A conformal parameterization is one that preserves angles, and hence local shape; by the classical uniformization theorem, every simply connected open surface (a surface topologically equivalent to a disk) admits a conformal map onto the planar unit disk. Computing such maps numerically on triangulated surface meshes is a basic problem of digital geometry processing and computational conformal geometry.

In the discrete setting the surface is a triangular mesh $M$ with $n$ vertices and the unknown is a complex vector $\mathbf{f}\in\mathbb{C}^n$ assigning planar coordinates to the vertices. The standard discrete surrogate of conformality is the conformal energy

$$\mathcal{E}_C(\mathbf{f}) \;=\; \mathcal{E}_D(\mathbf{f}) \;-\; \mathcal{A}(\mathbf{f}),$$

where $\mathcal{E}_D(\mathbf{f})=\tfrac{1}{2}\mathbf{f}^{*}L\mathbf{f}$ is the discrete Dirichlet energy (the standard discrete analogue of the integral of the squared gradient of the map), $L$ is the cotangent Laplacian, i.e. the stiffness matrix whose off-diagonal weight on an edge $[i,j]$ is $-\tfrac{1}{2}(\cot\alpha_{ij}+\cot\alpha_{ji})$ with $\alpha_{ij},\alpha_{ji}$ the two angles opposite that edge, and $\mathcal{A}(\mathbf{f})$ is the signed area of the planar image. One always has $\mathcal{E}_C\ge 0$, with equality exactly at conformal maps. For a disk map the boundary vertices must lie on the unit circle, while for fixed boundary values the energy is minimized when the interior vertices solve a discrete Laplace equation; the resulting interior map is called the discrete harmonic extension of the boundary map. The central difficulty is that the harmonic extension is determined only after the boundary map is chosen, and selecting the boundary map that makes the composite map conformal is a nonlinear problem.

Yueh, Lin, Wu, and Yau (2017) proposed the conformal energy minimization (CEM) algorithm for this problem. Writing $\mathrm{i}$ and $\mathrm{b}$ for the interior and boundary index sets and block-partitioning

$$L \;=\; \begin{bmatrix} L_{\mathrm{i,i}} & L_{\mathrm{i,b}} \\ L_{\mathrm{i,b}}^{\top} & L_{\mathrm{b,b}} \end{bmatrix},$$

the algorithm fixes the interior by the harmonic extension $\mathbf{f}_{\mathrm{i}}=-L_{\mathrm{i,i}}^{-1}L_{\mathrm{i,b}}\mathbf{f}_{\mathrm{b}}$ and updates the boundary by solving a linear system, then centralizing the result (subtracting the mean via $C=I-\mathbf{1}\mathbf{1}^{\top}/n_{\mathrm{b}}$, where $\mathbf{1}$ is the all-ones vector and $n_{\mathrm{b}}$ is the number of boundary vertices) and radially normalizing it (dividing each entry by its modulus, so that every boundary vertex lands on the unit circle). The resulting boundary iteration, Eq. (26) of the paper, is

$$\mathbf{f}_{\mathrm{b}}^{(k+1)} \;=\; \big(N_{\mathrm{b}}^{(k)}\big)^{-1}\, C\, K\, \mathbf{f}_{\mathrm{b}}^{(k)}, \qquad K \;=\; L_{\mathrm{b,b}}^{-1} L_{\mathrm{i,b}}^{\top} L_{\mathrm{i,i}}^{-1} L_{\mathrm{i,b}},$$

with normalization matrix $N_{\mathrm{b}}^{(k)}=\mathrm{diag}(|CK\mathbf{f}_{\mathrm{b}}^{(k)}|)$. A practically important modification, Eq. (30) of the paper, replaces the boundary right-hand side $-L_{\mathrm{b,i}}\mathbf{f}_{\mathrm{i}}^{(k)}$ by $-L_{\mathrm{b,i}}\big(\mathrm{diag}(|\mathbf{f}_{\mathrm{i}}^{(k)}|)\big)^{-2}\mathbf{f}_{\mathrm{i}}^{(k)}$ before centralization and normalization; on the test meshes of the paper this modified iteration decreases the conformal energy monotonically, and later work by the same group reports that it typically converges in fewer than twenty steps, but no proof of either behavior is given.

The theory of the paper covers the well-conditioned case. Definition 1 of the paper assumes a Delaunay triangulation (no mesh vertex lies inside the circumcircle of any triangle, a condition that makes all cotangent weights nonnegative), that the mesh and its interior and boundary subgraphs are connected, and that every boundary vertex is adjacent to an interior vertex. Under these hypotheses $L$ is an M-matrix (a positive semidefinite matrix with nonpositive off-diagonal entries) and $K$ is a strictly positive matrix with spectral radius $\rho(K)=1$ (the spectral radius being the largest modulus of the eigenvalues), the eigenvalue $1$ being simple; this is a Perron-Frobenius-type statement, Perron-Frobenius theory being the spectral theory of entrywise positive matrices. Consequently $K$ maps every complex vector to a vector whose entries are convex combinations of the original entries. The main convergence-type result, Theorem 3 of the paper, assumes additionally that $\mathrm{rank}(K)\ge 3$ and that the initial boundary map is nonconstant, and proves that the sequence $\{\mathbf{f}_{\mathrm{b}}^{(k)}\}$ has a nontrivial accumulation point, i.e. a limit of some subsequence, which exists by a Bolzano-Weierstrass compactness argument because all iterates lie on the unit circle; the limit boundary map is nonconstant, hence nondegenerate.

What the paper does not establish is everything between an accumulation point and a usable guarantee: whether the full sequence converges; whether the limiting boundary map is unique, i.e. independent of the initial guess; how fast convergence takes place; whether the observed energy monotonicity of the modified iteration is a theorem; and what happens on meshes violating the hypotheses, where negative cotangent weights destroy the M-matrix structure on which the positivity of $K$ rests. These gaps are the subject of the problem stated below. They remain live even though the same research group later introduced a different, provably convergent algorithm for the same energy, CCEM, a line-search gradient descent (a descent method whose step size is chosen by minimizing the objective along the search direction) with a quadratic step-size model, proved globally convergent by Kuo, Lin, Yueh, and Yau (2021); even though Zhang and Tan (2022) proved a mesh-refinement consistency result for the discrete conformal energy minimizer; and even though convergence has been established for modified algorithms in neighboring settings, namely for spherical (genus-zero closed) conformal parameterizations by Liao, Huang, Lin, and Yueh (2024) and for spherical equiareal (area-preserving) parameterizations by Huang, Liao, and Lin (2022). None of these analyzes the original disk CEM boundary iteration, and Lin, Li, Lin, and Huang (2023) still state in print that strict convergence proofs for the CEM family, namely CEM together with its stretch-energy and volumetric stretch-energy siblings SEM and VSEM (which minimize alternative energies by the same fixed-point pattern), are lacking and under investigation.

Problem Statement

Let $M$ be a simply connected open triangular mesh whose triangulation is Delaunay and which satisfies the well-conditioned-mesh conditions of Definition 1 of Yueh-Lin-Wu-Yau (2017): the mesh, its interior subgraph, and its boundary subgraph are connected, and every boundary vertex is adjacent to at least one interior vertex. Let $L$ be the cotangent Laplacian, block-partitioned into interior ($\mathrm{i}$) and boundary ($\mathrm{b}$) index sets, let

$$K \;=\; L_{\mathrm{b,b}}^{-1} L_{\mathrm{i,b}}^{\top} L_{\mathrm{i,i}}^{-1} L_{\mathrm{i,b}}, \qquad C \;=\; I - \mathbf{1}\mathbf{1}^{\top}/n_{\mathrm{b}},$$

where $\mathbf{1}$ is the all-ones vector and $n_{\mathrm{b}}$ the number of boundary vertices, and let the CEM boundary iteration be

$$\mathbf{f}_{\mathrm{b}}^{(k+1)} \;=\; \big(N_{\mathrm{b}}^{(k)}\big)^{-1} C K \mathbf{f}_{\mathrm{b}}^{(k)}, \qquad N_{\mathrm{b}}^{(k)} \;=\; \mathrm{diag}\big(|C K \mathbf{f}_{\mathrm{b}}^{(k)}|\big),$$

with the interior given by the harmonic extension $\mathbf{f}_{\mathrm{i}}^{(k)}=-L_{\mathrm{i,i}}^{-1}L_{\mathrm{i,b}}\mathbf{f}_{\mathrm{b}}^{(k)}$. Let the modified update (Eq. (30) of the paper) be the variant in which the boundary right-hand side $-L_{\mathrm{b,i}}\mathbf{f}_{\mathrm{i}}^{(k)}$ is replaced by $-L_{\mathrm{b,i}}\big(\mathrm{diag}(|\mathbf{f}_{\mathrm{i}}^{(k)}|)\big)^{-2}\mathbf{f}_{\mathrm{i}}^{(k)}$ before centralization and normalization. What is known: $K$ is strictly positive with $\rho(K)=1$ and simple eigenvalue $1$, and under $\mathrm{rank}(K)\ge 3$ and nonconstant $\mathbf{f}_{\mathrm{b}}^{(0)}$ the sequence $\{\mathbf{f}_{\mathrm{b}}^{(k)}\}$ has a nontrivial accumulation point (Theorem 3 of the paper).

Establish the convergence theory of this iteration. Each component may be answered positively by proof or negatively by an explicit counterexample:

1. (Convergence) Does $\{\mathbf{f}_{\mathrm{b}}^{(k)}\}$ converge, not merely possess accumulation points, for every mesh satisfying the above conditions, or under precisely characterizable additional hypotheses on $M$ or on the initial boundary map? If not, exhibit a mesh and initial data for which it fails.
2. (Uniqueness of the limit) The update is built from real coefficients and a modulus normalization and therefore commutes with a nontrivial symmetry group acting on the boundary maps; uniqueness of the limit can hold only modulo that group. When the iteration converges, is the limiting boundary map determined by the initial boundary map up to these symmetries, or can different initial data yield limits that are not related by any such symmetry? Determine the relevant symmetry group, and if the limit is not so determined, characterize the set of attainable limits.
3. (Rate) What is the convergence rate of the boundary iterates and of the conformal energy $\mathcal{E}_C(\mathbf{f}^{(k)})=\tfrac{1}{2}(\mathbf{f}^{(k)})^{*}L\mathbf{f}^{(k)}-\mathcal{A}(\mathbf{f}^{(k)})$, e.g. linear or asymptotically R-linear?
4. (Monotonicity) Is $\mathcal{E}_C(\mathbf{f}^{(k)})$ monotonically nonincreasing along the modified (Eq. (30)) iteration for every mesh satisfying the above conditions? Prove it, or exhibit a counterexample mesh and initial data with a strict energy increase at a stated iteration.
5. (Behavior under hypothesis failure) Analyze the iteration when the hypotheses fail, for each of the following failures in turn: non-Delaunay edges (negative cotangent weights destroy the M-matrix structure), a disconnected interior subgraph, or boundary vertices with no interior neighbor. Is the iteration still well defined, and does it converge; if not, what preprocessing of the mesh restores well-definedness and the above guarantees?
6. (Scaling) Provide a rigorous asymptotic complexity and scaling analysis of the algorithm for very large meshes, including the effect on the accuracy and convergence of the computed iterates of replacing the direct sparse solve for the harmonic extension by other sparse-direct or iterative solvers.

The common scientific objective is a complete reliability theory of the CEM boundary iteration, the algorithm actually implemented and used in applications: items 1-4 concern its convergence behavior on the meshes it was designed for, item 5 its domain of validity, and item 6 the computational scaling left unanalyzed in the source. The items are jointly the missing theory of one fixed-point iteration, not independent problems.

References

1. Mei-Heng Yueh, Wen-Wei Lin, Chin-Tien Wu, Shing-Tung Yau (2017). An Efficient Energy Minimization for Conformal Parameterizations. Journal of Scientific Computing 73(1):203-227. DOI: 10.1007/s10915-017-0414-y. https://doi.org/10.1007/s10915-017-0414-y
2. Yueh-Cheng Kuo, Wen-Wei Lin, Mei-Heng Yueh, Shing-Tung Yau (2021). Convergent Conformal Energy Minimization for the Computation of Disk Parameterizations. SIAM Journal on Imaging Sciences 14(4):1790-1815. DOI: 10.1137/21M1415443. https://doi.org/10.1137/21M1415443
3. Pui Tung Choi, Lok Ming Lui (2015). Fast Disk Conformal Parameterization of Simply-Connected Open Surfaces. Journal of Scientific Computing 65(3):1065-1090. DOI: 10.1007/s10915-015-9998-2. https://doi.org/10.1007/s10915-015-9998-2
4. Zhong-Heng Tan, Zhenyue Zhang (2022). Stable Discrete Minimization of Conformal Energy for Disk Conformal Parameterization. arXiv:2210.09125. https://arxiv.org/abs/2210.09125
5. Zhenyue Zhang, Zhong-Heng Tan (2022). Convergence Analysis of Discrete Conformal Transformation. arXiv:2210.10990. https://arxiv.org/abs/2210.10990
6. Jia-Wei Lin, Tiexiang Li, Wen-Wei Lin, Tsung-Ming Huang (2023). Ellipsoidal conformal and area-/volume-preserving parameterizations and associated optimal mass transportations. Advances in Computational Mathematics 49(4), article 50. DOI: 10.1007/s10444-023-10048-w. https://doi.org/10.1007/s10444-023-10048-w
7. Wei-Hung Liao, Tsung-Ming Huang, Wen-Wei Lin, Mei-Heng Yueh (2024). Convergence of Dirichlet Energy Minimization for Spherical Conformal Parameterizations. Journal of Scientific Computing 98(1), article 29. DOI: 10.1007/s10915-023-02424-x. https://doi.org/10.1007/s10915-023-02424-x (preprint arXiv:2206.15167, titled 'Convergence Analysis of Dirichlet Energy Minimization for Spherical Conformal Parameterizations': https://arxiv.org/abs/2206.15167)
8. Tsung-Ming Huang, Wei-Hung Liao, Wen-Wei Lin (2022). Fundamental Theory and R-linear Convergence of Stretch Energy Minimization for Equiareal Parameterizations. arXiv:2207.13943. https://arxiv.org/abs/2207.13943 (published version: Fundamental Theory and R-linear Convergence of Stretch Energy Minimization for Spherical Equiareal Parameterization, Journal of Numerical Mathematics, 2023, DOI: 10.1515/jnma-2022-0072, https://doi.org/10.1515/jnma-2022-0072)
9. Shu-Yung Liu, Mei-Heng Yueh (2024). Convergent Authalic Energy Minimization for Disk Area-Preserving Parameterizations. Journal of Scientific Computing 100(2), article 43. DOI: 10.1007/s10915-024-02594-2. arXiv:2307.11363. https://arxiv.org/abs/2307.11363
10. Shu-Yung Liu, Mei-Heng Yueh (2025). Energy-Based Distortion-Balancing Parameterization for Open Surfaces. SIAM Journal on Imaging Sciences 18(4):2059-2093. DOI: 10.1137/24M1708437. arXiv:2412.09909. https://arxiv.org/abs/2412.09909
11. Wei-Hung Liao, Mei-Heng Yueh (2022). A Constructive Algorithm for Disk Conformal Parameterizations. Journal of Scientific Computing 92(2), article 40. DOI: 10.1007/s10915-022-01898-5. https://doi.org/10.1007/s10915-022-01898-5