Conformal Wasserstein distance: II. Computational aspects and extensions. (English) Zbl 1281.65034

This paper is the continuation of Part I [Adv. Math. 227, No. 3, 1047–1077 (2011; Zbl 1217.53026)]. It is full of important results, concerning the algorithm for comparing disk type surfaces and analysis, respectively, numerical procedures and algorithms for computing the alignment of two disk surfaces. The present paper is also devoted to the study of sphere type surfaces and disk type surfaces. The main tools used by the authors in this paper are from various fields, I just enumerate some of them: complex analysis, namely, Möbius transformations; from computational geometry: Voronoi diagrams; and also from computer science various sets of notions. In conclusion, the paper is well written and is at the border between complex analysis, computational geometry and computer science.


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
53D20 Momentum maps; symplectic reduction
53A05 Surfaces in Euclidean and related spaces


Zbl 1217.53026


Full Text: DOI arXiv


[1] [BBK06] R. Kimmel, A. M. Bronstein, M. M. Bronstein, Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, Proc. National Academy of Sciences (PNAS) 103 (2006), no. 5, 1168-1172. · Zbl 1160.65306
[2] [Jukka07] Mikael Fortelius, Jukka Jernvall, Alistair R. Evans, Gregory P. Wilson, High-level similarity of dentitions in carnivorans and rodents, Nature 445 (2007), 78-81.
[3] [Brenner:2008:MTF] Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, third ed., Texts in Applied Mathematics, vol. 15, 2008. · Zbl 1135.65042
[4] [BBK2007non\textunderscorerigid\textunderscorebook] Alexander Bronstein, Michael Bronstein, and Ron Kimmel, Numerical geometry of non-rigid shapes, 1st ed., Springer Publishing Company, Incorporated, 2008. · Zbl 1178.68608
[5] [BBK06b] Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel, Efficient computation of isometry-invariant distances between surfaces, SIAM J. Sci. Comput. 28 (2006), no. 5, 1812-1836. · Zbl 1123.65010
[6] [Cela98] E. Cela, The quadratic assignment problem: Theory and algorithms (combinatorial optimization), Springer, 1998. · Zbl 0909.90226
[7] [Dziuk88] Gerhard Dziuk, Finite elements for the \(B\) eltrami operator on arbitrary surfaces, vol. 1357, Springer Berlin / Heidelberg, 1988. · Zbl 0663.65114
[8] [eldar97farthest] Y. Eldar, M. Lindenbaum, M. Porat, and Y. Zeevi, The farthest point strategy for progressive image sampling, 1997.
[9] [Fischl99] Bruce Fischl, Martin I. Sereno, Roger B. H. Tootell, and Anders M. Dale, High-resolution intersubject averaging and a coordinate system for the cortical surface, Hum. Brain Mapp 8 (1999), 272-284.
[10] [Giorgi07] Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi, SHREC:SHape REtrieval Contest: Watertight models track, http://watertight.ge.imati.cnr.it/, 2007.
[11] [Gromov06] Mikhail Gromov, M. Katz, P. Pansu, and S. Semmes, Metric structures for Riemannian and non-Riemannian spaces, Birkh\"auser Boston, December 2006.
[12] [Gu03] Xianfeng Gu and Shing-Tung Yau, Global conformal surface parameterization, SGP ’03: Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (Aire-la-Ville, Switzerland, Switzerland), Eurographics Association, 2003, pp. 127-137.
[13] [Haker04optimalmass] Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent, Optimal mass transport for registration and warping, International Journal on Computer Vision 60 (2004), 225-240. · Zbl 1477.68510
[14] [Hildebrandt06] Hildebrandt, Klaus, Polthier, Konrad, Wardetzky, and Max, On the convergence of metric and geometric properties of polyhedral surfaces, Geometriae Dedicata 123 (2006), no. 1, 89-112. · Zbl 1125.52014
[15] [Kantorovich1942] L. Kantorovich, On the translocation of masses, C.R. (Dokl.) Acad. Sci. URSS (N.S.) 37 (1942), 199-201. · Zbl 0061.09705
[16] [Farkas92] Irwin Kra, Hershel M. Farkas, Riemann surfaces, Springer, 1992. · Zbl 0764.30001
[17] [Lovasz86] M.D. Plummer, L. Lov\'asz, Matching theory, North-Holland, 1986. · Zbl 0618.05001
[18] [Lancaster00] L.M. Parsons, M. Liotti, C.S. Freitas, L. Rainey, P.V. Kochunov, D. Nickerson, S.A. Mikiten, P.T. Fox, J.L. Lancaster, M.G. Woldorff, Automated talairach atlas labels for functional brain mapping, Human Brain Mapping 10 (2000), 120-131.
[19] [Lipman\textunderscoreDaubechies:2010:polytimesurfcomp] Yaron Lipman and Ingrid Daubechies, Conformal Wasserstein distances: Comparing surfaces in polynomial time, Advances in Mathematics (ELS), 227 (2011), no. 3, 1047-1077, (2011). · Zbl 1217.53026
[20] [Lipman:2009:MVF] Yaron Lipman and Thomas Funkhouser, M\"obius voting for surface correspondence, ACM Transactions on Graphics (Proc. SIGGRAPH) 28 (2009), no. 3.
[21] [memoli07] Facundo Memoli, On the use of Gromov-Hausdorff distances for shape comparison, Symposium on Point Based Graphics (2007).
[22] [memoli05] Facundo M\'emoli and Guillermo Sapiro, A theoretical and computational framework for isometry invariant recognition of point cloud data, Found. Comput. Math. 5 (2005), no. 3, 313-347. · Zbl 1101.53022
[23] [Billingsley68] Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, 1968. · Zbl 0172.21201
[24] [Pinkall93] Ulrich Pinkall and Konrad Polthier, Computing discrete minimal surfaces and their conjugates, Experimental Mathematics 2 (1993), 15-36. · Zbl 0799.53008
[25] [Polthier00] Konrad Polthier, Conjugate harmonic maps and minimal surfaces, Preprint No. 446, TU-Berlin, SFB 288 (2000).
[26] [Polthier05] \bysame, Computational aspects of discrete minimal surfaces, Global Theory of Minimal Surfaces, Proc. of the Clay Mathematics Institute 2001 Summer School, David Hoffman (Ed.), CMI/AMS (2005).
[27] [Rubner2000-TEM] Y. Rubner, C. Tomasi, and L. J. Guibas, The earth mover’s distance as a metric for image retrieval, International Journal of Computer Vision 40 (2000), no. 2, 99-121. · Zbl 1012.68705
[28] [Haxby09] B. Conroy, R.E. Bryan, P.J. Ramadge, J.V. Haxby, M.R. Sabuncu, B.D. Singer, Function-based intersubject alignment of human cortical anatomy, Cereb Cortex. (2009).
[29] [Schrijver08] Alexander Schrijver, A course in combinatorial optimization, course notes, 2008.
[30] [Springborn:2008:CET:1399504.1360676] Boris Springborn, Peter Schr\`“oder, and Ulrich Pinkall, Conformal equivalence of triangle meshes, ACM SIGGRAPH 2008 papers (New York, NY, USA), SIGGRAPH ”08, ACM, 2008, pp. 77:1-77:11.
[31] [Springer57] George Springer, Introduction to Riemann surfaces, AMS Chelsea Publishing, 1981. · Zbl 0501.30039
[32] [Villani:2003] Cedric Villani, Topics in optimal transportation (Graduate Studies in Mathematics, vol. 58), American Mathematical Society, March 2003. · Zbl 1106.90001
[33] [Gu2008\textunderscorea] W. Zeng, X. Yin, Y. Zeng, Y. Lai, X. Gu, and D. Samaras, 3d face matching and registration based on hyperbolic Ricci flow, CVPR Workshop on 3D Face Processing (2008), 1-8.
[34] [Gu2008\textunderscoreb] W. Zeng, Y. Zeng, Y. Wang, X. Yin, X. Gu, and D. Samaras, 3d non-rigid surface matching and registration based on holomorphic differentials, The 10th European Conference on Computer Vision (ECCV) (2008).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.