License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.615
URN: urn:nbn:de:0030-drops-50997
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5099/
Goswami, Mayank ;
Gu, Xianfeng ;
Pingali, Vamsi P. ;
Telang, Gaurish
Computing Teichmüller Maps between Polygons
Abstract
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+epsilon)-approximation of the Riemann map in linear time. However, only heuristics have been studied in the case of Teichmüller maps.
We present two results in this paper. One studies the problem in the continuous setting and another in the discrete setting.
In the continuous setting, we solve the problem of finding a finite time procedure for approximating Teichmüller maps. Our construction is via an iterative procedure that is proven to converge in O(poly(1/epsilon)) iterations to a (1+epsilon)-approximation of the Teichmuller map. Our method uses a reduction of the polygon mapping problem to the marked sphere problem, thus solving a more general problem.
In the discrete setting, 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 a (1+epsilon)-approximation algorithm.
BibTeX - Entry
@InProceedings{goswami_et_al:LIPIcs:2015:5099,
author = {Mayank Goswami and Xianfeng Gu and Vamsi P. Pingali and Gaurish Telang},
title = {{Computing Teichm{\"u}ller Maps between Polygons}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {615--629},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-83-5},
ISSN = {1868-8969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5099},
URN = {urn:nbn:de:0030-drops-50997},
doi = {10.4230/LIPIcs.SOCG.2015.615},
annote = {Keywords: Teichm{\"u}ller maps, Surface registration, Extremal Quasiconformal maps, Computer vision}
}
|
Keywords: |
|
Teichmüller maps, Surface registration, Extremal Quasiconformal maps, Computer vision |
|
Collection: |
|
31st International Symposium on Computational Geometry (SoCG 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
12.06.2015 |
