 Open Journal of Applied Sciences, 2013, 3, 106-111 doi:10.4236/ojapps.2013.31B1022 Published Online April 2013 (http://www.scirp.org/journal/ojapps) The 4-Point α-Ary Approximating Subdivision Scheme Abdul Ghaffar1, Ghulam Mustafa1, Kaihuai Qin2 1Department of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, Pakistan 2Dept. of Computer Science & Technology, Tsinghua University, Beijing 100084, P. R. China Email: abdulghaffar.jaffar@gmail.com, ghulam.mustafa@iub.edu.pk, qkh-dcs@tsinghua.edu.cn Received 2013 ABSTRACT A general formula for 4-point -Ary approximating subdivision scheme for curve designing is introduced for any ar-ity 2. The new scheme is extension of B-spline of degree 6. Laurent polynomial method is used to investigate the continuity of the scheme. The variety of effects can be achieved in correspondence for different values of parameter. The applications of the proposed scheme are illustrated in comparison with the established subdivision schemes. Keywords: Approximating Subdivision Scheme; Binary; Ternary; -Ary; Continuity; Convergence and Shape Parameters 1. Introduction Subdivision modeling methods are effective algorithms to generate continuous curves and surfaces from a dis-crete set of control points by subdividing them according to some refining rules, recursively. Repetition of this process produces a very good approximation to the curve or surface defined by the original set of control points. In recent years, the subject of subdivision gained popularity due to some new applications, such as in the 3D anima-tion industry. The next venture is to introduce these methods to be more consistent and efficient to the world of geometric modeling in the industry. Approximating schemes were first developed by Rham and Chaikin [1,2]. Consequent to this, a lot of work has been done by different authors in the field of binary sub-division schemes, but the research communities are in-terested in introducing higher arity schemes (i.e. ternary, quaternary, ...n-ary) which give better result and less computational cost. In late 80,s with the help of wavelet theory, a relation-ship between subdivision scheme and the “mask” of re-finable function have been developed. Lian [3,4] has introduced 3, 4, 5 and 6-point a-ary interpolating schemes. In these research papers, Lian used wavelets theory, a relatively new subject area that has been deeply studied for the last two decades or so, and found many successful applications. Lian  also offered 2m and (2m + 1) -point interpolating a-ary schemes for curve design-ing. In 2009, Mustafa and Khan  for the first time in-troduced a new 4-point quaternary approximating subdi-vision scheme. Mustafa and Najma  presented same perspective for constructing (2b + 2) and (2b + 4) -point n-ary interpolating and approximating schemes. Ghaffar et al. presented unified 3-point -ary approximation schemes and discussed various properties . This moti-vates us to present 4-point -ary approximating scheme with high smoothness and more degree of freedom for curve designing. One of the main objectives of current work is to extend “The B-Spline of degree 6” to 4-point -ary approximating subdivision scheme. This paper is organized as follows: General form of 4-point -ary subdivision scheme is constructed in Sec-tion 2. The family of 4-point -ary approximating scheme, basic properties and analysis are presented in Section 3. Comparison of 4-point -ary schemes is given in Section 4. Finally conclusion is given in Section 5. 2. Main Results In this section, we are introducing family of 4-point -ary approximating subdivision scheme for curve de-signing for any arity 2. This family is the extension of B-spline of degree six i.e. (4-point approximating sub-division scheme): 121 112111 2735211,6464 6464121357.6464 6464kkkkiiiikkkkiiii2kikiffffffffff , (1) If there exist a unique −sequence that de-scribes the “two scale equation” 2l{}kP 2kkxPxk (2) Copyright © 2013 SciRes. OJAppS A. GHAFFAR ET AL. 107of scaling function . Then corresponding to this - sequence, let us introduce the notation 2l1() ,2kkkPzP zPz (3) Due to the development of the wavelet theory, the schemes (1) can be easily re-discovered by the scaling functions 4 satisfying the two-scale equations    444 444444127 21212264 352335242125 72627,ttt ttttttR      t (4) By taking the Fourier transforms of (4), we arrive at the following two-scale equations of 4 2444322445324411 721ˆˆˆ ˆ64 22222235 35ˆˆ 222221 7ˆˆ 2222 iwiwiwiwiwiwwwweewweewwee          4w7241ˆ.22iw we This implies  42232443021311ˆˆ.2241iwjiwiwjewweje     This normalization simplifies to the following Fourier transform formulation:  4441ˆˆ ,22wwP z where  423430311 ,14jjzPz zjz (5) and 2.iwze By introducing the shape parameter in (5), we get ju 4234203111.144jjjzPz uzjz (6) By taking and , we get 034uu w 124(1 )uu w 2441(1 )()()(1 )(1 ).16 (1)zPzwwzwzwzzNow, if we allow the scaling factor, denoted by a, to be , and denote such a scaling function denoted by 2a, then the Fourier transforms of two-scale equation of a becomes ,iwaaaawwPa  e and .aaawwPa z where and again, is its two-scale symbol and (/)iw azeaPa is then equivalent to satisfies aP42431(1 )()()(1)(1 ).(1 )(2)aazPZwwzwzwzza3 (7) 3. Family of 4-Point a-Ary Schemes In this section, we discuss only three 4-point schemes. For setting 2,3a and 4 in (7), we obtain three poly-nomials aPza4 with following sets of coef-ficients called the mask of the 4-point binary, ternary and quaternary schemes, respectively. ,2,3,424,13 ,5,105 ,1,105 ,5,13,16www www ww (8) 34,13,55,143,263,1359 ,359,263,143,,54 55,13,ww wwwwwwwwww  (9) and 44,13 ,55 ,147 ,305 ,51,717,8413 ,8413,1,717 ,51,305,147 ,12855,13,ww wwwwwwwwww wwww  (10) Order of continuities of the above schemes is given in Table 1. One can easily find the order of continuity over the parametric intervals by using the approach of . 3.1. Support of Basic Limit Function The basic function of a subdivision scheme is the limit function of the proposed scheme for the following data 01, 0,0, 0.iifi (11) 23 The following theorem is related to the support of ba-sic limit functions of the 4-point a-ary scheme. Theorem 1. The basic limit functions of 4 pro-posed 4-point a-ary approximating schemes have support ΦaCopyright © 2013 SciRes. OJAppS A. GHAFFAR ET AL. Copyright © 2013 SciRes. OJAppS 108 Table 1. The order of continuity of proposed 4-point a-ary schemes for certain ranges of parameter. Scheme Parameter Cn Scheme Parameter Cn Binary 3522w C0 Quaternary 3314 2w C0 ... 3522w C1 ... 131922w C1 ... 1322w C2 ... 35w C2 ... 1322w C3 ... 13w C3 01w C4 ... 14w C5 Ternary 23 3144w C0 ... 7122w1 C1 ... 24w C2 ... 13w C3 (a) (b) (c) Figure 1. (a-c) represent the basic limit functions of the 4-point binary, ternary and quaternary schemes, respectively. by 4112aa on both sides. Hence after k subdivision width 411asa, for which implies 2, 3,4,...,,amthat it vanishes outside the interval 4141,2121aaaa. steps the furthest non-zero vertex on the left will be at 21041111 241 1.kkjjaaaaaaa Proof. Since the basic function is the limit function of the scheme corresponding to (7) for the data (11), its support width “s” can be determine by computing how far the effect of the non-zero vertex 00f will propagate along by. As the mask of a-ary 4-point scheme is 41a long sequence by centering it on that vertex; the dis-tances to the last of its left and right non-zero coefficients So the total support width is 0411 412.1jjaaaaa   are equal to 412a At the first subdivision step we see 3.2. Precision Set that the vertices on the both sides of 10f at 412a are For approximating schemes, we do not expect new verti-ces to be lie on the same curve as old ones, so it is nec-essary to look to see whether all the vertices lie on a common curve. We can calculate the order of precision by using the technique as given in . the furthest non-zero new vertices. At each refinement, the distances on both sides are reduced by the factor 1a. At the next step of the scheme, this will propagate along A. GHAFFAR ET AL. 109Lemma 2. The scheme (3.1) has cubic precision. Proof. We carry out this result by taking our origin the middle of an original span with ordinate ,5,3,1,1,3,5,nnnnnn   If nyx, then we have      12344321111143214321,531 15311,3113,3113,,1135,nnnnnnnnnnnnnnnnn nnya aa aaaaaaaaaaaaaaaaa    ,n where 1234375,,,1616 1616aaaa1. If 1yx, then we have 2531135,,,,,,,2 22222,1,1,1,1,1,0,yyy   where  represents the differences of the vertices. If 2yx, then we have 15 73 3, 2,2,2,22 222715 2,2,22y wwwwww, Taking further differences, we get . 30yIf 3yx, then we have ,2515,9 9,22, 22,99,2515,ywwww w  w by taking further differences, we get . 4δy0tThus the scheme has cubic precision. For this analysis we observe that the scheme (8) is de-signed so that it has cubic precision for any value of . While the schemes (9) and (10) have cubic precision for wany value of w and with the special values 1w3 and 1w2, the schemes have quartic precision, respectively. 4. Comparison and Application In this section, we show that the popular existing schemes are special cases of our proposed family of schemes (8)- (10).  With the special values of parameter (w0 and 1w4), the subdivision schemes generated by B-splines of degree 4 and 6, respectively, are obtained from the schemes (8).  Moreover, the proposed scheme (8) is a generalized scheme, as the mask of the proposed scheme coincides with the mask of schemes [9,11-13] after setting 5w,8 1w0,wω6 and wu respectively.  It may be noted that if we put 11wω,w u6162 13 and 35w24 in (9), the proposed 4-point scheme can also be consid-ered as the general form of the stationary 4-point ternary approximating schemes of [8,13,16], respectively.  For substituting 21w8 , the obtained mask of scheme (10) coincides with mask of the famous 4-point quaternary scheme of Ko . Here we compare our proposed schemes with the ex-isting binary, ternary and quaternary schemes (see Table 2). It is observed that the continuity and approximation order of proposed schemes are better than the existing schemes. Moreover, Figure 2 is exposed to show the role of free parameters when the schemes (8)-(10) applied on discrete data points. In Figure 2(a), black, red and blue lines show the visual smoothness of the binary scheme at the parametric values 10, 8ww and 12w, re-spectively. In Figure 2(b), blue, green, black and red lines show the visual smoothness of the ternary scheme at the parametric values 11,, 02ww w, and 12w, respectively. In Figure 2(c), blue, green, black and red lines show the visual smoothness of the quaternary scheme at the parametric values 1,w 1,2ww0 and 12w, respectively. From Figure 2, we conclude that the behavior of the limiting curve acts as tightness/looseness when the values of free pa-ameter vary. rCopyright © 2013 SciRes. OJAppS A. GHAFFAR ET AL. Copyright © 2013 SciRes. OJAppS 110 Table 2. Comparison of 4-point ternary schemes. Type Support Scheme Order Cn Binary 4-point  Inteng rpolati6 4 1 Binary 4-point  Interpolating 4 6 1 Binary 4-point  Approximating 7 4 2 Interpolating Ternary 4-point  5 4 1 Interpolating 5 3 Ternary 4-point [21, 3] 1 Interpolating Ternary 4-point  5 2 Interpolating 5 Ternary 4-point  3 1 Ternary 4-point  Approximating 4 5.5 2 Approximating 5 4 Quaternary 4-point  2 Approximating 4 Quaternary 4-point  5 3 Approximating 7 3 Binary 4-point proposed 5 Approximating 5 Ternary 4-point proposed 5.5 3 Approximating 5 5 Quaternary 4-point proposed 3 (a) (b) (c) Figure 2. ectively. . Conclusiooint a-ary approximating schemes for 027), the National Natural a (60973101) and HEC Paki-G. de Rham, “Un Peude Mathematiques a Proposed Une Courbe Plane,” Revwede Mathematiques Elementry II, Oevred Comp (a-c) show the role of shape parameter of the schemes (8), (9) and (10) resp5ns 6. Acknowledgement The families of 4-pcurve design were established in general. The first family is binary, the second is ternary and the third family is quaternary approximating. The support of subdivision scheme influences the locality. One of the best ways to get a smaller support is to raise the arity. This is one of the advantages of the proposal of the scheme. We have also studied its continuity and determined its order of precision. It is observed that the order of precision set increases by increasing the arity of the schemes while the continuity decreases by increasing the arity of the scheme. Moreover, we have showed that several previ-ously proposed schemes are members of this family. It has been shown that proposed schemes are better than existing schemes in the sense of smoothness and ap-proximation order. This work is supported by the Beijing Municipal Natural Science Foundation (4102Science Foundation of Chinstan. REFERENCES  letes, 1947, pp. 678-689. G. M. Chaikin, “An Algorithm for High-Speed Curve Generation,” Computer Graphics and Image Processing, Vol. 3, No. 4, 1974, pp. 346-349. doi:10.1016/0146-664X(74)90028-8  J. -A. Lian, “On A-ary Subdivision for Curve Design: I. 4-point and 6-point Interpolatory Schemes,” Applications A. GHAFFAR ET AL. 111and Applied Mathematics: An Inte3, No. 1, 2008, pp.18-29. rnational Journal, Vol.7. p. 434-444.  J. -A. Lian, “On A-ary Subdivision for Curve Design: II. 3-point and 5-point Interpolatory Schemes,” Applications and Applied Mathematics: An International Journal, Vol. 3, No. 2, 2008, pp. 176-18 J. -A. Lian, “On a-ary Subdivision for Curve design: III. 2m-point and (2m+1) point Interpolatory Schemes,” Ap-plications and Applied Mathematics: An International Journal, Vol. 4, No. 2, 2009, p G. Mustafa and F. Khan, “A New 4-point Quaternary Approximating Subdivision Scheme,” Abstract and Ap-plied Analysis, Vol. 2009, Article ID 301967, 14 pages.  G. Mustafa and A. R. Najma , “The Mask of (2b + 4)-point n-ary Subdivision Scheme,” Computing, Vol. 90, No. 1-2, 2010, pp. 1-14. doi:10.1007/s00607-010-0108-x  A. Ghaffar, G. Mustafa and K. Qin, “Unification and Application of 3-point Approximating Subdivision Schemes of Varying Arity,” Open Journal of Applied Sciences, Vol. 2, No. 4B, 2012, pp. 48-52. doi:10.4236/ojapps.2012.24B012  M. F. Hassan and N. A. Dodgson, “Ternary and Three-point Univariate Subdivision Schemes,” In: A. Cohen, J. L. Marrien, L. L. Schumaker (EdSurface Fitting: Sant-Malo2002, Ns.), Curve and ashboro Press, Brent-nger, 2002, pp. 51-68. wood, 2003, pp. 199-208.  N. Dyn, “Analysis of Convergence and Smoothness by the Formalism of Laurent Polynomials,” In: A.Iske, E. Quak, M. S Floater (Eds), Tutorials on Multiresolution in Geometric Modelling, Spridoi:10.1007/978-3-662-04388-2_3  G. Mustafa, F. Khan and A. Ghaffar, “The -Point Ap-proximating Subdivision Scheme,” Lobachevskii Journal of Mathematics, Vol. 30, No. 2, 2009, pp. 138-145. doi:10.1134/S1995080209020061  N. Dyn, M. S. Floater and K. Horman, “A Four-Point Subdivision Scheme with Fourth Order Accuracy and its Extension,” In Mathematical Methods for Curves and Surfaces: Tromso 2004, M. Daehlen, K. Morken, and Lring, 2009, pp. . L. Schumaker (eds.), 2005, pp. 145-156.  H. Zheng, M. Hu and G. Peng, “P-ary Subdivision Gen-eralizing B-splines,” Second International Conference: On Computer and Electrical Enginee214-218. doi:10.1109/ICCEE.2009.204  A. Ghaffar and G. Mustafa, “A Family of Even-Point ternary Approximating Schemes,” ISRN Applied Mathe-matics, Vol. 2012, 2012, Article ID 197383, 14 pages. er- H. Zheng, M. Hu and G. Peng, “Ternary Even Symmetric 2n-point Subdivision,” International Conference on: Computational Intelligence and Software Engineing,2009, pp. 1-4.doi:10.1109/CISE.2009.5363033  K. P. Ko, B. -G. Lee and G. Joon Yoon. “A Ternary 4-point Approximating Subdivision Scheme,” Applied Mathematics and Computation, Vol. 190, 2007  K. P. Ko, “A Quatnary Approximating 4-point Subdivi-sion Scheme,” J. KSIAM, Vol. 13, No. 4, 2009, PP. 307-341.  C. Beccari, G. Casciola and L. Romani, “A Non-stationary Uniform Tension Controlled Interpolating 4-point Scheme Reproducing Conics,” Computer Aided Geometric Design, Vol. 24, No. 1, 2007, pp. 1-9.  G. Casciola and L. Romani. “An Interpolating 4-point Ternarynon-stationary Subdivision Scheme with Tension Control,” Computer Aided Geometric Design, Vol. 24, . 1, 2009, pp. 916-927. No. 2, 2007, pp. 210-219.  G. Casciola and L. Romani, “Shape Controlled Interpola-tory Ternary Subdivision,” Applied Mathematics and Computation, Vol. 215, No G. Deslauriers and S. Dubic, “Symmetric Iterative Inter-polation Process,” Constractive Approximation, Vol. 5, No. 1, 1989, pp. 49-68. doi:10.1007/BF01889598  M. F. Hassan, I. P. Ivrissimitzis, N. A. Dodgson and M. A. Sabin, “An Interpolating 4-points C2 Ternary Stationary Subdivision Scheme,” Computer Aided Geometric Design, Vol. 19, 2002, pp. 1-18. Copyright © 2013 SciRes. OJAppS