Abstract
We present a framework for analyzing nonlinear \(\mathbb {R}^d\)-valued subdivision schemes which are geometric in the sense that they commute with similarities in \(\mathbb {R}^d\). It allows us to establish \(C^{1,\alpha }\)-regularity for arbitrary schemes of this type, and \(C^{2,\alpha }\)-regularity for an important subset thereof, which includes all real-valued schemes. Safe bounds on the domain of convergence of the scheme and on the Hölder exponent of the limit curves can be found by determining the range of certain real-valued functions. This task can be executed automatically and rigorously by a computer when using interval arithmetics.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
It should be noted that the regularity of the limit curve may indeed depend on the initial data. For instance, this phenomenon can be observed for medianinterpolating subdivision [31], where nonmonotonic data may yield nondifferentiable limits.
References
Cashman, T., Hormann, K., Reif, U.: Generalized Lane–Riesenfeld algorithms. Comput. Aided Geom. Des. 30(4), 398–409 (2013)
Cavaretta, A., Dahmen, W., Micchelli, C.: Stationary subdivision. Mem. AMS 93(453), 1–186 (1991)
Chaikin, G.: An algorithm for high-speed curve generation. Comput. Graph. Image Process. 3, 346–349 (1974)
Cohen, A., Dyn, N., Matei, B.: Quasilinear subdivision schemes with applications to ENO interpolation. Appl. Comput. Harmon. Anal. 15(2), 89–116 (2003)
Daubechies, I., Runborg, O., Sweldens, W.: Normal multiresolution approximation of curves. Constr. Approx. 20(3), 399–463 (2004)
de Boor, C.: Cutting corners always works. Comput. Aided Geom. Des. 4, 125–131 (1987)
de Rham, G.: Sur une courbe plane. J. Math. Pures Appl. 35, 25–42 (1956). Collected works, 696–713
Dodgson, N., Sabin, M.: A circle-preserving variant of the four-point subdivision scheme. In: Dæhlen, M., Morken, K., Schumaker, L. (eds.) Mathematical Methods for Curves and Surfaces: Tromsø 2004, pp. 275–286. Nashboro Press, Brentwood (2005)
Donoho, D., Drori, I., Rahman, I., Schröder, P., Stodden, V.: Multiscale representations for manifold-valued data. Multiscale Model. Simul. 4(4), 1201–1232 (2005)
Donoho, D., Yu, T.P.Y.: Nonlinear pyramid transforms based on median-interpolation. SIAM J. Math. Anal. 31(5), 1030–1061 (2000)
Dubuc, S.: Interpolation through an iterative scheme. J. Math. Anal. Appl. 114(1), 185–204 (1986)
Dyn, N., Floater, M.S., Hormann, K.: Four-point curve subdivision based on iterated chordal and centripetal parameterizations. Comput. Aided Geom. Des. 26(3), 279–286 (2009)
Dyn, N., Gregory, J., Levin, D.: Analysis of uniform binary subdivision schemes for curve design. Constr. Approx. 7(1), 127–147 (1991)
Dyn, N., Hormann, K.: Geometric conditions for tangent continuity of interpolatory planar subdivision curves. Comput. Aided Geom. Des. 29(6), 332–347 (2012)
Dyn, N., Levin, D.: Subdivision schemes in geometric modelling. Acta Numer. 11, 73–144 (2002)
Dyn, N., Wallner, J.: Convergence and \({C}^1\) analysis of subdivision schemes on manifolds by proximity. Comput. Aided Geom. Des. 22(7), 593–622 (2005)
Floater, M.S., Beccari, C., Cashman, T., Romani, L.: A smoothness criterion for monotonicity-preserving subdivision. Adv. Comput. Math. 39(1), 193–204 (2013)
Goldman, R., Schaefer, S., Vouga, E.: Nonlinear subdivision through nonlinear averaging. Comput. Aided Geom. Des. 25(3), 162–180 (2008)
Griewank, A., Walther, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2008)
Grohs, P.: Smoothness analysis of subdivision schemes on regular grids by proximity. SIAM J. Numer. Anal. 46(4), 2169–2182 (2008)
Grohs, P.: A general proximity analysis of nonlinear subdivision schemes. SIAM J. Math. Anal. 42(2), 729–750 (2010)
Kuijt, F., van Damme, R.: Monotonicity preserving interpolatory subdivision schemes. J. Comput. Appl. Math. 101(1–2), 203–229 (1999)
Micchelli, C.: Mathematical Aspects of Geometric Modeling. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia (1995)
Nava-Yazdani, E., Wallner, J., Weinmann, A.: Convergence and smoothness analysis of subdivision rules in Riemannian and symmetric spaces. Adv. Comput. Math. 34(2), 201–218 (2011)
Oswald, P.: Smoothness of a nonlinear subdivision scheme. In: Cohen, A., Merrien, J.L., Schumaker, L.L. (eds.) Curve and Surface Fitting: Saint-Malo 2002, pp. 323–332. Nashboro Press, Brentwood (2003)
Oswald, P.: Smoothness of nonlinear median-interpolation subdivision. Adv. Comput. Math. 20(4), 401–423 (2004)
Rump, S.: INTLAB—INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing, pp. 77–104. Kluwer, Dordrecht (1999). http://www.ti3.tuhh.de/rump/
Sabin, M.: Analysis and Design of Univariate Subdivision Schemes, Geometry and Computing, vol. 6. Springer, Berlin (2010)
Stolfi, J., de Figueiredo, L.: An introduction to affine arithmetic. Tend. Mat. Apl. Comput. 4(3), 297–312 (2003)
Wallner, J.: Smoothness analysis of subdivision schemes by proximity. Constr. Approx. 24(3), 289–318 (2006)
Xie, G., Yu, T.P.Y.: Smoothness analysis of nonlinear subdivision schemes of homogeneous and affine invariant type. Constr. Approx. 22(2), 219–254 (2005)
Xie, G., Yu, T.P.Y.: Smoothness equivalence properties of manifold-valued data subdivision schemes based on the projection approach. SIAM J. Numer. Anal. 45(3), 1200–1225 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Peter Oswald.
Rights and permissions
About this article
Cite this article
Ewald, T., Reif, U. & Sabin, M. Hölder Regularity of Geometric Subdivision Schemes. Constr Approx 42, 425–458 (2015). https://doi.org/10.1007/s00365-015-9305-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00365-015-9305-3