Computing Teichmüller Maps between Polygons

Authors Mayank Goswami, Xianfeng Gu, Vamsi P. Pingali, Gaurish Telang



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.615.pdf
  • Filesize: 0.63 MB
  • 15 pages

Document Identifiers

Author Details

Mayank Goswami
Xianfeng Gu
Vamsi P. Pingali
Gaurish Telang

Cite AsGet BibTex

Mayank Goswami, Xianfeng Gu, Vamsi P. Pingali, and Gaurish Telang. Computing Teichmüller Maps between Polygons. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 615-629, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.615

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.
Keywords
  • Teichmüller maps
  • Surface registration
  • Extremal Quasiconformal maps
  • Computer vision

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. L. V. Ahlfors. Lectures on quasiconformal mappings, volume 38 of University Lecture Series. American Mathematical Society, Providence, RI, second edition, 2006. With supplemental chapters by C. J. Earle, I. Kra, M. Shishikura and J. H. Hubbard. Google Scholar
  2. C. Bishop. Conformal mapping in linear time. Discrete and Comput. Geometry, 44(2):330-428, 2010. Google Scholar
  3. Christopher Bishop. Analysis of conformal and quasiconformal maps. Results from prior NSF support, 2012. URL: http://www.math.sunysb.edu/~bishop/vita/nsf12.pdf.
  4. C. Carathéodory. Über die gegenseitige Beziehung der Ränder bei der konformen Abbildung des Inneren einer Jordanschen Kurve auf einen Kreis. Mathematische Annalen, 73(2):305-320, 1913. Google Scholar
  5. P. Daripa and M. Goswami, 2014. Private communication. Google Scholar
  6. Prabir Daripa. A fast algorithm to solve the beltrami equation with applications to quasiconformal mappings. Journal of Computational Physics, 106(2):355-365, 1993. Google Scholar
  7. T. A. Driscoll and L. N. Trefethen. Schwarz-Christoffel Mapping. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2002. Google Scholar
  8. T. A. Driscoll and S. A. Vavasis. Numerical conformal mapping using cross-ratios and delaunay triangulation. SIAM J. Sci. Comput, 19:1783-1803, 1998. Google Scholar
  9. D. Gaidashev and D. Khmelev. On numerical algorithms for the solution of a beltrami equation. SIAM Journal on Numerical Analysis, 46(5):2238-2253, 2008. Google Scholar
  10. F. P. Gardiner and N. Lakic. Quasiconformal Teichmüler theory. American Mathematical Society, 1999. Google Scholar
  11. M. Goswami, X. Gu, V. Pingali, and G. Telang. Computing Teichmüller maps between polygons. arXiv:1401.6395 - http://arxiv.org/abs/1401.6395, 2014.
  12. H. Grötzsch. Über die Verzerrung bei nichtkonformen schlichten Abbildungen mehrfach zusammenhngender Bereiche. Leipz. Ber., 82:69-80, 1930. Google Scholar
  13. X. Gu, Y. Wang, T. F. Chan, P. M. Thompson, and S. T. Yau. Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Transactions on Medical Imaging, 23(7):949-958, 2004. Google Scholar
  14. X. Gu and S.T. Yau. Global surface conformal parameterization. In Symposium on Geometry Processing (SGP'03), volume 43, pages 127-137, 2003. Google Scholar
  15. J. H. Hubbard. Teichmüller theory and applications to geometry, topology, and dynamics. Matrix Editions, 2006. Google Scholar
  16. Ldmm - the large deformation diffeomorphic metric mapping tool. URL: http://cis.jhu.edu/software/lddmm-volume/tutorial.php.
  17. L. Lui, K. Lam, S. Yau, and X. Gu. Teichmüller Mapping (T-Map) and Its Applications to Landmark Matching Registration. SIAM Journal on Imaging Sciences, 7(1):391-426, 2014. Google Scholar
  18. L. M. Lui, Xianfeng Gu, and Shing Tung Yau. Convergence of an iterative // algorithm for Teichmüller maps via generalized harmonic maps. arXiv:1307.2679 - http://arxiv.org/abs/1307.2679, 2014.
  19. Lok Ming Lui, Tsz Wai Wong, Wei Zeng, Xianfeng Gu, Paul M. Thompson, Tony F. Chan, and Shing-Tung Yau. Optimization of surface registrations using beltrami holomorphic flow. Journal of Scientific Computing, 50(3):557-585, 2012. Google Scholar
  20. P.M. Pardalos and M.G.C. Resende. Handbook of applied optimization, volume 1. Oxford University Press New York, 2002. Google Scholar
  21. J. Ruppert. A delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms, 18(3):548-585, 1995. Google Scholar
  22. O. Teichmüller. Extremale quasikonforme Abbildungen und quadratische Differentiale. Preuss. Akad. Math.-Nat., 1, 1940. Google Scholar
  23. O. Teichmüller. Bestimmung der extremalen quasikonformen Abbildungen bei geschlossenen orientierten Riemannschen Flächen. Preuss. Akad. Math.-Nat., 4, 1943. Google Scholar
  24. Y. Wang, M. Gupta, S. Zhang, S. Wang, X. Gu, D. Samaras, and P. Huang. High Resolution Tracking of Non-Rigid Motion of Densely Sampled 3D Data Using Harmonic Maps. International Journal of Computer Vision, 76(3):283-300, 2008. Google Scholar
  25. Y. Wang, J. Shi, X. Yin, X. Gu, T. F. Chan, S. T. Yau, A. W. Toga, and P. M. Thompson. Brain surface conformal parameterization with the ricci flow. IEEE Transactions on Medical Imaging, 31(2):251-264, 2012. Google Scholar
  26. O. Weber, A. Myles, and D. Zorin. Computing extremal quasiconformal maps. Comp. Graph. Forum, 31(5):1679-1689, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail