Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A global approach to the refinement of manifold data

Authors: Nira Dyn and Nir Sharon
Journal: Math. Comp. 86 (2017), 375-395
MSC (2010): Primary 65D99, 40A99, 58E10
Published electronically: April 13, 2016
MathSciNet review: 3557803
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A refinement of manifold data is a computational process, which produces a denser set of discrete data from a given one. Such refinements are closely related to multiresolution representations of manifold data by pyramid transforms, and approximation of manifold-valued functions by repeated refinements schemes. Most refinement methods compute each refined element separately, independently of the computations of the other elements. Here we propose a global method which computes all the refined elements simultaneously, using geodesic averages. We analyse repeated refinements schemes based on this global approach, and derive conditions guaranteeing strong convergence.

References [Enhancements On Off] (What's this?)

References References
  • Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften : a series of comprehensive studies in mathematics, vol. 319, Springer, 1999.
  • Thomas J Cashman, Kai Hormann, and Ulrich Reif, Generalized Lane–Riesenfeld algorithms, Computer Aided Geometric Design 30 (2013), no. 4, 398–409.
  • George M. Chaikin, An algorithm for high-speed curve generation., Comput. Graph. Image Process 3 (1974), 346–349.
  • Keenan Crane, Clarisse Weischedel, and Max Wardetzky, Geodesics in heat: A new approach to computing distance based on heat flow, ACM Transactions on Graphics (TOG) 32 (2013), no. 5, 152.
  • Gilles Deslauriers and Serge Dubuc, Symmetric iterative interpolation processes, Constr. Approx. 5 (1989), no. 1, 49–68. Fractal approximation. MR 982724, DOI
  • Manfredo P. DoCarmo, Riemannian geometry, Springer, 1992.
  • N. Dyn, Subdivision schemes in computer-aided geometric design, Advances in numerical analysis, Vol. II (Lancaster, 1990) Oxford Sci. Publ., Oxford Univ. Press, New York, 1992, pp. 36–104. MR 1172120
  • Nira Dyn, Three families of nonlinear subdivision schemes, Studies in Computational Mathematics 12 (2006), 23–38.
  • Nira Dyn and Elza Farkhi, Spline subdivision schemes for compact sets with metric averages, Trends in approximation theory, 2001, pp. 1–10.
  • Nira Dyn and Ron Goldman, Convergence and smoothness of nonlinear Lane–Riesenfeld algorithms in the functional setting, Foundations of Computational Mathematics 11 (2011), no. 1, 79–94.
  • Nira Dyn, David Levin, and John A. Gregory, A $4$-point interpolatory subdivision scheme for curve design, Comput. Aided Geom. Design 4 (1987), no. 4, 257–268. MR 937365, DOI
  • Nira Dyn and Nir Sharon, The convergence of manifold-valued subdivision schemes based on geodesic averaging. In prepration. Available at
  • Oliver Ebner, Convergence of refinement schemes on metric spaces, Proceedings of the American Mathematical Society 141 (2013), no. 2, 677–686.
  • Abbas M Faridi and EL Schucking, Geodesics and deformed spheres, Proceedings of the American Mathematical Society (1987), 522–525.
  • Svatopluk Fucik and Alois Kufner, Nonlinear differential equations, New York (1980).
  • Daniel Genin, Boris Khesin, and Serge Tabachnikov, Geodesics on an ellipsoid in minkowski space, Enseign.Math. (2) 53 (2007), 307–331.
  • Philipp Grohs and Johannes Wallner, Definability and stability of multiscale decompositions for manifold-valued data, Journal of the Franklin Institute 349 (2012), no. 5, 1648–1664.
  • Fumio Hiai and Dénes Petz, Riemannian metrics on positive definite matrices related to means, Linear Algebra Appl. 430 (2009), no. 11-12, 3105–3130. MR 2517863, DOI
  • Arieh Iserles, Hans Z Munthe-Kaas, Syvert P Nørsett, and Antonella Zanna, Lie-group methods, Acta Numerica 2000 9 (2000), no. 1, 215–365.
  • Uri Itai and Nir Sharon, Subdivision schemes for positive definite matrices, Foundations of Computational Mathematics 13 (2013), no. 3, 347–369.
  • Shay Kels and Nira Dyn, Subdivision schemes of sets and the approximation of set-valued functions in the symmetric difference metric, Foundations of Computational Mathematics 13 (2013), no. 5, 835–865.
  • Ron Kimmel and James A Sethian, Computing geodesic paths on manifolds, Proceedings of the National Academy of Sciences 95 (1998), no. 15, 8431–8435.
  • Jeffrey M. Lane and Richard F. Riesenfeld, A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-2 (1980), no. 1, 35–46.
  • Yongdo Lim and Miklós Pálfia, Approximations to the karcher mean on hadamard spaces via geometric power means, Forum mathematicum, 2013.
  • Valery Marenich, Geodesics in heisenberg groups, Geometriae Dedicata 66 (1997), no. 2, 175–185.
  • Facundo Mémoli and Guillermo Sapiro, Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces, Journal of computational Physics 173 (2001), no. 2, 730–764.
  • Lyle Noakes, Nonlinear corner-cutting, Advances in Computational Mathematics 8 (1998), no. 3, 165–177.
  • Lyle Noakes, Accelerations of Riemannian quadratics, Proceedings of the American Mathematical Society 127 (1999), no. 6, 1827–1836.
  • Inam Ur Rahman, Iddo Drori, Victoria C. Stodden, David L. Donoho, and Peter Schröder, Multiscale representations for manifold-valued data, Multiscale Model. Simul. 4 (2005), no. 4, 1201–1232. MR 2203850, DOI
  • Scott Schaefer and Ron Goldman, Non-uniform subdivision for b-splines of arbitrary degree, Computer Aided Geometric Design 26 (2009), no. 1, 75–81.
  • S. Schaefer, E. Vouga, and R. Goldman, Nonlinear subdivision through nonlinear averaging, Comput. Aided Geom. Design 25 (2008), no. 3, 162–180. MR 2389938, DOI
  • Nir Sharon and Uri Itai, Approximation schemes for functions of positive-definite matrix values, IMA Journal of Numerical Analysis 33 (2013), no. 4, 1436–1468.
  • John Stillwell, Naive Lie theory, Undergraduate Texts in Mathematics, Springer, New York, 2008. MR 2431402
  • J. Wallner, E. Nava Yazdani, and P. Grohs, Smoothness properties of Lie group subdivision schemes, Multiscale Model. Simul. 6 (2007), no. 2, 493–505. MR 2338492, DOI
  • Johannes Wallner, On convergent interpolatory subdivision schemes in Riemannian geometry.
  • Johannes Wallner and Nira Dyn, Convergence and $C^1$ analysis of subdivision schemes on manifolds by proximity, Comput. Aided Geom. Design 22 (2005), no. 7, 593–622. MR 2169051, DOI
  • Gang Xie and Thomas P.-Y. Yu, Smoothness equivalence properties of interpolatory Lie group subdivision schemes, IMA J. Numer. Anal. 30 (2010), no. 3, 731–750. MR 2670112, DOI

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D99, 40A99, 58E10

Retrieve articles in all journals with MSC (2010): 65D99, 40A99, 58E10

Additional Information

Nira Dyn
Affiliation: School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv, Israel
MR Author ID: 61245

Nir Sharon
Affiliation: School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv, Israel
MR Author ID: 974347

Keywords: Manifold data, geodesic average, convergence analysis
Received by editor(s): August 14, 2014
Published electronically: April 13, 2016
Article copyright: © Copyright 2016 American Mathematical Society