 American Journal of Computational Mathematics, 2013, 3, 217-221 http://dx.doi.org/10.4236/ajcm.2013.33031 Published Online September 2013 (http://www.scirp.org/journal/ajcm) A Family of 4-Point n-Ary Interpolating Scheme Reproducing Conics Mehwish Bari, Ghulam Mustafa Department of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, Pakistan Email: ghulam.mustafa@iub.edu.pk, mehwishbari@yahoo.com Received April 16, 2013; revised June 5, 2013; accepted July 5, 2013 Copyright © 2013 Mehwish Bari, Ghulam Mustafa. This is an open access article distributed under the Creative Commons Attribu-tion License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT The n-ary subdivision schemes contrast favorably with their binary analogues because they are capable to produce limit functions with the same (or higher) smoothness but smaller support. We present an algorithm to generate the 4-point n-ary non-stationary scheme for trigonometric, hyperbolic and polynomial case with the parameter for describing curves. The performance, analysis and comparison of the 4-point ternary scheme are also presented. Keywords: Interpolation; Non-Stationary; Univariate Ternary Refinement; Continuity; Conic Section 1. Introduction Subdivision is a method for making smooth curves/sur- faces, which first emerged an addition of splines to arbi- trary topological control nets. Effectiveness of subdivi- sion algorithms, their flexibility and ease make them ap- propriate for many relative computer graphics applica- tions. The schemes generating curves are considered to be the basic tools for the design of schemes generating surfaces. A general form of univariate n-ary subdivision scheme S which maps a control polygon kkiiff to a re- fined polygon 11kkiiff is defined by 1,0,1,2,,kkni snj sijjfafS1,n where the set iaai of coefficients is called mask of the subdivision scheme. The set of coefficients :kkiaaikka d etermines the subdivision ru le at level and is termed as the mask at -th level. If the mask is independent of , namely if , the subdivision scheme is called stationary otherwise it is called non-stationary. Sometimes, in computer graphics and geometric modeling, it is required to have schemes to construct circular parts or parts of conics. It seems that (linear) stationary schemes cannot generate conics and non-stationary schemes have such a capability to gener- ate trigonometric polynomials, trigonometric splines and, in particular, circles, ellipses and so on. Such schemes kk,kaakare useful in computer graphics and geometric modeling. Successful efforts have been made to establish approxi- mating and interpolating non-stationary schemes which can provide smooth curves and reproduce circle or some trigonometric curves. The theoretical bases regarding non-stationary schemes are derived from the analysis of stationary schemes. Jena et al.  worked on 4-point binary non-stationary subdi- vision scheme for curve interpolation. Yoon  pre- sented the analysis of binary non-stationary interpolating scheme based on exponential polynomials. Beccari et al.  worked on 4-point binary non-stationary uniform ten- sion controlled interpolating scheme reproducing conics. Daniel and Shunmugaraj  presented 4-point ternary non-stationary interpolating subdivision scheme. In this paper, we present an algorithm to construct 4-point n-ary scheme. For simplicity, we have discussed and analyzed 4-point ternary scheme. This paper is organized as follows. Section 2 presents the construction of 4-point n-ary non-stationary interpo- lating subdivision schemes. As an example, 4-point ter- nary scheme is presented in this section. Section 3 pro- vides the smoothness of proposed schemes. In the last section conclusion and visual performance of proposed schemes are presented. 2. Construction of 4-Point n-Ary Scheme Here we suggest the following algorithm to construct the non-stationary n-ary 4-point 2,3,4, ,n interpo- Copyright © 2013 SciRes. AJCM M. BARI, G. MUSTAFA 218 lating schemes for trigonometric, hyperbolic and poly- nomial cases.  Choose interpolating function 01 23cossin ,fxaaxaxa x 01 23cosh sinh or ,fxaaxa xa x or 2301 23.fxaaxaxax   Then define the points kipi at level k and get system of linear equations by interpolating.  The data kihp corresponding to the abscissas ,1,0,1,khtxhn2.  Solve the system of linear equations by any well known method to get the values of unknowns.  Evaluate the interpolating function fx at the grid points 11:2,3,,. krtrnn Define the new points 1. kkni ipp Define the new points 111,1,2,3,,kni jkrtpf jrrn,n as a lin- ear combination of four consecutive points 1kip, , and kip1kip2.kipTernary 4-Point Interpolating Scheme Given a set of control points at level , using above algorithm, we define a unified ternary 4-point in- terpolating scheme that makes a new set of control points by the rule: kPk1kp1313111 231421324 132 112,,,kkiikkkkkkkkkiiiiikkkkkkkkkiiiipppppppppppp  where 1124 1,kkk5  321 141(161)kkkk5,  4331114882 1,kkkkk5  4141kkk5,  with 22511641 21,kkk   where the parameter 1k can easily be updated at each subdivision step through following equation 101,0,1,2,, 1,2kkk. (2.2) Therefore, given parameter ,k the subdivision rules are achieved by first computing 1k using Equation (2. 2) an d th en by substituting 1k into (2.1). As a result, depending on the choice of the parameter, we get differ- ent schemes. For 111cosh 3kkti3 ,costk and 1 in (2.1), we can generate following schemes exact for tri- gonometric (2.3), hyperbolic (2.4) and polynomial (2.5) respectively. 1313111231 421324 132 112,,,kkiikkkkkkkkkiiiiikkkkkkkkkiiiipppppppppppp  (2.3) where i (2.1) 112sin33sin 23,kkkttk  1122sin2 3sin36sin233sin3,kkkkktt ttk 1133sin 23sin 232sin36sin3,kkkkkttttk  14sin 33sin 3,kkkttk  6sin3cos 31kkktt. 1313111 231 421324 132 112,,,kkiikkkkkkkkkiiiiikkkkkkkkkiiiipppppppppppp  kki (2.4) where 11, 22,kk 33,kk 44,kk after replacing sin and cos functions by sinh and cosh func- tions in 12,,k34,.kkk 1313111 213211 2,560304,81818181430605,81 8181 81kkiikkkkiiiikkkkiiiippppppppppp   kikip (2.5) Remark 2.1. The scheme (2.3) and (2.4) can be consid- ered as a non-stationary counterpart of the DD stationary scheme  i.e. scheme (2.5) because, the masks of the schemes (2.3) and (2.4) converge to the mask of scheme (2.5): Copyright © 2013 SciRes. AJCM M. BARI, G. MUSTAFA 2191122 3344560,,81 81814,.s81 akkkk kkkk k  30, 3. Smoothness Analysis The subdivision scheme given in the previous subsection, the coefficients 1,2 ,3,4kii in (2.1) may vary from one refinement level to another. Hence the scheme is non- stationary and its smoothness properties can be derived by asymptotical equivalence  with the corresponding stationary scheme. Two subdivision schemes and are said asymptotically equivalent if kaSaS.kakaSS In particular, our analysis is based on the generalization of Theorem 8 in  to ternary sub-division. Since our schemes (2.3) and (2.4) are non-stationary then we can use the theory of asymptotic equivalence and generating function formalism  to investigate the smoothness of the schemes. First, we need some esti-mates of ki and which are specified in subsequent lemmas. ,1,2,3,4,kiiLemma 3.1. The mask of scheme (2.3) satisfies following inequali-ties for sufficiently large . k1) 112,33k 2) 241,3k  3) 3104 ,27 3k 4) 411.63k Proof. We make use the inequalities sinsinaabb for 02ab , csc csctt for 02t and sincosxxx (or 1csc xcosxx) for 02x to prove the above inequa lities: Since   11121222sin36sin 3cos312sin3sin2 3sin 3sin 3cos3.6sin3sin2 32sin3sin2 3kkkkkkkkkkkkttttttttt ttkt Then for k 111213cos 313cos 31636sin23kkkkttt and also for , we get k1122122sin36sin3cos312sin3sin2 322 6sin232.312sin2 3kkkkkkktttttttk This proves 1). The pro o fs of 2) , 3) an d 4) are sim i l ar. Lemma 3.2. The coefficients in the scheme (2.4) satisfy following inequalities when subdivision level . k1) 110,3k 2) 277,66k 3) 344,33k 4) 410.6k Proof. We make use of following inequality of  211coscos,,.cosh2222xxxx     This claim holds true if the function fx is non- negative on 0, 2. Some other inequalities for 02x are 12sinhsinh,sinh 0,33kkxxx    11,0coshsinh1 coshxxx x. Since   112sinh33sinh 236sinh3cosh312sinh3.6sinh3cosh31kkkkkkkkttttttt Then for k121cos 3133cosh313 1cos31cos 31,332sin23kkkkkkttttt   Copyright © 2013 SciRes. AJCM M. BARI, G. MUSTAFA 220 and similarly for k   112sinh33sinh236sinh3cosh313sinh 30.6sinh 3cosh 31kkkkkkkkttttttt This proves 1). The pro o fs of 2) , 3) an d 4) are sim i l ar. The following two Lemmas are the consequence of previous Lemm as. Lemma 3.3. 1) 1559,81 81k 2) 260 21,81 81k 3) 330 78,81 81k 4) 4431.81 81k Proof. Since 1581k as and by 1) of kLemma 3.1, we have 1). Similarly, we get 2), 3) and 4). Lemma 3.4. 1) 155,81 81k 2) 260 23,81 54k 3) 330 78,81 81k 4) 444.81 81k Proof. Since 1581k as and by 1) of kLemma 3.2, we have 1). Similarly, we get 2), 3) and 4). Lemma 3.5. The Laurent polynomial kz of the level of the scheme thkkS defined by (2.1) can be written as  213kkzzzaz21 where  543414 1 34123434123114433 333333 3.kkkkkkkkkkk kkkkk kazzz zzzzzz  Proof. By (2.1), we have 5421413 222453141.k kkkkkkkkzzzzzzzzz   It can be easily verified that  21.3kkzzzaz Lemma 3.6. The stationary scheme aS defined by (2.5) associ- ated with the symbol 542 1245145306081 608130 5 4azzzzzzzzz1 is 1.CProof. To prove that aS is consider 1,C22321233114 3 617634.27azbz zzzzzzzz Since 3313max ,,25 99max, ,127 27 27bjjjj jSbb 2jb then by [, corollary 4.11] the scheme aS is 1.CLemma 3.7. The scheme kS defined by (2.1) is 1.CProof. Since aS is by Lemma 3.6, in view of [, Theorem 8(a)], it is sufficient to show that 1C03kkakSS where 333131 3232143414 1234max ,,54 26max 3333,27 2727122333333 .27 27kakk kjjj jjjjj jkkkkkk kkkkSSaa a  9    Note that 123412342933332756030.81818181kkkkkkkk4 Since 1053,81kkk Copyright © 2013 SciRes. AJCM M. BARI, G. MUSTAFA Copyright © 2013 SciRes. AJCM 2215. Acknowledgements 20603,81kkk3030381kkk and This work is supported by the Indigenous Ph.D Schol- arship Scheme of Higher Education Commission (HEC) Pakistan. 104381kkk, then by Lemma 3.3, it follows that REFERENCES 11234029381kkkkkk.  M. K. Jena, P. Shunmugaraj and P. C. Das, “A Non-Sta- tionary Subdivision Scheme for Curve Interpolation,” ANZIAM Journal, Vol. 44, No. E, 2003, pp. 216-235. By Lemma 3.3, we can also show that 10533 ,27kkk 40433 ,27kkk  J. Yoon, “Analysis of Non-Stationary Interpolatory Sub- division Schemes Based on Exponential Polynomials,” Geometric Modeling and Processing, Vol. 4077, 2006, pp. 563-570. 3402633 327kk kk and  C. Beccari, G. Casciola and L. Romani, “A Non-Station- ary Uniform Tension Controlled Interpolating 4-Point Scheme Reproducing Conics,” Computer Aided Geomet- ric Design, Vol. 24, No. 1, 2007, pp. 1-9. doi:10.1016/j.cagd.2006.10.003 140236 6.27kkkk Hence 03kkakSS.  S. Daniel and P. Shunmugaraj, “Some Interpolating Non- Stationary Subdivision Schemes,” International Sympo- sium on Computer Science and Society, Kota Kinabalu, 16-17 July 2011, pp. 400-403. doi:10.1109/ISCCS.2011.110 4. Conclusions To the aim of reproducing conic sections, we introduce an algorithm for generation of 4-point n-ary interpolating scheme. In particular, we define 4-point interpolating scheme that unifies three different curves schemes which are capable of representing trigonometric, hyperbolic and polynomial functions.  G. Deslauriers and S. Dubuc, “Symmetric Iterative Inter- polation Processes,” Constructive Approximation, Vol. 5, No. 1, 1989, pp. 49-68. doi:10.1007/BF01889598  N. Dyn and D. Levin, “Analysis of Asymptotically Equi- valent Binary Subdivision Schemes,” Journal of Mathe- matical Analysis and Applications, Vol. 193, No. 2, 1995, pp. 594-621. doi:10.1006/jmaa.1995.1256 The resulting ternary algorithm allows u s to efficiently define limit curves that combine all the ingredients of locality, smoothness, user-independence, local ten- sion control and reproduction of conics, see Figure 1. 1C N. Dyn and D. Levin, “Subdivision Schemes in Geomet- ric Modelling,” Acta Numerica, Vol. 11, 2002, pp. 73-144. doi:10.1017/S0962492902000028  R. Klen, M. Lehtonen and M. Vuorinen, “On Jordan Type Inequalities for Hyperbolic Functions,” Journal of Ine- qualities and Applications, Vol. 2010, 2010, Article ID: 362548. (a) (b) (c) (d) Figure 1. Dotted lines indicate the initial closed and open polygons. Solid continuous curves are generated by pro- posed ternary interpolating scheme for trigonometric case.