Analysis of uniform binary subdivision schemes for curve design (Q2644876): Difference between revisions

Suppose that a set of points is given in two or more dimensions and it is required to find a continuous curve or surface which is generated by these points in some way. One possible solution would be to devise an interpolation scheme based on polynomials which would provide continuations. However it is likely that these will have unwanted ripples. An alternative is to use a recursive subdivision algorithm. This is a technique for the fast generation of curves and surfaces by the repeated smoothing of a control polygon which leads, in the limit, to a smooth object. An example of this is Chaiken's binary subdivision scheme which is based on quadratic B-splines and given by \[ f_{2i}^{k+1}=(3f^ k_ i+f^ k_{i+1})/4,\quad f^{k+1}_{2i+1}=(f^ k_ i+3f^ k_{i+1})/4,\quad i\in Z,\quad k=0,1,2,.... \] The authors present a generalization of this and analyse the convergence of the control polygons to a \(C^ 0\) curve in terms of the convergence to zero of a derived scheme for the differences \(f^ k_{i+1}-f^ k_ i\). The analysis of the smoothness of the limit curve is reduced to the convergence analysis of ``differentiated'' schemes which correspond to divided differences of \(\{f^ k_ i:\) \(i\in Z\}\) with respect to the dyadic parametrization \(t^ k_ i=i/2^ k\). The inverse process of ``integration'' provides schemes with limit curves which have additional orders of smoothness. Some examples are given.