Ahlfors Bers Colloquium
May
19-22, 2005
University of
Michigan
Ann Arbor, Michigan
Registration
Organizers
Dick
Canary
Juha
Heinonen
For website problems, contact webmaster
Plenary
Talks
Abstract Detail
| Conformal mapping in linear time
What is the computational complexity of conformal mapping? The Riemann mapping theorem says any simply connected, proper plane domain can be mapped conformally to the unit disk, and there are many numerical methods for approximating this map in practice. We will show that if the domain is bounded by an n-gon, then a (1+k)-QC map can be computed in time O(n), with an explicit constant depending only on the desired accuracy, k. We start with a simple, geometrically defined mapping to the disk which is quasiconformal with an estimate independent of the domain; an iteration using solutions of the Beltrami equation then converges quadratically to the conformal map. The proof uses ideas from various areas: 3-dimensional hyperbolic geometry (the Sullivan-Epstein-Marden theorem on convex hulls), computational geometry (linear time construction of Vorono diagrams and the medial axis), geometric function theory quasiconformal mappings, holomorphic motions) and numerical analysis (the fast multipole method). If time permits, we will touch on connections to other problems such as Bowen's dichotomy for Kleinian groups and Brennan's conjecture. | ||
|
|