clopen.solutions
OP-00382 Open

Global convergence of the simple CRDT conformal-mapping iteration

Submit a result

Let $P$ be a bounded simple polygon with nonzero interior angles. First subdivide its boundary as Driscoll and Vavasis do. At each vertex of interior angle at most $\pi/4$, take the largest isosceles triangle in $P$ formed by the vertex and its two adjacent edges, insert the midpoints of its two equal sides as new vertices, and protect the two resulting edges at the vertex. Then, in passes, simultaneously trisect every unprotected edge $e$ whose geodesic distance inside $P$ to a vertex other than its endpoints is less than $|e|/(3\sqrt{2})$, until no such edge remains; Driscoll and Vavasis prove that this terminates. Write $z_1, \dots, z_n$ for the vertices of the subdivided polygon in counterclockwise order and $\theta_j$ for the interior angle at $z_j$, and fix a constrained Delaunay triangulation of it. Each of its $n - 3$ internal diagonals is a diagonal of the quadrilateral formed by its two neighbouring triangles; label that quadrilateral's vertices counterclockwise as $z_{\kappa(i,1)}, \dots, z_{\kappa(i,4)}$, with the diagonal joining the first and the third, for $1 \le i \le n - 3$. Set $$\rho(a,b,c,d) = \frac{(d - a)(b - c)}{(c - d)(a - b)}, \qquad c_i = \log\bigl|\rho(z_{\kappa(i,1)}, z_{\kappa(i,2)}, z_{\kappa(i,3)}, z_{\kappa(i,4)})\bigr|.$$ For $\sigma \in \mathbb{R}^{n-3}$ there are points $w_1, \dots, w_n$ in counterclockwise order on the unit circle with $\rho(w_{\kappa(i,1)}, \dots, w_{\kappa(i,4)}) = -e^{\sigma_i}$ for every $i$, unique up to automorphisms of the disk (Driscoll and Vavasis). Let $$f_\sigma(w) = \int_0^w \prod_{j=1}^n (1 - \omega/w_j)^{\theta_j/\pi - 1}\, d\omega,$$ with the branches analytic in the disk and equal to $1$ at the origin, put $\zeta_j(\sigma) = f_\sigma(w_j)$, and $$F_i(\sigma) = \log\bigl|\rho(\zeta_{\kappa(i,1)}(\sigma), \dots, \zeta_{\kappa(i,4)}(\sigma))\bigr| - c_i,$$ which, where finite, does not depend on the choice of the $w_j$. In their experiments with the iteration below, Driscoll and Vavasis always observed $\|F(\sigma^{(k+1)})\|_2 \le \alpha \|F(\sigma^{(k)})\|_2$ for some problem-dependent $\alpha < 1$. Bishop proved that the initial guess $\sigma^{(0)} = c$ is close to the true prevertices in a quasiconformal sense: some $K$-quasiconformal self-map of the disk carries the true prevertices to points with log-cross-ratios $c$, with $\log K$ bounded independently of $P$. He also showed that the corresponding bound measured by cross-ratios, as Driscoll and Vavasis had asked, fails.

Problem. Let $\sigma_*$ be the vector of $\log(-\rho)$ of the true conformal prevertices of $P$, taken over the same quadrilaterals. In exact arithmetic with exact integrals, does the iteration $$\sigma^{(0)} = c, \qquad \sigma^{(k+1)} = \sigma^{(k)} - F(\sigma^{(k)})$$ remain well defined and converge to $\sigma_*$ for every such polygon and every constrained Delaunay triangulation of its subdivision? Only this initial vector is considered, not arbitrary ones.

Source: Driscoll and Vavasis (1998), who observed the convergence of the simple iteration in experiments without explaining it; Bishop (2010), §7, open question (3), whether CRDT can be proved to converge. Stated in this form by AIM — Open Applied Problems.

Imported from github.com/MColbrook/AIM.

Classification

Primary
NA — Numerical Analysis
Secondary
CV
Keywords
AIM Open Applied Problems, cross-ratios, numerical conformal mapping, Schwarz–Christoffel maps

References

@article{driscoll1998,
  author  = {Driscoll, Tobin A. and Vavasis, Stephen A.},
  title   = {Numerical conformal mapping using cross-ratios and {D}elaunay triangulation},
  journal = {SIAM J. Sci. Comput.},
  volume  = {19},
  number  = {6},
  year    = {1998},
  pages   = {1783--1803},
  doi     = {10.1137/S1064827596298580},
}
@article{bishop2010,
  author  = {Bishop, Christopher J.},
  title   = {Bounds for the {CRDT} conformal mapping algorithm},
  journal = {Comput. Methods Funct. Theory},
  volume  = {10},
  number  = {1},
  year    = {2010},
  pages   = {325--366},
  doi     = {10.1007/BF03321771},
}
@misc{aim-simple-crdt-convergence,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Global convergence of the simple CRDT conformal-mapping iteration}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/651-simple-crdt-convergence.md},
  note         = {Entry 651 at commit a153f46, 2026-10-13},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00382, "Global convergence of the simple CRDT conformal-mapping iteration", clopen.solutions.