On the computational complexity of the Riemann mapping (Q942023)

The paper is devoted to the theoretical foundations of numerically approximating the Riemann conformal mapping of a domain \(\Omega\) onto the unit disk \(\mathbb D\). The authors propose a new algorithm for computing the Riemann map using the random walks solution to the general Dirichlet problem to solve the uniformization problem. The computational complexity depends on how the boundary of the computable uniformized domain \(\Omega\) is specified. The approximation of the boundary is given either as a list of pixels or by a Turing machine. In both settings nontrivial upper and lower bounds are obtained. The general formulations assume that the algorithm will have an access to an oracle for the computing function. In the scale where the entire boundary is given explicitly, and not by an oracle for it, the result is stated in Theorem 1.11: There is an algorithm \(A'\) that computes the uniformizing map in the following sense. Let \(\Omega\) be a bounded simply connected domain, and \(w_0\in\Omega\). Suppose that for some \(n=2^k\), \(\partial\Omega\) is given to \(A'\) with precision \(1/n\) by \(O(n^2)\) pixels. Then \(A'\) computes the absolute values of the uniformizing map \(\phi: (\Omega,w_0)\to(\mathbb D,0)\) within an error of \(O(1/n)\) in randomized space bounded by \(O(k)\) and time polynomial in \(n=2^k\) (that is, by a BPL(n)-machine). Furthermore, the algorithm computes the value of \(\phi(w)\) with precision \(1/n\) as long as \(| \phi(w)| <1-1/n\). The complexity of the uniformization can be quite high, even to compute the conformal radius of \(\Omega\). The corresponding theorems describe the computational complexity of this problem.