×

Polynomial reproduction for univariate subdivision schemes of any arity. (English) Zbl 1211.65022

Authors’ abstract: The authors study the ability of convergent subdivision schemes to reproduce polynomials in the sense that for initial data, which is sampled from some polynomial function, the scheme yields the same polynomial in the limit. This property is desirable because the reproduction of polynomials up to some degree \(d\) implies that a scheme has approximation order \(d+1\). They first show that any convergent, linear, uniform, and stationary subdivision scheme reproduces linear functions with respect to an appropriately chosen parameterization. The authors then present a simple algebraic condition for polynomial reproduction of higher order. All results are given for subdivision schemes of any arity \(m\geq 2\) and they use them to derive a unified definition of general \(m\)-ary pseudo-splines. Their framework also covers non-symmetric schemes and they give an example where the smoothness of the limit functions can be increased by giving up symmetry.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Cavaretta, A. S.; Dahmen, W.; Micchelli, C. A., Stationary subdivision, Mem. Amer. Math. Soc., 93, 453 (1991), vi+186 · Zbl 0741.41009
[2] Chaikin, G. M., An algorithm for high speed curve generation, Comput. Graph. Image Process., 3, 4, 346-349 (1974)
[3] Choi, S. W.; Lee, B.-G.; Lee, Y. J.; Yoon, J., Stationary subdivision schemes reproducing polynomials, Comput. Aided Geom. Design, 23, 4, 351-360 (2006) · Zbl 1097.65032
[4] Deslauriers, G.; Dubuc, S., Symmetric iterative interpolation processes, Constr. Approx., 5, 1, 49-68 (1989) · Zbl 0659.65004
[5] Dong, B.; Shen, Z., Pseudo-splines, wavelets and framelets, Appl. Comput. Harmon. Anal., 22, 1, 78-104 (2007) · Zbl 1282.42035
[6] Dubuc, S., Interpolation through an iterative scheme, J. Math. Anal. Appl., 114, 1, 185-204 (1986) · Zbl 0615.65005
[7] Dyn, N., Subdivision schemes in computer-aided geometric design, (Light, W., Advances in Numerical Analysis, vol. II (1992), Oxford University Press: Oxford University Press New York), 36-104 · Zbl 0760.65012
[8] Dyn, N.; Floater, M. S.; Hormann, K., A \(C^2\) four-point subdivision scheme with fourth order accuracy and its extensions, (Dæhlen, M.; Mørken, K.; Schumaker, L. L., Mathematical Methods for Curves and Surfaces. Mathematical Methods for Curves and Surfaces, Tromsø2004. Mathematical Methods for Curves and Surfaces. Mathematical Methods for Curves and Surfaces, Tromsø2004, Modern Methods in Mathematics (2005), Nashboro Press: Nashboro Press Brentwood, TN), 145-156 · Zbl 1080.65526
[9] Dyn, N.; Hormann, K.; Sabin, M. A.; Shen, Z., Polynomial reproduction by symmetric subdivision schemes, J. Approx. Theory, 155, 1, 28-42 (2008) · Zbl 1159.41003
[10] Dyn, N.; Levin, D., Subdivision schemes in geometric modelling, Acta Numer., 11, 73-144 (2002) · Zbl 1105.65310
[11] Faheem, K.; Mustafa, G., Ternary six-point interpolating subdivision scheme, Lobachevskii J. Math., 29, 3, 153-163 (2008) · Zbl 1221.65045
[12] Han, B.; Jia, R.-Q., Multivariate refinement equations and convergence of subdivision schemes, SIAM J. Math. Anal., 29, 5, 1177-1199 (1998) · Zbl 0915.65143
[13] M.F. Hassan, Further analysis of ternary and 3-point univariate subdivision schemes, Technical Report UCAM-CL-TR-599, University of Cambridge, Computer Laboratory, August 2004.; M.F. Hassan, Further analysis of ternary and 3-point univariate subdivision schemes, Technical Report UCAM-CL-TR-599, University of Cambridge, Computer Laboratory, August 2004.
[14] Hassan, M. F.; Dodgson, N. A., Ternary and three-point univariate subdivision schemes, (Cohen, A.; Merrien, J.-L.; Schumaker, L. L., Curve and Surface Fitting. Curve and Surface Fitting, Saint-Malo 2002. Curve and Surface Fitting. Curve and Surface Fitting, Saint-Malo 2002, Modern Methods in Mathematics (2003), Nashboro Press: Nashboro Press Brentwood, TN), 199-208 · Zbl 1037.65024
[15] Hassan, M. F.; Ivrissimtzis, I. P.; Dodgson, N. A.; Sabin, M. A., An interpolating 4-point \(C^2\) ternary stationary subdivision scheme, Comput. Aided Geom. Design, 19, 1, 1-18 (2002) · Zbl 0984.68167
[16] Hormann, K.; Sabin, M. A., A family of subdivision schemes with cubic precision, Comput. Aided Geom. Design, 25, 1, 41-52 (2008) · Zbl 1172.65308
[17] Ivrissimtzis, I.; Sabin, M. A.; Dodgson, N. A., On the support of recursive subdivision, ACM Trans. Graph., 23, 4, 1043-1060 (2004)
[18] Ko, K. P.; Lee, B.-G.; Yoon, G. J., A study on the mask of interpolatory symmetric subdivision schemes, Appl. Math. Comput., 187, 2, 609-621 (2007) · Zbl 1120.65314
[19] Ko, K. P.; Lee, B.-G.; Yoon, G. J., A ternary 4-point approximating subdivision scheme, Appl. Math. Comput., 190, 2, 1563-1573 (2007) · Zbl 1144.65012
[20] Lagarias, J. C.; Wang, Y., The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear Algebra Appl., 214, 17-42 (1995) · Zbl 0818.15007
[21] Levin, A., Polynomial generation and quasi-interpolation in stationary non-uniform subdivision, Comput. Aided Geom. Design, 20, 1, 41-60 (2003) · Zbl 1069.41503
[22] Lian, J., On \(a\)-ary subdivision for curve design: I. 4-point and 6-point interpolatory schemes, Appl. Appl. Math., 3, 1, 18-29 (2008) · Zbl 1175.65027
[23] Lian, J., On \(a\)-ary subdivision for curve design: II. 3-point and 5-point interpolatory schemes, Appl. Appl. Math., 3, 2, 176-187 (2008) · Zbl 1175.65028
[24] Mustafa, G.; Khan, F., A new 4-point \(C^3\) quaternary approximating subdivision scheme, Abstr. Appl. Anal. (2009), Article ID 301967, 14 pages · Zbl 1167.65342
[25] Rioul, O., Simple regularity criteria for subdivision schemes, SIAM J. Math. Anal., 23, 6, 1544-1576 (1992) · Zbl 0761.42016
[26] Sauer, T., Multivariate refinable functions, differences and ideals—a simple tutorial, J. Comput. Appl. Math., 221, 2, 447-459 (2008) · Zbl 1154.65382
[27] Strang, G.; Fix, G. J., A Fourier analysis of the finite element variational method, (Geymonat, G., Constructive Aspects of Functional Analysis. Constructive Aspects of Functional Analysis, Centro Internazionale Matematico Estivo, vol. 2 (1973), Edizioni Cremonese: Edizioni Cremonese Roma), 795-840 · Zbl 0278.65116
[28] Wang, H.; Qin, K., Improved ternary subdivision interpolation scheme, Tsinghua Sci. Technol., 10, 1, 128-132 (2005)
[29] Zheng, H.; Zhao, H.; Ye, Z.; Zhou, M., Differentiability of a 4-point ternary subdivision scheme and its application, IAENG Int. J. Appl. Math., 36, 1 (2007), Article 4 · Zbl 1227.65022
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.