Subdivision schemes and irregular grids (Q1430245): Difference between revisions

In computer aided geometric design, subdivision schemes are a classical process to construct curves and surfaces. This paper deals only with curves. The principle is simple. A curve in \(\mathbb R^d\) is obtained as the limit of a sequence of polygonal lines in this space. At each level, each vertex of the polygonal line is calculated from a finite number of vertices of the polygonal line of the previous level (actually, as a linear combination in the linear case). The limit curve is expected to be at least continuous, and if possible, to satisfy additional smoothness properties. As an instance, starting from a bi-infinite sequence of initial vertices, suppose that the new vertices are located at one fourth and three fourths respectively on each segment of the initial polygonal line. Repeating this process describes the well-known Chaikin algorithm, and the limit curve it produces is the quadratic \(C^1\) polynomial spline curve associated with regularly spaced knots, the control polygon of which is the initial polygonal line. The latter particular example is naturally related to the regular grid of \(\mathbb R\). The analysis of the convergence of any subdivision schemes is generally done by reference to the regular grid too, that is by considering the convergence of the sequence of piecewise affine functions parametrizing the polygonal line of level \(j\), with knots at the points \(2^{-j}k\), \(k\in\mathbb Z\). However the limitation to regular grids is far too restrictive. The necessity of allowing non regular ones naturally arises, for instance, through the example of spline curves. Another motivation for the consideration of non regular grids comes from wavelets and multiresolution analysis to which subdivision schemes are closely related. For a long time wavelets were considered on regular grids. Yet, the necessity of extending them to the nonregular case appeared in recent years with the introduction of second generation wavelets. The present paper studies the convergence of subdivision schemes defined relative to irregular grids. The main idea is to derive the convergence of a given subdivision scheme by comparison with another subdivision scheme to which it is equivalent in some sense. A sufficient condition for convergence for subdivision schemes in terms of the difference schemes is established. This condition extends a well-known necessary and sufficient condition for stationary and uniform schemes associated with the regular grid. If the nonregular grid is not so far from the regular one (quasi-regularity), the limit functions are more regular than just continuous, exactly as in the regular case. The notion of equivalence between subdivision schemes is introduced, and it is shown that if two schemes are equivalent and one of them satisfies the sufficient condition, the other also satisfies it, and therefore it converges. Applying the latter result to the derived schemes, it is shown how to derive smoothness of higher order of the limit functions produced by a given subdivision scheme from properties satisfied by an equivalent one. The results are illustrated through the study of Lagrange interpolating subdivision schemes associated with particular quasi-regular grids. The convergence is then deduced from that of the corresponding regular Lagrange interpolating schemes. A weak additional assumption on the grids enabled to obtain interesting results of convergence for any odd degrees.