Computing Teichmüller Maps Between Polygons

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). Such maps exist, are unique, and are known as extremal quasiconformal maps or Teichmüller maps. There are many efficient ways to approximate conformal maps, and the recent breakthrough result by Bishop computes a (1 + ε) -approximation of the Riemann map in linear time. However, only heuristics have been studied in the case of Teichmüller maps. This paper solves the problem of finding a finite-time procedure for approximating Teichmüller maps in the continuous setting. Our construction is via an iterative procedure that is proven to converge in O(poly (1 / ε)) iterations to a map whose dilatation is at most ε more than that of the Teichmüller map, for any ε> 0. We reduce the problem of finding an approximation algorithm for computing Teichmüller maps to two basic subroutines, namely, computing discrete (1) compositions and (2) inverses of discretely represented quasiconformal maps. Assuming finite-time solvers for these subroutines, we provide an approximation algorithm with an additive error of at most ε.