# Computing Teichmuller maps between polygons

## Mayank Goswami, Max-Planck Institute for Informatics

## September 2, 2014

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.