Wednesday, February 18, 2015 - 14:05
1 hour (actually 50 minutes)
SUNY Stony Brook
The Riemann mapping theorem says that every simply connected proper plane domain can be conformally mapped to the unit disk. I will discuss the computational complexity of constructing a conformal map from the disk to an n-gon and show that it is linear in n, with a constant that depends only on the desired accuracy. As one might expect, the proof uses ideas from complex analysis, quasiconformal mappings and numerical analysis, but I will focus mostly on the surprising roles played by computational planar geometry and 3-dimensional hyperbolic geometry. If time permits, I will discuss how this conformal mapping algorithm implies new results in discrete geometry, e.g., every simple polygon can be meshed in linear time using quadrilaterals with all angles \leq 120 degrees and all new angles \geq 60 degrees (small angles in the original polygon must remain).