By the Riemann-mapping theorem, one can bijectively map the interior of an $n$-gon $P$ to that of another $n$-gon $Q$ conformally (i.e., in an angle preserving manner). However, when this map is extended to the boundary it need not necessarily map the vertices of $P$ to those of $Q$. For many applications it is important to find the "best" vertex-preserving mapping between two polygons, i.e., one that minimizes the maximum angle distortion (the so-called dilatation) over all points in $P$. Teichmuller (1940) proved the existence and uniqueness of such maps, which are called extremal quasiconformal maps, or Teichmuller maps. There are many efficient ways to compute or approximate conformal maps, and the recent breakthrough result by Bishop computes a $(1+\epsilon)$-approximation of the Riemann map in linear time. However, there is currently no such algorithm for extremal quasiconformal maps (which generalize conformal maps), and only heuristics have been studied so far.
We solve the open problem of finding a finite time procedure for approximating Teichmuller maps in the continuous setting. Our construction is via an iterative procedure that is proven to converge quickly (in $O(\mathrm{poly}(1/\epsilon))$ iterations) to a $(1+\epsilon)$-approximation of the Teichmuller map, and in the limit to the exact Teichmuller map. Furthermore, every step of the iteration involves convex optimization and solving differential equations, two operations which may be solved in polynomial time in a discrete implementation. Our method uses a reduction of the polygon mapping problem to the punctured sphere problem, thus solving a more general problem. Building upon our results in the continuous setting, we give a discrete algorithm for computing Teichmuller maps.