Editing Riemann mapping theorem (section)

== Algorithms ==
Computational conformal mapping is prominently featured in problems of applied analysis and mathematical physics, as well as in engineering disciplines, such as image processing.

In the early 1980s an elementary algorithm for computing conformal maps was discovered. Given points <math>z_0, \ldots, z_n</math> in the plane, the algorithm computes an explicit conformal map of the unit disk onto a region bounded by a Jordan curve <math>\gamma</math> with <math>z_0, \ldots, z_n \in \gamma.</math> This algorithm converges for Jordan regions<ref>A Jordan region is the interior of a [[Jordan curve]].</ref> in the sense of uniformly close boundaries. There are corresponding uniform estimates on the closed region and the closed disc for the mapping functions and their inverses. Improved estimates are obtained if the data points lie on a <math>C^1</math> curve or a {{math|''K''}}-[[quasicircle]]. The algorithm was discovered as an approximate method for conformal welding; however, it can also be viewed as a discretization of the [[Loewner differential equation]].<ref name=Marshall2007>{{Cite journal|doi=10.1137/060659119|title=Convergence of a Variant of the Zipper Algorithm for Conformal Mapping|journal=SIAM Journal on Numerical Analysis|volume=45|issue=6|pages=2577|year=2007|last1=Marshall|first1=Donald E.|last2=Rohde|first2=Steffen|citeseerx=10.1.1.100.2423}}</ref>

The following is known about numerically approximating the conformal mapping between two planar domains.<ref name=Binder07>{{Cite journal |doi= 10.1007/s11512-007-0045-x| title=On the computational complexity of the Riemann mapping|journal=Arkiv för Matematik| volume=45 |issue=2 |pages=221| year=2007|last1=Binder|first1=Ilia|last2=Braverman|first2=Mark|last3=Yampolsky|first3=Michael|arxiv=math/0505617|bibcode=2007ArM....45..221B| s2cid=14545404}}</ref>

Positive results:

* There is an algorithm A that computes the uniformizing map in the following sense. Let <math>\Omega</math> be a bounded simply-connected domain, and <math>w_0\in\Omega</math>. <math>\partial\Omega</math> is provided to A by an oracle representing it in a pixelated sense (i.e., if the screen is divided to <math>2^n \times 2^n</math> pixels, the oracle can say whether each pixel belongs to the boundary or not). Then A computes the absolute values of the uniformizing map <math>\phi:(\Omega, w_0) \to (D, 0)</math> with precision <math>2^{-n}</math> in space bounded by <math>Cn^2</math> and time <math>2^{O(n)}</math>, where <math>C</math> depends only on the diameter of <math>\Omega</math> and <math>d(w_0, \partial\Omega).</math> Furthermore, the algorithm computes the value of <math>\phi(w)</math> with precision <math>2^{-n}</math> as long as <math>|\phi(w)| < 1-2^{-n}.</math> Moreover, A queries <math>\partial\Omega</math> with precision of at most <math>2^{-O(n)}.</math> In particular, if <math>\partial\Omega</math> is polynomial space computable in space <math>n^a</math> for some constant <math>a\geq 1</math> and time <math>T(n) < 2^{O(n^a)},</math> then A can be used to compute the uniformizing map in space <math>C\cdot n^{\max(a,2)}</math> and time <math>2^{O(n^a)}.</math>

* There is an algorithm A′ that computes the uniformizing map in the following sense. Let <math>\Omega</math> be a bounded simply-connected domain, and <math>w_0 \in \Omega.</math> Suppose that for some <math>n=2^k,</math> <math>\partial\Omega</math> is given to A′ with precision <math>\tfrac{1}{n}</math> by <math>O(n^2)</math> pixels. Then A′ computes the absolute values of the uniformizing map <math>\phi:(\Omega, w_0) \to (D, 0)</math> within an error of <math>O(1/n)</math> in randomized space bounded by <math>O(k)</math> and time polynomial in <math>n=2^k</math> (that is, by a BPL({{math|''n''}})-machine). Furthermore, the algorithm computes the value of <math>\phi(w)</math> with precision <math>\tfrac{1}{n}</math> as long as <math>|\phi(w)|< 1 -\tfrac{1}{n}.</math>

Negative results:

* Suppose there is an algorithm A that given a simply-connected domain <math>\Omega</math> with a linear-time computable boundary and an inner radius <math>>1/2</math> and a number <math>n</math> computes the first <math>20 n</math> digits of the [[conformal radius]] <math>r(\Omega, 0),</math> then we can use one call to A to solve any instance of a [[Sharp-SAT|#SAT]]({{math|''n''}}) with a linear time overhead. In other words, [[Sharp-P|#P]] is poly-time reducible to computing the conformal radius of a set.

* Consider the problem of computing the conformal radius of a simply-connected domain <math>\Omega,</math> where the boundary of <math>\Omega</math> is given with precision <math>1/n</math> by an explicit collection of <math>O(n^2)</math> pixels. Denote the problem of computing the conformal radius with precision <math>1/n^c</math> by <math>\texttt{CONF}(n,n^c).</math> Then, <math>\texttt{MAJ}_n</math> is [[AC0]] reducible to <math>\texttt{CONF}(n,n^c)</math> for any <math>0 < c < \tfrac{1}{2}.</math>